7ο Εξάμηνο - Κατεύθυνση Μαθηματικού Εφαρμογών

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

Κωδικός: 9116
Κατηγορία: Υποχρεωτικό Ροής
Κατεύθυνση: Μαθηματικού Εφαρμογών
Ροή: Ροή Μ.Π.: Μαθηματικά Πληροφορικής
Εξάμηνο: 7ο
Ώρ./εβδ.: 4

Περιγραφή Μαθήματος

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

Διδάσκοντες