Η αρχική έκδοση του αυτή η ιστορία Εμφανίστηκε στο περιοδικό Quanta.
Οι επιστήμονες υπολογιστών συχνά ασχολούνται με αφηρημένα προβλήματα που είναι δύσκολο να κατανοηθούν, αλλά ένας συναρπαστικός νέος αλγόριθμος έχει σημασία για όποιον κατέχει βιβλία και τουλάχιστον ένα ράφι. Ο αλγόριθμος αντιμετωπίζει κάτι που ονομάζεται πρόβλημα ταξινόμησης της βιβλιοθήκης (πιο τυπικά, το πρόβλημα “επισήμανσης λίστας”). Η πρόκληση είναι να επινοήσουμε μια στρατηγική για την οργάνωση βιβλίων σε κάποιο είδος ταξινομημένης τάξης – για παράδειγμα, για παράδειγμα – που ελαχιστοποιεί πόσο καιρό χρειάζεται να τοποθετηθεί ένα νέο βιβλίο στο ράφι.
Φανταστείτε, για παράδειγμα, ότι κρατάτε τα βιβλία σας συσσωρευμένα μαζί, αφήνοντας κενό χώρο στην άκρα δεξιά του ράφι. Στη συνέχεια, αν προσθέσετε ένα βιβλίο από την Isabel Allende στη συλλογή σας, ίσως χρειαστεί να μετακινήσετε κάθε βιβλίο στο ράφι για να το κάνετε χώρο για αυτό. Αυτό θα ήταν μια χρονοβόρα λειτουργία. Και αν λάβετε ένα βιβλίο από τον Douglas Adams, θα πρέπει να το κάνετε ξανά. Μια καλύτερη ρύθμιση θα άφηνε μη κατοχυρωμένους χώρους που διανέμονται σε όλο το ράφι – αλλά πώς, ακριβώς, πρέπει να διανεμηθούν;
Το πρόβλημα αυτό εισήχθη σε ένα έγγραφο του 1981 και υπερβαίνει απλά την παροχή βιβλιοθηκονόμων με οργανωτική καθοδήγηση. Αυτό οφείλεται στο γεγονός ότι το πρόβλημα ισχύει και για τη διάταξη αρχείων σε σκληρούς δίσκους και σε βάσεις δεδομένων, όπου τα στοιχεία που πρόκειται να διευθετηθούν θα μπορούσαν να αριθμήσουν στα δισεκατομμύρια. Ένα αναποτελεσματικό σύστημα σημαίνει σημαντικούς χρόνους αναμονής και σημαντικές υπολογιστικές δαπάνες. Οι ερευνητές έχουν εφεύρει κάποιες αποτελεσματικές μεθόδους για την αποθήκευση αντικειμένων, αλλά από καιρό ήθελαν να καθορίσουν τον καλύτερο δυνατό τρόπο.
Πέρυσι, σε μια μελέτη που παρουσιάστηκε στα θεμέλια της Συνδιάσκεψης Πληροφορικής στο Σικάγο, μια ομάδα επτά ερευνητών περιέγραψε έναν τρόπο να οργανώσουν αντικείμενα που έρχονται έντονα κοντά στο θεωρητικό ιδεώδες. Η νέα προσέγγιση συνδυάζει μια μικρή γνώση των προηγούμενων περιεχομένων του βιβλιοθήκη με την εκπληκτική δύναμη της τυχαιότητας.
“Είναι ένα πολύ σημαντικό πρόβλημα”, δήλωσε ο Seth Pettie, επιστήμονας υπολογιστών στο Πανεπιστήμιο του Μίτσιγκαν, επειδή πολλές από τις δομές δεδομένων που βασιζόμαστε στις πληροφορίες αποθηκεύουν διαδοχικά τις πληροφορίες. Κάλεσε το νέο έργο “εξαιρετικά εμπνευσμένο (και) εύκολα ένα από τα τρία κορυφαία αγαπημένα μου χαρτιά της χρονιάς”.
Στενό όρια
Λοιπόν, πώς μπορεί κανείς να μετρήσει ένα καλά ταξινομημένο ράφι; Ένας κοινός τρόπος είναι να δούμε πόσο καιρό χρειάζεται για να εισαγάγετε ένα μεμονωμένο στοιχείο. Φυσικά, αυτό εξαρτάται από το πόσα στοιχεία υπάρχουν στην πρώτη θέση, μια τιμή που συνήθως υποδηλώνει n. Στο παράδειγμα της Isabel Allende, όταν όλα τα βιβλία πρέπει να μετακινηθούν για να φιλοξενήσουν ένα νέο, ο χρόνος που χρειάζεται είναι ανάλογος n. Όσο μεγαλύτερος το nόσο περισσότερο χρειάζεται. Αυτό καθιστά αυτό το “ανώτερο όριο” στο πρόβλημα: δεν θα διαρκέσει ποτέ περισσότερο από το χρόνο αναλογικό n για να προσθέσετε ένα βιβλίο στο ράφι.
Οι συντάκτες του εγγράφου του 1981 που προκάλεσαν σε αυτό το πρόβλημα ήθελαν να μάθουν αν ήταν δυνατόν να σχεδιάσουμε έναν αλγόριθμο με μέσο χρόνο εισαγωγής πολύ μικρότερο από n. Και πράγματι, απέδειξαν ότι κάποιος θα μπορούσε να κάνει καλύτερα. Δημιούργησαν έναν αλγόριθμο που εγγυάται ότι θα επιτύχει έναν μέσο χρόνο εισαγωγής αναλογικό προς (log n·2. Αυτός ο αλγόριθμος είχε δύο ιδιότητες: ήταν “ντετερμινιστική”, που σημαίνει ότι οι αποφάσεις του δεν εξαρτώνται από τυχαία και ήταν επίσης “ομαλή”, πράγμα που σημαίνει ότι τα βιβλία πρέπει να εξαπλώνονται ομοιόμορφα μέσα σε υποτμήματα του ράφι όπου οι εισαγωγές (ή διαγραφές) γίνονται. Οι συγγραφείς άφησαν να ανοίξουν το ερώτημα εάν το ανώτερο όριο θα μπορούσε να βελτιωθεί ακόμη περισσότερο. Για πάνω από τέσσερις δεκαετίες, κανείς δεν κατάφερε να το πράξει.
Ωστόσο, τα παρελθόντα χρόνια είδαν βελτιώσεις στο κατώτερο όριο. Ενώ το ανώτερο όριο καθορίζει τον μέγιστο δυνατό χρόνο που απαιτείται για την εισαγωγή ενός βιβλίου, το κατώτερο όριο δίνει τον ταχύτερο δυνατό χρόνο εισαγωγής. Για να βρουν μια οριστική λύση σε ένα πρόβλημα, οι ερευνητές προσπαθούν να περιορίσουν το χάσμα μεταξύ των ανώτερων και των κατώτερων ορίων, ιδανικά μέχρι να συμπέσουν. Όταν συμβεί αυτό, ο αλγόριθμος θεωρείται βέλτιστος – οριοθετημένος από πάνω και κάτω, αφήνοντας κανένα περιθώριο για περαιτέρω βελτίωση.
