Αλγόριθμοι και Συνδυαστική Βελτιστοποίηση

Επίσημο περίγραμμα μαθήματος του ΤΜΗΥΠ (Πανεπιστήμιο Πατρών), όπως δημοσιεύεται στη σελίδα του μαθήματος και στο συνημμένο αρχείο «Περίγραμμα Μαθήματος». Το κείμενο παρατίθεται αυτούσιο, χωρίς τα πρότυπα οδηγιών του εντύπου.

Στόχοι

• Με την ολοκλήρωση της διδασκαλίας του μαθήματος οι φοιτητές θα είναι ικανοί να:
• Να κατανοούν θεμελιώδη ζητήματα συνδυαστικής βελτιστοποίησης και βελτιστοποίησης δικτύων.
• Να εφαρμόζουν κλασικές και προηγμένες αλγοριθμικές τεχνικές για την αποδοτική επίλυση θεμελιωδών προβλημάτων συνδυαστικής βελτιστοποίησης και βελτιστοποίησης δικτύων.

Πάτρα, Ιούλιος 2024

• Να εφαρμόζουν γενικευμένες τεχνικές (γραμμικός προγραμματισμός) για την επίλυση θεμελιωδών προβλημάτων συνδυαστικής βελτιστοποίησης και βελτιστοποίησης δικτύων.

Με την ολοκλήρωση της διδασκαλίας του μαθήματος οι φοιτητές θα έχουν αναπτύξει τις ακόλουθες δεξιότητες:

• Να μοντελοποιούν αποδοτικά προβλήματα συνδυαστικής βελτιστοποίησης και βελτιστοποίησης δικτύων.
• Να έχουν εξοικειωθεί στη χρήση κλασικών και προηγμένων συνδυαστικών τεχνικών για το σχεδιασμό αλγορίθμων σε θεμελιώδη και σύνθετα ζητήματα συνδυαστικής βελτιστοποίησης και βελτιστοποίησης δικτύων.
• Να έχουν εξοικειωθεί στη χρήση γενικευμένων τεχνικών (γραμμικός προγραμματισμός) για την επίλυση θεμελιωδών και σύνθετων προβλημάτων συνδυαστικής βελτιστοποίησης και βελτιστοποίησης δικτύων.

Περιεχόμενο (ύλη)

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

Πάτρα, Ιούλιος 2024

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

Αξιολόγηση

Γλώσσα αξιολόγησης: Ελληνική (Αγγλικά αν χρειαστεί)

Αξιολόγηση (τα κριτήρια βρίσκονται στην ιστοσελίδα του μαθήματος): - Ασκήσεις (30% του τελικού βαθμού). - Γραπτή τελική εξέταση (70% του τελικού βαθμού).

Γραπτή τελική εξέταση: διαβαθμισμένης δυσκολίας, η οποία περιλαμβάνει ερωτήσεις σύντομης απάντησης, επίλυση προβλημάτων με εφαρμογή ή/και ανάπτυξη αλγορίθμων, αποδείξεις ορθότητας και πολυπλοκότητας αλγορίθμων, μοντελοποίηση προβλημάτων, επίλυση προβλημάτων με εφαρμογή γενικευμένων τεχνικών βελτιστοποίησης.

Σειρά πρακτικών ασκήσεων με στόχο την εξοικείωση, εξάσκηση και απόκτηση εμπειρίας:

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

Πάτρα, Ιούλιος 2024 γενικευμένων μεθόδων βελτιστοποίησης.

Βιβλιογραφία

• J. Kleinberg and E. Tardos, Σχεδιασμός Αλγορίθμων. Ελληνική έκδοση. Εκδόσεις Κλειδάριθμος, 2008. Διαθέσιμο στον Εύδοξο.
• T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Εισαγωγή στους Αλγορίθμους. Ελληνική 2η έκδοση. Πανεπιστημιακές Εκδόσεις Κρήτης, 2016. Διαθέσιμο στον Εύδοξο.
• R. Rardin, Βελτιστοποίηση στην Επιχειρησιακή Έρευνα, (2η έκδοση Αμερικανική Έκδοση), Εκδόσεις ΚΛΕΙΔΑΡΙΘΜΟΣ, 2022. Διαθέσιμο στον Εύδοξο.
• Ι. Κολέτσος και Γ. Στογιάννης, Επιχειρησιακή Έρευνα: Θεωρία, Αλγόριθμοι & Εφαρμογές. 1η έκδοση. Εκδόσεις Συμεών, 2021. Διαθέσιμο στον Εύδοξο.
• R. Ahuja, T. Magnanti, and J. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, 1993.
• C. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, 1982.
• W. Cook, W. Cunningham, W. Pulleyblank, and A. Schrijver, Combinatorial Optimization, John Wiley & Sons, 1998.
• Διδακτικές σημειώσεις και διαφάνειες που αναρτώνται στην ιστοσελίδα του μαθήματος.

-Συναφή επιστημονικά περιοδικά:

• ACM Transactions on Algorithms.
• Algorithmica, Springer.
• European Journal of Operational Research, Elsevier.
• Journal of Discrete Algorithms, Elsevier.
• Journal of the ACM.
• Journal of Optimization Theory and Applications, Springer.
• Operations Research, INFORMS.
• Operational Research, Springer.
• SIAM Journal on Optimization.
• Theoretical Computer Science, Elsevier.