Glazba je NP-potpun problem

A few years ago someone asked Steven Rudich, a complexity theorist at Carnegie-Mellon, why he thought P is different than NP. He replied “I can recognize great music but I can’t create great music,” the implication being that it’s much harder to find a solution than to verify one.

– Lance Fortnow, stručnjak za teorijsko računarstvo

Najvažniji i najpoznatiji neriješeni matematički problem glasi: je li P = NP? Problem se, grubo rečeno, svodi na sljedeće: ako je u nekom kombinatornom zadatku moguće brzo provjeriti rješenje (NP), je li ga moguće brzo i pronaći (P)? Primjer je, recimo, problem trgovačkog putnika: ako je zadan popis od stotinu gradova i cijene putovanja između svakog para gradova, je li moguće s ukupno C eura obići sve gradove? Za bilo koju odabranu rutu (redoslijed posjećivanja gradova) moguće je lako provjeriti je li cijena zadovoljavajuća, ali jako je teško pronaći jeftinu rutu jer broj mogućih redoslijeda daleko premašuje broj atoma u svemiru. Zato vjerujemo da je P ≠ NP.

Kakve to veze ima s glazbom? Grubo rečeno, melodija je ruta, redoslijed tonova. Za dobru melodiju u dobroj pjesmi lako čujemo da je dobra: uvlači nas i čini da se dobro osjećamo. Evaluacija je vrlo izravna i primitivna, nema promišljanja ili traženja razloga zašto je neka glazba dobra, to prepoznajemo instinktivno. (Taj instinkt nije jednak kod svakog, pa ni ista pjesma neće svakom biti dobra, ali nema veze: dovoljno je promatrati sebe, tj. samo vlastiti ukus.) Moj mozak može, dakle, “provjeriti” vrhunsku pjesmu – uz dovoljno vremena mogu je i odsvirati, razumjeti akorde i ostale komponente od kojih je sastavljena, tako da u njoj ne ostane ništa skriveno – ali ne mogu obrnuti taj proces, ne mogu skladati vrhunsku pjesmu. Neki mogu, ali rijetko, i ne kad im se prohtije: svi imaju neki vrhunac koji poslije ne mogu ponoviti. Evo što je rekao najveći:

“I tell students all the time, ‘Look, I don’t know how to do this,’” he said, mentioning that “Yesterday” came to him in a dream. “Every time I approach a song, there’s no rules. Sometimes the music comes first, sometimes the words – and if you’re lucky, it all comes together.”

– Paul McCartney (za rollingstone.com)

A riječ je o kombinatornom problemu, jer melodije (a i tekstovi) samo su nizovi koji se slažu od nekoliko osnovnih kockica, dakle, ima ih konačno mnogo i teoretski, uz neograničeno mnogo vremena, mogli bismo ih sve generirati i isprobati. Dobar skladatelj, dakle, pronalazi dobre vektore u višedimenzionalnom prostoru mogućih skladbi. Tehnike kojima to radi očito su heuristike: rijetko daju optimalno rješenje, ali ponekad – ne uvijek – daju dobra rješenja. Upravo tako u praksi rješavamo i NP-potpune probleme poput gore spomenutog trgovačkog putnika.

Ovaj argument – grub i neformalan, ovo je ionako poetičan blog – može ići u oba smjera:

  1. Težina skladanja sugerira da je P ≠ NP.
  2. Budući da (neovisno o glazbi) imamo dobre razloge vjerovati da je P ≠ NP, skladanje je vjerojatno teško.

Neki će ovdje pomisliti na umjetnu inteligenciju koja sklada. Ne znam… Kad me to dotakne kao prava glazba, možemo razgovarati. Sumnjam da će se to dogoditi.

Računalo i šah

Šahovski svijet ovih dana bruji o potencijalnom varanju stanovitog velemajstora. Postoje statistički indikatori varanja, korišteni ponajviše od stranica za online igranje poput chess.com, koji mjere koliko se potezi igrača podudaraju s potezima koje bi u istoj poziciji igrali šahovski programi (koji su odavno daleko nadmašili ljudske prvake). Ispada da rezultati mogu biti kontroverzni: dok stručnjak za šahovsko varanje Ken Regan ne pronalazi ništa sumnjivo u partijama Hansa Niemanna, analize od prije nekoliko dana koje kolaju društvenim mrežama upućuju na suprotno, tj. na neobično veliku podudarnost s računalom u nekim njegovim partijama.

Htio sam staviti nekoliko poveznica, ali ima toliko toga da ne znam odakle bih počeo, pa je najbolje ostaviti ovaj tekst čistim od linkova i skočiti na zaključak – jumping to conclusions! A praktični zaključak glasi: tko god je sklon statistici, može napraviti doktorat o detekciji varanja u šahu na osnovi poteza, jer to se područje očigledno tek razvija. Štoviše, čini mi se relativno jednostavno napisati nekakav znanstveni rad iz ovog područja. Zašto? Postoji stotinu načina da mjerimo performans igrača i uspoređujemo ga sa strojem; dovoljno je od golemih mogućnosti skrojiti neku metriku, ili nekoliko njih, koja daje dobre rezultate na bazama šahovskih partija. Tanak sam s vremenom, ali neću se žaliti ako mi se javi netko tko želi surađivati i odraditi dosadniji dio posla – istraživanje dosadašnjih radova, usporedba s postojećim mjerama, bla bla – a ja da pomognem s idejama 😀 😀

