Αλγοριθμικές Βάσεις στη Γεωπληροφορική

Γενικά

• Κωδικός: 507
• Εξάμηνο: 5ο
• Επίπεδο Σπουδών: Προπτυχιακό
• Τύπος μαθήματος: Επιστημονικής Περιοχής
• Γλώσσα διδασκαλίας και εξετάσεων: Ελληνικά
• Μέθοδοι Διδασκαλίας (Ώρες/εβδ.): Διαλέξεις (2) / Εργαστηριακές Ασκήσεις (1)
• Μονάδες ECTS: 4
• Σελίδα μαθήματος: https://elearning.cm.ihu.gr/course/view.php?id=42

Περιεχόμενα μαθήματος

Περιεχόμενο διαλέξεων θεωρίας:

• Αλγόριθμοι και τύποι γεωγραφικών Δεδομένων: αλγόριθμοι, γεωγραφική πληροφορία και Συστήματα Γεωγραφικών Πληροφοριών, διανυσματικά (vector) και ψηφιογραφικά (raster) δεδομένα
• Αλγόριθμοι και διανυσματικά δεδομένα:
  • βασικές έννοιες και ορισμοί γράφων, μονοπατιών και κύκλων (ή κυκλωμάτων)
  • μετατροπή διανυσματικών δεδομένων σε (οδικό) δίκτυο
  • ελάχιστα μονοπάτια και αλγόριθμοι Dijkstra και Bellman-Ford
  • ελαχιστοβαρή συνδετικά δένδρα και αλγόριθμοι Prim και Kruskal
  • πρόβλημα πλανόδιου πωλητή (Travelling Salesman Problem ή TSP) και εξαντλητικός, ευριστικοί, προσεγγιστικοί και ακριβείς αλγόριθμοι επίλυσης
  • προβλήματα βέλτιστης θέσης (facility location problems) και αλγόριθμοι επίλυσης
• Αλγόριθμοι και ψηφιογραφικά δεδομένα: Σχετική και απόλυτη ταξινόμηση/κατηγοριοποίηση, αλγόριθμοι k-means και ISODATA.

Περιεχόμενα εργαστηριακών ασκήσεων:

• Μετατροπή διανυσματικών δεδομένων σε (οδικό) δίκτυο (γράφο)
• Αναπαράσταση και ιδιότητες Γράφων: Πίνακες και λίστες γειτνίασης, βαθμοί κόμβων
• Αλγόριθμοι Dijkstra και Bellman-Ford
• Αλγόριθμοι Prim και Kruskal
• TSP: Εξαντλητικός και ευριστικοί, προσεγγιστικοί αλγόριθμοι
• TSP: Ακριβής αλγόριθμος Branch and Bound με συνάρτηση κάτω φράγματος
• Αλγόριθμος k-means
• Αλγόριθμος ISODATA

Μαθησιακοί Στόχοι

Το μάθημα στοχεύει στην απόκτηση βασικών γνώσεων αλγορίθμων που εφαρμόζονται σε σύγχρονα προβλήματα Γεωπληροφορικής, με είσοδο τόσο διανυσματικά (vector) όσο και ψηφιογραφικά (raster) δεδομένα. Πιο συγκεκριμένα το μάθημα αποσκοπεί στην κατανόηση της σημασίας των αλγορίθμων και της εφαρμογής τους σε προβλήματα όπως η δρομολόγηση ή η αποδοτική διασύνδεση σημείων σε δίκτυα, η εύρεση βέλτιστης θέσης τοποθέτησης υπηρεσιών και η κατηγοριοποίηση/ταξινόμηση γεωχωρικών δεδομένων.

Με την επιτυχή ολοκλήρωση του μαθήματος ο φοιτητής / τρια θα είναι σε θέση να:
• Αναγνωρίζει τα θεμελιώδη μεγέθη των αλγορίθμων και των προβλημάτων που επιλύουν και να προσδιορίζει ποιοτικά και ποσοτικά το κόστος εφαρμογής τους σε μνήμη και χρόνο.
• Να διακρίνει τα -αλγοριθμικά- δισεπίλυτα προβλήματα Γεωπληροφορικής.
• Να κατανοεί τη διάκριση των αλγορίθμων σε προσεγγιστικούς, ευριστικούς και ακριβείς.
• Να περιγράφει λεπτομερώς τα βήματα των αλγορίθμων.
• Να συνδυάζει αλγορίθμους για την επίλυση προβλημάτων.
• Να παρέχει είσοδο (γεωχωρικά δεδομένα) και παραμέτρους σε υπηρεσίες βάσει θέσης (γεωυπηρεσίες) που υλοποιούν τους σχετικούς αλγορίθμους και να αναλύει/ερμηνεύει τα αποτελέσματα που επιστρέφονται από αυτές

Γενικές Ικανότητες

• Εργασία σε διεθνές περιβάλλον
• Εργασία σε διεπιστημονικό περιβάλλον
• Παραγωγή νέων ερευνητικών ιδεών
• Προαγωγή της ελεύθερης, δημιουργικής και επαγωγικής σκέψης

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

Πρόσωπο με πρόσωπο (Στην αίθουσα διδασκαλίας και στο εργαστήριο)

Χρήση Τεχνολογιών Πληροφορίας και Επικοινωνιών

• Ανάπτυξη αλγορίθμων σε HTML/JavaScript
• Ηλεκτρονική πλατφόρμα μάθησης
• Ηλεκτρονική αλληλογραφία

Οργάνωση Διδασκαλίας

Αξιολόγηση Φοιτητών

Γλώσσα αξιολόγησης: Ελληνική.
Δοκιμασία Πολλαπλής Επιλογής, Ερωτήσεις Σύντομης Απάντησης, Επίλυση Προβλημάτων, Εργαστηριακή Εργασία

Κριτήρια αξιολόγησης:

• Στο θεωρητικό μέρος: η επίδοση Δοκιμασίας Πολλαπλής Επιλογής
• Στο εργαστηριακό μέρος: ποσόστωση επί των επιδόσεων Επίλυσης Προβλημάτων και Εργαστηριακής Εργασίας.

Συνιστώμενη Βιβλιογραφία

1. CORMEN T.H., LEISERSON CH.E., RIVEST R.L., STEIN C., Εισαγωγή στους αλγορίθμους, Τόμος Α, Πανεπιστημιακές Εκδόσεις Κρήτης, 2006
2. LIU C.L., Στοιχεία διακριτών μαθηματικών, ΙΤΕ/Πανεπιστημιακές εκδόσεις Κρήτης, 2009