Παρουσίαση/Προβολή
Αλγόριθμοι & Βελτιστοποίηση 2025-2026
(NE5057 ) - Χρήστος Ζαρολιάγκης & Σπύρος Κοντογιάννης
Περιγραφή Μαθήματος
Στόχος μαθήματος: η εμβάθυνση των φοιτητών σε κλασικές και προηγμένες αλγοριθμικές τεχνικές καθώς και σε τεχνικές συνδυαστικής βελτιστοποίησης.
Περιεχόμενο μαθήματος:
1. Βασικά Στοιχεία Συνδυαστικής Βελτιστοποίησης και Βελτιστοποίησης Δικτύων
Βασικά μοντέλα προβλημάτων βελτιστοποίησης. Αναπαράσταση προβλημάτων βελτιστοποίησης και η σχέση τους με την αλγοριθμική αποδοτικότητα και χρονική πολυπλοκότητα.
2. Προηγμένες Αλγοριθμικές Τεχνικές Επίλυσης Θεμελιωδών Προβλημάτων Βελτιστοποίησης
Συντομότερες διαδρομές: Χαρακτηριστικά και ιδιότητες. Θεωρήματα εύρεσης και επαλήθευσης βέλτιστης λύσης. Αλγόριθμοι Dijkstra, Bellman-Ford-Moore, Dial, Radix-Heap, και άλλες αποδοτικές υλοποιήσεις με χρήση ουρών προτεραιότητας. Μέθοδοι ανίχνευσης αρνητικών κύκλων.
Μέγιστη ροή: Χαρακτηριστικά και ιδιότητες. Θεωρήματα εύρεσης και επαλήθευσης βέλτιστης λύσης. Αλγόριθμοι διαδρομής επαύξησης, συντομότερης διαδρομής επαύξησης, προροής-προώθησης.
Μέγιστη ροή ελάχιστου κόστους: Χαρακτηριστικά και ιδιότητες. Θεωρήματα εύρεσης και επαλήθευσης βέλτιστης λύσης. Αλγόριθμοι απαλοιφής κύκλων, διαδοχικής συντομότερης διαδρομής.
3. Γενικευμένες Τεχνικές Επίλυσης Προβλημάτων Βελτιστοποίησης
Εισαγωγή στις γενικευμένες τεχνικές βελτιστοποίησης. Τοπικά και ολικά βέλτιστα σημεία. Κυρτός προγραμματισμός. Γραμμικός προγραμματισμός. Βάσεις και μέθοδος Simplex. Δυϊσμός. Η μέθοδος του ελλειψοειδούς. Μέθοδοι εσωτερικού σημείου. Ακέραιος προγραμματισμός.
Ημερομηνία δημιουργίας
Παρασκευή, 26 Σεπτεμβρίου 2025
-
Βιβλιογραφία
Βασικά Συγγράμματα
Πρώτο Εναλλακτικό Σύγγραμμα:
- J. Kleinberg and E. Tardos, Σχεδιασμός Αλγορίθμων, ελληνική έκδοση, Εκδόσεις Κλειδάριθμος, 2008.
Δεύτερο Εναλλακτικό Σύγγραμμα:
- T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Εισαγωγή στους Αλγορίθμους, ελληνική 2η έκδοση, Πανεπιστημιακές Εκδόσεις Κρήτης, 2016.
Τρίτο Εναλλακτικό Σύγγραμμα:
- I. Κολέτσος και Δ. Στογιάννης, Εισαγωγή στην Επιχειρησιακή Έρευνα, 4η έκδοση, 2021.
Άλλα Συγγράμματα
- [AMO93] R. Ahuja, T. Magnanti, J. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, 1993.
- [PS82] C. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, 1982.
- [BG01] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer-Verlag, 2001.
- [CCPS98] W. Cook, W. Cunningham, W. Pulleyblank, and A. Schrijver, Combinatorial Optimization, John Wiley & Sons, 1998.
Μέθοδοι αξιολόγησης
Η αξιολόγηση του μαθήματος θα διεξαχθεί με τελική εξέταση στο τέλος του εξαμήνου (με ανοικτές σημειώσεις). Επιπλέον, θα δοθoύν 2-3 ομάδες ασκήσεων, οι οποίες είναι προαιρετικές αλλά ενθαρρύνονται όλοι να τις εκπονήσουν.
Ο τελικός βαθμός του μαθήματος προκύπτει από τον παρακάτω τύπο:
Τελικός Βαθμός = max{(Βαθμός Εξέτασης), 0.3 x (Βαθμός Ασκήσεων) + 0.7 x (Βαθμός Εξέτασης)}