Αλγόριθμοι

Συζητήσεις σχετικά με τα μαθήματα του μεταπτυχιακού προγράμματος Επιστήμης Υπολογιστών.
Post Reply
User avatar
rapadder
Gbyte level
Gbyte level
Posts: 1896
Joined: Thu Jun 17, 2004 7:12 pm
Academic status: Alumnus/a
Gender:

Αλγόριθμοι

Post by rapadder » Sat Oct 22, 2005 1:40 pm

Σχετικά με την πρώτη σειρά ασκήσεων, στις αναδρομικές σχέσεις (άσκηση 2), εκτός από το υποερώτημα (α) και (γ), έχει λύσει κανείς τα (β) και (δ);
... αντάρτες της πορδής με τα λεφτά του μπαμπά...
User avatar
mikem4600
Gbyte level
Gbyte level
Posts: 1363
Joined: Fri Mar 12, 2004 2:00 pm
Academic status: Alumnus/a
Gender:
Location: A Galaxy Far, Far Away
Contact:

Post by mikem4600 » Sat Oct 22, 2005 2:09 pm

Ναι, εφαρμόζοντας απλώς τη μέθοδο της αντικατάστασης.
Autocracy hates questions. Anarchy hates answers.
User avatar
rapadder
Gbyte level
Gbyte level
Posts: 1896
Joined: Thu Jun 17, 2004 7:12 pm
Academic status: Alumnus/a
Gender:

Post by rapadder » Sat Oct 22, 2005 9:42 pm

Ευχαριστώ :-) .
... αντάρτες της πορδής με τα λεφτά του μπαμπά...
User avatar
rapadder
Gbyte level
Gbyte level
Posts: 1896
Joined: Thu Jun 17, 2004 7:12 pm
Academic status: Alumnus/a
Gender:

Post by rapadder » Wed Jan 04, 2006 5:16 pm

Έχω μια μικρή παρατήρηση να κάνω. Στο CLRS στη σελίδα 1007, στο σχήμα 34.15 δείχνει ότι εάν ο αρχικός γράφος G = (V, E) έχει κλίκα (clique) που αποτελείται από τους κόμβους {u, v, x, y} τότε το ανάστροφο γράφημα έχει Vertex Cover που αποτελείται από τους κόμβους (που περισσεύουν) {z, w}. Επίσης οι κόμβοι {u, v, x, y } συνιστούν ένα Independent Set (IS). Αποδεικνύεται και το αντίστροφο.
Παρατηρώ ότι ο γράφος G έχει Vertex Cover που αποτελείται από τους κόμβους {y, x}. Ρίχνοντας όμως μια ματιά στο ανάστροφο γράφημα, βλέπω ότι δεν υπάρχει κλίκα (clique) που να αποτελείται από τους κόμβους {u, v, z, w}, αφού αυτοί οι τέσσερις κόμβοι δεν σχηματίζουν πλήρες υπογράφημα. Δεν θα έπρεπε να ισχύει κάτι τέτοιο;
... αντάρτες της πορδής με τα λεφτά του μπαμπά...
User avatar
nap
Kilobyte level
Kilobyte level
Posts: 239
Joined: Tue Nov 23, 2004 5:25 pm
Location: In da ghetto
Contact:

Post by nap » Wed Jan 04, 2006 11:04 pm

rapadder wrote:Έχω μια μικρή παρατήρηση να κάνω. Στο CLRS στη σελίδα 1007, στο σχήμα 34.15 δείχνει ότι εάν ο αρχικός γράφος G = (V, E) έχει κλίκα (clique) που αποτελείται από τους κόμβους {u, v, x, y} τότε το ανάστροφο γράφημα έχει Vertex Cover που αποτελείται από τους κόμβους (που περισσεύουν) {z, w}. Επίσης οι κόμβοι {u, v, x, y } συνιστούν ένα Independent Set (IS). Αποδεικνύεται και το αντίστροφο.
Σωστό.
rapadder wrote:Παρατηρώ ότι ο γράφος G έχει Vertex Cover που αποτελείται από τους κόμβους {y, x}.
Είσαι σίγουρος; Το {y, x} στο γράφημα G (34.15 a) δεν είναι VC (αφού υπάρχουν ακμές που δεν "καλύπτονται" από τους κόμβους x και y, όπως οι (z,w), (u,v) κ.ά.).
It is by will alone I set my mind in motion...
User avatar
rapadder
Gbyte level
Gbyte level
Posts: 1896
Joined: Thu Jun 17, 2004 7:12 pm
Academic status: Alumnus/a
Gender:

Post by rapadder » Thu Jan 05, 2006 12:50 am

Έχεις δίκιο nap. Στραβομάρα εντελώς... Ευχαριστώ πολύ για την απάντηση. Ελπίζω να ρωτήσουν και άλλοι τίποτα για να κινηθεί το thread. (Θέλω να πιστεύω ότι δεν είμαι ο μόνος που δεν τα ξέρει όλα :-) ).
... αντάρτες της πορδής με τα λεφτά του μπαμπά...
User avatar
mikem4600
Gbyte level
Gbyte level
Posts: 1363
Joined: Fri Mar 12, 2004 2:00 pm
Academic status: Alumnus/a
Gender:
Location: A Galaxy Far, Far Away
Contact:

Post by mikem4600 » Thu Jan 05, 2006 9:55 pm

Να σου πω την αλήθεια, εγώ δεν έχω κοιτάξει (ακόμα) την τελευταία σειρά ασκήσεων...
Autocracy hates questions. Anarchy hates answers.
User avatar
rapadder
Gbyte level
Gbyte level
Posts: 1896
Joined: Thu Jun 17, 2004 7:12 pm
Academic status: Alumnus/a
Gender:

