Anteprima

Διατμηματικό Μεταπτυχιακό Πρόγραμμα ΣΜΗΝ (SPCS)

Στόχος μαθήματος: εμβάθυνση σε κλασικές και προηγμένες αλγοριθμικές τεχνικές καθώς και σε τεχνικές συνδυαστικής βελτιστοποίησης.

Περιεχόμενο μαθήματος:

1. Βασικά Στοιχεία Βελτιστοποίησης Δικτύων

Βασικά μοντέλα προβλημάτων βελτιστοποίησης δικτύων. Αναπαράσταση προβλημάτων βελτιστοποίησης δικτύων και η σχέση τους με την αλγοριθμική αποδοτικότητα και χρονική πολυπλοκότητα.

2. Προηγμένες Αλγοριθμικές Τεχνικές Επίλυσης Θεμελιωδών Προβλημάτων Βελτιστοποίησης Δικτύων

Συντομότερες διαδρομές: Χαρακτηριστικά και ιδιότητες. Θεωρήματα εύρεσης και επαλήθευσης βέλτιστης λύσης. Αλγόριθμοι Dijkstra, Bellman-Ford-Moore, Dial, Radix-Heap, και άλλες αποδοτικές υλοποιήσεις με χρήση ουρών προτεραιότητας. Μέθοδοι ανίχνευσης αρνητικών κύκλων.

Μέγιστη ροή: Χαρακτηριστικά και ιδιότητες. Θεωρήματα εύρεσης και επαλήθευσης βέλτιστης λύσης. Αλγόριθμοι διαδρομής επαύξησης, συντομότερης διαδρομής επαύξησης, προροής-προώθησης.

Μέγιστη ροή ελάχιστου κόστους:  Χαρακτηριστικά και ιδιότητες. Θεωρήματα εύρεσης και επαλήθευσης βέλτιστης λύσης. Αλγόριθμοι απαλοιφής κύκλων, διαδοχικής συντομότερης διαδρομής.

3. Γενικευμένες Τεχνικές Επίλυσης Προβλημάτων Βελτιστοποίησης Δικτύων

Εισαγωγή στις γενικευμένες τεχνικές βελτιστοποίησης δικτύων. Τοπικά και ολικά βέλτιστα σημεία. Κυρτός προγραμματισμός. Γραμμικός προγραμματισμός. Βασικές εφικτές λύσεις. Δικτυακή μέθοδος Simplex. Δυϊσμός. Η μέθοδος του ελλειψοειδούς. Μέθοδοι εσωτερικού σημείου. Ακέραιος προγραμματισμός.