Προβλήματα ταξινόμησης και επιλογής σε μερικώς διατεταγμένα σύνολα

Σε αυτή την εργασία παρουσιάζουμε κάποια αποτελέσματα από την βιβλιογραφία σχε­τικά με προβλήματα ταξινόμησης και επιλογής σε μερικώς διατεταγμένα σύνολα. Στο πρόβλημα ταξινόμησης μας δίνεται ένα μερικώς διατεταγμένο σύνολο 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^ω) χρονική πολυπλοκότητα.