Θέμα: Ομιλία Τετάρτη 17 Ιανουαρίου - Γενικό Σεμινάριο Τμήματος

Το Γενικό Σεμινάριο του Τμήματος συνεχίζεται. Τα στοιχεία της επόμενης ομιλίας έχουν ως εξής:

Παρουσίαση Διδακτορικής Διατριβής
Ημερομηνία: Τετάρτη 17 Ιανουαρίου 2024. Ώρα: 14:00-15:00. Αίθουσα 342.
Ομιλήτρια: κα. Αγγελική-Παναγιώτα Παναγοπούλου, Υποψήφια Διδάκτορας του Τμήματος Μαθηματικών
Τίτλος ομιλίας: Νέοι Αλγόριθμοι για το Πρόβλημα του Δυικού Υπεργραφήματος

Περίληψη της ομιλίας: Ένα υπεργράφημα είναι μία οικογένεια υποσυνόλων ενός πεπερασμένου συνόλου, η οποία πληροί την ιδιότητα Sperner. Το Δυικό Υπεργράφημα είναι το πρόβλημα της εύρεσης του υπεργραφήματος, του οποίου οι υπερακμές είναι όλες οι ελαχιστικές διατέμνουσες του αρχικού υπεργραφήματος. Η ανάγκη του υπολογισμού του δυικού υπεργραφήματος προκύπτει σε πολλά επιστημονικά πεδία, όπως στην Τεχνητή Νοημοσύνη, στις Βάσεις Δεδομένων, στην Υπολογιστική Γεωμετρία και αλλού, αλλά έχει και ιδιαίτερη θεωρητική αξία. Στην ομιλία αυτή θα παρουσιαστούν νέες προσεγγίσεις στο πρόβλημα βασιζόμενες κυρίως στην μοντελοποίησή του σαν πρόβλημα ικανοποιησιμότητας (satisfiability) ειδικού τύπου λογικών εκφράσεων σε Συζευκτική Κανονική Μορφή. Η προσέγγιση αυτή οδήγησε σε νέα θεωρητικά αποτελέσματα, όπως στον υπολογισμό του λεγόμενου υπολειπόμενου δυικού υπεργραφήματος, καθώς και σε υπερπολυωνυμικά κάτω φράγματα στο μέγεθός του. Επίσης, εξετάστηκε η χρήση της μεθόδου της Επίλυσης (Resolution) για τη λύση του αντίστοιχου προβλήματος ικανοποιησιμότητας, η οποία έδωσε έναν καινούριο αλγόριθμο για τον υπολογισμό του δυικού υπεργραφήματος, βασιζόμενο σε διαμέριση των υπερακμών του σαν υπερσύνολα ξένων υποδιατεμνουσών. Τέλος, εξετάστηκε η επίδοση του αλγορίθμου των Fredman-Khachiyan σε διάφορα γνωστά υπεργραφήματα από την βιβλιογραφία και σχεδιάστηκαν ευρετικές μέθοδοι για την πολλαπλασιαστική μέθοδο του Berge.