Antické algoritmy: Co nám egyptské zlomky říkají o moderním programování

Kdykoli napíšete rekurzivní funkci nebo implementujete greedy algorithm, jdete ve stopách matematiků, kteří žili před tisíci lety. Egyptské zlomky — matematické výrazy používající pouze převrácené hodnoty celých čísel — představují jeden z nejstarších zdokumentovaných algoritmů v historii lidstva. A jsou daleko sofistikovanější, než se na první pohled zdá.

Problém, který Egypťané řešili

Moderní zlomky nám přijdou přirozené: 3/7, 5/12, 17/23. Jenže tato notace se v Evropě běžně nepoužívala až do 18. století. Předtím, pokud jste chtěli vyjádřit zlomek, museli jste ho rozložit na součet jednotkových zlomků — tedy zlomků s jedničkou v čitateli.

Egypťané čelili praktické výzvě: jak spravedlivě rozdělit 7 bochníků chleba mezi 8 lidí? Řešení rozhodně nebylo jednoduše napsat 7/8. Místo toho vyjádřili tento zlomek jako součet různých jednotkových zlomků: 1/2 + 1/4 + 1/8.

Tento na první pohled jednoduchý přístup vyžadoval promyšlené matematické myšlení a dal vzniknout tomu, co dnes nazýváme egyptský zlomkový algoritmus.

Greedy algorithm, staroegyptským způsobem

Tady to začíná být zajímavé pro vývojáře. Metoda, kterou Egypťané používali k převodu jakéhokoli zlomku na egyptský zlomek, je v podstatě greedy algorithm — vyber největší možný jednotkový zlomek, odečti ho a opakuj.

Vezměme si 4/23. Algoritmus se ptá: jaké je nejmenší celé číslo větší než 23/4? Je to 6. Takže začínáme s 1/6, odečteme ho od 4/23, dostaneme 1/138 a jsme hotoví: 4/23 = 1/6 + 1/138.

Tento postup funguje vždy — jde o matematickou větu dokázanou v roce 1880, přestože Evropané tuto techniku znali už od Fibonacciho ve 12. století.

Proč by to mělo zajímat dnešní programátory

Na první pohled to vypadá jako historická zajímavost. Ale zamyslete se nad tím, co se v tom algoritmu děje:

1. Rekurzivní dekompozice — rozložte komplexní problém na jednodušší dílčí problém
2. Greedy výběr — v každém kroku učiňte optimální lokální rozhodnutí
3. Důkaz ukončení — zbytek se vždy zmenšuje, což garantuje dokončení

Tyto koncepty jsou základem moderního algoritmického myšlení. Když píšete rekurzivní funkci, aplikujete stejnou logickou strukturu, jakou používali tito antičtí matematici.

Historický paradox

Tady je třeba zmínit nepohodlnou historii. Egyptská metoda zlomků předchází řecké matematice o tisíciletí. Přesto když evropští matematici v 19. století „znovuobjevili" Rhindův papyrus, byla technika často přisuzována řeckým učencům místo skutečným tvůrcům ze starověkého Egypta.

Tento vzorec — kdy jsou příspěvky afrických a dalších neevropských civilizací minimalizovány nebo vymazány z matematických dějin — přetrvává dodnes v tom, jak vyučujeme a diskutujeme počítačovou vědu.

Matematická záhada

Jedna fascinující hádanka zahrnuje to, co někteří badatelé nazývají „egyptská trojice": 13, 17 a 173. Když je interpretujeme jako 3 + 1/13 + 1/17 + 1/173, tento výraz aproximuje π na čtyři desetinná místa — přesněji než běžně uváděná egyptská hodnota 3,16.

Zda to bylo záměrné nebo náhoda, zůstává mezi historiky matematiky předmětem debat.

Od starověku k moderní době

Egyptské zlomky souvisejí s řetězovými zlomky, tématem, které se stále studuje v informatice a teorii čísel. Přístup greedy algorithm má moderní aplikace v problémech zabývajících se alokací zdrojů, plánováním a optimalizací.

Takže až budete příště ladit rekurzivní funkci nebo vysvětlovat, proč greedy přístup funguje, vzpomeňte si: účastníte se matematické tradice, která sahá téměř 4000 let zpátky.

Někdy jsou ty nejstarší algoritmy stále tím nejlepším řešením.