Spyros Kontogiannis
Associate Professor
Computer Science & Engineering Department
University of Ioannina
Συστατικές Επιστολές
Όσοι επιθυμούν να λάβουν συστατική επιστολή, θα πρέπει να κάνουν τα εξής:
1. Φροντίστε να ζητήσετε έγκαιρα τη συστατική σας.
2. Στείλτε το αίτημά σας ηλεκτρονικά, με την ακόλουθη συνοδευτική πληροφορία:
Διπλωματικές Εργασίες
Όσοι επιθυμούν να εκπονήσουν πτυχιακή εργασία ή διπλωματική εργασία ειδίκευσης υπό την επίβλεψη του κ. Κοντογιάννη, θα πρέπει να στείλουν τις παρακάτω πληροφορίες με ένα email.
Υποψήφια Θέματα Διπλωματικών Εργασιών (2018-19) [*]
Τ Ι Τ Λ Ο Ι Π Ρ Ο Τ Ε Ι Ν Ο Μ Ε Ν Ω Ν Θ Ε Μ Α Τ Ω Ν
(A) Multicriteria-based Personalized Renewable Mobility in Smart Cities.
(B) Visualisation of Optimal Routes in Smartphones.(C) Supply/Demand Management in Energy Networks.
(D) The effect of Competition in Social Networks.
Λ Ε Π Τ Ο Μ Ε Ρ Ε Ι Σ Π Ε Ρ Ι Γ Ρ Α Φ Ε Σ Π Ρ Ο Τ Ε Ι Ν Ο Μ Ε Ν Ω Ν Θ Ε Μ Α Τ Ω Ν
Α. Πολυκριτηριακή Κινητικότητα σε Έξυπνες Πόλεις
Τα τελευταία χρόνια δίνεται συνεχώς όλο και μεγαλύτερη έμφαση στις ολοκληρωμένες υπηρεσίες ανανεωνόμενης κινητικότητας (renewable mobility) μέσα σε έξυπνες πόλεις. Οι υπηρεσίες αυτές συνδυάζουν προεπεξεργασμένα δεδομένα κίνησης πραγματικού χρόνου που συλλέγονται χρησιμοποιώντας τη λεγόμενη τεχνική του πληθοπορισμού (crowd-sourcing), για την αξιολόγηση συνιστώμενων διαδρομών.
Στόχος είναι η δημιουργία μιας γνωσιακής βάσης δεδομένων κίνησης που θα επιτρέπει τη γρήγορη εύρεση βέλτιστων διαδρομών, θα προσαρμόζεται στις πραγματικές συνθήκες κίνησης και θα παρέχει ενεργειακά και περιβαλλοντικά αποδοτικές προσωποπαγείς υπηρεσίες ανανεωνόμενης κινητικότητας στους πολίτες.
Οι προκλήσεις στο σχεδιασμό ενός τέτοιου συστήματος είναι τεχνολογικές και αλγοριθμικές. Μια από τις αλγοριθμικές προκλήσεις αφορά στην ανάπτυξη υπηρεσιών για την κατ' απαίτηση δημιουργία μιας πολυκριτηριακής αλυσίδας κινητικότητας (multi-criteria mobility chain on demand) σε αστικά δίκτυα συγκοινωνιών. Σε μια τέτοια υπηρεσία ο χρήστης λαμβάνει συνιστώμενες διαδρομές σύμφωνα με ένα κριτήριο που θέτει ο ίδιος και που κατά τη γνώμη του είναι το πιο σημαντικό (π.χ. συντομότερος χρόνος ταξιδιού, συντομότερη άφιξη στον προορισμό, ελάχιστη κατανάλωση καυσίμου, κ.λπ.), υπό τον περιορισμό ότι τα υπόλοιπα κριτήρια δεν ξεπερνούν κάποιο όριο που θέτει ο ίδιος ο χρήστης. Για παράδειγμα, ένας χρήστης μπορεί να θέλει να φτάσει όσο το δυνατόν νωρίτερα στον προορισμό του, αλλά και να μην περπατήσει περισσότερο από μια συγκεκριμένη απόσταση, ή να επιθυμεί περιορισμό στη συνολική κατανάλωση καυσίμου, κ.λπ. Μετά το τέλος του ταξιδιού, ο χρήστης καλείται να αξιολογήσει την προταθείσα διαδρομή που τελικά χρησιμοποίησε.
Στο πλαίσιο της παρούσας διπλωματικής ζητούνται:
(Α.1) Κριτική επισκόπηση αλγοριθμικών μεθόδων εύρεσης πολυκριτηριακών διαδρομών σε αστικά κυκλοφοριακά δίκτυα.
(Α.2) Σχεδιασμός και ανάπτυξη μιας καινοτόμου μεθόδου εύρεσης πολυκριτηριακών διαδρομών σε αστικά κυκλοφοριακά δίκτυα.
(Α.3) Υλοποίηση της νέας μεθόδου και η εκτενής πειραματική της αξιολόγηση σε συνθετικά και πραγματικά δεδομένα κίνησης.
Ενδεικτική Βιβλιογραφία
[1] H. Bast, D. Delling, A. Goldberg, M. Mueller-Hannemann, T. Pajor, P. Sanders, D. Wagner, and R. Werneck. Route planning in transportation networks. Technical Report MSR-TR-2014-4, Microsoft Research, 2014.
[2] Andrea Raith, Matthias Ehrgott: A comparison of solution strategies for biobjective shortest path problems. Computers & Operations Research, 2009.
[3] Antonio Sedeño-Noda, Andrea Raith: A Dijkstra-like method computing all extreme supported non-dominated solutions of the biobjective shortest path problem. Computers & Operations Research, 2014.
[4] C. Daskalakis, I. Diakonikolas, M. Yannakakis How Good is the Chord Algorithm? In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010). Extended version in ArXiv (September 2013).
Β. Οπτικοποίηση Βέλτιστων Διαδρομών σε Έξυπνες Συσκευές (Smartphones)
Η σύγχρονη πλοήγηση αυτοκινήτων διαφέρει κατά πολύ από εκείνη των παλαιότερων χρόνων όπου ο κύριος τρόπος πλοήγησης ήταν οι παραδοσιακοί έντυποι χάρτες. Η σύγχρονη τεχνολογία παρέχει, εδώ και μερικά χρόνια, εφαρμογές σε έξυπνες συσκευές (smartphones) οι οποίες χρησιμοποιούν ψηφιακούς χάρτες για απεικόνιση της βέλτιστης διαδρομής που επιθυμεί ο χρήστης. Αυτό γίνεται με ένα πρόγραμμα οπτικοποίησης που οπτικοποιεί το αποτέλεσμα της εκτέλεσης ενός αλγόριθμου βέλτιστων διαδρομών πάνω σε μια αναπαράσταση ενός χάρτη ως γράφημα και το παρουσιάζει σε μια φιλική προς τον χρήστη μορφή στην (μικρή) οθόνη της συσκευής. Ωστόσο, λόγω του μεγέθους των δικτύων, που συνήθως είναι της τάξης των δεκάδων εκατομμυρίων κορυφών και ακμών, η άμεση οπτικοποίησή τους δεν είναι εύκολη. Πρέπει να προηγηθεί ένα βήμα επεξεργασίας, που να λαμβάνει υπόψιν το εύρος του δικτύου που πρέπει να οπτικοποιηθεί, καθώς και την κλίμακα της οπτικοποίησης και να παρουσιάσει τα αντίστοιχα δεδομένα στον χρήστη.
Στο πλαίσιο της διπλωματικής αυτής ζητούνται:
(Β.1) Η δημιουργία μιας εφαρμογής οπτικοποίησης γραφημάτων και αλγορίθμων σε OpenGL, με χρηση δεδομένων OSM και πρωτύπου KML, η οποία θα τρέχει σε έξυπνες συσκευές (smartphones.
(Β.2) H σχεδίαση ενός πρωτοκόλου επικοινωνίας της εφαρμογής με άλλες εφαρμογές για την οπτικοποίηση των αποτελεσμάτων τους σε πραγματικό χρόνο.
(Β.3) Η γραφική αξιολόγηση της εφαρμογής με υπάρχοντες αλγόριθμους εύρεσης βέλτιστων διαδρομών.
Ενδεικτική Βιβλιογραφία:
[1] http://en.wikipedia.org/wiki/OpenGL
Γ. Διαχείριση Ζήτησης Ηλεκτρικής Ενέργειας
Η διαχείριση της ζήτησης της ηλεκτρικής ενέργειας αφορά μεθόδους (προγράμματα) που υλοποιούνται από τις εταιρείες παροχής ηλεκτρικής ενέργειας προκειμένου να ελέγξουν την κατανάλωση ενέργειας από τους καταναλωτές. Ο στόχος είναι τα προγράμματα αυτά να χρησιμοποιούν αποδοτικότερα τη διαθέσιμη ενέργεια του δικτύου και έτσι να μην απαιτείται η εγκατάσταση νέων συστημάτων παραγωγής και μεταφοράς της ηλεκτρικής ενέργειας. Η διαχείριση της ζήτησης περιλαμβάνει ένα ευρύ φάσμα προβλημάτων, μεταξύ άλλων και τη διαχείριση του φορτίου των οικιακών καταναλωτών στοχεύοντας στην μείωση της κατανάλωσης ή στη χρήση ηλεκτρικής ενέργειας σε ώρες χαμηλής ζήτησης. Προκειμένου να υπάρξει η επιθυμητή ανταπόκριση από πλευράς οικιακών καταναλωτών, ένα σημαντικό ζητούμενο είναι η ανάπτυξη κατανεμημένων πολιτικών διαχείρισης ζήτησης της ηλεκτρικής ενέργειας βασισμένων σε κίνητρα.
Στο πλαίσιο της συγκεκριμένης διπλωματικής εργασίας ζητούνται:
(Γ.1) Η κριτική επισκόπηση της υπάρχουσας βιβλιογραφίας σε διαχείριση ζήτησης ηλεκτρικής ενέργειας.
(Γ.2) Η επέκταση ενος παιγνιοθεωρητικού μοντέλου για την εύρεση μιας κατανεμημένης παιγνιοθεωρητικής πολιτικής διαχείρισης ζήτησης της ηλεκτρικής ενέργειας βασισμένων σε κίνητρα.
(Γ.3) Η εκτενής πειραματική αξιολόγηση της παιγνιοθεωρητικής αυτής πολιτικής.
Ενδεικτική Βιβλιογραφία
[1] A.H. Mohsenian-Rad, V. Wong, J. Jatskevich, R. Schober, and A. Leon-Garcia. Autonomous Demand-Side Management Based on Game-Theoretic Energy Consumption Scheduling for the Future Smart Grid. IEEE Trans. on Smart Grid 1(3), 2010.
[2] S. Jain, B. Narayanaswamy, Y. Narahari, S.A. Hussain, and V.N. Yoong. Constrained Tatonnement for Fast and Incentive Compatible Distributed Demand Management in Smart Grids. In ACM e-Energy 2013.
[3] S. Keshav and C. Rosenberg. How Internet Concepts and Technologies Can Help Green and Smarten the Electrical Grid, In ACM SIGCOMM Computer Communication Review 41(1), 2011.
[4] A. Bessas, S. Kontogiannis, and C. Zaroliagis, ''Incentive-Compatible Robust line Planning" In Robust and Online Large-Scale Optimization, Chapter 4, Springer 2009, pp. 85-118.
[5] A. Bessas, S. Kontogiannis, and C. Zaroliagis, "Robust Line Planning in case of Multiple Pools and Disruptions", in Theory and Practice of Algorithms in Computer Systems - TAPAS 2011, Lecture Notes in Computer Science Vol.6595 (Springer 2011), pp. 33-44.
Δ. Διάχυση Πληροφορίας σε Κοινωνικά Δίκτυα
Τα κοινωνικά δίκτυα εμφανίζονται όλο και πιο έντονα στην καθημερινότητά μας. Πολλές αποφάσεις που λαμβάνουμε, από επιλογή μεταξύ ανταγωνιστικών προϊόντων, ή επιλογή υποψηφίου σε μια εκλογική διαδικασία, ή διατύπωση γνώμης σε μια ηλεκτρονική ψηφοφορία, επηρεάζονται σε σημαντικό βαθμό από τους φίλους, τους συνεργάτες, ή τους ανθρώπους που συναναστρεφόμαστε. Στόχος λοιπόν των άμεσα ενδιαφερόμενων εταιρειών, ή υποψηφίων, είναι η επιρροή, π.χ. μέσω στοχευμένης διαφήμισης, συγκεκριμένων "σημαντικών" οντοτήτων του κοινωνικού δικτύου, με μεγάλη δυνατότητα επιρροής στον σχηματισμό άποψης των μελών του δικτύου.
Οι προκλήσεις στο σχεδιασμό μεθόδων για τον εντοπισμό των πλέον σημαντικών οντοτήτων του δικτύου είναι σημαντικές, ενώ εξαρτώνται σε μεγάλο βαθμό κι από τον τρόπο διάχυσης της πληροφορίας εντός του κοινωνικού δικτύου. Επιπρόσθετα, κάθε ενδιαφερόμενος να επηρεάσει τη διάχυση της άποψής του εντός του κοινωνικού δικτύου, θα πρέπει να λάβει υπόψη του ότι δεν είναι μόνος του, αλλά ανταγωνίζεται εντός του ίδιου δικτύου κι άλλους ενδιαφερόμενους που προωθούν τη δική τους καμπάνια για τη διάχυση της δικής τους άποψης. Αυτό που τελικά προκύπτει είναι ένα ανταγωνιστικό περιβάλλον μεταξύ των διαφορετικών εταιρειών εντός του ίδιου κοινωνικού δικτύου, με επίγνωση του εκάστοτε τρόπου διάχυσης της πληροφορίας εντός του δικτύου.
Στο πλαίσιο της διπλωματικής αυτής ζητούνται:
(Δ.1) Επισκόπηση βασικών τεχνικών για επιλογή σημαντικών οντοτήτων σε κοινωνικά δίκτυα.
(Δ.2) Επισκόπηση πρωτοκόλλων διάχυσης πληροφορίας μέσα στο κοινωνικό δίκτυο, βασιζόμενα στο (συνεχές) De Groot μοντέλο και στα (διακριτά) μοντέλα καταρράκτη (cascading) και κατωφλίου (threshold) για διάχυση πληροφορίας.
(Δ.3) Υλοποίηση των πιο προσαρμοστικών τεχνικών επιλογής σημαντικών κόμβων (adaptive versions of centrality measures), και υλοποίηση μοντέλων καταρράκτη για διάχυση πληροφορίας.
Ενδεικτική Βιβλιογραφία
[1] Matthew Jackson, Yves Zenou: Games on Networks. In Handbook of Game Theory Vol. 4, edited by Peyton Young and Shmuel Zamir, Elsevier Science, 2014.
[2] Matthew Jackson: Decisions, Behavior, and Games on Networks. Chapter 9 in book Social and Economic Networks, Princeton University Press, 2008.
[3] David Easly and Jon Kleinberg: Cascading Behavior in Networks. Chapter 19 in book Networks, Crowds and Markets, Cambridge University Press, 2010.
E. Πειραματική Αξιολόγηση Ουρών Προτεραιότητας ως προς την Επίδοση Αλγορίθμων για θεμελιώδη Συνδυαστικά Προβλήματα σε Ευρείας Κλίμακας Στιγμιότυπα του Πραγματικού Κόσμου
Στη διεθνή βιβλιογραφία της Θεωρητικής Πληροφορικής υπάρχουν πάρα πολλές δομές δεδομένων που αφορούν Σωρούς (heaps), που όμως σε μεγάλο βαθμό δεν έχουν αξιολογηθεί πειραματικά σε πραγματικά στιγμιότυπα των προβλημάτων τα οποία τις αξιοποιούν. Είναι βέβαια γνωστό από παλαιότερες πειραματικές αξιολογήσεις ότι απλούστερες υλοποιήσεις ουρών προτεραιότητας (πχ, m-ary heaps) είναι ορισμένες φορές πιο αποδοτικές από άλλες, αρκετά πιο περίπλοκες στην υλοποίησή τους αλλά θεωρητικά πιο αποδοτικές υλοποιήσεις (πχ, ως fibonacci heaps).
Σκοπός της διπλωματικής είναι η υλοποίηση, προσαρμογή και πειραματική ορισμένων κλασσικών αλλά και νεώτερων υλοποιήσεων ουρών προτεραιότητας. Θα μελετήσουμε τη συμπεριφορά αυτών των υλοποιήσεων στο πλαίσιο ευρείας κλίμακας στιγμιοτύπων από τον πραγματικό κόσμο που αφορούν χρόνους διέλευσης σε αστικά οδικά δίκτυα, κατά την αξιοποίησή τους από κλασσικούς αλγορίθμους για θεμελιώδη συνδυαστικά προβλήματα (πχ, sorting, minimum spanning trees, shortest path trees).
Στο πλαίσιο της διπλωματικής αυτής ζητούνται:
(Ε.1) Επισκόπηση της πρόσφατης βιβλιογραφίας για βασικές δομες δεδομένων για την υλοποίηση ουρών προτεραιότητας.
(Ε.2) Υλοποίηση και προσαρμογή ή επιμέρους βελτιστοποιήσεις υπαρχουσών υλοποιήσεων, για τις πιο διαδεδομένες κι επιτυχημένες στην πράξη υλοποιήσεις.
(Ε.3) Υλοποίηση θεμελιωδών αλγορίθμων για προβλήματα συνδυαστικής βελτιστοποίησης (sorting, minimum spanning trees, shortest paths) με αξιοποίηση διαφορετικών υλοποιήσεων ουράς προτεραιότητας.
(Ε.4) Πειραματική αξιολόγηση σε πραγματικά δεδομένα που αφορούν χρόνους διέλευσης σε μητροπολιτικά οδικά δίκτυα.
Ενδεικτική Βιβλιογραφία
[1] D.H. Larkin, S. Sen. R.E. Tarjan: A Back-to-Basics Empirical Study of Priority Queues. In SIAM Meeting on Algorithm Engineering & Experiments (ALENEX 2014).
[2] S. Kontogiannis and C. Zaroliagis: Distance Oracles for Time-Dependent Networks. In ALGORITHMICA (2016).
[3] S. Kontogiannis, W. Wagner and C. Zaroliagis: Hierarcical Time-Dependent Oracles. In International Symposium on Algorithms and Computation (ISAAC 2016).
[4] S. Kontogiannis, G. Michalopoulos, G. Papastavrou, A. Paraskevopoulos, D. Wagner, C. Zaroliagis: Engineering Oracles for Time-Dependent Road Networks. In SIAM Meeting on Algorithm Engineering & Experiments (ALENEX 2016).
[*] Για περισσότερες πληροφορίες, οι ενδιαφερόμενοι μπορούν να επικοινωνήσουν με τον διδάσκοντα.
Contact Info
Office Hours
Latest News
Useful Links