Συνδυαστική βελτιστοποίηση
Πανεπιστήμιο Μακεδονίας
Τμήμα Εφαρμοσμένης Πληροφορικής
Έτος: 2014-2015
Διδάσκων: Σιφαλέρας Άγγελος
Περιγραφή Μαθήματος
Το μάθημα διδάσκεται στο 7ο εξάμηνο σπουδών του τμήματος Εφαρμοσμένης Πληροφορικής και στοχεύει σε μια εισαγωγή στα μοντέλα βελτιστοποίησης δικτύων και στον ακέραιο προγραμματισμό. Δίνεται έμφαση στην αλγοριθμική επίλυση προβλημάτων βελτιστοποίησης δικτύων αλλά και στη μοντελοποίηση με χρήση ακεραίου προγραμματισμού.
Video-Διαλέξεις
Διάλεξη 01: Εισαγωγή στη συνδυαστική βελτιστοποίηση (2014-10-02)
Διάλεξη 02: Εφαρμογές ακεραίου προγραμματισμού (2014-10-16)
Παραδείγματα μαθηματικών μοντέλων ακεραίου προγραμματισμού.
Διάλεξη 03: Μεθοδολογίες επίλυσης προβλημάτων ακεραίου προγραμματισμού (2014-10-23)
Παράδειγμα προβλήματος κάλυψης ενός συνόλου (set covering problem). Εισαγωγή στον αλγόριθμο κλάδου και φραγής (branch & bound algorithm), Περιγραφή μεθόδων περιορισμού του εφικτού χώρου (cutting-plane method) και συλλογών μετρό-προβλημάτων (benchmarks).
Διάλεξη 04: Υπολογιστική πολυπλοκότητα (2014-10-30)
Εισαγωγή στο πρόβλημα του σακιδίου (knapsack problem). Υπολογιστική πολυπλοκότητα και NP-πληρότητα (NP-completeness).
Διάλεξη 05: Εισαγωγή στη βελτιστοποίηση δικτύων (2014-11-06)
Εισαγωγή στη βελτιστοποίηση δικτύων (network οptimization). Τρόποι αποθήκευσης γράφων και δικτύων.
Διάλεξη 06: Το πρόβλημα ελαχίστων δρόμων (2014-11-13)
Μοντελοποίηση του προβλήματος ροής ελαχίστου κόστους, των προβλημάτων ελαχίστων δρόμων και εφαρμογές τους. Περιγραφή του αλγορίθμου Dijkstra.
Διάλεξη 07: Το πρόβλημα ελαχίστων δένδρων καλυμμάτων (2014-11-20)
Μοντελοποίηση του προβλήματος ελαχίστων δένδρων καλυμμάτων (minimum spanning tree problem) και εφαρμογές του. Εισαγωγή σε άπληστους αλγορίθμους – αλγόριθμος του Kruskal, αλγόριθμος αντίστροφης διαγραφής (reverse-delete algorithm), αλγόριθμος του Prim.
Διάλεξη 08: Το πρόβλημα μεγίστης ροής (2014-11-27)
Μοντελοποίηση του προβλήματος μεγίστης ροής (maximum flow problem) και συνθήκες βελτιστότητας. Περιγραφή του αλγορίθμου των αυξανόντων δρόμων (augmenting – path).
Διάλεξη 09: Δυναμικός προγραμματισμός (2014-12-04)
Εισαγωγή στο δυναμικό προγραμματισμό και εφαρμογές σε προβλήματα διακριτής βελτιστοποίησης.
Διάλεξη 10: Το πρόβλημα του πλανόδιου πωλητή (2014-12-11)
Περιγραφή του προβλήματος του πλανόδιου πωλητή (traveling salesman problem) και μεθοδολογίες επίλυσης του. Εισαγωγή σε άλλα προβλήματα όπως το πρόβλημα της εύρεσης ενός Hamiltonian κύκλου και το πρόβλημα του υπολογισμού ενός δένδρου Steiner.
Διάλεξη 11: Το πρόβλημα αντιστοίχισης (2014-12-18)
Μοντελοποίηση του προβλήματος αντιστοίχισης (assignment problem) και η Ουγγρική μέθοδος επίλυσης του.
Διάλεξη 12: Επαναληπτικά παραδείγματα και ερωτήσεις (2015-01-15)
Επαναληπτικά παραδείγματα και ερωτήσεις. Επίλυση προβλήματος Sudoku με χρήση ακεραίου προγραμματισμού.