Αλγόριθμοι και Πολυπλοκότητα (ΣΗΜΜΥ)
χειμερινό εξάμηνο 2013-2014
Γενικά
Διδάσκοντες
- Στάθης Ζάχος, Καθηγητής ()
- Δημήτρης Φωτάκης, Λέκτορας ()
Βοηθοί Διδασκαλίας
- Σωτήρης Δήμος, Υ.Δ. ()
- Μάρκος Επιτρόπου, Υ.Δ. ()
- Μανώλης Ζαμπετάκης, Υ.Δ. ()
- Θανάσης Λιανέας, Υ.Δ. ()
- Ανδρέας Μάντης, Υ.Δ. ()
Βοηθοί Εργαστηρίου
- Κυριάκος Αξιώτης
- Μάκης Αρσένης
- Γιώργος Παναγιωτάκος
- Δημήτρης Τσίπρας
- Γιάννης Χατζημίχος
Διαλέξεις
- κάθε Δευτέρα 15:00-17:00 (Αμφιθέατρο 1, νέο κτήριο Ηλεκτρολόγων)
- κάθε Πέμπτη 17:00-19:00 (Αμφιθέατρο 4, νέο κτήριο Ηλεκτρολόγων την 1η ώρα, και Αμφιθέατρο 1, νέο κτήριο Ηλεκτρολόγων την 2η)
Ώρες Γραφείου
- κάθε Δευτέρα 14:00-15:00 στο εργαστήριο 1.1.3 (CoReLab) ή στο γρ. 1.1.10 του κτηρίου Ηλεκτρολόγων.
- κάθε Πέμπτη 16:00-17:00 στο εργαστήριο 1.1.3 (CoReLab) ή στο γρ. 1.1.10 του κτηρίου Ηλεκτρολόγων.
Ενημερωτικό Φυλλάδιο
Μπορείτε να βρείτε το ενημερωτικό φυλλάδιο του μαθήματος εδώ.
Βιβλιογραφία
- Thomas Cormen, Charles Leiserson, Ronald Rivest and Cliff Stein: "Introduction to Algorithms", 3rd edition, MIT Press, 2009.
- J. Kleinberg, E. Tardos: "Algorithm Design", Addison-Wesley, 2005.
- S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani: "Algorithms", MacGraw-Hill, 2006 (Μπορείτε να βρείτε draft έκδοση του βιβλίου αυτού εδώ).
- J. Edmonds. How to Think About Algorithms. Cambridge University Press, 2008.
- G. Brassard, P. Bratley: "Algorithmics: Theory and Practice", Prentice-Hall.
- Sara Baase, Allen Van Gelder, "Computer Algorithms: Introduction to Design and Analysis", 3rd edition, Addison Wesley Longman, 2000.
- Alfred V. Aho, John E. Hopcroft, "The Design and Analysis of Computer Algorithms", Addison-Wesley Series in Computer Science and Information Processing, 1974.
- Dexter C. Kozen, "The Design and Analysis of Algorithms", Springer, 1991.
- A. Levitin: "Ανάλυση και Σχεδίαση Αλγορίθμων", Εκδόσεις Τζιόλα, 2007.
- G. J. E. Rawlings: "Αλγόριθμοι: Ανάλυση και Σύγκριση", Εκδόσεις Κριτική, 2004.
Ανακοινώσεις
- [17/08/2014] Βαθμολογία χαριστικής εξέτασης Ιουλίου 2014.
- [25/4/2014] Βαθμολογία εξεταστικής περιόδου Μαρτίου: προπτυχιακοί και μεταπτυχιακοί φοιτητές. Η βαθμολογία της εξέτασης έχει ως άριστα το 80, η βαθμολογία των γραπτών ασκήσεων έχει ως άριστα το 10, και η βαθμολογία των προγραμματιστικών ασκήσεων έχει ως άριστα το 15. Οι βαθμοί των γραπτών και των προγραμματιστικών ασκήσεων του ακαδ. έτους 2012-2013 έχουν συνυπολογιστεί (για όσους είχαν παραδώσει ασκήσεις), αλλά δεν συμπεριλαμβάνονται σε αυτόν τον πίνακα. Για να δείτε τα γραπτά σας και για οποιεσδήποτε ερωτήσεις σχετικά με τη βαθμολογία σας, μπορείτε να έρθετε στο Corelab (1.1.3), την Τετάρτη 30 Απριλίου, ώρα 16:30 - 18:00.
- [27/3/2014] "Άνοιξε" ο grader για εκπρόθεσμη υποβολή των προγραμματιστικών ασκήσεων 2 και 3 (με μειωμένη βαθμολογία, ίση με το 80% της συνολικής). Ο grader θα παραμείνει ανοικτός μέχρι το Σάββατο 12 Απριλίου (ώρα 23:00).
- [10/3/2014] Η διανομή σημειώσεων "Αλγορίθμων και Πολυπλοκότητας" θα γίνεται κάθε μέρα, 16:00-18:00, στο CoReLab (αιθ. 1.1.3, ΠΚΗ).
- [15/02/2014] Βαθμολογία χαριστικής εξέτασης Φεβρουαρίου 2014.
- [28/12/2013] Έχει "ανοίξει" ο grader για την υποβολή της 1ης προγραμματιστικής άσκησης. Για την υποβολή, πρέπει να χρησιμοποιείται τα login name και password που έχετε για το moodle του μαθήματος (και όχι άλλα accounts που πιθανώς έχετε ήδη στον grader), ώστε να μην υπάρξουν προβλήματα με τη βαθμολογία σας. Καλή επιτυχία!
- [19/12/2013] Μπορείτε να υποβάλετε τις γραπτές ασκήσεις ηλεκτρονικά, στο moodle, αναρτώντας τις λύσεις σας στο αντίστοιχο θέμα συζήτησης.
- [11/12/2013] Όσοι συμμετείχαν στην εξέταση του Αυγούστου μπορούν να δουν τα γραπτά τους ή να ρωτήσουν σχετικά με τη βαθμολογία τους την Τρίτη 17/12, ώρα 18:15 - 19:30, στο Corelab (αίθουσα 1.1.3, στο παλαιό κτήριο Ηλεκτρολόγων).
- [10/12/2013] Οι αίθουσες διδασκαλίας άλλαξαν. Παρακαλώ δείτε την αντίστοιχη ενότητα.
- [5/12/2013] Το moodle του μαθήματος είναι ενεργό. Πρέπει να γραφτείτε όλοι μέχρι την Πέμπτη 12/12, ώστε να γίνει η απαραίτητη προετοιμασία για την ανακοίνωση της 1ης προγραμματιστικής άσκησης. Από τα στοιχεία που θα δηλώσετε στο moodle πρέπει να προκύπτουν με σαφήνεια το Ονοματεπώνυμό σας και ο Αριθμός Μητρώου σας. Τα login name και password που θα δηλώσετε στο moodle θα χρησιμοποιούνται και για την πρόσβαση / υποβολή των προγραμματιστικών ασκήσεων στον grader. Πρέπει να τα φυλάξετε προσεκτικά, γιατί ο grader δεν υποστηρίζει μηχανισμό ανάκτησης κωδικού πρόσβασης!
- [27/11/2013] Η πρώτη διάλεξη θα γίνει την Πέμπτη 28 Νοεμβρίου, στις 17:00.
- [15/09/2013] Βαθμολογία εξεταστικής περιόδου Σεπτεμβρίου 2013: προπτυχιακοί και μεταπτυχιακοί φοιτητές. Ημερομηνία για την επίδειξη των γραπτών θα ανακοινωθεί μετά το τέλος των κινητοποιήσεων.
Υλικό
Διαφάνειες Μαθήματος
- Διάλεξη 28/11/2013: Εισαγωγή και Διαδικαστικά. Εισαγωγικές Έννοιες.
- Διάλεξη 2/12/2013: Ασυμπτωτικός Συμβολισμός.
- Διάλεξη 5/12/2013: Δομές Δεδομένων. Ουρές Προτεραιότητας: Σωρός. Κάτω Φράγμα στη χρονική πολυπλοκότητα συγκριτικών αλγόριθμων ταξινόμησης.
- Διάλεξη 9/12/2013: Union - Find. Αλγόριθμοι Διαίρει-και-Βασίλευε: Merge-Sort.
- Διάλεξη 12/12/2013: Master Theorem. Αλγόριθμοι Διαίρει-και-Βασίλευε: Πολλαπλασιασμός αριθμών και πινάκων, ύψωση σε δύναμη.
- Διάλεξη 16/12/2013: Quicksort. Πιθανοτική Quicksort.
- Διάλεξη 19/11/2013: Το πρόβλημα της επιλογής. Δυαδική Αναζήτηση.
- Διάλεξη 23/12/2013: Αναζήτηση με Παρεμβολή. Άπληστοι Αλγόριθμοι.
- Διάλεξη 9/1/2014: Άπληστοι αλγόριθμοι. Δυναμικός προγραμματισμός.
- Διάλεξη 13/1/2014: Δυναμικός προγραμματισμός.
- Διάλεξη 16/1/2014: Δυναμικός προγραμματισμός. Συζήτηση 1ης σειράς ασκήσεων.
- Διάλεξη 20/1/2014: Δυναμικός προγραμματισμός: Ασκήσεις. Εξερεύνηση Γραφημάτων: Αναζήτηση κατά Πλάτος.
- Διάλεξη 23/1/2014: Αναζήτηση κατά Βάθος. Ελάχιστο Συνδετικό Δέντρο.
- Διάλεξη 27/1/2014: Ελάχιστο Συνδετικό Δέντρο: αλγόριθμος Kruskal, αλγόριθμος Prim, αλγόριθμος Boruvka.
- Διάλεξη 3/2/2014: Συντομότερες διαδρομές από μία αρχική κορυφή: αλγόριθμος Bellman-Ford, αλγόριθμος Dijkstra.
- Διάλεξη 6/2/2014: Συντομότερες διαδρομές από μία αρχική κορυφή: αλγόριθμος Dijkstra. Συντομότερες διαδρομές για όλα τα ζεύγη κορυφών: αλγόριθμος Floyd-Warshall, αλγόριθμος Johnson.
- Διάλεξη 10/2/2014: Μέγιστη Ροή - Ελάχιστη Τομή. Μηχανές Turing και Υπολογισιμότητα.
- Διάλεξη 13/2/2014: Υπολογιστική Πολυπλοκότητα - Αναγωγές.
- Διάλεξη 17/2/2014: Μη Ντετερμινισμός. Η Κλάση NP. NP-Πληρότητα. Παραδείγματα αναγωγών.
- Διάλεξη 20/2/2014: NP-Πληρότητα. Παραδείγματα αναγωγών.
- Διάλεξη 24/2/2014: NP-Πληρότητα. Παραδείγματα αναγωγών.
- Διάλεξη 27/2/2014: Παραδείγματα αναγωγών. Συζήτηση 1ης και 3ης σειράς ασκήσεων.
- Διάλεξη 6/3/2014: Χωρική Πολυπλοκότητα. Προσεγγιστικοί Αλγόριθμοι.
Σημειώσεις - Συμπληρωματικό Υλικό
- Προγραμματιστικές Ασκήσεις: Μια απλή συνάρτηση σε C για να διαβάζετε γρήγορα την είσοδο όταν αυτή αποτελείται από μη αρνητικούς ακέραιους και τα testcases είναι πολύ μεγάλα.
- Σύντομη Εισαγωγή στη Θεωρία Γραφημάτων (σημειώσεις του Δ. Φωτάκη). Για τις βασικές έννοιες της Θεωρίας Γραφημάτων δείτε ακόμη τις ακόλουθες διαφάνειες: Εισαγωγή στη Θεωρία Γραφημάτων, και Βασικές Έννοιες της Θεωρίας Γραφημάτων: 1η, 2η, και 3η σειρά.
- Συμπληρωματικές σημειώσεις του Δ. Φωτάκη. Καλύπτουν μόνο ένα μέρος της ύλης του μαθήματος.
- Ένα ενδιαφέρον άρθρο από τον Bernard Chazelle: The Algorithm: Idiom of Modern Science.
- Ένα ενδιαφέρον άρθρο από τον Jeff Ullman σχετικά με την θεωρητική και την πειραματική αξιολόγηση των αλγορίθμων: Experiments as Research Validation – Have We Gone too Far?
Προτεινόμενες Ασκήσεις (με τις λύσεις τους) και Παραδείγματα
- 1η σειρά: Ασυμπτωτικός συμβολισμός, αναδρομικές σχέσεις, ταξινόμηση.
- 2η σειρά: Άπληστοι αλγόριθμοι, δυναμικός προγραμματισμός.
- 3η σειρά: Αλγόριθμοι γραφημάτων, Ελάχιστο Συνδετικό Δέντρο.
- 4η σειρά: Συντομότερα Μονοπάτια, Μέγιστη Ροή, Αναγωγές.
- 5η σειρά: Παραδείγματα αναγωγών (διαφάνειες).
Ασκήσεις
Γραπτές Ασκήσεις
| Εκφώνηση | Ημερομηνία Παράδοσης | Σχέδιο Λύσεων |
|---|---|---|
| Πρώτη σειρά | 23/12/2013 |
Διαφάνειες |
| Δεύτερη σειρά | 27/1/2014 |
Διαφάνειες |
| Τρίτη σειρά | 17/2/2014 |
Διαφάνειες |
| Τέταρτη σειρά | 24/3/2014 |
Διαφάνειες |
Προγραμματιστικές Ασκήσεις
| Εκφώνηση | Συμπληρωματικά Αρχεία | Ημερομηνία Παράδοσης |
|---|---|---|
| Πρώτη σειρά | 7/1/2014 |
|
| Δεύτερη σειρά | 2/2/2014 |
|
| Τρίτη σειρά | 24/2/2014 |
|
| Τέταρτη σειρά | 11/4/2014 |
Παρατηρήσεις
- Οι προγραμματιστικές ασκήσεις υποβάλλονται (source code) στον grader, και αξιολογούνται ηλεκτρονικά. Η προθεσμία υποβολής λήγει τα μεσάνυχτα της ημέρας παράδοσης. Για την υποβολή, θα χρησιμοποιήσετε τα login name και password που έχετε για το moodle του μαθήματος. Τα προγράμματά σας πρέπει να είναι σε C/C++, να διαβάζουν την είσοδο από το standard input, και να τυπώνουν την έξοδο στο standard output. Μια υποβολή θεωρείται επιτυχής (και συνεχίζει στο στάδιο της αξιολόγησης) αν "περάσει" επιτυχώς τα επιλεγμένα test cases για το αντίστοιχο ερώτημα. Η αξιολόγηση γίνεται με αντίστοιχα (κοινά για όλους, αλλά διαφορετικά από αυτά που ελέγχονται κατά την υποβολή) test cases, μετά την λήξη της προθεσμίας. Με κάθε άσκηση, θα δίνεται και ένας αριθμός test cases (με τις απαντήσεις τους), που μπορείτε να χρησιμοποιήσετε για προκαταρκτικό έλεγχο των λύσεων σας.
- Στις γραπτές ασκήσεις να γράφετε ονοματεπώνυμο και αριθμό μητρώου. Είτε τις παραδίδετε στους βοηθούς διδασκαλίας, κατά προτίμηση στο μάθημα της Δευτέρας, είτε τις αναρτάτε στο moodle. Η προθεσμία λήγει στις 19:00 της ημέρας παράδοσης. Εάν δοθεί παράταση θα ανακοινωθεί σε αυτή τη σελίδα και στο moodle.
- Δεν γίνεται δεκτή η παράδοση ασκήσεων με e-mail.
- Συνεργασία επιτρέπεται και μάλιστα ενθαρρύνεται (εάν γίνεται σωστά), αλλά τελικά κάθε φοιτητής πρέπει να διατυπώσει μόνος του τη λύση. Πανομοιότυπες διατυπώσεις θα εκλαμβάνονται ως αντιγραφή και δεν θα προσμετράται ο βαθμός τους, ενώ πιθανόν να υπάρξουν συνέπειες για όλες τις σειρές ασκήσεων.
- Για απορίες πάνω στις ασκήσεις και στη θεωρία μπορείτε να έρχεστε στο CoReLab (κτ. ΗΜΜΥ 1.1.3) στις ώρες γραφείου.