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

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

ΠΕΡΙΛΗΨΗ

Η μελέτη προβλημάτων συνδυαστικής βελτιστοποίησης, όπως για παράδειγμα η εύρεση βέλτιστων διαδρομών, σε στιγμιότυπα του πραγματικού κόσμου που αφορούν τεχνολογικά δίκτυα και δίκτυα υποδομών ευρείας κλίμακας, είναι μια πολύ σημαντική ερευνητική τάση της Τεχνολογίας Υλοποίησης Αλγορίθμων. Λόγω της ευρείας κλίμακας αυτών των στιγμιοτύπων, κλασικοί αλγόριθμοι επίλυσης όπως ο αλγόριθμος του Dijkstra καθίστανται μη εφικτοί για υπηρεσίες που απαιτούν αποκρίσεις πραγματικού χρόνου σε δεκάδες αιτήματα εύρεσης βέλτιστων διαδρομών. Για τον λόγο αυτό την τελευταία δεκαπενταετία έχει αναπτυχθεί μια σημαντική ερευνητική κατεύθυνση, η οποία αποσκοπεί στην παροχή των λεγόμενων τεχνικών επιτάχυνσης και χρησμών απόστασης που επιτυγχάνουν αποκρίσεις για αιτήματα εύρεσης βέλτιστων διαδρομών σε πραγματικό χρόνο ή/και σε χρόνο αποδεδειγμένα μικρότερο από τον χρόνο απόκρισης του αλγορίθμου του Dijkstra, αξιοποιώντας κατάλληλα προεπεξεργασμένες δομές δεδομένων. Μια επιπρόσθετη δυσκολία σε στιγμιότυπα του πραγματικού κόσμου είναι ότι συχνά διέπονται από χρονικά μεταβαλλόμενα χαρακτηριστικά. Για παράδειγμα, σε ένα οδικό δίκτυο κάθε ακμή του δικτύου ενδέχεται να συνοδεύεται, όχι από μια τιμή, αλλά από μια συνάρτηση που καθορίζει τον χρόνο διέλευσής της ανάλογα με τη χρονική στιγμή που χρησιμοποιείται η εν λόγω ακμή. Αυτού του είδους τα στιγμιότυπα πολλές φορές καθιστούν το υπό μελέτη πρόβλημα ιδιαίτερα περίπλοκο, σε ορισμένες περιπτώσεις δε ακόμη και δυσεπίλυτο.
Στην παρούσα ομιλία παρουσιάζονται οι πρώτοι χρησμοί απόστασης που εμφανίστηκαν στη διεθνή βιβλιογραφία, με αποδεδειγμένες εγγυήσεις ποιότητας της παρεχόμενης λύσης, για εύρεση βέλτιστων διαδρομών σε χρονοεξαρτώμενα οδικά δίκτυα. Επιπρόσθετα, παρουσιάζεται μια εκτενής πειραματική αξιολόγηση των χρησμών αυτών σε πραγματικά δεδομένα που αφορούν τη μητροπολιτική περιοχή του Βερολίνου. Η συγκεκριμένη πειραματική αξιολόγηση αναδεικνύει και τη σπουδαιότητα της Τεχνολογίας Υλοποίησης Αλγορίθμων, μιας σύγχρονης ερευνητικής και εκπαιδευτικής τάσης που επιχειρεί να γεφυρώσει το χάσμα ανάμεσα στη αλγοριθμική θεωρία και στην πράξη.

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

Valid XHTML 1.0 Strict Valid CSS!