Χρήση της μαθηματικής θεωρίας για την εύρεση του πραγματικού δυναμικού των αλγορίθμων!

Κάθε εξάμηνο, ο Αναπληρωτής Καθηγητής Βιρτζίνια Βασιλέβσκα Ουίλιαμς προσπαθεί να μεταδώσει ένα θεμελιώδες μάθημα στους προπτυχιακούς φοιτητές της στον τομέα της πληροφορικής: Το μάθημα είναι το θεμέλιο των πάντων.

Συχνά, οι μαθητές μπαίνουν στην τάξη του Williams, 6.006 (Εισαγωγή στους Αλγορίθμους), θέλοντας να βυθιστούν σε προηγμένο προγραμματισμό που τροφοδοτεί τις τελευταίες, μεγαλύτερες τεχνικές υπολογιστικής. Τα μαθήματά της επικεντρώνονται στο πώς σχεδιάζονται οι αλγόριθμοι γύρω από τα μαθηματικά μοντέλα και τις έννοιες του πυρήνα.

«Όταν παίρνουν μια τάξη αλγορίθμων, πολλοί μαθητές αναμένουν να προγραμματίσουν πολύ και ίσως να χρησιμοποιήσουν βαθιά μαθήματα, αλλά είναι πολύ μαθηματικές και έχουν πολύ μικρό προγραμματισμό», λέει ο Williams, ο Steven G. (1968) και ο Renee Finn Καθηγητής Καριέρας Ανάπτυξης θητεία στο Τμήμα Ηλεκτρολόγων Μηχανικών και Επιστήμης Υπολογιστών. «Δεν έχουμε πολύ χρόνο μαζί στην τάξη (μόνο δύο ώρες την εβδομάδα), αλλά ελπίζω ότι εκείνη τη στιγμή θα δουν λίγο από την ομορφιά των μαθηματικών – επειδή τα μαθηματικά σας επιτρέπουν να δείτε πώς και γιατί τα πάντα δουλεύουν μαζί. Είναι πραγματικά ένα όμορφο πράγμα. “

Η ζωή του Williams είναι πολύ διαμορφωμένη από τα μαθηματικά. Ως παιδί δύο μαθηματικών γονέων, ερωτεύτηκε το θέμα νωρίς. Αλλά παρόλο που διακρίθηκε στο θέμα, τα μαθήματα του γυμνασίου επικεντρώθηκαν στη γερμανική, τη γραφή και τη βιολογία. Επιστρέφοντας στην πρώτη της αγάπη στο κολλέγιο και πέρα ​​από αυτήν, εφάρμοσε τις δεξιότητές της στα μαθηματικά για να κάνει κύματα στην επιστήμη των υπολογιστών.

Σε μια εξαιρετικά επιρροή δουλειά, ο Williams το 2012 βελτίωσε έναν αλγόριθμο για τον “πολλαπλασιασμό των πινάκων” – μια θεμελιώδη λειτουργία σε όλη την επιστήμη των υπολογιστών – που θεωρήθηκε ως η ταχύτερη επανάληψη για 24 χρόνια. Χρόνια αργότερα, συνύπασε ένα αναδυόμενο πεδίο με την ονομασία “λεπτόκοκκο πολυπλοκότητα”, το οποίο επιδιώκει να εξηγήσει, εν μέρει, πόσο γρήγορα ορισμένοι αλγόριθμοι μπορούν να λύσουν διάφορα προβλήματα.

Στον πολλαπλασιασμό των πινάκων, το έργο της έχει μετατοπιστεί ελαφρώς, δείχνοντας ότι οι υπάρχουσες τεχνικές “δεν μπορούν να κάνουν καλύτερα”, λέει. “Δεν μπορούσαμε πλέον να βελτιώσουμε την απόδοση των δικών μας αλγορίθμων, έτσι βρήκαμε τρόπους για να εξηγήσουμε γιατί δεν μπορούσαμε και γιατί και άλλες μέθοδοι δεν μπορούν να βελτιώσουν την απόδοση”.