Ipak, osobno me više privlači nešto mnogo beskorisnije, nešto što su drugi već napravili i to daleko bolje – izrada programa koji dobro igra šah. Recimo, bolje od mene – s tim bih bio sasvim zadovoljan. To bih radio iz čiste zabave, kao lijep, težak i prilično bogat programerski izazov. Bogat u smislu različitih podizazova koji se javljaju: od optimizacije utroška vremena i memorije, do samog algoritma, redoslijeda pretraživanja pozicija i rezanja grana (pruning) te ključnog i najtežeg dijela – evaluacije pozicije. Nije lako ni odabrati jezik: program u C++-u bio bi daleko brži od onog u Pythonu, ali u Pythonu je brže i ljepše programirati, a budući da sve to radim iz gušta, moj je odabir jasan… Jedini je uvjet da ne koristim nikakve postojeće šahovske biblioteke. Ali smijem koristiti baze šahovskih partija!

Za one koji ne znaju, a zanima ih, pokušat ću ugrubo objasniti kako računalo igra šah.

Za početnu ilustraciju odaberimo jednostavniju igru: kružić-križić. U bilo kojoj poziciji ove igre možemo razmišljati ovako: ako ja odigram ovo, što će protivnik igrati? Ako on odigra ovo, što ću nakon toga ja igrati? Ako ja na to odigram ovo, što će onda on… I tako dalje, sve do kraja, do pozicije gdje je jasan pobjednik (ili je neriješeno). Kada postoji više mogućih odgovora, treba isprobati sve “grane stabla”. Uz dovoljno vremena i papira možemo nacrtati sve dohvatljive pozicije i točno znati što treba igrati da bismo zajamčili pobjedu ili izbjegli poraz. Tako će, naravno, igrati i računalo.

U šahu se primjenjuje sličan postupak, ali postoji velika razlika. U križić-kružiću već nakon nekoliko poteza dolazimo do kraja, do pozicije za koju znamo ishod (pobjeda/poraz/neriješeno). U šahu je broj pozicija prevelik i analiza ne može doći do kraja. Možda možemo pregledati sve pozicije do kojih možemo doći nakon jednog, dva, tri, četiri i pet poteza – ali u nekom trenutku moramo stati jer smo vremenski i memorijski ograničeni. Mnoge od predviđenih pozicija neće biti ništa jasnije, ništa bliže završetku partije od pozicije u kojoj se trenutačno nalazimo. Što onda?

Dolazimo do ključnog dijela šahovskog programa, a to je evaluacija pozicije. Kad provjerava neku poziciju, ako se više nema vremena granati, program mora na drugi način ocijeniti koliko je ta pozicija poželjna. Ta procjena bit će neki broj: recimo, od -10 do 10, gdje nula znači da su snage izjednačene, pozitivan broj znači prednost bijeloga, a negativan broj prednost crnoga. Ali kako se on računa? Program Stockfish procjenjuje poziciju zbrajajući elemente za koje iskustvo kaže da su važni: vrijednosti figura, sigurnost kralja, struktura pješaka, kontrola središta ploče, napadanja, odmakli pješaci itd. Težinski parametri u formuli podešavaju se strojnim učenjem na osnovi goleme baze partija šahovskih velemajstora – za koje znamo kako su završile, pa za sve pozicije koje su se javile u tim partijama znamo kakav je bio njihov ishod. Općenito, u takav program ugrađeno je mnogo ljudskog znanja o šahu. To nije slučaj s još boljim programima kao što je AlphaZero koji ne koristi nikakvo ljudsko znanje o šahu (osim samih pravila). On poziciju ubacuje u golemu formulu koja ljudskom oku nije razumljiva – neuronsku mrežu – čije brojeve podešava kad sazna je li pogriješio, a uči igrajući sam protiv sebe.

To su osnovne ideje u pozadini šahovskih programa. Naravno, preskočili smo mnoge detalje, ali kraće je slađe. Ne znam hoću li se na kraju upustiti u programiranje ovako nečega, ali ako se netko želi natjecati, možda me to dodatno motivira… 😉

Što čini (dobru) križaljku?

Odijelo ne čini čovjeka. Ali što čini križaljku?

Ljeto je odmor za dušu i tijelo pa se vraćam na matematičke teme. Tu mislim na matematiku u širem smislu, jer križaljka i žongliranje riječima nisu drugo nego lijepa jezična kombinatorika. Pokušavam napraviti program koji će iz liste riječi hrvatskog (ili nekog drugog) jezika složiti križaljku. To nije nimalo jednostavno i trenutačno je moj program poprilično lošiji od ljudskih majstora enigmatičara. Mogu li ih sustići?

Da bismo osvijestili u čemu je stvar, potrudio sam se na jednom mjestu prikupiti komponente koje su važne za dobru križaljku. One nisu međusobno neovisne, nego uglavnom jedna podupire drugu, ali vrijedi razmotriti svaku ponaosob.

  • Broj crnih polja. Riječ je o “praznim” poljima koja u križaljci razdvajaju riječi (ostala polja sadrže slova). Ovo je osnovna i najlakše uočljiva metrika. Cilj je, naravno, da ih bude što manje. Enigmatičari lako dođu do cca 12%, a ispod 10% je majstorstvo.
  • Duljina riječi. Križaljka je ljepša i zanimljivija što su u njoj dulji pojmovi. Dobra križaljka često će imati nekoliko dugačkih pojmova koji prolaze cijelom križaljkom ili njenim većim dijelom. Također se gleda prosječna duljina riječi. Što dulje, to bolje! Ako je mnogo kratkih riječi (od 1-3 slova), to kvari dojam. S tim u vezi se, primjerice, u dobroj križaljci izbjegavaju jednoslovi i dvoslovi, koji se obično opisuju nekom pokratom ili inicijalima neke poznate ili ne baš poznate osobe.
  • Velike bjeline. Riječ je o nekom dijelu križaljke koji sadrži samo slova, tj. nema crnih polja. Jako je teško dobiti veliku bjelinu! Primjerice, na slici je križaljka Nebojše Dragomirovića – sastavljena na natjecanju unutar 2.5 sata – koja u sredini ima bjelinu dimenzija 6 x 7:
  • Prožetost. Dijelovi križaljke trebaju biti biti dobro povezani. To recimo znači da se izbjegavaju lanci crnih polja koji bi razdvojili križaljku na slabo povezana područja. Primjerice, ako imamo veći broj crnih polja poredanih dijagonalno, onda pojmovi s jedne i druge njihove strane nisu povezani – ne čine cjelinu, nego se križaljka raspada na dvije manje.
  • Zanimljivost sadržaja. Aktualni, a ne zastarjeli pojmovi; poznate osobe, mjesta, filmovi; zanimljive fraze (npr. krokodilske suze); uporaba niskofrekventnih pojmova umjesto onih koji su u križaljkama česti; tematske križaljke s većim brojem srodnih pojmova; izbjegavanje ponavljanja iste riječi ili korijena riječi (npr. Francis i Francuska).
  • Rješivost, izbjegavanje vrlo opskurnih pojmova; normiranost riječi (nominativ, infinitiv i slično).

