Poluosvrt na vrijeme kada je natjecanje bilo offline

Prije dvije godine napisao sam Poluosvrt na EJOI 2018. Ako je to bio poluosvrt, dakle pola osvrta, gdje je onda druga polovica? Napisat ću onda sada poluosvrt na EJOI 2017. u Bugarskoj gdje sam bio stručni voditelj. Iako je od tada prošlo više od tri godine, ali eto, slučajno sam naišao na ove fotografije i došlo mi je da se prisjetim kako je to bilo kad natjecanja nisu bila online. (Pola osvrta na EJOI 2018. i pola osvrta na EJOI 2017. daju jedan osvrt na… ne znam što.)

EJOI 2017. bila je prva europska juniorska olimpijada. Ondje sam na nekom bugarskom placu kupio stanovitu frulu s dvije cijevi, dvojanku:

Kupio sam je za dvadeset eura od nekog tipičnog “plac trgovca” koji nije znao engleski pa mi je na bugarskom objašnjavao da je to ozbiljan instrument, da voli Hrvatsku i da je bio u Splitu i na Korčuli. Kako god bilo, kupio bih taj egzotični instrument i da je bio dvostruko skuplji. To je bilo na nekom izletu; pokušavao sam odmah skužiti kako se frula svira i je li slična blok-flauti. Zapitkivao sam okolo ljude jesu li išli u glazbenu školu i mogu li čuti je li interval između dvaju tonova mala ili velika sekunda kad im odsviram. U busu sam uspio približno odsvirati melodiju iz uvoda pjesme Lipe cvatu (ne onu prvu nego onu drugu, normalniju). Nervirao sam ljude, netko me zamolio da prestanem.

EJOI 2017. bilo je jedino natjecanje na kojemu sam se ošišao. Zašto ne, pomislio sam; imao sam vremena i kosa mi je bila zrela za šišanje. Uspio sam se nekako sporazumjeti s frizerkom; ondje iz nekog razloga traže fotografiju kako da te ošišaju. Ošišao sam se vrlo kratko jer je to najbolja strategija kad ne znaš koliko je frizer sposoban. Potom sam u šetnji otkrio predivnu zgradu:

Kad sam je obišao da je bolje pogledam, još sam se više oduševio:

Poslije sam na mobitelu mjerio frekvencije tonova dvojanke. Lijeva cijev nema rupa i daje uvijek isti ton frekvencije oko 485 Hz. Desna cijev ima šest rupa naprijed i jednu iza, a daje tonove frekvencija redom oko 426, 485, 527, 570, 629, 685, 757, 813 Hz pri čemu su mjerenja vrlo neprecizna jer variraju i ovise o jačini daha. Dakle, lijeva cijev kao dron daje osnovni ton, od kojeg s desnom cijevi možemo otići “jedan niže” ili “do šest više”. Međutim, iz frekvencija se vidi da ti tonovi ne odgovaraju našim standardnim tonovima, a ni intervali nisu standardni – omjer frekvencija susjednih tonova te “ljestvice” kreće se otprilike između 1.08 i 1.10, što je točno između male i velike sekunde (1.06 i 1.12), s iznimkom prvog intervala (onog “jedan niže”) koji je oko 1.14. Nema nigdje ni oktave. Precizno sviranje standardnih melodija, dakle, nije moguće, ali zato su moguće drugačije melodije na koje nismo navikli. Druga logika!

Ovdje sam pisao više o stvarima, a manje o ljudima: o druženju, našim i stranim natjecateljima, voditeljima, organizatorima, djevojkama koje su nas vodile uokolo (tzv. gajdice) i slično. O njima neću ništa napisati, dovoljno je podsjetiti da su ljudi još zanimljiviji od frule i zgrada. (U genijalnom tekstu ABBA-ine pjesme The Day Before You Came, pjevačica u detalje opisuje trivijalne sitnice koje su se dogodile prije nego što je došao taj netko, i iako o toj osobi i tom događaju nema ni jedne riječi, o njemu je zapravo cijela pjesma.)

A samog natjecanja i rezultata više se i ne sjećam. Natjecanje je važno, i važne stvari motiviraju život, ali sačinjavaju ga one nevažne, offline sitnice sa strane.

Znanost i algoritmi, drugi dio

Prije nekoliko mjeseci u postu Znanost i algoritmi pisao sam o nekim znanstvenim radovima u kojima glavnu ulogu igraju algoritmi ne toliko različiti od onih na natjecanjima. U međuvremenu sam se sjetio još dvaju dobrih primjera u kojima glavnu ulogu igraju naši algoritmaši. Za početak spomenimo članak u kojem su naši bivši uspješni natjecatelji (Goran Žužić i Filip Pavetić) objavili efikasan algoritam računanja sličnosti stringova. A o drugom primjeru treba napisati nešto više, pa krenimo.

Na 1. kolu HONI-ja 2012. postavio sam zadatak Mars. U njemu je riječ o potpunom binarnom stablu u kojemu možemo proizvoljno zamijeniti lijevo i desno podstablo bilo kojeg vrha – ili, ekvivalentno, odabrati permutaciju listova u kojoj svako podstablo i dalje pokriva uzastopan podniz – tako da zbroj “odbojnosti” susjednih listova (koja je definirana za sve parove u ulaznim podatcima) bude što manji.

Zanimljivo je da sam poslije naišao na znanstvene radove koji rješavaju isti problem. Ovaj članak rješava isti problem za PQ-stablo i primjenjuje ga na poznati problem trgovačkog putnika (Travelling Salesman Problem ili TSP). U ovom članku problem se rješava za K-arna stabla (u binarnom stablu je K = 2) i primjenjuje u bioinformatici za sortiranje gena. Algoritmi i jednog i drugog članka svode se na O(n^3) za binarno stablo, što je i složenost mog rješenja u zadatku Mars.

Ali to nije najbolja moguća složenost! Kao što pokazuje ovaj članak Urlika Brandesa, problem za binarna stabla moguće je riješiti u O(n^2 \log_2 n). Zanimljivo je da je jedan natjecatelj na samom natjecanju pronašao takvo, brže rješenje (o kojem je, dakle, netko prethodno napisao znanstveni rad) – to je bio Luka Kalinovčić na COCI natjecanju. Nakon što sam proučio njegovo rješenje, opisao sam ga (uz vlastito) u službenim rješenjima, tada još ne znajući za cijelu ovu priču. Svaka čast Luki!

