Δημόσια υποστήριξη της Διδακτορικής Διατριβής της κ. Αγγελικής-Παναγιώτας Παναγοπούλου

Την Παρασκευή 23 Φεβρουαρίου 2024, ώρα 10:00, θα γίνει η δημόσια υποστήριξη της διδακτορικής διατριβής της υποψηφίας διδάκτορος του Τμήματος Μαθηματικών κ. Αγγελικής-Παναγιώτας Παναγοπούλου, διαδικτυακά μέσω zoom στον σύνδεσμο:

https://upatras-gr.zoom.us/j/9934533...RzeUE1WUJBQT09

Τίτλος: Νέοι Αλγόριθμοι για το Πρόβλημα του Δυικού Υπεργραφήματος

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

Για την επταμελή Εξεταστική Επιτροπή

Δημήτρης Καββαδίας
Επίκουρος Καθηγητής