Ovo nije sve; moguće je u križaljci biti kreativan na razne načine, primjerice u njenom obliku ili nekoj lijepoj pravilnosti rasporeda crnih polja. A o programu koji pokušavam napraviti i njegovom algoritmu, koji će vjerojatno ostati nedorastao većini ovih zahtjeva, bit će riječi u nekoj od idućih objava. Kao što bi rekao Robert Wyatt, if you’re still there – stay tuned!

I tako sve

Kad sam bio mali, imali smo neku ogromnu debelu ilustriranu enciklopediju na njemačkom. Nisam znao njemački, ali listajući i gledajući te slike zaključio sam da je to knjiga o svemu. Mislio sam to sasvim doslovno: bio sam uvjeren da na svijetu ne postoji pojam kojeg nema u toj knjizi. Kad smo u školi počeli čitati prve knjige, pa su neki pričali da doma imaju knjigu o ovome ili onome, ja sam se hvalio da imam knjigu o SVEMU. Baš svemu. To nije bilo moguće nadmašiti. “Jeste li čuli, Satja ima knjigu o SVEMU!”

S vremenom, sam, naravno, spoznao onu Hamletovu (“There are more things in heaven and earth, Horatio, than are dreamt of in your philosophy“) i shvatio da ta knjiga ne može biti baš o svemu.

Neki filozofi (poput Davida Lewisa) tvrde da postoji baš sve što je moguće, drugim riječima, postoje svi mogući svjetovi. To bi čak moglo vrijediti ako je naš svemir samo divovska matematička struktura i ako on postoji naprosto zato što sve konzistentne matematičke strukture (poput prirodnih brojeva) postoje same po sebi, kako tvrdi Max Tegmark.

Matematičari su početkom dvadesetog stoljeća shvatili da ne postoji skup svih skupova. (Kad bi on postojao, postojao bi i njegov podskup X koji sadrži samo one skupove koji ne sadrže sami sebe kao element – ali onda bi X sadržavao sebe ako i samo ako se ne sadrži, što je kontradikcija, odnosno Russelov paradoks. Osim toga, partitivni skup skupa svih skupova prema Cantorovu teoremu morao bi biti još veći skup, što opet vodi u kontradikciju.)

Iako ne postoji skup svih skupova, sasvim sigurno postoji beskonačnost. Aristotel je razlikovao potencijalnu i aktualnu beskonačnost. Aktualna je ona koja je potpuna – “gotova” i već sadrži svih beskonačno mnogo elemenata, dok potencijalna nikad nije potpuna nego se u nju uvijek mogu dodavati elementi, ali nikad svih beskonačno. S vremenom je u matematici aktualna (“dovršena”) beskonačnost postala prihvaćena i uobičajena, ali ona nije intuitivna. Kao djeca shvaćamo da prirodnih brojeva ima beskonačno mnogo zato što svakom broju možemo dodati jedan – ali to je potencijalna beskonačnost, ona koja raste u nedogled, a ne sadrži “sve odjednom”.

Ipak, nedavno sam upoznao fantastičnu osobu koja umjesto fraze “i tako dalje” ponekad kaže “i tako sve”. Dakle, umjesto potencijalnog – aktualno! Nema onog neodređenog “dalje“, nego odmah “sve“. Riječ je dakle o intuiciji koja je (barem iz matematičke perspektive) na visokoj razini.

Na kraju, jedan moj doživljaj od prije nekoliko godina. Organizirao sam neko informatičko natjecanje i bio je neki problem, nešto smo sjebali, možda neki zadatak ili tako nešto. Idućeg dana na poslu sam pričao s Antom Đerekom (koji je prije mene organizirao ta natjecanja) i rekao mu da se grizem zbog te pogreške. On je tada izgovorio tu jednostavnu, tihu rečenicu: “A ne možeš sve.”

Možda je još nešto rekao, ali ovo je bio dovoljno, ta kratka rečenica puna razumijevanja, empatije i mudrosti. Napravio si mnogo, ali ne možeš sve. Ne postoji knjiga o svemu, ne postoje svi mogući svjetovi, ne postoji skup svih skupova i u životu će uvijek biti stotinu grešaka i nedovršenih stvari – nikad nećeš biti gotov. Ipak se kaže “i tako dalje”. Ne možeš sve.

FAQ ili Često postavljana pitanja o logaritamskoj krivulji

Logaritamskoj, ne blogaritamskoj! Zasjala je ovdje iznad, u headeru stranice koji je doživio mali makeover ili barem beauty tretman kao što je bio i zaslužio. Vidite je?

Otkud uopće logaritam u nazivu bloga? Najprije kao simbol matematike. Potom, budući da je mnogo objava bilo vezano za algoritamske zadatke, kao riječ koja je slična riječi algoritam, a ujedno se javlja u vremenskoj složenosti mnogih algoritama (npr. N log N). I naravno, kao igra riječima. Može li bolje?

