ΠΑΝΕΠΙΣΤΗΜΙΟ ΙΩΑΝΝΙΝΩΝ - ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ SITE MAP | ΠΑΝΕΠΙΣΤΗΜΙΟ ΙΩΑΝΝΙΝΩΝ - ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ΕΛΛΗΝΙΚΑ | ΠΑΝΕΠΙΣΤΗΜΙΟ ΙΩΑΝΝΙΝΩΝ - ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ENGLISH
Παρασκευή, 12/12/2014   -   Ομιλίες
Σεμινάριο Τμήματος με τίτλο:"Αλγοριθμική Θεωρία Γραφημάτων: Απόκρυψη Πληροφορίας και 2-Κυριαρχία", Σταύρος Δ. Νικολόπουλος

Στο πλαίσιο της διοργάνωσης των εβδομαδιαίων σεμιναρίων του τμήματος θα πραγματοποιηθεί την Παρασκευή 12/12/2014 και ώρα 12:00 στην αίθουσα Σεμιναρίων του Τμήματος Μηχανικών Η/Υ και Πληροφορικής, ομιλία με τίτλο "Αλγοριθμική Θεωρία Γραφημάτων: Απόκρυψη Πληροφορίας και 2-Κυριαρχία". Ομιλητής θα είναι ο κ. Σταύρος Δ. Νικολόπουλος, Καθηγητής του Τμήματος Μηχανικών Η/Υ & Πληροφορικής, Πανεπιστήμιου Ιωαννίνων.

ΠΕΡΙΛΗΨΗ

Παρουσιάζουμε την κλάση των Τέλειων γραφημάτων (Perfect graphs), ορίζουμε την υποκλάση των Μεταθετικών γραφημάτων (Permutation), και δίδουμε δύο ισοδύναμες απεικονίσεις ενός μεταθετικού γραφήματος G = (V, E): (i) ως ένα σύνολο σημείων στο επίπεδο (2D-απεικόνιση), και (ii) ως μια δομή κατευθυνόμενου γραφήματος (DAG- απεικόνιση). Βασιζόμενοι σε δομικές ιδιότητες των 2D και DAG απεικονίσεων σχεδιάζουμε και αναλύουμε αλγορίθμους για το πρόβλημα της 2-κυριαρχίας (2-pair domination) σε μεταθετικά γραφήματα και για το πρόβλημα της απόκρυψης πληροφορίας (information hiding) σε ψηφιακά αντικείμενα. Συγκεκριμένα, επιλύουμε το πρόβλημα της 2-κυριαρχίας σε μεταθετικά γραφήματα σε O(n) χρόνο, δηλαδή, σε χρόνο γραμμικό ως προς την τάξη του γραφήματος G, σαρώνοντας τα σημεία της 2D-απεικόνισης του γραφήματος G (σημειώνουμε ότι το πρόβλημα της 2-κυριαρχίας στη γενική περίπτωση είναι NP-πλήρες). Προτείνουμε ένα codec σύστημα για το πρόβλημα της υδατοσήμανσης λογισμικού κωδικοποιώντας αρχικά έναν ακέραιο w σε αυτo-ανάστροφη (self-inverting) μετάθεση π* και ενσωματώνοντας την μετάθεση π* σε ένα RPG γράφημα (reducible permutation graph) F[π*] με την χρήση της DAG-απεικόνισης της μετάθεση π*. Στη συνέχεια υδατογραφούμε ένα πρόγραμμα λογισμικού P ενσωματώνοντας σε αυτό το (υδατο-) γράφημα F[π*] με κατάλληλη τροποποίηση ενός γραφήματος κλήσεων συναρτήσεων του P, παράγοντας έτσι το υδατογραφημένο πρόγραμμα Pw.

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

Valid XHTML 1.0 Strict Valid CSS!