Διαδρομή προς τα μαθηματικά

Μεγαλώνοντας στη Σόφια της Βουλγαρίας, ο Ουίλιαμς αγάπησε τα μαθηματικά και ήταν ένας ταλαντούχος μαθητής. Αλλά οι γονείς της συχνά υπενθύμισαν ότι η ζωή του μαθηματικού δεν ήταν ακριβώς λαμπερή – ειδικά όταν προσπαθούσε να βρει συναυλίες στην ίδια περιοχή για δύο άτομα. Μερικές φορές ταξίδεψαν εκεί που τα πήγαν οι εργασίες.

Αυτό περιελάμβανε μια σύντομη οδύσσεια γύρω από τις ΗΠΑ ως παιδί. Η πρώτη στάση ήταν ο Laramie, το Wyoming. Οι γονείς της επισκέπτονταν καθηγητές στο Πανεπιστήμιο του Ουαϊόμινγκ, ενώ ο Ουίλιαμς αρχικά αγωνίστηκε στην τέταρτη τάξη λόγω του γλωσσικού φραγμού. “Δεν μίλησα πραγματικά αγγλικά, και ρίχτηκα σε αυτό το σχολείο. Ο αδελφός μου και εγώ μάθαμε αγγλικά παρακολουθώντας το κανάλι της Disney, το οποίο ήταν πολύ διασκεδαστικό “, λέει ο Ουίλιαμς, ο οποίος σήμερα μιλάει βουλγαρικά, αγγλικά, γερμανικά και κάποια ρωσικά.

Η επόμενη στάση ήταν το Λος Άντζελες – ακριβώς την εποχή των αναταραχών του Rodney King. “Το σπίτι στην άλλη πλευρά του δρόμου μας πυροδότησε”, θυμάται ο Ουίλιαμς. «Αυτές ήταν μερικές πολύ περίεργες αναμνήσεις του L.A.”

Επιστρέφοντας στη Βουλγαρία μετά από δύο χρόνια, η Williams αποφάσισε να «εξερευνήσει τις επιλογές της» έξω από τα μαθηματικά εγγράφοντας στο γερμανικό Γυμνάσιο Γυμνασίου στη Σόφια, το κορυφαίο γυμνάσιο της χώρας τότε, όπου σπούδασε γερμανική γλώσσα, λογοτεχνία, ιστορία και άλλα ανθρωπιστικά θέματα. Αλλά, όταν ήρθε στην εφαρμογή στα κολέγια, δεν θα μπορούσε ποτέ να ταρακουνήσει την πρώτη της αγάπη. “Προσπάθησα πραγματικά να αρέσει στις ανθρωπιστικές επιστήμες και αυτό που έμαθα είναι πολύ χρήσιμο για μένα στις μέρες μας. Αλλά αυτά τα θέματα ήταν πολύ δύσκολα για μένα. Το μυαλό μου απλά δεν λειτουργεί έτσι “, λέει. «Επέστρεψα σε ό, τι μου αρέσει».

Διόρθωση με αλγόριθμους

Το 1999, ο Williams εγγράφηκε στο Caltech. Κατά το δεύτερο έτος σπουδών της, χτυπήθηκε από ένα συναρπαστικό νέο πεδίο: την επιστήμη των υπολογιστών. “Πήρα την πρώτη μου σειρά μαθημάτων προγραμματισμού και μου άρεσε πολύ”, λέει.

Έγινε μετασχηματισμός με αλγόριθμους πολλαπλασιασμού μήτρας, οι οποίοι έχουν στον πυρήνα κάποια μαθηματικά βαρέως τύπου. Αυτοί οι αλγόριθμοι υπολογίζουν πολλαπλές συστοιχίες αριθμών που αντιστοιχούν σε μερικά δεδομένα και εξάγουν μία μόνο συνδυασμένη μήτρα μερικών τιμών στόχων. Οι εφαρμογές είναι ευρείας εμβέλειας, συμπεριλαμβανομένων των γραφικών υπολογιστών, του σχεδιασμού προϊόντων, της τεχνητής νοημοσύνης και της βιοτεχνολογίας.