Spomenimo i da navedeni Brandesov članak navodi još neke primjene ovog problema kao što je sortiranje piksela u svrhu sažimanja slika, te je predloženi algoritam zbog memorijske složenosti od O(n) bolji od algoritma iz članka koji se izvorno bavi tim praktičnim problemom.

Argument u prilog postojanju dobrog i lošeg ukusa

Poznata je rečenica O ukusima se ne raspravlja. Kao što ću ispod objasniti koristeći i neke matematičke alate, mislim da nije baš tako.

Krenimo s jednostavnijom tvrdnjom, onom o ljudskoj ljepoti. Ljepota je subjektivna, ljepota je u oku promatrača. Ne, nije: istraživanja pokazuju da se ljudi u velikoj mjeri slažu oko toga koja su lica lijepa, a koja nisu. To znači da postoji “definicija” ljepote koja nam je u velikoj mjeri zajednička. Idemo li tu ljepotu dublje istraživati (što za ovaj argument i nije potrebno), vjerojatno ćemo doći do određenih pravilnosti, simetrija i proporcija koje čine tu ljepotu. Naravno da postoje “protuprimjeri” gdje je nekome lijepo/ružno što drugima nije, ali živimo u praktičnom svijetu i ima smisla reći da je netko lijep ako se većina ljudi oko toga slaže.

Ovaj argument ne možemo tako lako proširiti na ukus, gdje ne postoji slično slaganje i veća su razilaženja među ljudima. Ta činjenica mogla bi nas čak navesti na suprotni zaključak: za razliku od ljepote, “dobar ukus” ne postoji. Ali pokušat ću ovdje iznijeti malo finiji argument u prilog dobrom ukusu, barem u kontekstu umjetnosti (poput književnosti i glazbe), motiviran intuicijom koja mi kaže da tako nešto postoji, da određeni ljudi s više iskustva primjećuju više i bolje i često se slažu oko vrijednosti (ili njenog nedostatka) umjetničkih djela. Iako je filozofski možda lakše braniti stavove koji negiraju postojanje nečega (objektivnog morala, slobodne volje, svijesti, dobrog ukusa…), u mnogim slučajevima takve pozicije propuštaju ili gube iz vide neki stvaran fenomen koji (ako i nije egzaktan) postoji i važan je.

Umjesto dobrog ukusa možda je lakše govoriti o kvaliteti; to nisu sinonimi, ali mislim da se u svojoj suštini ne razlikuju izjave “postoje dobar i loš ukus” i “postoji ono što je objektivno kvalitetno i ono što nije”, barem u kontekstu umjetnosti. Sada ću pokušati definirati kvalitetu na način koji smatram dobrim. Radi jednostavnosti i bez smanjenja općenitosti, ograničimo se na književnost i definirajmo kvalitetnog pisca. I to na sljedeći način:

Kvalitetni pisci su oni ljudi za koje drugi kvalitetni pisci kažu da su kvalitetni pisci.

Znam, ovo na prvi pogled nema smisla, definiram kvalitetu koristeći kvalitetu. (To me podsjeća na definiciju ceste iz autoškole, koja je počinjala otprilike ovako: “Cesta je svaka javna cesta…”). Ali ne, izraziti iks pomoću iks nije nužno besmislica. Što je, recimo, s jednadžbom x=x^2-2? To je ono na što ciljam: gornja definicija zapravo je matematička jednadžba koja ima svoje rješenje. (Zato i ovaj post jest na Blogaritmu.)

Ta jednadžba u suštini je PageRank, algoritam koji Google koristi da bi rangirao stranice po važnosti samo na temelju poveznica. Ideja je da na važne stranice upućuje mnogo drugih stranica, pri čemu poveznica s važnije stranice vrijedi više. Na donjoj slici, veličina svakog lica proporcionalna je ukupnoj veličini onih lica koja na nju pokazuju. Tako su, recimo, zelena lica malena jer na njih nitko ne pokazuje, dok su ostala lica veća jer primaju više poveznica. Žuto lice znatno je veće od plavog (iako primaju skoro jednak broj poveznica) jer žuto lice prima poveznice od većih izvora (npr. od plavog lica) nego što ih prima plavo lice. Gornje crveno lice prima samo jednu poveznicu, ali je relativno veliko jer ta poveznica dolazi od velikog žutog lica. Dakle, slično našoj definiciji kvalitetnog pisca, velika lica su ona lica za koja druga velika lica kažu da su velika.

Naglasimo da veličina lica u ovom primjeru nije nigdje unaprijed zadana, nego su zadane samo poveznice, a veličina iz njih onda sama proizlazi – primjerice, rješavanjem odgovarajućeg sustava jednadžbi. Tako i kvaliteta iz naše definicije sama proizlazi iz preferencija svih onih koji imaju neko mišljenje o književnosti, pri čemu nitko nije unaprijed odabran kao kvalitetan.

Kao ilustraciju, uzmimo skup takvih (živućih) ljudi i zamislimo anketu u kojoj svaki od njih bira 50 (ili proizvoljno mnogo) subjekata iz tog istog skupa koje smatra kvalitetnim piscima. Da bismo iz tih preferencija izračunali kvalitete, svakom subjektu inicijalno dajmo, recimo, 100 bodova i neka se njegovi bodovi potom ravnomjerno rasporede piscima koje je on odabrao. Nismo još gotovi: zasad smo samo dobili popularnost, jer će pisci koji su najviše puta odabrani imati najviše bodova. No sada će ponovno svaki subjekt (istodobno) svoje bodove ravnomjerno rasporediti svojim favoritima. I ponovno, i ponovno… Tako preferencije pisaca postaju važnije jer oni imaju više bodova od običnih čitatelja. Recimo, ako u prvom koraku najviše bodova dobije J. K. Rowling, u drugom koraku ona će tu gomilu bodova podijeliti piscima koji su njoj kvalitetni, oni će ih dalje dijeliti svojim favoritima itd. Intuitivno, bodovi se slijevaju najboljima. Treba napomenuti da se u svakom koraku određeni manji postotak bodova (damping factor) svakog subjekta mora ravnomjerno rasporediti po cijelom skupu da bi subjekti koji nisu ničiji favoriti (nego su obični čitatelji) i dalje imali svoj bodovni utjecaj. E sad, važna matematička činjenica jest da nakon velikog broja ponavljanja situacija postaje stabilna. Recimo, nakon tisuću koraka bodovi pojedinog pisca više neće varirati, tj. svaki pisac dobivat će konstantan broj bodova u svakom idućem koraku. Taj broj odgovara njegovoj kvaliteti. (Upravo sam ugrubo skicirao iterativni algoritam računanja PageRanka, a precizniji detalji mogu se pronaći u linkanom članku ili na Wikipediji.)