Logaritamski rast, kao što vidimo iz gornje krivulje, ide najprije brzo a onda sve sporije i sporije. Kad bismo je pratili još neko vrijeme, krivulja bi postajala sve sličnija horizontalnoj liniji – ali i dalje bi uvijek rasla.

Evo nekoliko primjera. Kad počnemo redovito vježbati i pratiti svoj učinak (npr. prosječnu brzinu trčanja ili masu koju možemo podići), on na početku – dok stječemo formu – raste brzo, a poslije sve sporije. Onaj tko nema naviku trčanja lako može poboljšati svoje vrijeme za nekoliko sekundi, ali profesionalac vrlo teško. Slično je s učenjem nove vještine, novog jezika, ili s produktivnosti općenito: ako nismo uopće produktivni, mali hakovi (poput gašenja mobitela i interneta na nekoliko sati) mogu višestruko povećati učinak; no što smo više produktivni, to je teže biti još produktivniji.

Suprotna je, recimo, eksponencijalna funkcija (koji je upravo inverz logaritamske) koja raste sve brže i brže. Što si više bogat, to je lakše biti još bogatiji. To je znao i Isus: “onomu tko ima dat će se, a onomu tko nema oduzet će se i ono što ima“. Možda je mislio na kapitalizam, ali vjerojatnije je psihološko tumačenje: što imaš više ljubavi, lakše je imati još više. Ako ti manjka, imat ćeš još manje.

Ali i ovdje se možemo vratiti na logaritamski rast: poznato je da, recimo, sreća u ovisnosti o bogatstvu raste sve sporije i sporije. Tako razlika između jedne i dvije tisuće kuna primanja može subjektivno biti daleko veća nego između 10 i 20 tisuća kuna. Svaka nova kuna vrijedi sve manje, iako ju je sve lakše dobiti. Također, pretpostavljam da slično “raste” zdravlje u ovisnosti o navikama. Uvođenje jednog treninga tjedno (umjesto nijednog) pomoći će mnogo više nego uvođenje četvrtog treninga kad već imamo tri. Kad je stanje loše, prednost je što su mali pomaci zapravo golemi. Jedno brzinsko pospremanje učinit će mnogo za neuredan prostor, više nego temeljito čišćenje za onaj koji je već relativno uredan. Kad ti se ne da raditi, prvi riješeni zadatak učinit će najveću razliku u raspoloženju. Jedan topao telefonski poziv učinit će najviše onda kada nije očekivan. Nešto je uvijek beskonačno puta bolje od ničega. Iz rupe se možda i nije toliko teško izvući.

Na kraju, ako se zarotira u smjeru suprotnom od kazaljke sata, logaritamska krivulja postaje (stilizirano) slovo L – ono koje nedostaje u headeru, a ujedno i najljepše slovo abecede.

Koliko sam dobro trčao? (drugi dio)

Sanjao sam sfingu koja daje proročanstva i mogao sam postaviti jedno pitanje. Pitao sam: kada će na Blogaritmu ponovno osvanuti nešto normalno, matematičko? Sfinga je odgovorila: hokus pokus, bogovi su odlučili, to će biti danas!

Ovo je nastavak objave Koliko sam dobro trčao? (prvi dio) u kojoj sam pitao:

Ako sam pretrčao S metara u T sekundi, koliko sam uspješno trčao?

I evo, tijekom ovog sunčanog vikenda riješio sam taj problem.

Nakon što sam pri kraju te objave zaključio da je uspjeh dobro računati kao kombinaciju doprinosa prijeđenog puta S i prosječne brzine V (= S / T), te u međuvremenu kratkim istraživanjem po webu shvatio da je riječ o približno eksponencijalnom odnosu, odlučio sam da formula treba biti umnožak oblika:

S^\beta V^\gamma

s parametrima \beta i \gamma takvima da se iznos kreće od 0 do 100 – pri čemu bi svjetski rekord dao rezultat 100. Da bismo izračunali dotične parametre, valja pogledati te svjetske rekorde – osim sprinteva (S < 1000) u kojima su principi malo drugačiji. Ako je, recimo, (s, v) jedan konkretan rekord, onda treba vrijediti:

s^\beta v^\gamma = 100 \quad\Rightarrow\quad \beta \log s + \gamma \log v = 2.

Ako u matricu X po redcima stavimo parove (\log s, \log v) za sve promatrane svjetske rekorde, iz gornjih jednadžbi dobivamo preodređeni sustav jednadžbi:

X [\beta \, \,\, \gamma]^T = [2, 2, ..., 2]^T,

čije najpreciznije rješenje u smislu najmanjih kvadrata dobivamo na sljedeći način:

[\beta \,\,\, \gamma]^T = (X^T X)^{-1} X^T [2, 2, ..., 2]^T.

Konačno, formula za uspjeh trčanja (na osnovi liste svjetskih rekorda danih u donjem kodu), ako je S izražen u metrima, a V u metrima po sekundi, ispada približno:

uspjeh = S^{0.14} \cdot V^{1.81}

Primjerice, ako sam pretrčao 5 kilometara (S = 5000) u 25 minuta (V = 5000 / (25 \cdot 60) = 3.33), uspjeh ispada 5000^{0.14} \cdot 3.33^{1.81} = 29.1 od mogućih 100. Prilično loše, hahaha!

Evo i koda u Pythonu. Pokrenete li ga, vidjet ćete da formula nije potpuno precizna: uspjesi svjetskih rekordera kreću se između 97 i 103.

#!/usr/bin/python3
from math import log
import numpy as np

