Περιγραφή μαθήματος

Κωδικός μαθήματος: ΜΥΕ055

Εβδομαδιαίες ώρες διδασκαλίας: 3,0,2

Εξάμηνο σπουδών: >=6ο

Διδακτικές Μονάδες: 4

Μονάδες ECTS: 5

Ιστοσελίδα Μαθήματος:

Προσφερόμενο: Ακαδημαϊκό έτος 2024-2025

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

Περιεχόμενο:

Προβλήματα βελτιστοποίησης. Δυσεπίλυτα υπολογιστικά προβλήματα και προσεγγιστικοί αλγόριθμοι πολυωνυμικού χρόνου. Λόγος προσέγγισης και ασυμπτωτικός λόγος προσέγγισης. Προσεγγιστικά συστήματα πολυωνυμικού χρόνου. Τεχνικές σχεδίασης προσεγγιστικών αλγορίθμων: απληστία, τοπική αναζήτηση, στρωματοποίηση. Προσεγγιστικοί αλγόριθμοι για τα προβλήματα VERTEX COVER, SET COVER, STEINER TREE, METRIC-TSP, k-CENTER, STRIP PACKING, MINIMUM MAKESPAN SCHEDULING, EDGE COLORING, MAXIMUM CUT, MAXIMUM SATISFIABILITY. Ένα προσεγγιστικό σύστημα πολυωνυμικού χρόνου για το πρόβλημα KNAPSACK.  Ένα ασυμπτωτικό προσεγγιστικό σύστημα πολυωνυμικού χρόνου για το πρόβλημα BIN PACKING. Προσεγγιστικοί αλγόριθμοι βασισμένοι στον Γραμμικό Προγραμματισμό. Αναγωγές που διατηρούν τον λόγο προσέγγισης. Μη προσεγγισιμότητα.

Παρατηρήσεις: