Περιγραφή
Στο μάθημα θα καλύψουμε τις μεθόδους διαίρει-και-βασίλευε, δυναμικού προγραμματισμού, και απληστίας και αρκετούς αλγόριθμους γραφημάτων. Συγκεκριμένα, θα συζητήσουμε την Αναζήτηση Πρώτα σε Πλάτος, την Αναζήτηση Πρώτα σε Βάθος και τις εφαρμογές τους, αλγόριθμους για τον υπολογισμό ενός Ελάχιστου Επικαλύπτοντος Δέντρου, αλγόριθμους για το πρόβλημα των Συντομότερων Μονοπατιών, και αλγόριθμους για τα προβλήματα της Μέγιστης Ροής και της Ροής Ελάχιστου Κόστους. Θα παρουσιάσουμε μερικά αντιπροσωπευτικά παραδείγματα πιθανοτικών αλγορίθμων. Θα επιχειρήσουμε ακόμη μια σύντομη εισαγωγή στη Θεωρία Υπολογιστικής Πολυπλοκότητας εστιάζοντας στις κλάσεις P και NP και στην έννοια της NP-πληρότητας και των αλγοριθμικών συνεπειών της.
Διδάσκοντες
Δημήτρης Φωτάκης, Επίκουρος Καθηγητής - Θεωρία
Ελισάβετ Κωνσταντίνου, Λέκτορας - Εργαστήριο
Ύλη
Το μάθημα θα βασιστεί σε σημαντικό βαθμό στο βιβλίο του Π. Μποζάνη Αλγόριθμοι: Σχεδιασμός και Ανάλυση (2η έκδοση) και στις σημειώσεις του διδάσκοντα. Ένα σημαντικό μέρος της δουλειάς θα γίνει στο εργαστήριο όπου θα υλοποιήσουμε και θα πειραματιστούμε με τους σημαντικότερους αλγόριθμους που θα συναντήσουμε στο μάθημα.
Στην ύλη για τις εξετάσεις περιλαμβάνονται όλες οι ενότητες από το βιβλίο του Μποζάνη που αναγράφονται δίπλα στις διαλέξεις και το σύνολο της ύλης που υπάρχει στις σημειώσεις. Κάποια τμήματα της ύλης καλύπτονται μόνο από το βιβλίο και κάποια άλλα μόνο από τις σημειώσεις.
Επικοινωνία
Προσπαθήστε να παρακολουθείτε τις παραδόσεις συστηματικά και να συμμετέχετε ενεργά στο εργαστήριο. Σε μαθήματα σαν και αυτό, η περιστασιακή μελέτη δεν μπορεί να υποκαταστήσει την παρακολούθηση. Αν έχετε απορίες ή αντιμετωπίζετε δυσκολίες στη μελέτη σας, μη διστάσετε να τις συζητήσετε με τους διδάσκοντες.
Δ. Φωτάκης. Ώρες γραφείου: Τετάρτη 1
Σημειώσεις - Ασκήσεις
Αλγόριθμοι και Πολυπλοκότητα (σημειώσεις του διδάσκοντα).
Δομή Μαθήματος - Διαλέξεις - Οδηγός Μελέτης
Εισαγωγικές Έννοιες (βιβλίο: κεφάλαιο 1 εκτός από 1.2.7, σημειώσεις: κεφάλαιο 1)
Αναπαράσταση γραφημάτων (βιβλίο: ενότητες 3.1 και 3.2, σημειώσεις: 5.1).
Αναζήτηση Πρώτα σε Πλάτος (βιβλίο: 3.3.2, σημειώσεις: 5.2).
Αναζήτηση Πρώτα σε Βάθος (βιβλίο: ενότητες 3.3.1 και 3.4, σημειώσεις: 5.3)
Διαίρει-και-Βασίλευε: Πολλαπλασιασμός αριθμών, πινάκων, και ύψωση σε δύναμη (βιβλίο: ενότητες 2.1 και 8.2, σημειώσεις: ενότητες 2.1, 2.2, και 2.3).
Δυναμικός Προγραμματισμός (βιβλίο: ενότητα 2.2, σημειώσεις: ενότητες 3.1 και 3.3).
Άπληστοι Αλγόριθμοι (βιβλίο: ενότητα 2.3, σημειώσεις: 4.1, 4.2, και 4.3).
Ελάχιστα Επικαλύπτοντα Δέντρα (βιβλίο: ενότητες 4.1, 4.2, 4.3, και 4.5, σημειώσεις: ενότητα 5.4).
Συντομότερα Μονοπάτια (βιβλίο: ενότητες 5, 5.1, και 5.2, σημειώσεις: ενότητες 5.5, 5.6, και 5.7).
Εισαγωγή στη Θεωρία Υπολογιστικής Πολυπλοκότητας. Χρονική Πολυπλοκότητα, η κλάση P (βιβλίο: κεφάλαιο 11 (χωρίς την απόδειξη της παραγράφου 11.2.6), σημειώσεις: κεφάλαιο 6).
Μη-Ντετερμινισμός, η Κλάση NP, NP-Πληρότητα (σημειώσεις: κεφάλαιο 7)
Εξετάσεις - Βαθμολογία
Ο βαθμός του εργαστηρίου (ΒΕ) θα συνεισφέρει το 30% του τελικού βαθμού και κάποιος πρέπει να έχει ΒΕ>=5.0 για να περάσει το μάθημα. Ο βαθμός της τελικής εξέτασης (ΒΤΕ) θα συνεισφέρει το 70% του τελικού βαθμού και κάποιος πρέπει να έχει ΒΤΕ>=4.5 για να περάσει το μάθημα. Ο τελικός βαθμός του μαθήματος (ΤΒ) θα είναι:
TB = 0.3*BE + 0.7*BTE
και φυσικά πρέπει ΤΒ>=5.0 ώστε το μάθημα να θεωρηθεί ότι εξετάστηκε με επιτυχία.
Εργαστηριακές Ασκήσεις
Θα ανακοινωθούν έξι ατομικές, υποχρεωτικές εργαστηριακές ασκήσεις. Οι εκφωνήσεις των ασκήσεων ανακοινώνονται στην ιστοσελίδα της κας Κωνσταντίνου. Σε κάθε άσκηση θα υλοποιήσετε και θα πειραματιστείτε με μερικούς από τους αλγορίθμους που θα συζητήσουμε στο μάθημα. Οι υλοποιήσεις θα είναι σε γλώσσα C ή C++. Η παράδοση κάθε εργασίας μπορεί να πραγματοποιηθεί ΜΟΝΟ κατά την διάρκεια του αντίστοιχου εργαστηριακού μαθήματος (εργαστήριο Ηλέκτρα, κτίριο Λυμπέρη). Μετά τη λήξη του συγκεκριμένου εργαστηριακού μαθήματος ΔΕΝ θα γίνονται δεκτές άλλες εργασίες.
Εργαστηριακή άσκηση 1. Ημερομηνία παράδοσης 8/5/2007.
Εργαστηριακή άσκηση 2. Ημερομηνία παράδοσης 15/5/2007.
Εργαστηριακή άσκηση 3. Ημερομηνία παράδοσης 22/5/2007.
Εργαστηριακή άσκηση 4. Ημερομηνία παράδοσης 29/5/2007.
Εργαστηριακή άσκηση 5. Ημερομηνία παράδοσης 5/6/2007.
Εργαστηριακή άσκηση 6. Ημερομηνία παράδοσης 12/6/2007.
Συμπληρωματικό Υλικό
Πειραματιστείτε δημιουργώντας τυχαία γραφήματα.
Πειραματιστείτε με το FFT (υλοποίηση του FFT και του Inverse FFT σε C).
Πειραματιστείτε δημιουργώντας τυχαία στιγμιότυπα για το Πρόβλημα του Σακιδίου (Knapsack Problem).
Βιβλιογραφία
Π. Μποζάνης. Αλγόριθμοι: Σχεδιασμός και Ανάλυση. Εκδόσεις Τζιόλα, Θεσσαλονίκη, 2003.
Γ.Φ. Γεωργακόπουλος. Δομές Δεδομένων, Έννοιες, Τεχνικές και Αλγόριθμοι. Πανεπιστημιακές Εκδόσεις Κρήτης,
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms (2nd Edition). The MIT Press, 2003.
K. Mehlhorn. Data Structures and Algorithms. Springer Verlag, EATCS Monographs, 1984.
G. Brassard and P. Bratley. Algorithmics: Theory and Practice. Prentice-Hall, 1988.
Σχετικές Ιστοσελίδες
Ι. Μανωλόπουλος. Ανάλυση Αλγορίθμων, Άνοιξη 2005.
Η. Κουτσουπιάς. Αλγόριθμοι και Πολυπλοκότητα, Χειμώνας 2004.
E. Demaine and S. Goldwasser. Introduction to Algorithms. MIT, Spring 2004.
K. Pruhs. Algorithms Courses on the WWW.
Αν σας αρέσουν τα μαθηματικά και θέλετε να γίνετε πλούσιοι, κοιτάξτε τη σελίδα του Clay Mathematics Institute.