i i “Kovic” — 2016/1/11 — 7:39 — page 227 — #1 i i i i i i The Art Of Computer Programming Donald E. Knuth: The Art Of Computer Programming, Volume 4, Generating All Trees, History of Combinatorial Generation, Fascicle 4, Courier Corporation plant in Stoughton, Massachusets, januar 2006, 120 strani. Knjižica, v kateri so opisani raz- lični algoritmi za generiranje dre- ves, predstavljena pa je tudi zgo- dovina generiranja različnih kom- binatoričnih struktur, je le eden od mnogih zvezkov, s katerimi Donald E. Knuth, znan daleč po svetu po svojem pionirskem delu na podro- čju algoritmov in programerskih tehnik, po svoji iznajdbi TeXa in METAFONTa, ter kot ploden in vpliven pisec, zaslužni profesor Umetnosti računalnǐskega progra- miranja na Univerzi Stanford, suk- cesivno dopolnjuje, razširja in zao- krožuje svoje veličastno delo Ume- tnost računalnǐskega programira- nja, ki ga je začel pisati leta 1962. Knuthovo pisanje je deležno sogla- snega občudovanja strokovnjakov ne le zaradi svoje tehtnosti, am- pak tudi zaradi slogovnih odlik: lepote in elegance njegovih analiz, jasnosti in natančnosti njegovih razlag ter lucidnosti njegovih komentarjev. Kot pravi avtor sam, si je, potem ko je v preǰsnjih zvezkih obravnaval generiranje drugih kombinatoričnih struktur (npr. permutacij, kombinacij in particij), najbolǰse, generiranje dreves, prihranil za konec. Teorija dre- ves, ene ključnih diskretnih struktur, povezuje koncepte različnih vidikov računalnǐskega programiranja, probleme generiranja vseh dreves določenega razreda (npr. na n vozlǐsčih) pa so v primerjavi s problemi generiranja dru- gih kombinatoričnih struktur, ki so jih v različnih oblikah obravnavali že v številnih starodavnih kulturah (Indija, Kitajska, Japonska, stara Grčija, itd.), matematiki in računalnǐski strokovnjaki začeli intenzivno obravnavati šele po letu 1950. Pred tem so se z enumeriranjem vseh dreves določenega razreda ukvarjali le zelo redki, npr. Arthur Cayley je leta 1875 v svojem veli- Obzornik mat. fiz. 62 (2015) 6 227 i i “Kovic” — 2016/1/11 — 7:39 — page 228 — #2 i i i i i i Nove knjige kem delu o drevesih podal diagrame vseh binarnih dreves s tremi notranjimi vozlǐsči in štirimi listi. Algoritme za generiranje vseh vpetih dreves danega grafa so razvili številni avtorji po letu 1950, prvotna motivacija zanje pa je bilo raziskovanje električnih omrežij. Knjižica je pisana na kožo tako računalnǐskim strokovnjakom kot tudi tistim, ki jih navdušuje zgodovina matematičnih znanosti. Brez dolgoveze- nja in okolǐsenja začne z razlago temeljne zveze med »pravilno vgnezdenimi oklepaji« in drevesi, po kateri je vsak par ustrezajočih si oklepajev (ki mu ustreza neko vozlǐsče prirejenega drevesa) kodiran z zaporednima številkama levega oklepaja »(« in desnega oklepaja »)«. Tabela s 14 različnimi pravilno vgnezdenimi štirimi pari oklepajev in ustreznimi drevesi ter izomorfnimi strukturami prikaže tudi različne načine njihovega kodiranja. Zanimiva izo- morfna struktura so hkratna rokovanja 2n ljudi za okroglo mizo, pri katerih noben od n parov, ki si seže v roke, ne zmoti rokovanja nobenega drugega para. Po vrsti spoznamo algoritem za leksikografsko urejanje vgnezdenih okle- pajev, algoritem za generiranje binarnih dreves, pa tudi algoritme po vzoru Grayeve kode, ki generirajo vsa možna drevesa tako, da od vsakega ge- neriranega drevesa preidemo k naslednjemu le z majhno perturbacijo. Pre- gledu nekaterih ključnih dejstev o Catalanovih številih, ki ustrezajo številom objektov, dobljenih v teh algoritmih, sledi zanimiv odlomek o slučajno gene- riranih drevesih ter analiza tako imenovanega »vzorca božičnega drevesa«, v katerem so razporejena vsa dvojǐska zaporedja dolžine n natanko enkrat tako, da se zaporedja z istim številom enk pojavijo v istem stolpcu, in da se v vsaki vrstici zaporedni dvojǐski zaporedji razlikujeta le na enem mestu. Število vrstic takega božičnega drevesa reda n (ki ga je mogoče brez težav določiti) natančno ustreza velikosti največje antiverige podmnožic množice {1, 2, . . . , n}, znane iz izreka Emanuela Spernerja (1928). Teoretičnemu in zgodovinskemu delu sledijo številne naloge. Prvi del teh nalog bralcu pomaga razumeti in osvojiti strokovni, algoritemski del knjige; drugi del teh nalog pa je namenjen temu, da se vživimo v način razmǐsljanja matematikov (in drugih učenjakov, npr. gramatikov, ki so iskali vse možne ritmične različice sanskrtskih ali starogrških verzov, ali glasbenih teoretikov, ki so iskali vse možne sezname melodičnih linij iz danih različnih tonov), ki so prvi razmǐsljali o posameznih problemih, in da razumemo, da so bili različni koncepti in postopki v zvezi z generiranjem kombinatoričnih struktur, ki se morda danes zdijo enostavni, v svojih začetkih velik izziv celo za največje ume tistega časa. 228 Obzornik mat. fiz. 62 (2015) 6 i i “Kovic” — 2016/1/11 — 7:39 — page 229 — #3 i i i i i i The Art Of Computer Programming V zgodovinskem delu knjižice, za katerega Knuth pravi, da se je ob njego- vem raziskovanju naučil veliko zanimivega o človeku in njegovi kulturi, nam predstavi zelo zanimive in davne primere generiranja in enumeriranja različ- nih kombinatoričnih objektov, npr. 64 heksagramov (ki ustrezajo binarnim zaporedjem dolžine 6) iz slavne knjige I Ching (Knjiga sprememb), ene od petih klasičnih del konfucijanske modrosti, pa 52 diagramov (imenovanih po 52 poglavjih znanega literarnega dela japonske pisateljice Murasaki Šikubu: Zgodba o Genjiju iz 11. stoletja), ki ustrezajo različnim razdelitvam množice {1, 2, 3, 4, 5} v njene podmnožice (in katerih stilizirane variante je mogoče najti v standardnih katalogih kimono vzorcev v 20. stoletju), pa 56 različnih zaporedij treh metov kock, ki jih je, ker je bilo sicer priljubljeno kockanje du- hovnikom prepovedano, škof Wibold iz Cambraja iz severne Francije povezal s posameznimi vrlinami (npr. 111 = ljubezen, 112 = vera, 113 = upanje, itd.) ter tako izumil nekakšno igro zbiranja vrlin (Ludus clericalis), ki pa so jo smeli igrati in se jim tako ni bilo treba odreči metanju kock. Zanimiv je tudi problem, ki ga je neuspešno reševal celo Leibniz, in sicer, koliko je permutacij besed nekega latinskega verza, ki ustrezajo tudi določenim rit- mičnim omejitvam, ki so veljale za latinske verze. Problem je uspešno rešil šele James Bernoulli v svojem inavguracijskem govoru leta 1692. Knuth v zvezi s tem navaja tudi zanimiv Bernoullijev citat: »Celo najmodreǰsi in najbolj bistri ljudje včasih trpijo za nečim, kar Logiki imenujejo nezadostna enumeracija primerov.« Knjižica, ki mi je prǐsla v roke po naključju (tako se dostikrat, po nedo- umljivi igri naključja, zgodi s knjigami, ki so nam najbolj všeč!), mi je po eni strani zelo približala računalnǐsko programiranje, me je pa tudi izredno prijetno presenetila v svoji zgodovinski, humanistični dimenziji, saj prepri- čljivo kaže, da tudi vrhunska matematična oziroma računalnǐska strokovnost ni nezdružljiva z zgodovinsko analizo. Še en lep dokaz, da naši morebitni predsodki o tistem, česar ne poznamo dovolj, niso vredni, da jih obdržimo in cenimo kot nekaj vrednega. Če bi namreč vztrajal pri svojem predsodku, da takšna knjiga že ne more biti zanimiva, bi bil prikraǰsan za prebiranje navdihujočih misli, kot so npr.: »Za globlje razumevanje je koristno štu- dirati rekurzivno strukturo v osnovi algoritma P«, ali: »Povprečna oblika naključno generiranega binarnega drevesa je približno enaka spodnji polo- vici elipse.« Takšnih stavkov je v knjigi še veliko. Veselim se že branja tudi drugih Knuthovih del, omenjeno knjižico pa priporočam vsem bralcem, ki imajo radi računalnǐstvo in zgodovino matematike! Jurij Kovič Obzornik mat. fiz. 62 (2015) 6 229