csv = "1000,no,131.96,male,track,Noah Ngeny,1999-09-05\n\
1500,yes,206.00,male,track,Hicham El Guerrouj,1998-07-14\n\
1609.344,no,223.13,male,track,Hicham El Guerrouj,1999-07-07\n\
2000,no,284.79,male,track,Hicham El Guerrouj,1999-09-07\n\
3000,no,440.67,male,track,Daniel Komen,1996-09-01\n\
5000,yes,757.35,male,track,Kenenisa Bekele,2004-05-31\n\
10000,yes,1577.53,male,track,Kenenisa Bekele,2005-08-26\n\
10000,no,1604,male,road,Leonard Patrick Komon,2010-09-26\n\
15000,no,2473,male,road,Leonard Patrick Komon,2010-11-21\n\
20000,no,3386,male,track,Haile Gebrselassie,2007-06-27\n\
20000,no,3321,male,road,Zersenay Tadese,2010-03-21\n\
21097.5,no,3503,male,road,Zersenay Tadese,2010-03-21\n\
21285,no,3600,male,road,Haile Gebrselassie,2007-06-27\n\
25000,no,4345.4,male,track,Moses Mosop,2011-06-03\n\
25000,no,4310,male,road,Samuel Kosgei,2010-05-09\n\
30000,no,5207.4,male,track,Moses Mosop,2011-06-03\n\
30000,no,5257,male,road,Peter Cheruiyot Kirui,2011-09-25\n\
42195,yes,7418,male,road,Patrick Makau,2011-09-25"

x = []
y = []
for row in csv.split('\n'):
    data = row.split(',')
    s, t = float(data[0]), float(data[2])
    v = s / t
    x.append([np.log10(s), np.log10(v)])
    y.append(2)
x = np.array(x)
y = np.array(y)

beta, gamma = np.linalg.inv(x.T @ x) @ x.T @ y
print(beta, gamma)

for row in csv.split('\n'):
    data = row.split(',')
    s, t = float(data[0]), float(data[2])
    v = s / t
    print(s**beta * v**gamma)

Polumatematičke crtice s godišnjeg odmora

Posudio sam iz knjižnice debelu knjigu Number theory Andreja Dujelle, počeo je čitati i rješavati zadatke. Ide mi dobro, prisjećam se kako je to bilo vježbati za matematičke olimpijade. Ali ako velik dio dana provedem na taj način, osjećam se kao da sam gubio vrijeme. Jer sada, kada nemam neke vanjske motivacije za proučavanje teorije brojeva (niti se natječem niti se profesionalno bavim čistom matematikom), osjećaj je u istom rangu kao da rješavam sudoku: lijepo, ali beskorisno, ne doprinosi ničemu. Ne kažem da treba biti tako, samo da se ja tako osjećam, a osjećajima uglavnom ne možemo upravljati. Bolje se osjećam kada čitam nešto životnije.

Tako sam čitao Teda Chianga (inače odličnog SF pisca) i njegovu priču Division by zero. U toj priči on pokušava oslikati matematičarku kojoj je matematika daleko od sudokua i slične zabave: ona je praktički religiozno vezana za matematičke rezultate, baš kao i neki veliki vjernik za dogme u koje vjeruje. Poznajete li nekog takvog matematičara? Ja ga baš i ne poznajem. Kao što keramičaru neće svijet propasti ako mu se razbije paket pločica, tako je i većini matematičara vjerojatno svejedno je li Goldbachova ili Riemannova hipoteza istinita ili nije; zapravo im je vjerojatno stalo samo do toga da oni sami uspiju dati neki doprinos. Je li rezultat pet ili šest, koga briga, jer ništa se u svemiru ni u našim životima neće promijeniti. Ja sam kao mali, u osnovnoj školi, bio vatreni matematičar i možda mi je stvarno bilo stalo do tih rezultata. Sad više nije toliko, i ne znam nikoga tko je toliko “religiozan” u matematici da mu je doista stalo. Sve je to sudoku.

Uglavnom, u spomenutoj priči Division by zero, Ted Chiang uspijeva uvjerljivo opisati takvu duboku matematičarku Renee. (Tekst koji slijedi sadrži spoilere.) Što je najgore što se takvoj osobi može dogoditi? Kao što bi vatrenom vjerniku ili teologu najgora spoznaja bila da nema Boga, tako Renee – na svoje veliko zaprepaštenje – uspijeva dokazati da je matematika u sebi kontradiktorna, tj. da je moguće bez greške dokazati da je 1 = 2 (ili bilo koju drugu jednakost). Sve matematičke tvrdnje postaju jednako istinite i jednako neistinite. Njezinim je kolegama manje-više svejedno, ali Renee pada u tešku depresiju. Ali genijalnost leži tek u drugoj, paralelnoj radnji priče: kao što se Renee bori sa svojom spoznajom o kontradiktornosti matematike, tako se njezin suprug Carl bori sam sa sobom, sa spoznajom da više ne može razumjeti Renee, da se njegova ljubav prema njoj gasi, da je mora napustiti. Dok Renee gubi vjeru u matematiku koja je njezin život, Carl gubi vjeru u život i samoga sebe. U zadnjem odjeljku, koji je prikladno označen kao “1 = 2”, Carl napokon shvaća što osjeća Renee – jer on osjeća to isto, samo u drugoj domeni. Ali ta ih “jednakost” razdvaja, kao što jednakost 1 = 2 uništava matematiku.

*

Postoji teorem (tzv. Intermediate value theorem) koji kaže da ako imamo neprekidnu funkciju za koju je f(a) negativan i f(b) pozitivan, onda mora postojati neki c između a i b takav da je f(c) = 0. Prilično intuitivno, zar ne? Što ćemo onda sa sljedećim pitanjem: ako sa a = 15 godina nisi odrastao čovjek, a sa b = 35 godina jesi odrastao čovjek, u kojem se točno trenutku događa prijelaz? Ne mora on biti isti za svakoga, jer funkcija ne raste istom brzinom za svakoga, ali za svakoga tko će ikad odrasti očito mora postojati neki trenutak kada on počinje biti odrastao. (Žalite se teoremu, ne meni.)

