Αλγοριθμική Επιχειρησιακή Έρευνα

Εξάμηνο:
7ο
Τύπος Μαθήματος:
Προαιρετικό (ΠΜ)
Κατεύθυνση:
CS (Computer Science), CΕT (Computer Engineering and Telecoms)
Κωδικός:
ΘΠ09
ECTS:
6
Διδακτικές Ώρες
Ώρες Θεωρίας:
3
Ώρες Φροντιστηρίου:
1
Ώρες Εργαστηρίου:
-
Μάθημα στις Ειδικεύσεις
Θεμελιώσεις Πληροφορικής (S1):
B Βασικό
Διαχείριση Δεδομένων και Γνώσης (S2):
B Βασικό
Λογισμικό (S3):
-
Υλικό και Αρχιτεκτονική (S4):
-
Επικοινωνίες και Δικτύωση (S5):
-
Επεξεργασία Σήματος και Πληροφορίας (S6):
B Βασικό
Σχετικά Μαθήματα
Σύντομη περιγραφή Μαθήματος

Το μάθημα καλύπτει βασικά μαθηματικά μοντέλα λήψης αποφάσεων και παρουσιάζει αλγοριθμικές τεχνικές επίλυσής τους. Εστιάζει στο γραμμικό προγραμματισμό και στον αλγόριθμο simplex, στην δυϊκή θεωρία και στα προβλήματα μεταφοράς. Στον ακέραιο προγραμματισμό περιγράφει τις τεχνικές branch and bound για προβλήματα packing, covering και σακιδίου (knapsack problem) και του γενικευμένου γραμμικού προγραμματισμού για προβλήματα τεμαχισμού (cutting stock problems). Περιγράφει τεχνικές αποτίμησης της απόδοσης των αλγορίθμων (εμπειρική αποτίμηση, λόγος προσεγγισιμότητας). Αναπτύσσει αλγόριθμους τοπικής αναζήτησης και μελετά την δομή γειτονιάς και τις μεθόδους αναζήτησης στις γειτονιές για τα προβλήματα του πλανόδιου πωλητή (γειτονιές κ-OPT), της μέγιστης τομής (max cut) και της διαμέρισης γράφων (bipartitioning).

Βιβλιογραφία
  • Γιάννης Κολέτσος- Δ. Στογιάννης, Εισαγωγή στην Επιχειρησιακή Έρευνα, 3η Έκδοση, Εκδ. Συμεών., Κωδ. 50656312, 2017 (Εύδοξος).
  • Βασίλης Κώστογλου, Επιχειρησιακή Έρευνα, 2η Έκδοση, Εκδ. Τζιόλα, Κωδ. 50655958, 2016 (Εύδοξος).
  • Σημειώσεις, Αλγοριθμική Επιχειρησιακή Έρευνα, 2016, 2η έκδοση, Β. Ζησιμόπουλος https://eclass.uoa.gr/modules/document/index.php?course=D40&openDir=/4c2b3151ye79
  • Διαφάνειεςδιαλέξεων, https://eclass.uoa.gr/modules/document/index.php?course=D40&openDir=/59cab0d9gRUH
  • F.S. HILLIER and G.J. LIEBERMAN, Introduction to Operations Research, 8th ed., McGraw-Hill, New York, 2004