Αλγόριθμοι και Πολυπλοκότητα

Εισαγωγή. Δομές δεδομένων και αλγόριθμοι. Ασυμπτωτική ανάλυση. Γραφήματα. Βασι- κές έννοιες. Αναζήτηση κατά «βάθος» και κατά «πλάτος». Τοπολογική διάταξη. Η μέθοδος Διαίρει-και-Βασίλευε. Δυαδική αναζήτηση. Πολλαπλασιασμός πινάκων. Η μέθοδος της Απληστίας. Το πρόβλημα επιλογής δραστηριοτήτων. Κώδικες Huffman. Ελάχιστα μονοπάτια από κοινή αφετηρία (αλγόριθμος Dijkstra). Ελάχιστα διασυνδετικά δένδρα (Αλγόριθμος Prim). Δυναμικός Προγραμματισμός. Πολλαπλασιασμός αλυσίδας. Μεγίστη κοινή υπο-ακολουθία. Ελάχιστα μονοπάτια για κάθε ζεύγος κόμβων. Κάτω φράγματα. Φράγματα εισόδου-εξόδου. Φράγματα «αντιπάλου» (adversary). Ταξινόμηση, Κώδικες Huffman. Προβλήματα γραφημάτων. Έλεγχος ακυκλικότητας γραφήματος. Ισχυρά συνδεδεμένα συστατικά. Ελάχιστα διαδυνδετικά δένδρα: ο αλγόριθμος του Kruskal. Ελάχιστα μονοπάτια από κοινή αφετηρία: ο αλγόριθμος των Bellman-Ford. Μέγιστη ροή: ο αλγόριθμος των Ford-Fulkerson και ο αλγόριθμος των Edmonds-Karp. NP και υπολογιστική δυσεπιλυσιμότητα. Αναγωγές πολυωνυμικού χρόνου. Η κλάση NP. NP-πλήρη προβλήματα.