Παρουσίαση/Προβολή
Ειδικά Θέματα Αλγορίθμων 2026-2027
(SPCS309) - Χρήστος Ζαρολιάγκης & Σπύρος Κοντογιάννης
Περιγραφή Μαθήματος
Διατμηματικό Μεταπτυχιακό Πρόγραμμα ΣΜΗΝ (SPCS)
Στόχος μαθήματος: εμβάθυνση σε κλασικές και προηγμένες αλγοριθμικές τεχνικές καθώς και σε τεχνικές συνδυαστικής βελτιστοποίησης.
Περιεχόμενο μαθήματος:
1. Βασικά Στοιχεία Βελτιστοποίησης Δικτύων
Βασικά μοντέλα προβλημάτων βελτιστοποίησης δικτύων. Αναπαράσταση προβλημάτων βελτιστοποίησης δικτύων και η σχέση τους με την αλγοριθμική αποδοτικότητα και χρονική πολυπλοκότητα.
2. Προηγμένες Αλγοριθμικές Τεχνικές Επίλυσης Θεμελιωδών Προβλημάτων Βελτιστοποίησης Δικτύων
Συντομότερες διαδρομές: Χαρακτηριστικά και ιδιότητες. Θεωρήματα εύρεσης και επαλήθευσης βέλτιστης λύσης. Αλγόριθμοι Dijkstra, Bellman-Ford-Moore, Dial, Radix-Heap, και άλλες αποδοτικές υλοποιήσεις με χρήση ουρών προτεραιότητας. Μέθοδοι ανίχνευσης αρνητικών κύκλων.
Μέγιστη ροή: Χαρακτηριστικά και ιδιότητες. Θεωρήματα εύρεσης και επαλήθευσης βέλτιστης λύσης. Αλγόριθμοι διαδρομής επαύξησης, συντομότερης διαδρομής επαύξησης, προροής-προώθησης.
Μέγιστη ροή ελάχιστου κόστους: Χαρακτηριστικά και ιδιότητες. Θεωρήματα εύρεσης και επαλήθευσης βέλτιστης λύσης. Αλγόριθμοι απαλοιφής κύκλων, διαδοχικής συντομότερης διαδρομής.
3. Γενικευμένες Τεχνικές Επίλυσης Προβλημάτων Βελτιστοποίησης Δικτύων
Εισαγωγή στις γενικευμένες τεχνικές βελτιστοποίησης δικτύων. Τοπικά και ολικά βέλτιστα σημεία. Κυρτός προγραμματισμός. Γραμμικός προγραμματισμός. Βασικές εφικτές λύσεις. Δικτυακή μέθοδος Simplex. Δυϊσμός. Η μέθοδος του ελλειψοειδούς. Μέθοδοι εσωτερικού σημείου. Ακέραιος προγραμματισμός.
Ημερομηνία δημιουργίας
Τετάρτη 23 Σεπτεμβρίου 2026
-
Περίγραμμα
Μαθησιακοί στόχοι
Με την ολοκλήρωση της διδασκαλίας του μαθήματος οι φοιτητές θα είναι ικανοί να:
- Να κατανοούν θεμελιώδη ζητήματα βελτιστοποίησης δικτύων.
- Να εφαρμόζουν κλασικές και προηγμένες αλγοριθμικές τεχνικές για την αποδοτική επίλυση θεμελιωδών προβλημάτων βελτιστοποίησης δικτύων.
- Να εφαρμόζουν γενικευμένες τεχνικές (γραμμικός προγραμματισμός) για την επίλυση θεμελιωδών προβλημάτων βελτιστοποίησης δικτύων.
Με την ολοκλήρωση της διδασκαλίας του μαθήματος οι φοιτητές θα έχουν αναπτύξει τις ακόλουθες δεξιότητες:
- Να μοντελοποιούν αποδοτικά προβλήματα βελτιστοποίησης δικτύων.
- Να έχουν εξοικειωθεί στη χρήση κλασικών και προηγμένων συνδυαστικών τεχνικών για το σχεδιασμό αλγορίθμων σε θεμελιώδη και σύνθετα ζητήματα βελτιστοποίησης δικτύων.
- Να έχουν εξοικειωθεί στη χρήση γενικευμένων τεχνικών (γραμμικός προγραμματισμός) για την επίλυση θεμελιωδών και σύνθετων προβλημάτων βελτιστοποίησης δικτύων.
Βιβλιογραφία
Βασικό Σύγγραμμα
- R. Ahuja, T. Magnanti, J. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, 1993.
Άλλα Συγγράμματα
- [KT08] J. Kleinberg and E. Tardos, Σχεδιασμός Αλγορίθμων, ελληνική έκδοση, Εκδόσεις Κλειδάριθμος, 2008. Παροράματα .
- I. Κολέτσος και Δ. Στογιάννης, Εισαγωγή στην Επιχειρησιακή Έρευνα, 4η έκδοση, 2021.
- [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.
- [CLRS16] T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Εισαγωγή στους Αλγορίθμους, ελληνική 2η έκδοση, Πανεπιστημιακές Εκδόσεις Κρήτης, 2016.
Μέθοδοι αξιολόγησης
Η αξιολόγηση του μαθήματος θα διεξαχθεί με τελική εξέταση στο τέλος του εξαμήνου (με ανοικτές σημειώσεις). Επιπλέον, θα δοθoύν 2-3 ομάδες ασκήσεων, οι οποίες είναι υποχρεωτικές.
Ο τελικός βαθμός του μαθήματος προκύπτει από τον παρακάτω τύπο:
Τελικός Βαθμός = 0.3 x (Βαθμός Ασκήσεων) + 0.7 x (Βαθμός Εξέτασης)