Netko bi mogao prigovoriti da ovo rješenje nije egzaktno, nego ovisi o neprecizno definiranim podatcima i promjenom samo jedne preferencije mijenja se sustav jednažbi, a onda i njegovo rješenje. Slažem se da ovako definirana kvaliteta nije egzaktna, ali to je i slučaj i s mnogim stvarnim fenomenima za koje se slažemo da postoje (popularnost, uspjeh, inteligencija, ljepota, dobrota…). Što se tiče promjene jedne preferencije, važno je da sustav nije (u matematičkom smislu) kaotičan: ako promjene nisu velike, ni rješenje se značajno ne mijenja, i to ga čini realnim.

Moguće je napasti i samu gore napisanu definiciju kvalitete pa reći da je ona proizvoljna, da je kvalitetu moguće definirati na tisuću drugih načina i da je baš zbog toga ona i dalje subjektivna. Naravno, sve je moguće drugačije definirati. Ali kvaliteta iz gornje definicije u skladu je sa stvarnim pojavama, njeni brojevi neće ispasti nasumični, jer preferencije nisu raspoređene nasumično, nego se slijevaju prema najboljima. Dobiveni bi se rezultati vjerojatno dobro poklopili s ukusom onih koji se tom umjetnošću bave, vjerojatno bi “isplivali” upravo oni pisci u kojima uživaju, recimo, književna kritika i drugi priznati pisci. Nazovimo to kako hoćemo, ali it’s a real thing.

Za one koji još nisu uvjereni u takav ishod, ovaj argument u najmanju je ruku (matematičkim rječnikom) nekonstruktivan: dokazuje da neki entitet postoji, a da ga eksplicitno ne pronalazi. Ostalima on daje uvid u značenje kvalitete: ako vas zanima što je objektivno kvalitetno, krenite od onoga koga osobno smatrate kvalitetnim i pitajte njega, pa pitajte onoga koga on smatra kvalitetnim, i tako dalje. Kvalitetni jedni druge vole.

Beskonačno mnogo vremena

[Ova priča objavljena je 2016. godine na portalu Kultipraktik kada je ušla u konkurenciju za nagradu Prozak. U međuvremenu je taj portal ugašen pa sam priču odlučio objaviti ovdje. Matematičarima ona može biti zanimljiva i kao jedan pogled na staru raspravu o potencijalnoj i aktualnoj beskonačnosti.]

*

Ovaj zapis govori o slučaju koji još nije riješen, a tiče se zagrobnog života izvjesnog gospodina Slavka M. Taj čovjek na Zemlji nije nikamo žurio: živio je usporeno kao da života ima u izobilju. Govorili su da je lijen, ali to što je studirao deset godina, uvijek kasnio na posao i uzimao stanke za ručak u trajanju od po tri sata, po njegovim riječima nije bilo problematično. Objašnjavao je (onima koji su htjeli slušati njegov polagani govor, isprekidan povremenim odlascima u šetnju) da je njegovo ponašanje odraz svjetonazora koji donosi unutarnji mir i sprječava srčane i mnoge druge bolesti; on je stoga zapravo bio itekako odgovoran čovjek. Poginuo je na autocesti, u pedesetoj godini, u automobilskoj nesreći za koju je očevid utvrdio da joj je glavni uzrok bio prespora vožnja dotičnog Slavka M.

Nakon smrti stigao je u sobicu kamo svi kad-tad pristižu i sjeo za stol s Bogom, vragom i mršavim zapisničarom. Na sastanku je Slavko M. uspio isposlovati da ne ode u pakao na cijelu vječnost, nego samo na konačno mnogo vremena, nakon čega će otići u raj gdje će ostati zauvijek. Nezgodno je bilo što će trajanje vremena provedenog u paklu odrediti vrag, i to potpuno proizvoljno. Slavko će svakako jednom izaći iz pakla, ali kada će se to dogoditi – na vragu je bila odluka.

Slavko M. mirno se zaputio u pakao, znajući da nema tog vremena koje on ne bi mogao provesti u čekanju. On nije bio glup čovjek pa je bio svjestan da će vrag odabrati golem broj godina, veći od svake Slavkove predodžbe. Ali koliko god to vrijeme trajalo, ono je ništavno prema vječnosti koju će Slavko potom provesti u raju; tamo će od izobilja vremena kad-tad zaboraviti da je ikada i bio u paklu.

Slavko M., nažalost, nije znao da vrijeme nadmašuje sve njegovo strpljenje. Možda i nije teško u paklu proboraviti mjesec dana, godinu, pa čak i pet godina. Ali trideset godina, cijeli život, dva života, deset života? Slavku je prekipjelo već nakon pet života – to je već nekoliko stoljeća! – ali nakon toga je dalje čekao tisućljeće, dva tisućljeća, milijun godina, milijardu godina, starost Zemlje, starost svemira – a i to je bila tek sitnica prema onome što ga je čekalo.

Nakon nekoliko tridecilijardi godina Slavko M. rekao je sam sebi da više ovako ne može i odlučio se na žalbu. Nazvao je Boga (morao je čekati čak dvije minute dok se ovaj nije javio) i iznio mu svoj izračun prema kojemu je u paklu proboravio više života nego što ima atoma u svemiru; vrag očito krši dogovor i nikada ga neće pustiti. 

“Hm…” promrmljao je Bog, “tko si ono ti?” 

Slavku je trebalo čak pet minuta objašnjavanja dok se Bog nije napokon sjetio njega i dogovora koji je sklopljen. Tada se javio vrag koji je prisluškivao razgovor.

“Hoću, pustit ću ga, ali još nije došlo vrijeme.”

“Eto vidiš, sve je u redu”, odgovara Bog i poklapa slušalicu. Slavko se pognute glave vratio u pakao psujući Boga i vraga: u beskraju vremena bio je već smislio dugačke psovke čiji je izgovor trajao i po nekoliko tjedana.

