Algorithms in Geomatics

General

• Code: 507
• Semester: 5th
• Study Level: Undergraduate
• Course type: Specialised General Knowledge
• Teaching and exams language: Greek
• Teaching Methods (Hours/Week): Lectures (2) / Laboratorial exercises (1)
• ECTS Units: 4
• Course homepage: https://elearning.cm.ihu.gr/course/view.php?id=42

Course Contents

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

• Αλγόριθμοι και τύποι γεωγραφικών Δεδομένων: αλγόριθμοι, γεωγραφική πληροφορία και Συστήματα Γεωγραφικών Πληροφοριών, διανυσματικά (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

Educational Goals

This course aims to introduce the students to the principles of algorithms and their applications in spatial problems, with the use of vector and raster data. The students will learn the basics of algorithms and their application in common geo-spatial problems (e.g. routing, network connectivity, optimal mounting position) and the classification of spatial data.
Upon completion, the students will be able to:
• Recognize the fundamental characteristics of algorithms, their applications in problem solving and define the cost of their use (memory space and time)
• Identify the NP-problems in Geomatics
• Comprehend the differences between approachable, heuristic and exact algorithms
• Comprehend and describe step by step the algorithms
• Combine different algorithms to solve a problem
• Insert spatial data and parameters in position based services (geo-services), using algorithms and analyze the output

General Skills

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

Teaching Methods

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

Use of ICT means

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

Teaching Organization

Students Evaluation

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

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

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

Recommended Bibliography

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