ΠΑΝΕΠΙΣΤΗΜΙΟ ΙΩΑΝΝΙΝΩΝ - ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ SITE MAP | ΠΑΝΕΠΙΣΤΗΜΙΟ ΙΩΑΝΝΙΝΩΝ - ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ΕΛΛΗΝΙΚΑ | ΠΑΝΕΠΙΣΤΗΜΙΟ ΙΩΑΝΝΙΝΩΝ - ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ENGLISH
Παρασκευή, 09/12/2016   -   Ομιλίες
Σεμινάριο Τμήματος με τίτλο:"Ιεραρχικές Προσεγγίσεις για Βέλτιστες Διαδρομές σε Χρονοεξαρτώμενα Οδικά Δίκτυα: Θεωρία και Πράξη", Σπύρος Κοντογιάννης

Στο πλαίσιο της διοργάνωσης των σεμιναρίων του τμήματος, θα πραγματοποιηθεί την Παρασκευή 09/12/2016 και ώρα 12:00 στην αίθουσα Σεμιναρίων του Τμήματος Μηχανικών Η/Υ και Πληροφορικής, ομιλία με τίτλο "Ιεραρχικές Προσεγγίσεις για Βέλτιστες Διαδρομές σε Χρονοεξαρτώμενα Οδικά Δίκτυα: Θεωρία και Πράξη". Ομιλητής θα είναι ο κ. Σπύρος Κοντογιάννης, Επίκουρος Καθηγητής του Τμήματος Μηχανικών Η/Υ & Πληροφορικής, Πανεπιστημίου Ιωαννίνων.

ΠΕΡΙΛΗΨΗ

Η μελέτη προβλημάτων συνδυαστικής βελτιστοποίησης, όπως για παράδειγμα η εύρεση βέλτιστων διαδρομών, σε στιγμιότυπα του πραγματικού κόσμου που αφορούν τεχνολογικά δίκτυα και δίκτυα υποδομών ευρείας κλίμακας, είναι μια πολύ σημαντική ερευνητική τάση της Τεχνολογίας Υλοποίησης Αλγορίθμων. Λόγω της ευρείας κλίμακας αυτών των στιγμιοτύπων, κλασικοί αλγόριθμοι επίλυσης όπως ο αλγόριθμος του Dijkstra καθίστανται μη αποδοτικοί για υπηρεσίες που απαιτούν αποκρίσεις πραγματικού χρόνου σε δεκάδες αιτήματα εύρεσης βέλτιστων διαδρομών. Για τον λόγο αυτό την τελευταία δεκαπενταετία έχει αναπτυχθεί μια σημαντική ερευνητική κατεύθυνση, η οποία αποσκοπεί στην παροχή των λεγόμενων τεχνικών επιτάχυνσης και χρησμών απόστασης που παρέχουν (σχεδόν) βέλτιστες διαδρομές σε πραγματικό χρόνο ή/και σε χρόνο αποδεδειγμένα μικρότερο από τον χρόνο απόκρισης του αλγορίθμου του Dijkstra, αξιοποιώντας κατάλληλα προεπεξεργασμένες δομές δεδομένων. Μια επιπρόσθετη δυσκολία σε στιγμιότυπα του πραγματικού κόσμου είναι ότι συχνά διέπονται από χρονικά μεταβαλλόμενα χαρακτηριστικά. Για παράδειγμα, σε ένα οδικό δίκτυο κάθε ακμή του δικτύου ενδέχεται να συνοδεύεται, όχι από μια τιμή, αλλά από μια συνάρτηση αποτίμησης του χρόνου διέλευσης, ανάλογα με τη χρονική στιγμή που χρησιμοποιείται η εν λόγω ακμή. Αυτού του είδους τα στιγμιότυπα πολλές φορές καθιστούν το υπό μελέτη συνδυαστικό πρόβλημα ιδιαίτερα περίπλοκο, σε ορισμένες περιπτώσεις δε ακόμη και δυσεπίλυτο.
Η παρούσα ομιλία αποτελείται από δυο μέρη: (α) Παρουσιάζεται ο πρώτος ιεραρχικός χρησμός (HORN) για διαδρομές σε χρονοεξαρτώμενα αραιά δίκτυα. Ο χρησμός αυτός βασίζεται σε προϋπολογισμένες συναρτήσεις απόστασης από επιλεγμένα ορόσημα (landmarks), όχι προς όλους τους δυνατούς προορισμούς, αλλά προς τους προορισμούς που βρίσκονται εντός της δικής τους περιοχής κάλυψης. Η κατάλληλη επιλογή και οργάνωση σε επίπεδα των οροσήμων, καθιστά δυνατή την παροχή σχεδόν βέλτιστων διαδρομών σε χρόνο αποδεδειγμένα μικρότερο του χρόνου εκτέλεσης του Dijkstra, για σχεδόν όλα τα αιτήματα δρομολόγησης, ανεξάρτητα από την εμβέλειά τους. (β) Παρουσιάζεται εκτενής πειραματική αξιολόγηση σε δυο πραγματικά στιγμιότυπα ευρείας κλίμακας με διαφορετικά χαρακτηριστικά, τόσο ενός χρησμού (FLAT) που εισήγαγε, ανέλυσε και ανέπτυξε παλιότερα η ερευνητική μας ομάδα (όπου κάθε ορόσημο έχει ως περιοχή κάλυψης ολόκληρο το δίκτυο), όσο και του καινοτόμου ιεραρχικού χρησμού HORN. Εκτός από την αξιολόγηση των χρησμών, μελετάται και η δυνατότητα επικαιροποίησης των κυκλοφοριακών δεδομένων που τηρούνται, αξιοποιώντας δεδομένα πραγματικού χρόνου που παρέχονται από τους ίδιους τους ταξιδιώτες.

©2010 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING - UNIVERSITY OF IOANNINA
created by data|SCIENCE

Valid XHTML 1.0 Strict Valid CSS!