Taj se prijelaz dogodi, a nitko ga ne primijeti. U pjesmi Time, Floydi govore upravo o tome, te između ostalog kažu: “No one told you when to run, you missed the starting gun.” Ali ja ipak mislim da sam uočio taj trenutak. Noćas sam se probudio usred noći te, idući prema WC-u, ugledao plosnati predmet za koji sam na trenutak (u tom uspavanom stanju) pomislio da je matematička knjiga; imao je i uzorak šahovnice na “naslovnici”. Kad sam bolje pogledao, shvatio sam da je to paket vlažnih krpa za pranje poda koje sam jučer upotrebljavao (kupljen u Kauflandu ili Mülleru), a onaj šahovski uzorak na njegovu omotu oslikava pločice. Život se mijenja; matematičku knjigu zamjenjuje nešto mnogo prizemnije, čak i u najdoslovnijem smislu riječi “prizemno”. Zgodna slika odrastanja.

Koliko sam dobro trčao? (prvi dio)

Neki će reći da je dobar trening svaki onaj od kojeg se dobro oznojiš, te da je dobar rezultat na nekoj dionici trčanja (recimo 5 km) ono vrijeme koje je bolje od tvog prethodnog vremena. Fair enough, ali matematičar u meni želi kvantizirati uspjeh treninga trčanja. Ako sam pretrčao S kilometara u T vremena, koliko sam dobro trčao?

Naravno, nije svejedno jesam li trčao konstantnom brzinom ili sam, recimo, naizmjence ubrzavao i usporavao; a ni parametre poput temperature zraka, nagiba staze i brzine vjetra ne treba uvijek zanemariti. Ipak, radi jednostavnosti, zanemarit ćemo ih i pretpostaviti idealne uvjete, te da se brzina nije mnogo mijenjala tijekom trčanja, tj. da nije riječ o intervalnom treningu (koji je često efektivniji, ali to je druga tema).

I dalje, moguća su različita shvaćanja gornjeg pitanja:

  1. Koliko bi odrađeni trk bio uspješan u kontekstu neke utrke, odnosno, koliko je uspješan s obzirom na sposobnost koju pokazuje?
  2. Koliko je iscrpljujući?

Prvo shvaćanje rangiralo bi vrhunski otrčan sprint daleko bolje od osrednje otrčanog maratona, dok bi drugo shvaćanje učinilo upravo suprotno.

Što se tiče drugog pitanja (iscrpljujući), jedna je moguća strategija procijeniti utrošene kalorije, a one (ako sam dobro shvatio guglajući) najviše ovise o prijeđenom putu, dakle, o umnošku brzine i vremena. U tom bi smislu sporo otrčan maraton bio izjednačen s brzo otrčanim maratonom (“while running it doesn’t matter what speed you run a given distance, you will burn the same amount of calories as long as the distance is the same”, izvor). Čak mi se iz formula koje se spominju na webu (recimo ovdje) čini da bi sporiji trk na istoj udaljenosti potrošio malo više kalorija, jer se formula (kad zanemarimo masu i druge konstante) svodi na nešto tipa vrijeme * (0.2*brzina + 3.5) = 0.2*put + 3.5*vrijeme. To mi je neobično jer bi nas vremenski kraći trk na istoj dionici trebao više iscrpiti. S druge strane, možda se stvarno utroši manje energije jer imamo manje doticaja s tlom. Ako netko zna više, neka napiše u komentar.

Prvo je pitanje zanimljivije i u nastavku teksta okrećem se njemu. Pretpostavimo, dakle, da trčimo S metara za T sekundi konstantnom brzinom od V = S/T metara u sekundi. Najprije primijetimo:

  • veća brzina uvijek povećava uspjeh trka (bilo da fiksiramo vrijeme, bilo da fiksiramo put),
  • dulji put uvijek povećava uspjeh trka (bilo da fiksiramo vrijeme, bilo da fiksiramo brzinu),
  • ali vrijeme tako izravno ne utječe na uspjeh (ako je brzina fiksna, bolje je veće vrijeme; ako je put fiksan, bolje je kraće vrijeme).

Možemo stoga reći da je uspjeh neka kombinacija puta i brzine, S*V ili tako nešto. Što točno? O tome ću idući put, a ako imate ideju, napišite u komentar.

Refreshaj koliko hoćeš

Jeste li ikad bjesomučno refreshali neku stranicu čekajući neku vijest ili promjenu? (Recimo, popis pozvanih na Državno natjecanje koji se danas očekuje?)

Možda ste znali, a možda i niste, da se to refreshanje može automatizirati.

