Ο φοιτητής του προγράμματος Μερκούρης Παπαμιχαήλ θα παρουσιάσει τη διπλωματική του εργασία με θέμα:
Προβλήματα ταξινόμησης και επιλογής σε μερικώς διατεταγμένα σύνολα
την Τρίτη 27 Σεπτεμβρίου 2022 και ώρα 10:00, διαδικτυακά (webex*).
Σύνοψη Διπλωματικής:
Σε αυτή την εργασία παρουσιάζουμε κάποια αποτελέσματα από την βιβλιογραφία σχετικά με προβλήματα ταξινόμησης και επιλογής σε μερικώς διατεταγμένα σύνολα. Στο πρόβλημα ταξινόμησης μας δίνεται ένα μερικώς διατεταγμένο σύνολο U και, επιπλέον, μια συνάρτηση μαντείου. Έχουμε την δυνατότητα να συγκρίνουμε δύο στοιχεία του U, μόνο μέσω ερωτημάτων στη συνάρτηση μαντείου. Μπορούμε να συγκρίνουμε οποιαδήποτε δύο σημεία, το μαντείο μας επιστρέφει αν τα στοιχεία σχετίζονται καθώς και για την σχέση μεταξύ τους. Ο σκοπός μας είναι να ανακατασκευάσουμε την υποκείμενη, άγνωστη μερική διάταξη. Στο πρόβλημα k-επιλογής, μας ζητείτε να βρούμε τα k-μικρότερα στοιχεία στο ίδιο πλαίσιο. Ειδικότερα, εξετάζουμε δύο μοντέλα, το Μ ντέλο Φραγμένου Πλάτους και το Μοντέλο Απαγορευμένων Συγκρίσεων. Στο Μοντέλο Φραγμένου Πλάτους μας δίνεται επιπλέον ένα άνω φράγμα w στο πλάτος της μερικής< διάταξης. Το κύριο αποτέλεσμα που εξετάζουμε, σε αυτό το πλαίσιο, είναι ο βέλτιστος, ως προς τα ερωτήματα, Αλγόριθμος Entropy Sort, με O(n log n + nw) πολυ πλοκότητα ερωτημάτων αλλά εκθετική πολυπλοκότητα χρόνου. Επιπλέον, εξετάζουμε κάποιους τυχαιοκρατικούς και ντετερμινιστικούς αλγορίθμους σε αυτό το πλαίσιο για το πρόβλημα επιλογής. Από την άλλη πλευρά, στο πλαίσιο του Μοντέλου Απαγορευμένων Συγκρίσεων, η συνάρτηση μαντείου ορίζεται κάπως διαφορετικά, καθώς δεν επιτρέπεται η σύγκριση όλων των ζευγών σημείων, ενώ επιπλέον δύο στοιχεία όταν συγκρίνονται, πάντα σχετίζονται (απλά δεν γνωρίζουμε την σχέση τους). Όταν δεν μας επιτρέπεται να συγκρίνουμε τα δύο στοιχεία a, b∙ συμπεραίνουμε αυτές τις σχέσεις μέσω της μεταβατικότητας. Μας δίνεται, επίσης, ένα μη κατευθυνόμενο γράφημα συγκρίσεων G = (V, E), όπου υπάρχει η ακμή {a, b} αν τα δύο στοιχεία μπορούν να συγκριθούν. Επιπλέον, με q συμβολίζουμε τον αριθμό των ακμών που λεί πουν. Σε αυτό το πλαίσιο παρουσιάζουμε τον αλγόριθμο με O((q +n) log((n^2)/q)) πολυπλοκότητα ερωτημάτων και O(n^ω) χρονική πολυπλοκότητα, όπου ω είναι ο εκθέτης του πολλαπλασιασμού πινάκων. Τέλος, εξετάζουμε τις ειδικές περιπτώσεις χορδικών γραφημάτων και γραφημάτων συγκρισιμότητας, όπου δείχνουμε αλγορίθμους, O(n log n) πολυπλοκότητα ερωτημάτων και O(n^ω) χρονική πολυπλοκότητα.
Η Επιτροπή,
Αρχοντία Χ. Γιαννοπούλου,
Τμήμα Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Ιωάννης Z. Εμίρης,
Τμήμα Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Σταύρος Κολλιόπουλος (Επιβλέπων),
Τμήμα Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
* https://uoa.webex.com/uoa/j.php?MTID=m28905ef102b16b332ebc0e0270a3edab
Meeting number: 2734 955 3392
Password: mBRhD8VER73