|
|
|
|
ΕΠΛ 236: Αλγόριθμοι και Πολυπλοκότητα
Περιεχόμενο Μαθήματος |
|
Ενότητα |
Θέματα |
|
1 |
Εισαγωγή: Αλγόριθμος, Ανάλυση και Πολυπλοκότητα, Τάξη Αλγορίθμου και Προβλήματος,Σχεδιασμός αλγορίθμων |
|
2 |
Αλγόριθμοι
Οπισθοδρόμησης: Τεχνική Σχεδιασμού Οπισθοδρόμησης, Πρόβλημα
του Ευσταθούς Ταιριάσματος, Αλγόριθμος των Gale-Shapley |
|
3 |
Αλγόριθμοι τύπου Διαίρει και Βασίλευε. Μέρος Α’: Τεχνική Σχεδιασμού
Διαίρει-Βασίλευε, Αλγόριθμος του Strassen για Πολλαπλασιασμό
Πινάκων, Αλγόριθμος για Πολλαπλασιασμό Ακεραίων, Αλγόριθμος Επιλογής Μέρος Β’: Γεωμετρικοί Αλγόριθμοι
– Αλγόριθμος Υπολογισμού Κυρτού Περιβλήματος και Αλγόριθμος Εύρεσης Πλησιέστερου
Ζεύγους Σημείων Μέρος Γ’: Ταχύς Μετασχηματισμός Fourier – Συνέλιξη Διανυσμάτων και Πολλαπλασιασμός Πολυωνύμων,
Μιγαδικές Ρίζες της Μονάδας, Αλγόριθμος Υπολογισμού Συνέλιξης με τη Χρήση
Ταχύ Μετασχηματισμού Fourier |
|
4 |
Άπληστοι Αλγόριθμοι: Τεχνική Σχεδιασμού
Απληστίας, Τεχνικές Απόδειξης Βέλτιστης Λύσης, Αλγόριθμοι για
Χρονοπρογραμματισμό Διαστημάτων (με ένα πόρο, με πολλούς πόρους, με
προθεσμίες) |
|
5 |
Δυναμικός
Προγραμματισμός: Τεχνική Σχεδιασμού Δυναμικού Προγραμματισμού,
Αλγόριθμος για Πολλαπλασιασμό Αλυσίδας Πινάκων, Αλγόριθμος Σύγκρισης DNA
δύο Οργανισμών |
|
6 |
Δίκτυα
Ροής: Πρόβλημα Μέγιστης Ροής, Αλγόριθμος Ford-Fulkerson και FF κατα Edmonds-Karp,
Θεώρημα Μέγιστης Ροής και Ελάχιστης Αποκοπής Εφαρμογή: Διμερή
Ταιριάσματα |
|
7 |
Παραμετρικοί
Αλγόριθμοι: Παραμετρικό Πρόβλημα, Παραμετρικός Αλγόριθμος,
Πρόβλημα Κάλυψης Κορυφών, Πρόβλημα Ανεξαρτήτου Συνόλου σε Δένδρα |
|
8 |
Τυχαιοποιημένοι
Αλγόριθμοι: Τυχαιοποίηση,
Κατηγορίες Τυχαιοποιημένων Αλγορίθμων, Βασικές Τεχνικές Σχεδίασης, Πρόβλημα
Επαλήθευσης Γινομένου Πινάκων, Πρόβλημα Ελέγχου Πολυωνυμικών
Ταυτοτήτων, Πρόβλημα Καθολικής Ελάχιστης Αποκοπής |