ΠΑΝΕΠΙΣΤΗΜΙΟ ΙΩΑΝΝΙΝΩΝ - ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ SITE MAP | ΠΑΝΕΠΙΣΤΗΜΙΟ ΙΩΑΝΝΙΝΩΝ - ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ΕΛΛΗΝΙΚΑ | ΠΑΝΕΠΙΣΤΗΜΙΟ ΙΩΑΝΝΙΝΩΝ - ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ENGLISH
Παρασκευή, 14/11/2014   -   Ομιλίες
Σεμινάριο Τμήματος με τίτλο: Αλγόριθμοι εκθετικού χρόνου για NP-δύσκολα προβλήματα σε γραφήματα
Σεμινάριο Τμήματος

Στο πλαίσιο της διοργάνωσης εβδομαδιαίων σεμιναρίων του τμήματος διοργανώνεται η τέταρτη διάλεξη να πραγματοποιηθεί την Παρασκευή 14/11/2014 και ώρα 12:00 στην αίθουσα Σεμιναρίων του Τμήματος Μηχανικών Η/Υ και Πληροφορικής. Ομιλητής θα είναι ο κ. Χάρης Παπαδόπουλος, Επίκουρος Καθηγητής Τμήματος Μαθηματικών Πανεπιστημίου Ιωαννίνων, και o τίτλος της διάλεξης «Αλγόριθμοι εκθετικού χρόνου για NP-δύσκολα προβλήματα σε γραφήματα».

ΠΕΡΙΛΗΨΗ

Στην ομιλία θα παρουσιάσουμε δυο αλγοριθμικές τεχνικές για δύσκολα υπολογιστικά προβλήματα. Η πρώτη προσέγγιση αφορά τη σχεδίαση αλγορίθμων που χρειάζονται εκθετικό χρόνο εκτέλεσης ως προς την είσοδο του προβλήματος και η δεύτερη προσέγγιση αφορά τη σχεδίαση αλγορίθμων που χρειάζονται εκθετικό, παραμετροποιημένο, χρόνο εκτέλεσης ως προς την είσοδο και κάποια παράμετρο του προβλήματος. Για την πρώτη κατηγορία, θα ασχοληθούμε με το πρόβλημα της μεγιστοποίησης στοχευμένου άκυκλου υπογραφήματος (subset feedback vertex set) όπου σκοπός είναι η διαγραφή του ελάχιστου πλήθους κορυφών από ένα γράφημα έτσι ώστε το γράφημα που προκύπτει να μην έχει κύκλους που περνάνε από ένα δοσμένο σύνολο κορυφών. Για τη δεύτερη κατηγορία θα ασχοληθούμε με το πρόβλημα επεξεργασίας συστάδων (fuzzy cluster editing) όπου σκοπός είναι να επεξεργαστούμε το ελάχιστο πλήθος ακμών από ένα γράφημα έτσι ώστε το γράφημα που προκύπτει να αποτελείται από πλήρη υπογραφήματα.

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

Valid XHTML 1.0 Strict Valid CSS!