Το μάθημα εισάγει τις έννοιες της σχεδίασης και ανάλυσης του αλγορίθμου και παρουσιάζει τα βασικά μαθηματικά εργαλεία που χρησιμοποιούνται για την αποτίμηση της απόδοσής του. Περιγράφει τις τεχνικές αναζήτησης σε σύνολα (union and find) και παρουσιάζει τις θεμελιώδεις τεχνικές διάσχισης σε γραφήματα, κατά πλάτος (BFS) και κατά βάθος (DFS). Εστιάζει στις τρεις βασικές μεθόδους σχεδίασης αλγορίθμων, “διαίρει και βασίλευε”, άπληστοι (greedy) αλγόριθμοι και δυναμικός προγραμματισμός. Αναλύει τα χαρακτηριστικά κάθε μεθόδου και αναδεικνύει τα πρακτικά προβλήματα που επιλύονται αποτελεσματικά από κάθε μέθοδο. Ορίζει τα προβλήματα απόφασης και τις κλάσεις P και NP. Περιγράφει την έννοια της αναγωγής και προσδιορίζει τα προβλήματα NP-complete και NP-hard.
1. Th. H. Cormen, CH. E. Leiserson, R. L. Rivest and C. Stein, Introduction to algorithms, MIT-Press, 2009, 3rd edition, MIT Press, http://mitpress.mit.edu/algorithms/ (Εύδοξος).
2. Jon Kleinberg & Eva Tardos, Algorithm Design, Addison – Wesley, 2006 (Εύδοξος).
3. S. Dasgupta, C. H. Papadimitriou & U. V. Vazirani, Algorithms, McGraw-Hill, 2008 (Εύδοξος).
• Σημειώσεις, Αλγόριθμοι και Πολυπλοκότητα, 2016, Β. Ζησιμόπουλος
https://eclass.uoa.gr/modules/document/index.php?course=D469&openDir=/4c2b32c4z3e6
•Διαφάνειεςδιαλέξεων, https://eclass.uoa.gr/modules/document/index.php?course=D469&openDir=/4c2b32c4rt6n