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

[Thmmy.gr portal]

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

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

[Δείτε περισσότερα εδώ...]

Συμβουλές καλής χρήσης του φόρουμ: Youtube embed code and links, Shoutbox, Notify, ...

Δείτε περισσότερα εδώ...

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

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

Τι εκανε?

Στο χρονοδιαγραμμα στο 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 πχ φαινεται