Αρχαίοι Αλγόριθμοι: Τι Μας Διδάσκουν τα Αιγυπτιακά Κλάσματα για την Πληροφορική

Κάθε φορά που γράφεις μια recursive συνάρτηση ή υλοποιείς έναν greedy algorithm, βαδίζεις στα χνάρια μαθηματικών που έζησαν χιλιάδες χρόνια πριν. Τα αιγυπτιακά κλάσματα—μαθηματικές εκφράσεις που χρησιμοποιούν μόνο αντίστροφα ακέραιων αριθμών—αντιπροσωπεύουν έναν από τους παλαιότερους καταγεγραμμένους αλγορίθμους στην ιστορία της ανθρωπότητας. Και είναι πολύ πιο εξελιγμένα απ' ό,τι φαίνονται με την πρώτη ματιά.

Το Πρόβλημα που Λύσαν οι Αιγύπτιοι

Τα σύγχρονα κλάσματα μας φαίνονται φυσικά: 3/7, 5/12, 17/23. Όμως αυτός ο συμβολισμός δεν ήταν διαδεδομένος στην Ευρώπη μέχρι τον 18ο αιώνα. Πριν από αυτό, αν ήθελες να εκφράσεις ένα κλάσμα, έπρεπε να το αναλύσεις σε άθροισμα μοναδιαίων κλασμάτων—κλασμάτων με τον αριθμητή 1.

Οι Αιγύπτιοι αντιμετώπιζαν ένα πρακτικό πρόβλημα: πώς μοιράζεις δίκαια 7 καρβέλια ψωμί σε 8 ανθρώπους; Η απάντηση δεν ήταν απλά να γράψεις 7/8. Αντίθετα, το εξέφραζαν ως άθροισμα διακριτών μοναδιαίων κλασμάτων: 1/2 + 1/4 + 1/8.

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

Ο Greedy Algorithm με Αρχαίο Στυλ

Εδώ γίνεται ενδιαφέρον για εμάς τους developers. Η μέθοδος που χρησιμοποιούσαν οι Αιγύπτιοι για να μετατρέψουν οποιοδήποτε κλάσμα σε αιγυπτιακό κλάσμα είναι ουσιαστικά ένας greedy algorithm—διάλεξε το μεγαλύτερο δυνατό μοναδιαίο κλάσμα, αφαίρεσέ το, και επανάλαβε.

Πάρε το 4/23. Ο αλγόριθμος ρωτάει: ποιος είναι ο μικρότερος ακέραιος μεγαλύτερος από 23/4; Είναι το 6. Οπότε ξεκινάμε με 1/6, αφαιρούμε από το 4/23, παίρνουμε 1/138, και τελειώσαμε: 4/23 = 1/6 + 1/138.

Αυτή η προσέγγιση λειτουργεί πάντα—ένα μαθηματικό θεώρημα που αποδείχθηκε το 1880, παρόλο που οι Ευρωπαίοι γνώριζαν την τεχνική από τον Fibonacci τον 12ο αιώνα.

Γιατί Έχει Σημασία για τους Σύγχρονους Developers

Με την πρώτη ματιά, αυτό μοιάζει με ιστορικό ανέκδοτο. Αλλά σκέψου τι συμβαίνει μέσα σε αυτόν τον αλγόριθμο:

1. Recursive decomposition — Σπάσε ένα πολύπλοκο πρόβλημα σε ένα απλούστερο υποπρόβλημα
2. Greedy selection — Κάνε την τοπικά βέλτιστη επιλογή σε κάθε βήμα
3. Termination proof — το υπόλοιπο μικραίνει πάντα, εγγυώμενο την ολοκλήρωση

Αυτές οι έννοιες αποτελούν τη βάση της σύγχρονης αλγοριθμικής σκέψης. Όταν γράφεις μια recursive συνάρτηση, εφαρμόζεις την ίδια λογική δομή που χρησιμοποιούσαν αυτοί οι αρχαίοι μαθηματικοί.

Ένα Ιστορικό Κενό

Υπάρχει μια άβολη ιστορία εδώ που αξίζει να αναγνωρίσουμε. Η μέθοδος αιγυπτιακών κλασμάτων προηγείται κατά χιλιετίες της ελληνικής μαθηματικής παράδοσης. Όμως όταν οι ευρωπαίοι μαθηματικοί "ανακάλυψαν ξανά" τον Πάπυρο του Rhind τον 19ο αιώνα, η τεχνική συχνά αποδιδόταν σε Έλληνες μελετητές αντί για την πραγματική της προέλευση στην αρχαία Αίγυπτο.

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

Μαθηματικά Μυστήρια

Ένα συναρπαστικό παζλ αφορά αυτό που μερικοί μελετητές αποκαλούν "αιγυπτιακό τρίγωνο": 13, 17 και 173. Όταν ερμηνεύεται ως 3 + 1/13 + 1/17 + 1/173, αυτή η έκφραση προσεγγίζει το π με τέσσερα δεκαδικά ψηφία—πιο ακριβώς από την ευρέως αναφερόμενη αιγυπτιακή τιμή του 3,16.

Αν αυτό ήταν ηθελημένο ή σύμπτωση παραμένει αμφιλεγόμενο μεταξύ των ιστορικών των μαθηματικών.

Από τους Αρχαίους στους Σύγχρονους

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

Λοιπόν, την επόμενη φορά που θα κάνεις debug μια recursive συνάρτηση ή θα εξηγείς γιατί λειτουργεί μια greedy προσέγγιση, θυμήσου: συμμετέχεις σε μια μαθηματική παράδοση που εκτείνεται σχεδόν 4.000 χρόνια πίσω.

Μερικές φορές οι παλαιότεροι αλγόριθμοι παραμένουν οι καλύτεροι αλγόριθμοι.