Παρουσίαση/Προβολή

(ΘΠ11) -  Παρασκευή Ρούπα

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

Εισαγωγή στους Γεωμετρικούς Αλγόριθμους και προεκτάσεις προς τις ερευνητικά ενεργές περιοχές της Υπολογιστικής Γεωμετρίας.

Kυρτότητα: Κυρτό περίβλημα (convex hull) σε 2 και 3 διαστάσεις, αυξητικός αλγόριθμος, αλγόριθμος περιτύλιξης και πολυπλοκότητα ευαίσθητη εξόδου (output sensitive), μέθοδος «Διαίρει και βασίλευε». Άθροισμα Minkowski πολυέδρων. Γραμμική βελτιστοποίηση (Γραμμικός προγραμματισμός), Δυϊσμός, Πιθανοκρατικοί αλγόριθμοι. Εκφυλισμένα δεδομένα και διαταραχή.

Τριγωνοποιήσεις: Διάγραμμα Voronoi και κατασκευή ως προβολή πολυέδρου, τριγωνοποίηση Delaunay και δυϊσμός με το Διάγραμμα Voronoi, εφαρμογές στη δομική μοριακή βιολογία και την κίνηση ρομπότ ανάμεσα σε εμπόδια.

Γεωμετρική αναζήτηση: Δομές γεωμετρικών δεδομένων, αναζήτηση περιοχής (range search) σε 2 και περισσότερες διαστάσεις, (προσεγγιστική) εύρεση πλησιέστερου γείτονα με δενδρικές δομές, πίνακες κατακερματισμού ή τυχαιοκρατική εμβύθιση δεδομένων για μείωση διάστασης. Εφαρμογές στη συσταδοποίηση (clustering) και την εξόρυξη δεδομένων. Υλοποιήσεις σε Python και CGAL/C++.

 

Μέθοδοι διδασκαλίας

Το μάθημα θα γίνεται κάθε Δευτέρα και Τετάρτη 09:00-11:00.

 

Μέθοδοι αξιολόγησης

Οι φοιτητές αξιολογούνται με γραπτή εξέταση και γραπτή υπολογιστική εργασία. Συγκεκριμένα:
 - Θα δοθεί 1 υποχρεωτική υπολογιστική εργασία την οποία θα κληθείτε να παρουσιάσετε.
 - Στο τέλος του μαθήματος θα γίνει η γραπτή εξέταση του μαθήματος.

Τελικός βαθμός: 0.4 * (Εργασία) + 0.6 * (Τελική εξέταση) .

 

Προτεινόμενα συγγράμματα

• Ιωάννης Εμίρης, Υπολογιστική γεωμετρία: μία σύγχρονη αλγοριθμική προσέγγιση, Κλειδάριθμος, 2008.
• Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars, Computational geometry and Applications, Springer. Μετάφραση: Πανεπιστημιακές εκδόσεις Κρήτης, 2011.

 

Επιπλέον υλικό για το μάθημα

Μπορεί να βρεθεί και στην παλιά e-class του μαθήματος που βρίσκεται στο σύνδεσμο:

https://eclass.uoa.gr/courses/D42/

Ημερομηνία δημιουργίας

Σάββατο 19 Φεβρουαρίου 2022