Θεωρητική Πληροφορική II: Υπολογιστική Γεωμετρία (ΣΗΜΜΥ)
Προσεγγιστικοί Αλγόριθμοι και Υπολογιστική Γεωμετρία (ΜΠΛΑ)
εαρινό εξάμηνο 2004-2005
Γενικά
Διδάσκων
- Στάθης Ζάχος, Καθηγητής ()
Διαλέξεις
- Πέμπτη 5-9 μμ
- Αίθουσα: 1.1.29, Κτίριο Ηλεκτρολόγων, Πολυτεχνειούπολη Ζωγράφου
- Έναρξη: Πέμπτη 24/2/2005
Προαπαιτούμενα
Αλγόριθμοι και Πολυπλοκότητα (προπτυχιακό ή μεταπτυχιακό)
Περιεχόμενο μαθήματος
- Βασικές έννοιες: αλγόριθμοι, δομές δεδομένων, μοντέλα υπολογισμού και πολυπλοκότητα.
- Σχεδιασμός προσεγγιστικών αλγορίθμων πολυωνυμικού χρόνου για NP-δύσκολα προβλήματα βελτιστοποίησης. Τα αντίστοιχα προβλήματα απόφασης είναι συνήθως NP-πλήρη. Παρότι όλα αυτά τα NP-πλήρη προβλήματα είναι ισοδύναμα, ως προς την επιλυσιμότητά τους σε πολυωνυμικό χρόνο, ως προς την πολυωνυμικού χρόνου προσεγγισιμότητα εμφανίζουν ένα πλήθος διαφορετικών περιπτώσεων (καθόλου, πολυωνυμική, λογαριθμική, σταθερή κ.α.).
- Στρατηγικές για επίλυση γεωμετρικών προβλημάτων (divide and conquer, plane sweep, greedy). Κυρτότητα (π.χ. εύρεση ελάχιστου περιέχοντος κυρτού συνόλου (convex hull)). Γεωμετρικό πρόβλημα πλανόδιου πωλητή. Δέντρα Steiner. Τριγωνοποίηση ελαχίστου βάρους.
Βιβλιογραφία
- F. P. Preparata, M. I. Shamos. Computational Geometry. Springer-Verlag, 1985.
- V. V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001.
- D. S. Hochbaum, ed. Approximation Algorithms for NP-hard problems. PWS Publishing Company, 1997.
- J. Boissonat, M. Yvinec. Algorithmic Geometry. Cambridge University Press, 1998.
- G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi. Complexity and Approximation. Combinatorial optimization problems and their approximability properties. Springer Verlag, ISBN 3-540-65431-3, 1999.
Πληροφορίες
Στάθης Ζάχος, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Ε.Μ.Π., γραφείο 11.15, τηλ. 772 1644, ή 46, email: