[Ανάλυση Αλγορίθμων] Απορίες στις ασκησεις 2015

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Αντιστοίχηση Μαθημάτων ΝΠΣ με ΠΠΣ
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ.

[Αντιστοίχηση Μαθημάτων ΝΠΣ με ΠΠΣ]

Επίσημη ενημέρωση για Αντιστοίχηση Μαθημάτων ΝΠΣ με ΠΠΣ και η συζήτηση στο forum.

[Μεταλλαγμένη Πάπια]

Μπορει καποιος να ανεβασει τις ασκησεις απο τα τελυταια δυο μαθηματα με τον Θεμη?

Τι εκανε?

Στο χρονοδιαγραμμα στο ethmmy γραφει τι εκανε. Ηταν καποιες ασκησεις απο τα φυλλαδια των κεφαλαιων 17 και 23. Ειναι ολες ανεβασμενες και λυμενες.

[Gaara]

Τα εχω δει αυτα.
Περισυ ειχε κανει μια ασκηση με χρονοπρογραμματισμο σε λιμανι η οποια επεσε σχεδον αυτουσια. Δεν υπηρχε κατι στα φυλλαδια.

[Μεταλλαγμένη Πάπια]

Τα εχω δει αυτα.
Περισυ ειχε κανει μια ασκηση με χρονοπρογραμματισμο σε λιμανι η οποια επεσε σχεδον αυτουσια. Δεν υπηρχε κατι στα φυλλαδια.

Επειδη πηγα στα μαθηματα, εκανε ακριβως αυτα που λενε τα φυλλαδια, με εξαιρεση ενα παλιο θεμα που ειχε huffman και δεν ηταν τιποτα σπουδαιο.

[Μεταλλαγμένη Πάπια]

Επειδη παλευω τις τελευταιες μερες τα προβληματα στο contests (και μου βγαλανε λιγο τη ψυχη), βρηκα τη λυση στα πρωτα δυο και τη ποσταρω και εδω:

To cable cutting, ειναι ιδιο με το ακεραιο σακιδιο στο οποιο επιτρεπονται πολλα αντιγραφα του ιδιου αντικειμενου, η λυση ειναι εδω:
http://people.cs.clemson.edu/~bcdean/dp_practice/dp_0.swf

Το valar morghulis, ειναι ιδιο με αυτο εδω:
http://people.cs.clemson.edu/~bcdean/dp_practice/dp_8.swf

Αν καποιος εχει λυσει τα αλλα δυο, δε θα ταν κακο να τα ποσταρει εδω 

[c0ndemn3d]

Για τον Huffman υπάρχει αλγόριθμος στο βιβλίο, τα υπόλοιπα βήματα είναι τετριμμένα.
Για το άλλο είναι άπληστος αλγόριθμος. Βρίσκεις το μέγιστο κουτί που χωράει και θεωρείς μόνο εκείνες τις σειρές του πίνακα και τις γεμίζεις μετά με μικρότερα κ.ο.κ. Μετά από αυτό το βήμα κάποιες σειρές θα είναι γεμάτες, οπότε τις αγνοείς και συνεχίζεις με το υπόλοιπο κομμάτι του πίνακα και κάνεις τα ίδια βήματα.

[Μεταλλαγμένη Πάπια]

Για τον Huffman υπάρχει αλγόριθμος στο βιβλίο, τα υπόλοιπα βήματα είναι τετριμμένα.
Για το άλλο είναι άπληστος αλγόριθμος. Βρίσκεις το μέγιστο κουτί που χωράει και θεωρείς μόνο εκείνες τις σειρές του πίνακα και τις γεμίζεις μετά με μικρότερα κ.ο.κ. Μετά από αυτό το βήμα κάποιες σειρές θα είναι γεμάτες, οπότε τις αγνοείς και συνεχίζεις με το υπόλοιπο κομμάτι του πίνακα και κάνεις τα ίδια βήματα.

Και γω καπως ετσι το σκεφτηκα, αλλα δεν μπορω να γραψω την αναδρομικη σχεση που το εκφραζει αυτο...  (Toν απληστο εννοω οχι το huffman)

[lady_of_winter]

Επειδη παλευω τις τελευταιες μερες τα προβληματα στο contests (και μου βγαλανε λιγο τη ψυχη), βρηκα τη λυση στα πρωτα δυο και τη ποσταρω και εδω:

To cable cutting, ειναι ιδιο με το ακεραιο σακιδιο στο οποιο επιτρεπονται πολλα αντιγραφα του ιδιου αντικειμενου, η λυση ειναι εδω:
http://people.cs.clemson.edu/~bcdean/dp_practice/dp_0.swf

Το valar morghulis, ειναι ιδιο με αυτο εδω:
http://people.cs.clemson.edu/~bcdean/dp_practice/dp_8.swf

Αν καποιος εχει λυσει τα αλλα δυο, δε θα ταν κακο να τα ποσταρει εδω  

 

λοιπόν έχει κανείς ιδέα τι σημαίνει αυτό με τις περιθωριακές κορυφές στο πρώτο θέμα της περσινής προόδου ??

[Μεταλλαγμένη Πάπια]

Σχετικα με σωστο - λαθος στην προοδο 2014Β:

Τα πρωτα δυο μου φαινονται σωστα, δεν ξερω πως να τα αποδειξω.

Το τριτο νομιζω οτι ειναι λαθος, αν εχω καταλαβει καλα τι εννοει. Αν εννοει οτι ο κυκλος εχει μοναδικη ακμη μικροτερου βαρους e, τοτε ειναι λαθος και το αντιπαραδειγμα ειναι αυτη η ασχημη εικονα:
http://imgur.com/BfAKqL8
Το 2 ειναι η ακμη μικροτερου βαρους στον κυκλο εκεινο, αλλα οπως φαινεται μπορω να φτιαξω ΕΣΔ, χωρις να την συμπεριλαβω.

Αν εννοει οτι ειναι η μιρκοτερη σε ολοκληρο το γραφημα, τοτε παω πασο, σωστο πρεπει να ειναι. Να το αποδειξω δε μπορω 

Ας το επιβεβαιωσει καποιος.

[c0ndemn3d]

Άτοπο δοκίμασες; Συν ότι τα ΕΣΔ είναι άκυκλα

[Λήσταρχος Γιαγκούλας]

Σχετικα με σωστο - λαθος στην προοδο 2014Β:

Τα πρωτα δυο μου φαινονται σωστα, δεν ξερω πως να τα αποδειξω.

Το τριτο νομιζω οτι ειναι λαθος, αν εχω καταλαβει καλα τι εννοει. Αν εννοει οτι ο κυκλος εχει μοναδικη ακμη μικροτερου βαρους e, τοτε ειναι λαθος και το αντιπαραδειγμα ειναι αυτη η ασχημη εικονα:
http://imgur.com/BfAKqL8
Το 2 ειναι η ακμη μικροτερου βαρους στον κυκλο εκεινο, αλλα οπως φαινεται μπορω να φτιαξω ΕΣΔ, χωρις να την συμπεριλαβω.

Αν εννοει οτι ειναι η μιρκοτερη σε ολοκληρο το γραφημα, τοτε παω πασο, σωστο πρεπει να ειναι. Να το αποδειξω δε μπορω  

Ας το επιβεβαιωσει καποιος.

Όταν λεει όμως ότι το G έχει έναν κύκλο με...
Εννοεί ότι υπάρχει ΜΟΝΟ ένας κύκλος? ή υπάρχουν κι άλλοι?

Αν υπάρχει μόνο ένας είναι Σωστό.Αν υπάρχουν κι αλλοι είναι Λάθος.

[Πάτρικ Αστέρης]

Σχετικα με σωστο - λαθος στην προοδο 2014Β:

Τα πρωτα δυο μου φαινονται σωστα, δεν ξερω πως να τα αποδειξω.

Το τριτο νομιζω οτι ειναι λαθος, αν εχω καταλαβει καλα τι εννοει. Αν εννοει οτι ο κυκλος εχει μοναδικη ακμη μικροτερου βαρους e, τοτε ειναι λαθος και το αντιπαραδειγμα ειναι αυτη η ασχημη εικονα:
http://imgur.com/BfAKqL8
Το 2 ειναι η ακμη μικροτερου βαρους στον κυκλο εκεινο, αλλα οπως φαινεται μπορω να φτιαξω ΕΣΔ, χωρις να την συμπεριλαβω.

Αν εννοει οτι ειναι η μιρκοτερη σε ολοκληρο το γραφημα, τοτε παω πασο, σωστο πρεπει να ειναι. Να το αποδειξω δε μπορω 

Ας το επιβεβαιωσει καποιος.

νομιζω σωστα τα λεει η παπια

[Πάτρικ Αστέρης]

Να ρωτησω
Στην περσινη 2η προοδο ποιο ειναι το λαθος του αλγοριθμου στο 3ο θεμα; 

[Πάτρικ Αστέρης]

<a href="https://www.youtube.com/watch?v=4fQJGoeW5VE" target="_blank">http://www.youtube.com/watch?v=4fQJGoeW5VE</a>
αυτο για το 3ο θεμα

[Σα τανυστής]

Αν θυμαμαι καλα ο "λαθος" αλγοριθμος ελυνε το προβλημα απληστα, αντι με δυναμικο που το λυνει βελτιστα

Αν κανεις swap νουμερα σε αυτην που εχει ως παραδειγμα εβγαινε νομιζω.Δε το χω μπροστα μου αλλα πρεπει να βαλα το 7 στη θεση του 3 or sth

[Πάτρικ Αστέρης]

Να ρωτησω
Στην περσινη 2η προοδο ποιο ειναι το λαθος του αλγοριθμου στο 3ο θεμα; 
[/quote

Αν θυμαμαι καλα ο "λαθος" αλγοριθμος ελυνε το προβλημα απληστα, αντι με δυναμικο που το λυνει βελτιστα

Αν κανεις swap νουμερα σε αυτην που εχει ως παραδειγμα εβγαινε νομιζω.Δε το χω μπροστα μου αλλα πρεπει να βαλα το 7 στη θεση του 3 or sth

ola komple
ναι ειναι απληστος και δεν δουλευει
με το 5 9 6 7 πχ φαινεται