Μελέτη και ανάπτυξη αυτοοργανώμενων δομών δεδομένων

• Κύριος συγγραφέας: Αντωνίου, Δημήτριος
• Άλλοι συγγραφείς: Μακρής, Χρήστος
• Μορφή: Thesis
• Γλώσσα: Greek
• Έκδοση: 2009
• Θέματα: Αυτοοργανώμενες δομές δεδομένων; Αλγόριθμοι; Splay δέντρα; Self-organizing data structures; Algorithms; Splay trees; 005.73

Θέμα της παρούσης διπλωματικής εργασίας αποτελεί η μελέτη, ανάπτυξη και πειραματική επιβεβαίωση αλγοριθμικών τεχνικών για την σχεδίαση αυτοοργανώμενων δομών δεδομένων (self-organizing data structures) και η ανάπτυξη τυχαιοποιημένων εκδόσεών τους. Μια αυτοοργανώμενη δομή δεδομένων διαθέτει κάποιον αλγόριθμο για να αναδιοργανώνει τους δείκτες και τα δεδομένα κατάστασης μετά από κάθε πρόσβαση ή πράξη . Ο αλγόριθμος αυτοοργάνωσης είναι σχεδιασμένος ώστε αντιδρώντας σε αρχικά άγνωστες ιδιότητες της ακολουθίας αιτήσεων (request sequence), να οδηγεί τη δομή δεδομένων σε κατάσταση πλεονεκτική για τις ιδιότητες της ακολουθίας με αποτέλεσμα τη μείωση του χρόνου που χρειάζεται στο μέλλον ανά πράξη. Ο πρώτος αλλά και ο μόνος μέχρι σήμερα πιθανός υποψήφιος αλγόριθμος αναζήτησης σε δένδρο που μπορεί να είναι Ο(1)-ανταγωνιστικός είναι το splay δένδρο (splay tree) που παρουσιάστηκε από τους Sleator και Tarjan [1]. Στην εργασία των Sleator και Tarjan παρουσιάζονται κάποιες εικασίες, οι οποίες δεν έχουν αποδειχθεί. Σημαντικότερη είναι η εικασία δυναμικής βελτιστότητας (dynamic optimality conjecture) σύμφωνα με την οποία το splay δένδρο είναι Ο(1)-ανταγωνιστικό. Η εικασία δυναμικής δακτυλοδότησης (dynamic finger conjecture) και η εικασία διαπέρασης (traversal conjecture) είναι αληθείς, αν είναι αληθής η εικασία δυναμικής βελτιστότητας. Ο Cole [3], [4] προσπάθησε να αποδείξει την ορθότητα της εικασίας δυναμικής δακτυλοδότησης σε μια από τις σημαντικότερες εργασίες για τα splay δένδρα. O J. Iacono [2] ανέπτυξε εναλλακτικές δομές δεδομένων που έχουν χρόνο χειρότερης περίπτωσης ανά πράξη (και όχι επιμερισμένο κόστος) της τάξης του Ο(logn), σε αντιδιαστολή με τον Ο(n) χρόνο χειρότερης περίπτωσης των splay trees. Σε αντιπαράθεση με τη δομή του Iacono, οι Mihai Badoiu και Erik D. Demaine παρουσίασαν μια δυναμική δομή αναζήτησης[7], η οποία επιτυγχάνει την ενοποιημένη ιδιότητα και που είναι απλούστερη από τη δομή του Iacono. Μεταξύ όλων των δυναμικών δομών αναζήτησης με βάση τις συγκρίσεις , η συγκεκριμένη δομή έχει τον καλύτερο χρόνο εκτέλεσης. Εκτός της παραπάνω δομής, ο Demaine ανέπτυξε ένα Ο(loglogn) ανταγωνιστικό online δυαδικό δέντρο αναζήτησης[5] , βελτιώνοντας το μέχρι πρότινος βέλτιστο ανταγωνιστικό ποσοστό της τάξης Ο(logn). Αυτή είναι η πρώτη μεγάλη βελτίωση της εικασίας δυναμικής βελτιστότητας (dynamic optimality conjecture) των Sleator και Tarjan , σύμφωνα με την οποία υπάρχουν Ο(1) ανταγωνιστικά δυαδικά δέντρα αναζήτησης. Σε σχέση με τη δυναμική βελτιστότητα των Splay trees, σημαντική συνεισφορά αποτελεί και η εργασία του George F. Georgakopoulos[6]. Ο George F. Georgakopoulos παρουσιάζει μια επέκταση της splay τεχνικής , την οποία ονομάζει chain-splay(αλυσιδωτό splay) . Τα chain-splay δέντρα εφαρμόζουν splay στο στοιχείο που προσπελαύνουμε προς τη ρίζα όπως ακριβώς γίνεται και στα κλασικά splay trees, αλλά εκτελούν και μερικές τοπικές splay πράξεις τακτοποίησης κάτω από το στοιχείο που προσπελάσαμε. Αποδεικνύεται πως η τεχνική chain–splay είναι Ο(loglogn) ανταγωνιστική σε σχέση με οποιοδήποτε offline αλγόριθμο αναζήτησης. Tέλος, ο George F. Georgakopoulos [9] έδωσε ένα νέο λήμμα επαναζύγισης για τα splay δέντρα και με βάση αυτό το λήμμα, αποδεικνύει πως τα splay δέντρα είναι ανταγωνιστικά προς κάθε κλάση δυναμικών ισοζυγισμένων δέντρων. Οι παραπάνω δομές θα μελετηθούν τόσο σε θεωρητικό όσο και σε πειραματικό επίπεδο με σκοπό την εξαγωγή χρήσιμων συμπερασμάτων σε σχέση με την αποδοτικότητά τους αλλά και με σκοπό την καταγραφή των ακόμη ανοικτών προβλημάτων και των προοπτικών επίλυσης τους. Επιπλέον, θα παρουσιαστούν τυχαιοποιημένες εκδόσεις των δομών των Demaine και Georgakopoulos. Οι δομές αυτές θα υλοποιηθούν και η απόδοσή τους θα τεκμηριωθεί τόσο πειραματικά όσο και θεωρητικά. Σημαντικής σημασίας είναι η σύγκρισή τους με τις αρχικές δομές, ώστε να εξαχθούν συμπεράσματα σχετικά με την συμβολή της τυχαιοποίησης στη βελτίωση της απόδοσης των δομών.