Postoje online alati za to (recimo, https://www.followthatpage.com/), ali zašto ne bismo zasukali rukave i sami napisali odgovarajuću skripticu?

Ovo je moja:

"""
Usage: refresh.py [full_url] [refresh_interval_in_seconds] [optional: string_to_search]

If the search string is given, then refreshes until the string is found in page text.
Otherwise, refreshes until the page is changed.
"""

import urllib.request
import sys
from time import sleep
from bs4 import BeautifulSoup

def get_text(url):
    text = str(urllib.request.urlopen(url).read())
    soup = BeautifulSoup(text, 'html.parser')
    [s.extract() for s in soup(['style', 'script', '[document]', 'head', 'title'])]
    text = soup.getText()
    # ignore numbers
    for z in '0123456789':
        text = text.replace(z, '')
    return text

try:
    interval = int(sys.argv[2])
    url = sys.argv[1]
except:
    print(f'usage: {sys.argv[0]} [full_url] [refresh_interval_in_seconds] [optional: string to search]')
    exit(0)
if len(sys.argv) > 3:
    word = sys.argv[3]
else:
    word = None
print(f'reading {url} ...')
previous_text = get_text(url)
while True:
    sleep(interval)
    print(f'refreshing {url} ...', end=' ')
    text = get_text(url)
    if word: 
        if word in text:
            print(f'String "{word}" found in page text!')
            exit(0)
        else:
            print(f'string "{word}" not found')
    else:
        if text != previous_text:
            print(f'Page has changed!')
            exit(0)
        else:
            print('no change')
    previous_text = text

Ovaj dio s promjenom ne radi na stranicama s oglasima (npr. portali) jer su svaki put drugačije reklame pa skripta misli da se stranica promijenila. Možda ima i još bugova ili prostora za poboljšanje, slobodno komentirajte.

Napomena: Ne postavljajte refresh interval na manje od nekoliko sekundi; prečesto slanje requestova može biti nepristojno ili čak zabranjeno. Related: https://softwareengineering.stackexchange.com/a/304767

Komunikacijska složenost – ili – kako zakodirati partiju šaha

Na IOI-u 2010. prvi put smo se susreli s tipom zadatka u kojemu treba poslati neku informaciju u što manje bitova. Zadatak se zvao Saveit i trebalo je, za zadani graf, najkraće udaljenosti (između zadanih posebnih vrhova do svih ostalih) poslati kao bitovni niz iz jednog programa (encoder) u drugi program (decoder) koji će taj niz znati protumačiti, tj. iz binarnog niza rekonstruirati tražene udaljenosti. Trebalo je, naravno, napisati oba programa.

Naivno je rješenje svaku udaljenost poslati kao binaran broj, što rezultira prevelikim ukupnim brojem bitova. Ključna ideja bila je iskoristiti činjenicu da, ako su X i X’ susjedi u grafu, udaljenost(X, Y) razlikuje se od udaljenosti(X’, Y) najviše za 1. Zato je za ovu drugu udaljenost, pod pretpostavkom da smo već poslali prvu, dovoljno poslati samo razliku (-1, 0 ili 1) što možemo dvama bitovima. Ili, još bolje, konstruiramo ternarni niz koji prije slanja pretvorimo u binarni. Detalje ostavljamo čitateljici za vježbu, a cijelo rješenje imate npr. ovdje (napisala ga je moja malenkost, doduše poslije natjecanja).

Tako se na IOI-u pojavila nova tema, koju smo u Hrvatskoj ponekad zvali komunikacijskom složenošću jer se radi o veličini poruka između dvaju programa. Riječ je još i o zadatcima Parrots iz 2011., Supper iz 2012. i Stations iz 2020., a i na CEOI-u 2016. pojavio se zadatak Trick.

Ima to veze i s kompresijskim algoritmima, npr. onima koji smanje veličinu datoteka kad ih zipate, ali za razliku od tih algoritama koji su prilično generički (ne tumače sadržaj datoteka), u ovim problemima traži se kompresija specifična za dani problem. Tako mi je palo na pamet sljedeće pitanje: kako zakodirati partiju šaha, u smislu poteza koji su odigrani? Naravno, pitanje je prilično beskorisno budući da tekstualni zapis šahovske partije nije uopće velik, vjerojatno ste ga i vidjeli (riječ je o Portable Game Notation – PGN), primjerice:

1. e4 e5 2. Nf3 Nc6 3. Bb5 a6 4. Ba4 Nf6 5. O-O Be7 6. Re1 b5 7. Bb3 d6 8. c3 O-O 9. h3 Nb8 10. d4 Nbd7 11. c4 c6 12. cxb5 axb5 13. Nc3 Bb7 14. Bg5 b4 15. Nb1 h6 16. Bh4 c5 17. dxe5 Nxe4 18. Bxe7 Qxe7 19. exd6 Qf6 20. Nbd2 Nxd6 21. Nc4 Nxc4 22. Bxc4 Nb6 23. Ne5 Rae8 24. Bxf7+ Rxf7 25. Nxf7 Rxe1+ 26. Qxe1 Kxf7 27. Qe3 Qg5 28. Qxg5 hxg5 29. b3 Ke6 30. a3 Kd6 31. axb4 cxb4 32. Ra5 Nd5 33. f3 Bc8 34. Kf2 Bf5 35. Ra7 g6 36. Ra6+ Kc5 37. Ke1 Nf4 38. g3 Nxh3 39. Kd2 Kb5 40. Rd6 Kc5 41. Ra6 Nf2 42. g4 Bd3 43. Re6 1/2-1/2

Ali čemu tražiti svrhu, ni većina drugih informatičkih zadataka nije u ovom smislu korisna. Najbolje stvari su beskorisne. Razmislimo onda kako bismo zakodirali ovakav niz poteza u što manju (binarnu ili tekstualnu) datoteku. Želite li se sami zabaviti razmišljajući o tome, slobodno ovdje prestanite čitati…

Na prvi pogled nije lako jako nadmašiti gornji PGN zapis, ali neke redukcije možemo smisliti relativno brzo. Primjerice: nema potrebe navoditi redni broj poteza; moguće je izostaviti i razmake; ne trebaju nam znakovi x (za jedenje) i + (za šah). Moguća su i sitnija poboljšanja: rezultat na kraju može se zapisati samo jednim znakom, a ponekad (npr. u slučaju mata ili pata) on nije ni potreban jer slijedi iz pozicije; rokadu je moguće prikazati jednim znakom; neka jedenja od strane pješaka (npr. hxg5) dovoljno je pisati kao običan potez (g5) ako ne može doći do zabune, tj. ako u tom trenutku ne postoje dva pješaka koji mogu jesti na g5. Tu ideju možemo proširiti i na druge figure pa pisati npr. e1 umjesto Ke1 ako u tom trenutku samo kralj može odigrati na e1. Nisu ta poboljšanja nimalo loša, ali… zasad smo još uvijek vrlo bliski PGN formatu; i dalje nam trebaju 2-3 znaka po potezu. Ako je jedan znak jedan bajt, riječ je o približno 20 bitova po prosječnom potezu. To je nekoliko puta manje od originalnog PGN zapisa, ali može i bolje!

Dobra je ideja odustati od tekstualnog zapisa, od znakova, jer 8 bitova za jedan znak nije dobar deal. Ono što zapravo zapisujemo polja su šahovske ploče, a njih je 64 = 26, što znači da je za zapis jednog polja dovoljno samo 6 bitova. Zapisujemo li potez kao par (početno polje, završno polje), dovoljno je 12 bitova po potezu – mnogo bolje od tekstualnog zapisa! Ipak, postoje i posebni potezi koje nije moguće tako zapisati: mala/velika rokada, završetak partije (kao predaja bijelog/crnog ili dogovoreni remi) ili izvlačenje nove figure gdje treba precizirati izvlači li se kraljica ili nešto drugo. Srećom, možemo se izvući tako da svaki od tih nekoliko posebnih poteza zapišemo kao neki potez koji je inače nemoguć. Recimo, mala rokada može biti zapisana kao da je riječ o potezu a1-b8, velika kao a1-c8, predaja bijelog kao a1-d8, itd. I dalje smo na 12 bitova po potezu!

Slijedi zamjedba da je umjesto početnog polja (6 bitova) bolje zakodirati figuru koja odigrava potez, jer budući da igrač ima samo 16 figura, svaka može biti određena 4-bitnim kodom. Posebne poteze i ovdje možemo zakodirati kao poteze koji su inače nemogući (npr. za bijelog pješak na a1, b1…, a za crnog pješak na a8, b8…). Već smo na 10 bitova po potezu!

Prethodni odlomci navode nas na pomisao da kompresija još uvijek nije optimalna jer postoji nemogući potezi. Ali ne samo potezi koji su uvijek nemogući, poput bijelog pješaka na prvi red ploče ili bjelopoljnog lovca na crno polje, nego i mnoštvo poteza koji su nemogući u danom trenutku partije. Pozicija na ploči, u bilo kojem trenutku, dopušta samo vrlo ograničen skup poteza i nema potrebe koristiti cijeli skup od 210 šahovskih poteza da bismo zapisali što je u tom trenutku odigrano. Drugim riječima, većina kodova uopće ne opisuje dozvoljene poteze i to je očit znak da smo još uvijek rastrošni. To je pogotovo jasno, recimo, na početku partije kada se mogu micati samo pješaci i skakači, ili u završnici kad većine figura više i nema na ploči. Ako je u nekom trenutku samo desetak dozvoljenih poteza, ne bi li nam četiri bita trebala biti dovoljna?

Kako ostvariti tu ideju? Evo kako. Za trenutačnu poziciju odredimo sve dopuštene poteze, sortiramo ih “abecedno” (ili bilo kojim drugim kriterijem), pronađemo onaj indeks u tom nizu na kojem se nalazi potez koji je zaista odigran, i zakodiramo taj indeks. Našao sam na webu podatak (dobiven empirijski) da je prosječan broj dopuštenih poteza u nekoj poziciji približno 31. To znači da bi prosječno 5 bitova trebalo biti dovoljno. Na prvi pogled može biti nejasno kako to iskoristiti jer broj dopuštenih poteza može, naravno, biti i veći – poznata je pozicija iz stvarne partije gdje je taj broj bio 79, a teoretski se on može popeti i do 218 pa nam može zatrebati i 8 bitova. Treba li nam onda neki “separator” koji će dijeliti broj s manje bitova od onog s više bitova? Ne, jer dekoder u svakom trenutku – ako prati poziciju – može znati koliko je dopuštenih poteza, a time i koliko idućih bitova treba pročitati da bi odredio indeks odigranog poteza u tom nizu. Na primjer, ako je 14 dopuštenih poteza, pročitat će četiri iduća bita da otkrije indeks odigranog (makar on bio i 0000).

Dakle, prosječno samo 5 bitova po potezu! Mana je ovog rješenja što i enkoder i dekoder moraju biti programi koji znaju igrati šah, ili barem znaju njegova pravila, jer moraju znati odrediti dopuštene poteze (te ih sortirati po istom kriteriju). Ali čini se da bolje rješenje ne postoji: uočite da svaki proizvoljno dug niz bitova (bio on i slučajan), osim pri samom kraju gdje mu može “nedostajati” bitova, opisuje neku legalnu partiju – što za prijašnja rješenja ni izdaleka ne vrijedi. Ne može bolje! Ili?

Imam i nedovršenu ideju za bolje rješenje. Dosjetka je u tome da, iako pozicija nudi 30ak mogućih poteza, nisu svi jednako vjerojatni: postoje dobri i loši potezi te, što je potez bolji, veća je vjerojatnost da je odigran. To vrijedi i za partije potpunih amatera: u svakoj poziciji postoji značajan broj zbilja besmislenih poteza koje nitko normalan neće odigrati. Kako to iskoristiti? Ovdje nam, nažalost, nije dovoljno da enkoder i dekoder znaju igrati šah. Za ovo rješenje oni bi morali dobro igrati šah, procjenjujući (na jednak način) koliko je koji potez dobar. Pa dobro, to nije neostvarivo, mogu koristiti isti šahovski engine. No što dalje? Umjesto da sortiramo dopuštene poteze po abecedi, sortirat ćemo ih po kvaliteti poteza. Tako će bolji potezi (koji se češće igraju) imati manji indeks pa će za njihov zapis trebati manje bitova. Tako, as a side effect, kvalitetu igrača možemo mjeriti duljinom zapisa njegovih poteza.

No ovdje se javlja problem koji sam natuknuo u jednom od prethodnih odlomaka. Ako postoje, recimo, 32 dopuštena poteza (5 bitova), a odigran je šesti potez po kvaliteti, želimo iskoristiti činjenicu da je indeks mali i zapisati ga koristeći 3 bita. Ali kako će dekoder znati da treba pročitati samo iduća 3 bita, a ne 5? Treba nam, možda, neki separator, ali i on mora biti binaran, i ne smije zauzeti previše bitova… Ako netko ima pametnu ideju kako ovo riješiti, neka napiše u komentar.