Στα μέσα της δεκαετίας του 1970, σε μια αίθουσα του Πανεπιστημίου Harvard, ο καθηγητής πληροφορικής Χρήστος Παπαδημητρίου έθετε στους φοιτητές του ένα από εκείνα τα προβλήματα που μοιάζουν απλά, αλλά κρύβουν μεγάλη δυσκολία. Το ερώτημα ήταν μαθηματικό και ταυτόχρονα παιγνιώδες: πώς μπορεί κανείς να ταξινομήσει μια σειρά αριθμών χρησιμοποιώντας μόνο μια ιδιαίτερη κίνηση — την αναστροφή ενός αρχικού τμήματος της λίστας; Σαν να γυρίζει κανείς ανάποδα μια στοίβα από τηγανίτες με μία μόνο κίνηση της σπάτουλας.
Ο καθηγητής παρουσίασε ένα παράδειγμα:
τους αριθμούς 3-4-2-1-5.
Η προφανής λύση ήταν να γυρίσει πρώτα τους δύο πρώτους, ώστε να γίνουν 4-3-2-1-5, και στη συνέχεια τους τέσσερις πρώτους, ώστε να προκύψει η σωστή σειρά 1-2-3-4-5. Δύο κινήσεις. Ένα κομψό αποτέλεσμα.
Στην αίθουσα βρισκόταν όμως ένας νεαρός φοιτητής που δεν έμοιαζε να ικανοποιείται με «κομψές αλλά προφανείς» λύσεις.
Το όνομά του ήταν Bill Gates. Από παιδί είχε ήδη αφιερώσει αμέτρητες ώρες μπροστά σε υπολογιστές και στο Harvard είχε τη φήμη ότι προχωρούσε πιο γρήγορα από τους περισσότερους συμφοιτητές του. Ο Gates άρχισε να σκέφτεται το πρόβλημα όχι ως ένα απλό παράδειγμα, αλλά ως ένα γενικό μαθηματικό ερώτημα. Μελέτησε το μοτίβο των αναστροφών και κατέληξε σε έναν αλγόριθμο που έδειχνε ότι μια τέτοια ταξινόμηση μπορούσε να γίνει, κατά μέσο όρο, με περίπου 1,67 κινήσεις για κάθε στοιχείο — ένα αποτέλεσμα τόσο κομψό ώστε δημοσιεύθηκε αργότερα σε επιστημονικό περιοδικό και παρέμεινε για χρόνια σημείο αναφοράς.
Το πρόβλημα αυτό έγινε γνωστό ως το περίφημο “pancake sorting problem”, το «πρόβλημα της στοίβας με τις τηγανίτες». Παράξενο όσο κι αν ακούγεται, παρόμοια μαθηματικά μοντέλα χρησιμοποιούνται σήμερα ακόμη και στη βιολογία για να περιγράψουν αναστροφές τμημάτων στα ανθρώπινα χρωμοσώματα. Κι όμως, λίγα χρόνια αργότερα, ο ίδιος εκείνος φοιτητής πήρε μια απόφαση που άφησε πολλούς στο Harvard άφωνους: εγκατέλειψε το πανεπιστήμιο.
Ο Bill Gates μετακόμισε στο Albuquerque του Νέου Μεξικού για να ιδρύσει μια μικρή εταιρεία που έγραφε λογισμικό για μικροεπεξεργαστές. Όταν ο καθηγητής έμαθε την είδηση, θυμάται ότι σκέφτηκε: «Τόσο λαμπρό παιδί… τι κρίμα να χαραμιστεί έτσι.» Η μικρή εκείνη εταιρεία λεγόταν Microsoft. Και ο «χαμένος» φοιτητής έγινε ένας από τους ανθρώπους που άλλαξαν την ιστορία της τεχνολογίας.
(*) H κοινή δημοσιευση των Gates-Παπαδημητριου γαι το συγκεκριμένο πρόβλημα έχει τίτλο "Bounds for sorting by prefix reversal" ("Φράγματα για την ταξινόμηση μέσω αναστροφής αρχικού τμήματος"), η οποία δημοσιεύθηκε το 1979 στο έγκριτο περιοδικό Discrete Mathematics (Τόμος 27, Τεύχος 1, Σελίδες 47-57)
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου