Σε αυτή την εργασία παρουσιάζουμε κάποια αποτελέσματα από την βιβλιογραφία σχετικά με προβλήματα ταξινόμησης και επιλογής σε μερικώς διατεταγμένα σύνολα. Στο πρόβλημα ταξινόμησης μας δίνεται ένα μερικώς διατεταγμένο σύνολο 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^ω) χρονική πολυπλοκότητα.
(EL)
In this thesis we present some results from the literature regarding sorting and selection problems in partially ordered sets. In the sorting problem we are given a partially ordered set U and access to an oracle function. We are able to compare two elements of U, only by querying the oracle function. Our goal is to retrieve the underlying unknown partial order. In the k-selection problem, we are required to find the k-smallest elements in the same setting. In particular we examine two models, the Width-Based Model and the Forbidden Comparisons Model. In the Width-Based Model we are additionally given an upper bound w on the width of the underlying poset. The main result we present in this setting is the query-οptimal Entropy Sort algorithm with O(n log n + nw) query complexity, but exponential overall time. We also examine some randomized and deterministic algorithms in this setting for the selection problem. On the other hand, the Forbidden Comparisons Model, the oracle function is defined slightly differently, since we are not allowed to compare the two elements a, b; we deduce their relations (is they are related) through transitivity. We are also given an undirected comparison graph G = (V, E), where there exists the edge {a, b} if the two elements can be compared. Moreover, we denote with q the number of missing edges. In this setting we present the algorithm in with O((q +n) log((n^2) /q)) query complexity and O(n^ω) time complexity, where ω is the exponent of the matrix multiplication. Lastly, we examine the special cases of chordal and comparability graphs, where we present an algorithm with O(n log n) query and O(n^ω) time complexity, respectively.
(EN)
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