Nakon nekog vremena Slavku je postalo jasno da, koliko god eona provede u paklu, ni u jednom trenutku neće znati je li prošlo makar jedan posto od vremena koje mu je vrag predodredio. S tim je mislima ponovno nazvao Boga i rekao mu da je načuo da ga vrag uopće ne namjerava pustiti. Vrag je mirno odgovorio da za to nema nikakvih dokaza. Bogu je čitava stvar postala sumnjiva pa su se u sobici ponovno sastali on, vrag, Slavko M. i mršavi zapisničar. Slavko je Bogu iznio svoju optužnicu.

“Vrag je očito odlučio da me nikada neće pustiti. To je u suprotnosti s dogovorom koji je sklopljen.”

“Slažem se”, odgovara Bog kimajući glavom. Vrag se na to prestane ljuljati na stolcu, uspravi se i htjedne odgovoriti, no Slavko ga preduhitri.

“Ali on će se uvijek izvući! Kad god ga optužim da krši dogovor, vrag će samo odgovoriti da će me pustiti u budućnosti i da je stoga sve po dogovoru. Ne mogu nikada dokazati da me zapravo neće pustiti.”

“Dakle, nema dokaza!” sa smiješkom ustaje vrag. “Ne znam zašto uopće raspravljamo.”

“Zanimljivo”, reče Bog Slavku, ignorirajući vraga koji je ponovno sjeo. “Tvrdiš dakle da je vrag u zavidnoj poziciji: u mogućnosti je istodobno kršiti i ne kršiti dogovor.”

“Upravo tako”, odgovara Slavko, dodajući riječi “napokon si shvatio” sebi u bradu koja je već padala gotovo do poda.

“Molim?” pita Bog.

“Ništa, ništa…”

“Predlažem sljedeće rješenje”, obznani Bog, a zapisničar se prihvati posla. “Vrag mora odmah odlučiti o broju godina koje ćeš provesti u paklu i šapnuti ga meni. Tako ćemo biti sigurni da će dogovor biti ispoštovan.”

Nakon što je vrag teška srca to učinio, Slavko M. sretno se zaputio natrag u pakao, napokon siguran da će kad-tad izaći: njegov je dan izlaska fiksiran i svakim mu je danom bio bliže za točno jedan dan. Ali stvari nisu išle dobro: nemoguće je i zamisliti koliko je Slavko nakon toga čekao. Sve ono vrijeme prije drugog sastanka u sobici jedva da je činilo milijunti dio vremena koje je Slavko potom proveo u paklu ne dočekavši oslobođenje. Shvatio je da ni sada ne zna je li prošlo makar jedan posto, ili čak tisućiti dio, od vremena koje mu je vrag predodredio – štoviše, vjerojatno nije. Nakon što je i njemu, strpljivom i sporom čovjeku, čak septilijun puta prekipjelo, Slavko M. zatražio je novi sastanak s Bogom i vragom u istoj sobici. 

Slavkov je prijedlog bio sljedeći: vrag će ga odmah pustiti i otići će u raj. Ondje će, međutim, provesti konačno mnogo vremena, koliko on sam poželi, nakon čega se vraća u pakao na cijelu vječnost. 

Bio je to neobičan prijedlog, simetričan početnom dogovoru. Vrag je zaključio da je Slavko M. glup čovjek, ali baš iznimno glup čovjek, jer bi po starom dogovoru on u paklu proveo samo konačno mnogo vremena i poslije se ne bi vraćao, a po novome prijedlogu kad-tad će se vratiti u pakao na cijelu vječnost. Vragu je to odgovaralo pa je prijedlog bio prihvaćen, mršavi je zapisničar u spise dodao novu bilješku, a Slavko se zaputio u raj.

A tamo je, naravno, provodio na tisuće puta više vremena nego što je prethodno bio proveo u paklu i nije mu bilo ni na kraj pameti da uskoro izađe. Vrag, budući da ni on nije bio glup, shvatio je da Slavko može u nedogled boraviti u raju na isti način kao što je vrag prethodno odugovlačio njegov boravak u paklu.

“Onaj idiot krši dogovor i neće nikada izaći”, požalio se vrag Bogu.

“Hoću, izaći ću”, iz ležaljke odgovara Slavko M. “Prema dogovoru, moram izaći, ali onda kada sam odlučim.”

Vrag je podivljao. “Ovo je prevara i podvala! On može čitavu vječnost biti u raju i uvijek odgovarati da ipak nije prekršio dogovor jer će, tobože, jednom u budućnosti izaći. Ponovno imamo isti problem.”

“U redu”, odgovara Bog. “Slavko, evo ti komad papira. Bit će velik koliko god poželiš da bude. U skladu s vlastitim prijedlogom, moraš odlučiti koliko ćeš godina ostati u raju – taj broj, naravno, ne smije biti beskonačan – i napisati ga na ovaj papir. Tako ćemo znati da će tom vremenu doći kraj.”

Češkajući obraslu glavu, Slavko je uzeo olovku razmišljajući što će napisati. Nažalost, koji god broj napisao, u usporedbi s vječnošću je ništavan. Također, koji god broj napisao, uvijek može napisati još veći pa je odluka gotovo nemoguća. 

Nakon nekog vremena sine mu ideja i on počne pisati broj: jedan, nula, nula, nula, nula, i tako dalje, dakle: 1000000000000000000000000… Dopisivao je nule i nule, papir se sam od sebe povećavao, a Slavko je nule dopisivao danima, tjednima, mjesecima, godinama, životima. Vrag je shvatio da će ga još jako dugo čekati, ali ipak mirno ode spavati znajući da će nulama na papiru kad-tad doći kraj jer zapisani broj ne smije biti beskonačan.

Slavko M. konačno je došao na svoje: eonima je pisao nule na papiru, ne čineći ništa drugo i pitajući se zašto je u zemaljskom životu radio išta drugo kad je ispunjavanje praznoga papira nulama najlakši, najljepši i najopuštajući posao. Papir se povećavao i dosegnuo širinu četrdeset svemira. Videći kamo to ide, vrag se ponovno javi.

“Onaj vucibatina neće nikada završiti zapisivanje tog prokletog broja godina. Njegov broj je beskonačan, a to je protivno dogovoru.”

“Nije tako!” odgovara Slavko grickajući olovku. “Moj broj je konačan i završit ću s njegovim zapisivanjem jednom u budućnosti.”