Post by rapadder » Fri Jan 13, 2006 2:26 pm

Σχετικά με το πρόβλημα Bin Packing, έχω την εξής απορία. Το Bin Packing είναι Strongly NP-Complete. Όταν ζητείται η αναγωγή από ένα άλλο πρόβλημα (που γνωρίζουμε ότι είναι NP-Complete), πρέπει να δείξουμε κατ'αρχάς ότι υπάρχει ένας πολυωνυμικός αλγόριθμος που να μπορεί να απαντήσει ΝΑΙ σε ένα στιγμιότυπο του προβλήματος (αν αυτό είναι φυσικά αληθές). Για παράδειγμα, στον κύκλο Hamilton που επίσης είναι πρόβλημα Strongly NP-Complete, αρκεί να δούμε ότι ο προς έλεγχο κύκλος (το στιγμιότυπο του προβλήματος) καλύπτει κάθε κόμβο του γραφήματος, που γίνεται εύκολα σε πολυωνυμικό χρόνο. Το θέμα είναι ότι δεν μπορώ να σκεφτώ έναν προφανή πολυωνυμικό αλγόριθμο (για το Bin Packing), συγκεκριμένα την decision version του, που να τσεκάρει δηλαδή ότι ένας δοσμένος αριθμός Χ από κάδους (bins) χωρητικότητας Μ είναι ο ελάχιστος (για να τοποθετηθούν n αντικείμενα με διαφορετικό βάρος το κάθε ένα, ώστε το βάρος των αντικειμένων να μην ξεπερνάει την χωρητικότητα Μ του κάθε σακιδίου). Έχει βρει κανένας κανένα πολυωνυμικό αλγόριθμο για αυτόν τον έλεγχο;
Θα μπορούσα να παρέθετα απ' ευθείας την αναγωγή (απ' τό NP πλήρες πρόβλημα) αλλά πιστεύω ότι κάτι θα έλειπε για αν είμαι 100% σωστός...
... αντάρτες της πορδής με τα λεφτά του μπαμπά...
User avatar
rapadder
Gbyte level
Gbyte level
Posts: 1896
Joined: Thu Jun 17, 2004 7:12 pm
Academic status: Alumnus/a
Gender:

Post by rapadder » Fri Jan 13, 2006 3:19 pm

Μια προφανής απαίτηση είναι ότι το άθροισμα των περισσευούμενων χώρων σε κάθε κάδο (κάθε κάδος ή θα είναι τελείως γεμάτος ή θα περισσεύει κάποιος χώρος) θα πρέπει να είναι μικρότερο από την χωρητικότητα Μ του κάθε κάδου. Αφού μας ενδιαφέρει η ελαχιστοποίηση του αριθμού των κάδων, στην περίπτωση αυτή η λύση μπορεί να θεωρηθεί βέλτιστη (καθώς αν τα αντικείμενα έχουν συνολικό βάρος k*W+z, k ανήκει στο {0,1,2,…} και z < W τότε σαφώς απαιτούνται τουλάχιστον k+1 κάδοι. Το θέμα είναι εάν για κάθε σύνολο αντικειμένων (με βάρη μικρότερα από M το καθένα για να χωράνε στους κάδους), η βέλτιστη λύση έχει ακριβώς k+1 κάδους.
... αντάρτες της πορδής με τα λεφτά του μπαμπά...
User avatar
rapadder
Gbyte level
Gbyte level
Posts: 1896
Joined: Thu Jun 17, 2004 7:12 pm
Academic status: Alumnus/a
Gender:

Post by rapadder » Fri Jan 13, 2006 3:50 pm

Το όριο αυτό είναι υπερβολικά αυστηρό. Π.χ. για χωρητικότητα κάδου Μ = 10 μονάδες και αντικείμενα βάρους {9, 8, 7, 6}, το παραπάνω κάτω όριο είναι 3 κάδοι (9+8+7+6 = 30), ενώ απαιτούνται 4. Στη χειρότερη περίπτωση θα αντιστοιχεί ένας κάδος σε κάθε αντικείμενο. Οπότε ισχύει ότι ο ελάχιστος αριθμός κάδων θα είναι >= k+1 (δες παραπάνω post) και <= n (πλήθους αντικειμένων). Δεν νομίζω ότι στη γενική περίπτωση μπορούμε να βρούμε κάποιο συγκεκριμένο όριο ώστε κάθε βέλτιστη λύση να πρέπει να ισούται με αυτό.
Το θέμα παραμένει. Αφού το πρόβλημα είναι (strongly) NP – Complete, θα πρέπει να μπορώ να απαντήσω σε πολυωνυμικό χρόνο για ένα στιγμιότυπο του προβλήματος (αν αυτό ικανοποιείται).
... αντάρτες της πορδής με τα λεφτά του μπαμπά...
Erevodifwntas
Gbyte level
Gbyte level
Posts: 1098
Joined: Thu Apr 22, 2004 2:18 pm
Academic status: Alumnus/a
Gender:
Location: In a Long Time Ago in A Galaxy far far away
Contact:

Post by Erevodifwntas » Sat Jan 14, 2006 10:14 am

Το decision πρόβλημα δεν έχει σχέση με το ελάχιστο
Go To Statement Considered Harmful (Τιτλος δημοσίευσης του Edsger Dijkstra).

my personal site
Post Reply

Return to “Μεταπτυχιακό Επιστήμης Υπολογιστών”