Ως Ph.D. φοιτητής στο Carnegie Mellon και πέρα ​​από αυτήν, δημοσίευσε πολυάριθμα άρθρα σχετικά με θέματα όπως η ανάπτυξη αλγορίθμων πολλαπλασιασμού γρήγορων πινάκων σε ειδικές αλγεβρικές δομές, εφαρμογές που περιλαμβάνουν προγραμματισμό πτήσεων και δρομολόγηση δικτύου. Αφού απέκτησε το διδακτορικό δίπλωμα, πήρε μια σειρά από μεταδιδακτορικές και ερευνητικές θέσεις στο Ινστιτούτο Προχωρημένων Μελετών, στο Πανεπιστήμιο της Καλιφόρνιας στο Μπέρκλεϊ και στο Πανεπιστήμιο του Στάνφορντ, όπου απέκτησε θέση καθηγητή το 2013 διδάσκοντας μαθήματα αλγορίθμων.

Το 2012, ανέπτυξε έναν νέο αλγόριθμο που ήταν ταχύτερος από τον αλγόριθμο Coppersmith-Winograd, ο οποίος είχε βασιλεύσει τον υπέρτατο πολλαπλασιασμό της μήτρας από τη δεκαετία του 1980. Η μέθοδος του Ουίλιαμς μείωσε τον αριθμό των βημάτων που απαιτούνται για τον πολλαπλασιασμό των πινάκων. Ο αλγόριθμός της είναι ελαφρώς πιο αργός από τον τρέχοντα κάτοχο ρεκόρ.

Αντιμετώπιση της πολυπλοκότητας

Από το 2010 έως το 2015, ο Williams και ο σύζυγός του, Ryan Williams, ο οποίος είναι επίσης καθηγητής του MIT, έγιναν βασικοί ιδρυτές της «λεπτόκοκκης πολυπλοκότητας». Το παλαιότερο πεδίο της «υπολογιστικής πολυπλοκότητας» βρίσκει αποδεδειγμένα αποτελεσματικούς αλγορίθμους και αλγόριθμους, με βάση κάποιο κατώφλι των υπολογιστικών βημάτων που παίρνουν για να λύσουν ένα πρόβλημα.

Η λεπτή πολυπλοκότητα ομαδοποιεί τα προβλήματα μαζί με την υπολογιστική ισοδυναμία για να αποδείξει καλύτερα αν οι αλγόριθμοι είναι πραγματικά βέλτιστοι ή όχι. Για παράδειγμα, δύο προβλήματα μπορεί να φαίνονται πολύ διαφορετικά σε αυτό που επιλύουν και πόσες αλγορίθμους βήματα παίρνουν για να τα λύσουν. Αλλά η λεπτή πολυπλοκότητα δείχνει ότι τέτοια προβλήματα είναι μυστικά τα ίδια. Επομένως, εάν υπάρχει ένας αλγόριθμος για ένα πρόβλημα που χρησιμοποιεί λιγότερα βήματα, τότε πρέπει να υπάρχει ένας αλγόριθμος για το άλλο πρόβλημα που χρησιμοποιεί λιγότερα βήματα και αντίστροφα. Από την άλλη πλευρά, εάν υπάρχει ένας βολικά βέλτιστος αλγόριθμος για ένα πρόβλημα, τότε όλα τα ισοδύναμα προβλήματα πρέπει να έχουν βέλτιστους αλγόριθμους. Εάν κάποιος βρει ποτέ έναν πολύ πιο γρήγορο αλγόριθμο για ένα πρόβλημα, όλα τα ισοδύναμα προβλήματα μπορούν να επιλυθούν γρηγορότερα.

Από την εκτόξευση του πεδίου, “είναι μπαλόνι”, λέει ο Williams. “Για τα περισσότερα θεωρητικά συνέδρια για την επιστήμη των υπολογιστών, μπορείτε να υποβάλετε τώρα το χαρτί σας κάτω από την επικεφαλίδα” λεπτόκοκκο πολυπλοκότητα “.”