Nakon još nonilijun kvintilijuna godina, vrag se u raju pojavio sav crven. 

“Dosta je bilo ovoga cirkusa! Već treći put imamo isti paradoks: onaj smrdljivac krši dogovor pišući beskonačno mnogo znamenaka, a istodobno ga ne krši jer bilo kada može reći da će uskoro završiti. Želim garanciju da će pisanje kad-tad završiti!”

“Opet vas dvojica”, odgovara Bog uz duboki uzdah. “U redu: moramo biti sigurni da će Slavko završiti s pisanjem. Zato nam, Slavko, moraš obznaniti koliko još dana planiraš zapisivati te silne znamenke.”

“Pisat ću ih još mnogo dana”, mirno će Slavko. “Ja volim pisati.”

“Moramo znati točan broj dana”, ponovno će Bog brišući znoj sa čela. “Evo, napiši ga ovdje da to napokon riješimo”, reče i pruži mu novi papir.

Slavko M. uzeo je olovku i zamislio se. Potom je polako počeo pisati broj: jedan, nula, nula, nula, nula, nula, nula, nula, nula, nula, nula, nula, nula, nula, nula, nula, nula, nula, nula…

Knjiga koja se čita godinama

Govori se ovih dana o novom nobelovcu, fizičaru Rogeru Penroseu. Moj susret s njim dogodio se (i još se događa) kada mi je Ante Đerek povodom obrane doktorata poklonio njegovu knjigu The Road to Reality. Način da nekoga upoznamo, da uđemo u tuđi um i izravno čujemo njegove riječi, to su knjige. Oblik komunikacije, kao i blogovi i chat poruke, samo dulje i rjeđe. (Znam da je neobično objašnjavati što su knjige, ali možda je dobro.) Spomenuta The Road to Reality Penroseova je chat poruka od preko tisuću stranica u kojoj on, praktički od nule, pokušava objasniti svemir i sve njegove fundamentalne formule. Ovo je moj primjerak:

Prvu trećinu knjige čini sama matematika koja je potrebna za fiziku u ostatku knjige. Jedva čekam da dođem do fizike, jer matematika je pomalo naporna; već dugo sam stao na ovom mjestu jer (razumljivo) baš mi se i ne da:

Nedostaje mi samo malo discipline; nekoliko stranica dnevno i brzo bih prešao dosadne dijelove. Nema žurbe, to je projekt u kojemu se uživa godinama. Kao i poezija za koju sam nedavno naučio da ne treba čitati više od jedne pjesme dnevno – te su pjesme (neovisno o duljini) često mnogo “sporije” od matematike. Kad je Dylan pitao Cohena koliko mu je trebalo da napiše pjesmu Hallelujah, odgovor je bio dvije godine, iako kažu da mu je zapravo trebalo pet godina. Ja ću je možda razumjeti za deset. Penrose je ovu knjigu (The Road to Reality) pisao osam godina. Da je pisao brže, možda bi napisao više knjiga, ali one bi bile lošije. Manje je više (less is more) i vrijeme treba ispuniti (bolje rečeno isprazniti) jednostavnim ritualima: gašenjem konekcije, malim kavama s mlijekom koje se dugo ispijaju, stranicama koje se dugo i polako čitaju. Trebale su nam tisuće godina za razumijevanje svemira (i nismo još gotovi), a sada to znanje imamo na tisuću stranica jedne knjige. Stoga ako i cijeli život čitamo samo tu knjigu, vrijedno je. Iz te perspektive sljedeći vic u sebi nosi duboku mudrost: kad je Mujo pitao Hasu što želi za rođendan, želi li možda knjigu, Haso je odgovorio da već ima jednu.

Digresija: suvišnost matematike i jedna nova igra

Real mathematics is almost wholly useless.

– G. H. Hardy, “A Mathematician’s Apology

Teorija brojeva nekada je (u vrijeme gornjeg citata) bila praktično beskorisna, ali onda se pojavila kriptografija. Netko anoniman na internetu je napisao: “Mathematicians have had an exceedingly difficult time finding truly useless mathematics. And they’ve been trying for thousands of years.” Poanta nije u tome da velik dio matematike kad-tad nađe svoju primjenu, nego u tome da u početku ta primjena ne postoji – i zato je Hardyjev citat istinit. Ima nešto poetično, a mnogima i nejasno, u matematičaru koji proučava neka opskurna svojstva prirodnih brojeva ili tako nečega, dugo nakon što je prerastao natjecanja i nadmetanja s kolegama, ne zato, nego iz čiste želje i užitka. Iz istog razloga iz kojeg netko drugi rješava sudoku, skuplja salvete, čita hrvatsku poeziju ili proučava analitičke filozofe koji ne zanimaju nijednog od njegovih poznanika.

To ne razumiju oni ljudi (a ima ih mnogo) koji su uvijek goal-oriented, koji svemu traže svrhu i ne vide ljepotu suvišnog – onoga što uopće ne trebamo raditi. Takvi obično ne razumiju umjetnost i uvijek se pitaju što netko želi postići, koje su mu namjere, koja je poruka. Nema poruke! Nema drugih namjera! Takvi bi imali problema i s razumijevanjem ovog bloga. Jer on uza sve svoje korisne stvari, ruku na srce, obiluje i beskorisnim idejama o koječemu. Da budem potpuno jasan, one nemaju nikakvu svrhu, osim samih sebe, svoje potencijalne zanimljivosti i ljepote. Tako je, recimo, Igor Stravinski rekao da glazba nije sposobna izraziti ništa osim sebe same. Very true!

U duhu ovih odlomaka odlučio sam ovdje podijeliti jednu igru koju sam izmislio u snu. (Toliko je čudna da je i mogla nastati samo u snu.) Najprije valja spomenuti postojeću igru The Game koja se igra cijeli život i ima samo jedno pravilo: svaki put kada igrač pomisli na tu igru, on gubi. Cilj je, dakle, ne misliti na tu igru – igra se pobjeđuje misleći o drugim stvarima. Postoje majice na kojima piše “You lose The Game!” koje uzrokuju mnoge poraze u igri (onih igrača koji vide tu majicu).

E sad, igra koju sam izmislio nije naročito originalna u smislu da je potpuno ista kao The Game, samo ima drugačije ime: zove se The Game Too. Ovaj too dolazi kao igra riječima prema The Game 2, tj. The Game Two (druga verzija Gamea).

