Προχωρημένα Θέματα Θεωρητικής Πληροφορικής: Προσεγγιστικοί Αλγόριθμοι και Πολυπλοκότητα


Κωδικός 625
Εξάμηνο Εαρινό
Ώρες Διδασκαλίας - Ώρες Εργαστηρίου 4 - 0
Διδάσκοντες Ευστάθιος Ζάχος, Αριστείδης Παγουρτζής, Δημήτριος Φωτάκης

Περιγραφή

Ιστορική αναδρομή και αναφορά σε στοιχεία κλασικής γεωμετρίας. Βασικές έννοιες: αλγόριθμοι, δομές δεδομένων, μοντέλα υπολογισμού και πολυπλοκότητα. Αλγόριθμοι ελέγχου διαφόρων ιδιοτήτων σχημάτων (και σωμάτων π,χ, με προβολές) όπως κυρτότητα κ,α. Το πρόβλημα εύρεσης ελάχιστου περιέχοντος κυρτού συνόλου (convex hull). Προβλήματα εγγύτητας (proximity). Τομές γεωμετρικών σχημάτων και σωμάτων. Εφαρμογές αλγορίθμων στην ειδική περίπτωση των παραλληλογράμμων και εφαρμογές στη σχεδίαση VLSI. Θέματα: Προβλήματα εύρεσης θέσης σημείου. Προβλήματα καταμέτρησης σημείων κάποιας περιοχής. Βασικοί αλγόριθμοι επίλυσης του προβλήματος convex hull. Γενικεύσεις του προβλήματος convex hull και εφαρμογές. Διάφορα προβλήματα εγγύτητας (proximity), όπως εύρεση πλησιέστερου σημείου, ελάχιστο δέντρου σκελετού (minimum spanning tree), τριγωνοποίηση κ.α. Αλγόριθμοι εγγύτητας βασισμένοι σε διαγράμματα Voronoi. Τομές διαφόρων γεωμετρικών σχημάτων και σωμάτων.