National and Kapodistrian University of Athens
Sorting and Selection Problems in Partially Ordered Sets
Abstract
dc:descriptionΣε αυτή την εργασία παρουσιάζουμε κάποια αποτελέσματα από την βιβλιογραφία σχετικά με προβλήματα ταξινόμησης και επιλογής σε μερικώς διατεταγμένα σύνολα. Στο πρόβλημα ταξινόμησης μας δίνεται ένα μερικώς διατεταγμένο σύνολο 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^ω) χρονική πολυπλοκότητα.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Παπαμιχαήλ Μερκούριος-Χρήστος
- Papamichail Merkourios-Christos
Subjects
dc:subject × 2Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:3232651