Το 2017, ο Ουίλιαμς ήρθε στο MIT, όπου λέει ότι βρήκε παθιασμένους, ομοϊδεάτες ερευνητές. Πολλοί μεταπτυχιακοί φοιτητές και συνεργάτες, για παράδειγμα, εργάζονται σε θέματα που σχετίζονται με την λεπτή πολυπλοκότητα. Με τη σειρά της, οι φοιτητές της την έχουν εισαγάγει σε άλλα θέματα, όπως η κρυπτογραφία, όπου εισάγει τώρα ιδέες από λεπτόκοκκο πολυπλοκότητα.

Επίσης μελετά μερικές φορές “υπολογιστική κοινωνική επιλογή”, ένα πεδίο που έπεσε το μάτι της κατά τη διάρκεια της μεταπτυχιακής της σχολής. Το έργο της επικεντρώνεται στην εξέταση της υπολογιστικής πολυπλοκότητας που απαιτείται για την τοποθέτηση αθλητικών παιχνιδιών, προγραμμάτων ψηφοφορίας και άλλων συστημάτων όπου οι ανταγωνιστές τοποθετούνται σε ζευγμένες αγκύλες. Αν κάποιος ξέρει, για παράδειγμα, ποιος παίκτης θα κερδίσει σε ζευγάρια, ο διοργανωτής του τουρνουά μπορεί να τοποθετήσει όλους τους παίκτες σε συγκεκριμένες θέσεις κατά την αρχική σπορά για να εξασφαλίσει ότι ένας συγκεκριμένος παίκτης κερδίζει όλα.

Η προσομοίωση όλων των πιθανών συνδυασμών για την εγκατάσταση αυτών των σχημάτων μπορεί να είναι πολύ υπολογιστικά πολύπλοκη. Όμως ο Ουίλιαμς, ένας άπληστος παίκτης τενίστας, γράφει ένα χαρτί 2010 (PDF) που βρήκε ότι είναι αρκετά απλό να τερματίζει ένα τουρνουά αποκλεισμού, έτσι κερδίζει ένας συγκεκριμένος παίκτης, ανάλογα με τις ακριβείς προβλέψεις για τους νικητές και άλλους παράγοντες.

Αυτή τη χρονιά συνέγραψε ένα έγγραφο (PDF) που έδειξε ότι ένας διοργανωτής του τουρνουά θα μπορούσε να κανονίσει μια αρχική σπορά και να δωροδοκήσει ορισμένους κορυφαίους παίκτες – μέσα σε ένα συγκεκριμένο προϋπολογισμό – για να εξασφαλίσει ότι ο αγαπημένος παίκτης κερδίζει το τουρνουά. «Όταν χρειάζομαι ένα διάλειμμα από το συνηθισμένο έργο μου, δουλεύω σε αυτόν τον τομέα», λέει ο Williams. “Είναι μια διασκεδαστική αλλαγή του ρυθμού.”

Χάρη στην πανταχού παρούσα υπολογιστική σήμερα, οι μεταπτυχιακοί φοιτητές της Williams εισέρχονται συχνά στην τάξη της πολύ πιο έμπειρη στην επιστήμη των υπολογιστών από ό, τι ήταν στην ηλικία τους. Αλλά για να τους οδηγήσει σε ένα ξεχωριστό μονοπάτι, αντλεί έμπνευση από τις δικές της εμπειρίες στο κολέγιο, που γαντζώθηκε σε συγκεκριμένα θέματα που εξακολουθεί να επιδιώκει σήμερα.

“Για να κάνετε καλή έρευνα, πρέπει να ασχοληθείτε με ένα πρόβλημα”, λέει ο Williams. “Θέλω να βρουν κάτι στην πορεία μου μπορούν να εμμονές πάνω.”

Πατήστε εδώ για να συνεχίσετε

ΑΦΗΣΤΕ ΜΙΑ ΑΠΑΝΤΗΣΗ

Please enter your comment!
Please enter your name here