Odmah se postavlja vrlo opravdano pitanje jesu li dvije igre koje imaju potpuno ista pravila zapravo iste, je li riječ o plagijatu. No ovdje je situacija specifična. Poanta postojanja igre s drugačijim imenom leži u njezinom odnosu s prvom, standardnom igrom. Jer sada postoje igrači koji igraju obje igre. I svaki put kada netko od njih pomisli na The Game, postoji solidna šansa da pomisli i na The Game Too, i onda njegova izjava glasi: “I lost The Game, and I lost The Game Too!” (Vidite li sada svrhu igre riječima two -> too? :))

Postoje i druga zanimljiva pitanja vezana za odnos između ovih igara. Recimo, hoće li se nekome od igrača koji igraju obje igre dogoditi da se sjeti The Gamea, ali zaboravi na The Game Too? A je li moguće, je li ikako moguće, da se sjeti samo The Game Too? Hoće li postojati igrači koji će čuti samo za The Game Too i tako uvijek pobjeđivati u The Gameu, za koju nikada neće čuti? To će biti rijetki sretnici; njima moramo “prodati” neko drugo objašnjenje za ovaj Too da ih ostavimo u neznanju o postojanju standardne inačice igre.

Postoje prijepori oko toga igraju li The Game svi ljudi na svijetu ili samo oni koji znaju za tu igru. Kao autor i apsolutni gospodar igre The Game Too, odlučio sam definirati da tu igru igraju svi na svijetu. To znači da velika većina ljudi na svijetu stalno pobjeđuje u The Game Too (naravno i oni koji gube u The Game) i to je jako dobro. Širenjem glasa o novoj igri povećat će se broj njezinih gubitnika, što je s jedne strane loše (nitko ne voli gubiti), ali s druge strane dobro, jer povećava broj potencijalnih novih igara – novih inačica The Gamea – koje će ti ljudi izmisliti. Vidite, postoji vrlo razuman razlog zašto nisam otišao dalje i izmislio, recimo, The Game Three ili tako nešto – zato jer u takvoj igri onda ne bih pobjeđivao. Moj je cilj da drugi ljudi po uzoru na mene izmisle mnogo, što više novih inačica The Gamea u kojima ću onda ja (budući da ne znam za njih) uvijek pobjeđivati.

Everybody’s gangsta until you invert

Prijatelj Bruno Gašperov i ja imali smo raspravu oko jednog YouTube videa, točnije jedne slike koja je u njemu prikazana, a navodno oslikava inverz:

Bruno je primijetio da ovaj meme zapravo ne predstavlja inverz funkcije. Štoviše, on nema nikakve veze s inverzom. Što je na prvoj slici x, a što f? Je li riba x a mačka f()? Onda je f preslikavanje x -> pojedeni x, pa bi inverz trebalo biti nešto što pojedeni x vraća u x. Dakle, na drugoj slici bi trebalo biti nešto što pojedenu ribu pretvara u originalnu. Zapravo je povraćanje inverz, zaključio je Bruno.

Odgovorio sam da on želi prikazati f^{-1}(y), ali da slika prikazuje f^{-1}(x). Bruno je zaključio da to baš i nema smisla. Ako je f nešto što neki objekt pretvara u pojedeni objekt, onda je f^{-1} nešto što pojedeni objekt pretvara u nepojedeni. Domena od f su nepojedeni objekti, kodomena pojedeni. f^{-1} nije definiran na elementu domene, tj. na x. Dakle, f^{-1}(riba) ne postoji.

A čak i ako shvatimo da f^{-1}(riba) postoji, objašnjavao je Bruno, f^{-1} i dalje undo-a čin jedenja. Onda bi f^{-1}(riba) (za nepojedenu ribu) bio neki z koji, kad ga pojedeš, dobiješ nepojedenu ribu. Možda neka riba u ovojnici?

Složio sam se i zaključio da slika zapravo ne opisuje inverz nego reverse, okretanje poretka (mačka jede ribu -> riba jede mačku). Ali onda sam krenuo razmišljati može li se slika ipak nekako shvatiti tako da ima smisla kao inverz, tj. postoji li neko drugo, pametnije tumačenje što je x, a što je f. Pasivno razmišljajući dvadesetak minuta uz zujanje i kavu, nakon nekoliko krivih ideja, našao sam odgovarajuće tumačenje.

Ako je f(x) = onaj tko jede x, onda je na prvoj slici f(riba) = macka. To znači da je f^{-1}(macka) = riba. I onda druga slika prikazuje f^{-1} kao što prva prikazuje f!

Neovisno o dojmu da je takav f malo neprirodan, Bruno je primijetio da je onda čudno da je druga slika, koje prikazuje f^{-1}(x), tj onog koga jede x, vizualizirana na isti način. Bilo bi smislenije da je druga slika identična prvoj. Za drugu sliku treba biti f^{-1}(macka)=riba, što znači da mačka jede ribu, no na slici riba jede mačku. Na toj slici, dakle, “biti pojeden” su vizualizirali kao “jede” što nema baš smisla.

Odgovorio sam da nije tako nelogično ako shvatimo na sljedeći način. Za početak zaboravimo ikakvo jedenje i samo definirajmo f(riba)=macka, dakle f^{-1}(macka)=riba. Dalje uzmimo da slika vizualizira proizvoljnu funkciju na način da stavi x u usta onoga u koga se on preslikava. I sad jednostavno prva slika vizualizira f, a druga f^{-1}. Kao graf! Je li graf funkcije sinus identičan grafu njenog inverza (arcsin)? Ovdje je analogna situacija.

Bruno odgovara da onda relacija jedenja oslikana na slici zapravo samo indicira što je x a što je y, a ne govori ništa o samoj funkciji f. Nisam se baš složio: indiciranje što je x a što y jednoznačno opisuje funkciju. Funkcija nije drugo nego skup parova x, f(x). Slika prikazuje taj skup, točnije, jedan njegov dio. Govori nam o jednom paru x \to y (riba i mačka). Možda ih ima još, možda nema.

Bruno je ponovio prigovor od ranije. Ako je f(riba) = macka, onda je f^{-1}(macka)=riba. f(x) je onaj tko jede x, f^{-1}(x) je onaj koga jede x. Problem je što f(x) i f^{-1}(x) nisu vizualizirane na isti način. Trebale bi biti ista slika!

