Υπολογιστική Γεωμετρία (ΘΠ11 (προπτυχ.) 2021)
Αννα Καρασούλου και Γιάννης Εμίρης
Eισαγωγή στους Γεωμετρικούς Αλγόριθμους και προεκτάσεις προς τις ερευνητικά ενεργές περιοχές της Υπολογιστικής Γεωμετρίας. Η ύλη μεταβάλλεται κάθε χρόνο, σε κάποιο βαθμό, και συνδέεται με τα ερευνητικά ενδιαφέροντα του Εργαστηρίου Γεωμετρικών & Αλγεβρικών Αλγορίθμων. Το μάθημα διδάσκεται το Εαρινό εξάμηνο 2022, κάθε Δευτέρα και Παρασκευή 11-13.
ΥΛΗ:
Kυρτότητα: Κυρτό περίβλημα (convex hull) σε 2 και 3 διαστάσεις, αυξητικός αλγόριθμος, αλγόριθμος περιτύλιξης και πολυπλοκότητα ευαίσθητη εξόδου (output sensitive), μέθοδος Διαίρει και βασίλευε. Άθροισμα Minkowski πολυέδρων. Γραμμική βελτιστοποίηση (Γραμμικός προγραμματισμός)
[ Δυϊσμός, Πιθανοκρατικοί αλγόριθμοι. Εκφυλισμένα δεδομένα και διαταραχή ]
Τριγωνοποιήσεις: Διάγραμμα Voronoi και κατασκευή ως προβολή πολυέδρου, τριγωνοποίηση Delaunay και δυϊσμός με το Διάγραμμα Voronoi.
[ Αν επιτρέψει ο χρόνος: Εφαρμογές στη δομική μοριακή βιολογία και την κίνηση ρομπότ ανάμεσα σε εμπόδια. Προβλήματα ορατότητας, φύλαξη μουσείου (art gallery), τριγωνοποίηση σε 2 διαστάσεις, μέθοδος σάρωσης. Διατάξεις ευθυγράμμων τμημάτων και ευθειών στο επίπεδο.]
Γεωμετρική αναζήτηση: Δομές γεωμετρικών δεδομένων, αναζήτηση περιοχής (range search) σε 2 και περισσότερες διαστάσεις, (προσεγγιστική) εύρεση πλησιέστερου γείτονα με δενδρικές δομές, πίνακες κατακερματισμού ή τυχαιοκρατική εμβύθιση δεδομένων για μείωση διάστασης.
[ Εφαρμογές στη συσταδοποίηση (clustering) και την εξόρυξη δεδομένων. Υλοποιήσεις σε Python και CGAL/C++ ] (Πληροφορίες).
Eισαγωγή στους Γεωμετρικούς Αλγόριθμους και προεκτάσεις προς τις ερευνητικά ενεργές περιοχές της Υπολογιστικής Γεωμετρίας. Η ύλη μεταβάλλεται κάθε χρόνο, σε κάποιο βαθμό, και συνδέεται με τα ερευνητικά ενδιαφέροντα του Εργαστηρίου Γεωμετρικών & Αλγεβρικών Αλγορίθμων. Το μάθημα διδάσκεται το Εαρινό εξάμηνο 2022, κάθε Δευτέρα και Παρασκευή 11-13.
ΥΛΗ:
Kυρτότητα: Κυρτό περίβλημα (convex hull) σε 2 και 3 διαστάσεις, αυξητικός αλγόριθμος, αλγόριθμος περιτύλιξης και πολυπλοκότητα ευαίσθητη εξόδου (output sensitive), μέθοδος Διαίρει και βασίλευε. Άθροισμα Minkowski πολυέδρων. Γραμμική βελτιστοποίηση (Γραμμικός προγραμματισμός)
[ Δυϊσμός, Πιθανοκρατικοί αλγόριθμοι. Εκφυλισμένα δεδομένα και διαταραχή ]
Τριγωνοποιήσεις: Διάγραμμα Voronoi και κατασκευή ως προβολή πολυέδρου, τριγωνοποίηση Delaunay και δυϊσμός με το Διάγραμμα Voronoi.
[ Αν επιτρέψει ο χρόνος: Εφαρμογές στη δομική μοριακή βιολογία και την κίνηση ρομπότ ανάμεσα σε εμπόδια. Προβλήματα ορατότητας, φύλαξη μουσείου (art gall
Eισαγωγή στους Γεωμετρικούς Αλγόριθμους και προεκτάσεις προς τις ερευνητικά ενεργές περιοχές της Υπολογιστικής Γεωμετρίας. Η ύλη μεταβάλλεται κάθε χρόνο, σε κάποιο βαθμό, και συνδέεται με τα ερευνητικά ενδιαφέροντα του Εργαστηρίου Γεωμετρικών & Αλγεβρικών Αλγορίθμων. Το μάθημα διδάσκεται το Εαρινό εξάμηνο 2022, κάθε Δευτέρα και Παρασκευή 11-13.
ΥΛΗ:
Kυρτότητα: Κυρτό περίβλημα (convex hull) σε 2 και 3 διαστάσεις, αυξητικός αλγόριθμος, αλγόριθμος περιτύλιξης και πολυπλοκότητα ευαίσθητη εξόδου (output sensitive), μέθοδος Διαίρει και βασίλευε. Άθροισμα Minkowski πολυέδρων. Γραμμική βελτιστοποίηση (Γραμμικός προγραμματισμός)
[ Δυϊσμός, Πιθανοκρατικοί αλγόριθμοι. Εκφυλισμένα δεδομένα και διαταραχή ]
Τριγωνοποιήσεις: Διάγραμμα Voronoi και κατασκευή ως προβολή πολυέδρου, τριγωνοποίηση Delaunay και δυϊσμός με το Διάγραμμα Voronoi.
[ Αν επιτρέψει ο χρόνος: Εφαρμογές στη δομική μοριακή βιολογία και την κίνηση ρομπότ ανάμεσα σε εμπόδια. Προβλήματα ορατότητας, φύλαξη μουσείου (art gall
Πληροφορίες
Προτεινόμενα συγγράμματα
Γιάννης Εμίρης. Υπολογιστική γεωμετρία: μία σύγχρονη αλγοριθμική προσέγγιση. Κλειδάριθμος, 2008.
Mark Overmars et al. Computational geometry and Applications. Springer. Μετάφραση: Πανεπιστημιακές εκδόσεις Κρήτης, 2011.
Περαιτέρω βοηθήματα: http://cgi.di.uoa.gr/~compgeom/2012/biblio.html
Μέθοδοι αξιολόγησης 2021
Δύο εργασίες για το σπιτι, περίπου 25 και 35% αντίστοιχα για κάθε εργασία.
Απαλλακτική εργασία με παρουσίαση στην ταξη και παράδοση αναφοράς / κώδικα στο τελος της εξεταστικής (1 ή 2 άτομα)
Γιάννης Εμίρης. Υπολογιστική γεωμετρία: μία σύγχρονη αλγοριθμική προσέγγιση. Κλειδάριθμος, 2008.
Mark Overmars et al. Computational geometry and Applications. Springer. Μετάφραση: Πανεπιστημιακές εκδόσεις Κρήτης, 2011.
Περαιτέρω βοηθήματα: http://cgi.di.uoa.gr/~compgeom/2012/biblio.html
Δύο εργασίες για το σπιτι, περίπου 25 και 35% αντίστοιχα για κάθε εργασία.
Απαλλακτική εργασία με παρουσίαση στην ταξη και παράδοση αναφοράς / κώδικα στο τελος της εξεταστικής (1 ή 2 άτομα)
