Σκοπός του μαθήματος είναι η σε βάθος μελέτη τεχνικών σχεδίασης δομών δεδομένων και αλγορίθμων και ανάλυσης της πολυπλοκότητάς τους, καθώς και η απόκτηση από τους φοιτητές δυνατοτήτων αντιμετώπισης ενός ευρέως φάσματος προβλημάτων και κατανόησης της δυσκολίας τους.
Πολυπλοκότητα αλγορίθμων και προβλημάτων,
πολυπλοκότητα καλύτερης, χειρότερης και μέσης περίπτωσης, αποσβεστική
πολυπλοκότητα.
Διαχείριση συνόλων: ευρετήρια, ουρές προτεραιότητας, union-find.
Σχεδιασμός αποτελεσματικών αλγορίθμων: άπληστοι αλγόριθμοι, διαίρει και
βασίλευε, δυναμικός προγραμματισμός.
Αλγόριθμοι γραφημάτων: διάσχιση, συνεκτικότητα, μονοπάτια, μεταβατική
κλειστότητα, τοπολογική ταξινόμηση, επικαλυπτικά δένδρα, ροές, ταιριάσματα.
Aλγεβρικοί αλγόριθμοι: πίνακες, πολυώνυμα και ταχύς
μετασχηματισμός Fοurier.
Αλγόριθμοι θεωρίας αριθμών.
Αλγόριθμοι ταιριάσματος προτύπων.
Κλάσεις πολυπλοκότητας και ΝΡ-πλήρη προβλήματα.
Αλγόριθμοι για ΝP-πλήρη προβλήματα: προσεγγιστικοί αλγόριθμοι,
οπισθοδρόμηση, διακλάδωση-και-φράγμα, τοπική αναζήτηση. Εισαγωγή στους άμεσους
(on-line) αλγόριθμους.
Γ. Φ. Γεωργακόπουλος, "Δομές Δεδομένων:
Έννοιες Τεχνικές και Αλγόριθμοι", Πανεπιστημιακές Εκδόσεις Κρήτης, 2002.
Τ. Η. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, "Introduction
to Algorithms" (Second Edition), MIT Press and McGraw-Hill, 2001.
A. V. Aho, J. E. Hopcroft and J. D. Ullman, "Design and Analysis of
Computer Algorithms", Addison-Wesley, 1974.
C. H. Papadimitriou and K. Steiglitz, "Combinatorial Optimization",
Dover, 1998.
C. H. Papadimitriou, "Computational Complexity", Addison-Wesley,
1994.
Σύνολα, σχέσεις και συναρτήσεις. Γραφήματα και δένδρα. Συνδυαστική: μεταθέσεις, διατάξεις και συνδυασμοί. Βασικές έννοιες και εργαλεία θεωρίας πιθανοτήτων. Επαγωγή, αναδρομή και αναδρομικές σχέσεις. Πολυπλοκότητα αλγορίθμων και ασυμπτωτικοί συμβολισμοί (Ο, Ω, Θ, ο, ω, ?). Πίνακες και γραμμικές δομές δεδομένων (λίστες, στοίβες, ουρές). Δυαδικά δένδρα αναζήτησης, ισοζυγισμένα δένδρα, κατακερματισμός, σωροί. Αναζήτηση, ταξινόμηση και στατιστικές τάξεως. Βασικοί αλγόριθμοι γραφημάτων. Τεχνικές σχεδίασης αλγορίθμων και βασικά παραδείγματα (άπληστοι αλγόριθμοι, διαίρει και βασίλευε, δυναμικός προγραμματισμός). NP-πλήρη προβλήματα.