Odlučio sam se bolje izraziti. Zapravo, nije točno da je f(x) onaj tko jede x. Nego samo na slici vrijedi da je za funkciju na slici f(x) onaj koji jede x. Jedenje je samo vizualizacija neke funkcije koja sama po sebi neme veze s jedenjem. Isto kao što sinus nije “valovit” sam po sebi nego tek kad mu nacrtaš graf u Kartezijevoj ravnini. U tom smislu, f i f^{-1} jesu vizualizirane na isti način i sve je smisleno. Primjerice, “9 jede 3” bila bi analogna slika koja vizualizira kvadriranje, a “3 jede 9” korjenovanje i ništa nije čudno.

Bruno je shvatio. Dakle, imamo neku funkciju koja preslikava x (ribu) u y (mačku), i ta funkcija je (sasvim slučajno) prikazana tako da y jede x (mogli smo prikazati i kao da y pije x ili nešto treće). Jedenje samo indicira što je element domene x (jedeno), a što odgovarajući element kodomene y (jedač). I onda na drugoj slici želimo nacrtati inverz i stavimo obrnuto, da x (riba) jede y (mačku) jer su sad domena i kodomena obrnute. (Kao u slučaju grafova sinusa i arcsinusa.) I u tom smislu relacija jedenja ništa ne govori o samoj funkciji f jer smo funkciju mogli vizualizirati i nekom drugom relacijom, već je proizvoljno odabrana ta relacija da poveže element domene i kodomene. Slika je samo oznaka.

Bruno je onda predložio bolji meme za inverz:

… jer sad ne moramo toliko apstraktno ići, u skladu je sa slikama. f(x) je dobiti na lutriji, f^{-1}(x) potrošiti novac u kockarnici.

Komentirao sam da bih ovaj cijeli razgovor (u ispoliranom obliku) volio staviti na Blogaritam. (Ovaj meme na kraju, doduše, može se doimati politički nekorektnim. Kao, muškarac dobiva novac, a žena ga spiska. No dobro je što muškarac na slici nije zaradio novac, nego dobio na lutriji, pa ne ispada da muškarac zarađuje za ženu.)

Za kraj, Bruno je primijetio da autor originalnog memea sigurno nije imao našu interpretaciju na umu. On je zabrijao, ali ipak je dobro ispalo. Kao kad izgovorite nešto glupo, ali to iz nekog razloga na koji niste računali ispadne duhovito pa slučajno impresionirate ljude. Događalo mi se nekoliko puta.

Statistika i (neki) statističari

COVID! Napokon nešto o Covidu! Aaaaa! Prije mjesec dana pojavio se kontroverzni preprint (preprint znači znanstveni članak koji tek treba proći recenziju i biti prihvaćen za objavljivanje u časopisu) među čijim je autorima nekoliko naših znanstvenika (između ostalih Alemka Markotić, Dragan Primorac i Gordan Lauc). Ugrubo, članak na temelju određenih podataka o europskim pacijentima zaključuje da je ljetni covid manje opasan od zimskog. Kontroverzan je zato što je, s jedne strane, dobio dosta medijskog publiciteta i u nas i u inozemstvu, a s druge strane kritike od izvrsnog mladog znanstvenika Jana Homolaka i njegovih suradnika. Oni su kritizirali statističke metode kojima su Lauc i ekipa iz podataka došli do odgovarajućih zaključaka. Statistika nije moje područje pa toj raspravi (koja se proširila na Twitter i Facebook) ne mogu doprinijeti, osim ovakvim dijeljenjem koje nas, ako ništa drugo, može zainteresirati i dati dobar uvid u znanstvenu metodologiju.

A statističari bi ovu priču mogli rasvijetliti, te iz gomile složenih podataka koje je moguće tumačiti na tisuću načina izvući uzročno-posljedične veze. Statistikom se inače bavi naš prvi zlatni IMO-vac Domagoj Ćevid, a o nekim zanimljivostima govorio je ovdje (ako vas zanima više, poslušajte cijeli intervju).

Nedavno sam čitao o jednoj pogrešnoj, a nažalost vrlo utjecajnoj statistici. Krajem prošlog stoljeća istraživanja su (ugrubo) kazivala da ljudi koji piju prosječno 1-2 alkoholna pića dnevno imaju najbolje zdravlje, točnije, bolje od onih koji piju više ili ne piju ništa. Takav narativ svakako je poticao konzumaciju alkohola, no on je pogrešan:

But there was a problem with many of these studies: They compared drinkers to non-drinkers (…). And people who don’t drink are pretty fundamentally different from drinkers in ways that are hard to control for in a study. Their lives probably look dissimilar. Most importantly, they may be sicker at baseline (perhaps they quit drinking because of alcoholism, or because of a health issue like cancer). And something in these differences — not their avoidance of alcohol — may have caused them to look like they were in poorer health than the moderate drinkers. (This became known as the “sick quitter” problem in the world of alcohol research.)

Matematičarima je to možda strano, ali u znanosti (nažalost) ključnu demonstrativnu ulogu igraju eksperimenti i njihova analiza. U računarstvu, gdje se u znanstvenom radu obično predlaže neki algoritam, model, metoda ili protokol, eksperiment se sastoji od testiranja ili simulacije predložene metode na odabranim testnim podatcima, pri čemu je često važna usporedba s alternativnim, postojećim metodama. U medicini ili psihologiji eksperimenti se rade na ljudima koji se dijele na ove ili one skupine i moguće je pogriješiti na stotinu načina – što u izvedbi eksperimenta, što u tumačenju rezultata. Jedno od najvažnijih svojstava je ponovljivost, što znači: ako neki drugi istraživač neovisno izvede isti eksperiment, morao bi dobiti vrlo slične rezultate. Ovdje je zanimljivo da je 2015. godine provedena studija koja je pokušala replicirati razne rezultate prethodnih psihologijskih istraživanja, nažalost s razočaravajućim rezultatima.

Čovjek bi rekao da je u matematici provjera najlakša, jer riječ je o egzaktnoj znanosti – dokaz ili je ispravan, ili ima grešku u zaključivanju i ozbiljni matematičari (gotovo) uvijek će se međusobno složiti jer logika govori sama za sebe. Nekad je tu grešku lako detektirati – godišnje se pojavi stotinjak amaterskih “rješenja” velikih matematičkih problema poput dokaza da je P ≠ NP. Ipak ima i slučajeva kada su i najozbiljniji matematičari u nesuglasju, no takvi slučajevi vrlo su rijetki. O jednom od njih pisao sam u postu Matematika i (neki) matematičari.

