Τίτλος Μαθήματος Αλγόριθμοι και Συνδυαστική Βελτιστοποίηση
Κωδικός Μαθήματος 321-10001
Εξάμηνο 9
ECTS 5
Ώρες (Θεωρία) 3
Ώρες (Εργαστηρίο)
Διδάσκοντας Καπόρης Αλέξιος

Ύλη μαθήματος

Μαθηματική μοντελοποίηση προβλημάτων Συνδυαστικής Βελτιστοποίησης που εμφανίζονται σε πρακτικές εφαρμογές όπως της Βιολογίας, των Δικτύων (κοινωνικών, τηλεπικοινωνιακών, οδικών, Η/Υ, κ.λπ.), χρονοπρογραμματισμού διεργασιών, διαχείρισης πόρων (υπολογιστικών, κ.λπ.), τοποθέτησης εξυπηρετητών, μεταφοράς, Θεωρίας Παιγνίων, κ.λπ. Μελέτη τεχνικών επίλυσής τους, όπως: διαχώρισης και αποτίμησης (Branch and Bound), ευριστικοί αλγόριθμοι, μεταευριστικοί αλγόριθμοι, πιθανοτικές τεχνικές, πλεονεκτήματα - μειονεκτήματα. Ανάδειξη των ορίων των αλγορίθμων και επεξεργασία των πρόσφατων ερευνητικών εξελίξεων στο πεδίο. Δυναμικός Προγραμματισμός (dynamic programming) και προσεγγιστικοί αλγόριθμοι. Πολυωνυμικού χρόνου προσεγγιστικά σχήματα (PTAS, FPTAS). Μέθοδοι τοπικής αναζήτησης, PLS-completeness, δομές γειτονιών, εκθετικές γειτονιές αναζητούμενες πολυωνυμικά, προσεγγισιμότητα. Σύνδεση των μεθόδων τοπικής αναζήτησης με τη θεωρία παιγνίων και τη θεωρία τοπίων.

Επιδιωκόμενα μαθησιακά αποτελέσματα

Με την επιτυχή ολοκλήρωση του μαθήματος, ο φοιτητής/τρια θα:

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

Προαπαιτούμενα

Δεν απαιτούνται.

Εγχειρίδια του μαθήματος

Combinatorial optimization: algorithms and complexity. C. Papadimitriou, K. Steiglitz

Combinatorial Optimization
Polyhedra and Efficiency

Authors: Schrijver, Alexander

Συμπληρωματική βιβλιογραφία

Journal of combinatorial optimization

Διδακτικές και μαθησιακές μέθοδοι

 

Δραστηριότητα Φόρτος Εργασίας Εξαμήνου
Διαλέξεις 39 ώρες

 
Προσωπική μελέτη 83 ώρες
 
Τελική εξέταση 3 ώρες
Σύνολο Μαθήματος 125 ώρες (5 ECTS)

Μέθοδοι αξιολόγησης / βαθμολόγησης

Συμμετοχή στις διαλέξεις. Τελική εξέταση.

Γλώσσα διδασκαλίας

Ελληνικά (Αγγλικά αν υπάρχουν φοιτητές/φοιτήτριες ERASMUS)

Τρόπος παράδοσης μαθήματος

Φυσική Παρουσία, βιντεοδιαλέξεις διαθέσιμες online.