Tema dana: skakanje po neboderima (ili: Ne pokušavajte ovo kod kuće)

Prije petnaest godina, na jednom od prvih “težih” državnih natjecanja za osnovne škole (koje bi za današnje standarde bilo relativno lagano) pojavio se zadatak Spiderman u kojemu glavni lik (koji se zove “Spiderman”) skače po nizu nebodera zadanih visina.

Sedam godina poslije na HIO-u sam zadao nešto teži zadatak Trampolin sa sličnom tematikom skakanja po nizu nebodera, ali modernijim i suvremenijim glavnim likom. Riječ je o solidnom zadatku adhocness levela 2 koji je dobar za clear thinking jer treba pažljivo i što elegantnije pokriti sve slučajeve, a i rezultati pokazuju da to nije bilo baš lako – doduše, tada nije bilo feedbacka za vrijeme natjecanja.

Nakon još četiri godine bilo je dosta single junaka pa smo, po uzoru na najnovije filmove Batman v Superman ili Justice League, odlučili da po neboderima ima skakati više junaka. Tako je za JHIO 2016. nastao zadatak Superjunaci prema ideji Mislava Balunovića.

Zanimljivo je da su ove godine autori HONI-ja potpuno zaboravili na trendove i evoluciju tematike koju smo godinama predano razvijali, pa su ponovno zadali zadatak sa zastarjelim Spidermanom. Što reći? Neki bi zauvijek ostali u kamenom dobu.

Kad smo već kod kamenog doba, postoji još jedan moj zadatak u kojemu se umjesto niza nebodera skače po nizu stabala: Jane and Tarzan (o njemu je bilo riječi i u ovom postu). Naravno, Jane i Tarzan u zadatku koriste mobitele.

Kako vježbati?

Kako vježbati? WHO preporučuje barem 150 minuta tjedno aerobne aktivnosti (kao što su džogiranje, plivanje, bicikl) te vježbe jačanja mišića barem dvaput tjedno. Ali ovdje nije riječ o tom vježbanju, nego o natjecateljskom programiranju ili matematici. Na ovom sam blogu već pisao o raznim aspektima vježbanja, a sada to želim nekako sistematizirati.

Ovo pitanje tek rijetki shvaćaju dovoljno ozbiljno; čini mi se da većina pretpostavlja da je odgovor samo rješavaj zadatke ili nešto slično. Ali to je dobar odgovor samo ako:

  1. imamo dovoljno motivacije da redovito radimo;
  2. rješavamo i zadatke koji su dovoljno teški/izazovni, ne samo one koje znamo bez muke riješiti;
  3. imamo izvore novih znanja koji nam omogućuju napredak.

Bez prve točke nedostaje nam kvantiteta, bez druge točke kvaliteta treninga, a bez treće mentorski aspekt. Dobar trening sadrži sve tri komponente. Evo nekih prijedloga…

  1. Za prvu točku potrebna je disciplina. O njoj sam pisao u ovom postu. Ukratko, ako još ne radimo dovoljno redovito, za izgradnju navike dovoljno je svaki dan riješiti jedan lagani zadatak.
  2. Za drugu točku (izazov) potrebno je rješavati zadatke koji su otprilike toliko teški da uspijemo 50% puta, plus minus. Tako se postiže idealna razina motivacije:
    ChallengeMožete za sebe pronaći odgovarajuću razinu na Codeforcesu (npr. 2. zadatak na Div1) ili na HONI-ju (npr. 5. zadatak) i onda rješavati samo zadatke te težine. Jako je važno da neriješene zadatke upsolvate, tj. riješite nakon što pročitate opis algoritma (editorijal) ili pitate nekoga da vam objasni rješenje.
  3. Za treću točku postavlja se pitanje kako naučiti nove stvari. Tu su razna predavanja, knjige, web tutorijali, videi i tako dalje. Važan je i dobar mentor koji će vam, između ostaloga, ukazati na manjkavosti u vašim rješenjima i način na koji se nešto može bolje (vidi post code review).

Rečenica “pitajte nekoga da vam objasni rješenje” zaslužuje dodatni komentar. Nekima je lako pitati, ali sigurno ima onih koji misle da nemaju koga pitati, ili možda imaju, ali se boje da to možda nije pristojno, ne žele gnjaviti ljude, nisu s njima dovoljno dobri i slično. Možda i ne žele ispasti bedaci koji ne znaju riješiti zadatak ili im neka “sitnica” nije jasna. Odgovor je sljedeći. Malo zdrave “bahatosti” u smislu zapitkivanja i traženja pomoći je izvrsna životna kvaliteta. Dakle, bez ikakve zadrške, slobodno zapitkujte svoje poznanike ili čak nepoznanike, natjecatelje koji su malo stariji od vas, na messengeru, mailu ili gdje god. Ako vam je to bed, imajte na umu sljedeće. Osoba koju pitate najčešće neće misliti da je gnjavite, nego će vaše pitanje doživjeti kao kompliment svom znanju i iskustvu. Zamislite da vas netko traži takvu pomoć (kao što kad-tad i hoće), zar to nije lijep osjećaj? Nadalje, pitanjem ćete ostaviti dobar dojam zainteresirane i pristupačne osobe. To nije uvijek intuitivno onome tko se “usuđuje” pitati, ali je zbilja tako. Na primjer, reakcija nastavnika na studenta koji na predavanju postavi pitanje nije “šta ovaj sad hoće” ili “je li ovaj glup”, nego “napokon se netko ovdje ne boji komunicirati!” Ako onaj koga pitate ne želi ili ne može pomoći, najčešće će pristojno reći da nema vremena (ili će pristojno ignorirati) i sve štima. Medalje hrvatske informatike izviru upravo iz sustava u kojemu stariji natjecatelji pomažu mlađima. Neki su gnjavili mene, ja sam svojedobno gnjavio Žužića i Sluganovića, prije toga je Žužić gnjavio Kalinovčića, a danas novi klinci gnjave nove face. Ljudi koji ne žele nikoga gnjaviti gnjavež su sami sebi.