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.

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 , ali da slika prikazuje . Bruno je zaključio da to baš i nema smisla. Ako je f nešto što neki objekt pretvara u pojedeni objekt, onda je nešto što pojedeni objekt pretvara u nepojedeni. Domena od f su nepojedeni objekti, kodomena pojedeni. nije definiran na elementu domene, tj. na x. Dakle, ne postoji.

A čak i ako shvatimo da postoji, objašnjavao je Bruno, i dalje undo-a čin jedenja. Onda bi (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 onaj tko jede , onda je na prvoj slici . To znači da je . I onda druga slika prikazuje kao što prva prikazuje !

Neovisno o dojmu da je takav f malo neprirodan, Bruno je primijetio da je onda čudno da je druga slika, koje prikazuje , tj onog koga jede , vizualizirana na isti način. Bilo bi smislenije da je druga slika identična prvoj. Za drugu sliku treba biti , š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 , dakle . 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 , a druga . 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 (riba i mačka). Možda ih ima još, možda nema.

Bruno je ponovio prigovor od ranije. Ako je , onda je . f(x) je onaj tko jede x, je onaj koga jede x. Problem je što i 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, i 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. je dobiti na lutriji, 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.

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.

Najprije mala digresija, naime, zašto sam napisao dvadeset jedan umjesto 21? Zato što ovo drugo nije u duhu jezika. U kontekstu formula je naravno drugačije, ali u običnom tekstu nije; pokušajte zamisliti npr. Šenou, Krležu ili nekog pjesnika da ima znamenke u rečenici. Ružno je! Kao što bi rekao Goran Bare: “Tko razumije, razumije. Tko ne razumije, neće nikad ni razumjeti!” (Ako koga zanima, to je rekao na 0:45 na ovom koncertu.)

Jučer sam naletio na zanimljiv članak sa zadatcima s prijamnih ispita moskovskog matematičkog fakulteta. Članak se zove Jewish Problems jer je riječ o malo težim zadatcima koje su na usmenom ispitu postavljali židovskim kandidatima koje očito nisu naročito voljeli:

“Among problems that were used by the department to blackball unwanted candidate students, these problems are distinguished by having a simple solution that is difficult to find. Using problems with a simple solution protected the administration from extra complaints and appeals.”

Malo sam škicnuo rješenja i čini se da nisu sva baš tako kratka i jednostavna, ali izgleda da su zadatci odlični. Ono što je osobito dobro jest da prije poglavlja Solutions postoji poglavlje Ideas koji sadrži hintove za sve zadatke. To je odlična praksa! Kad sam se ja natjecao, u materijalima toga uglavnom nije bilo. Možda je sad drugačije, ali ako nije, svakako treba biti.

I za kraj, što drugo mogu nego preporučiti knjigu AHA! Matije Bašića! Pod uvjetom da se na ovoj vrućini ne razlijemo po kaučima i mozak nam ne postane toplo varivo.

Godine 2010. bio sam u prvoj generaciji maturanata koja je pisala državnu maturu. Dok još nismo znali sve detalje, razmišljali smo kako će biti implementirano upisivanje kandidata na studije na temelju rang lista i preferencija kandidata. Preciznije, problem je sljedeći. Svaki kandidat ima svoju rang listu studija koje preferira; svaki studij ima svoju rang listu kandidata (na osnovi rezultata državne mature i drugih kriterija) i određenu kvotu tj. najveći broj kandidata koje može upisati. Svakom kandidatu treba dodijeliti (najviše) jedan studij tako da… Tako da što?

Cilj je barem intuitivno (uglavnom) jasan, a neki početni algoritmi odmah padaju na pamet. Ali nije baš svaka ideja ispravna. Recimo, kandidata koji je prvi na rang-listi FER-a ne želimo nužno upisati na FER jer on možda preferira PMF. Ali slična ideja iz perspektive kandidata je točna: studij koji je prvi na rang-listi nekog kandidata, a on se nalazi unutar kvote na rang listi tog studija, možemo odmah dodijeliti tom kandidatu i obrisati ga s ostalih rang lista. To možemo činiti dok god ide.

Ali na kraju nam ostaje situacija gdje pridruživanje prestaje biti trivijalno. Najjednostavniji primjer je situacija gdje Ana preferira FER > PMF, Iva preferira PMF > FER, ostalo je još po jedno mjesto na oba studija, ali na FER-u je Iva ispred Ane dok je na PMF-u Ana ispred Ive. Ovdje su važnije preferencije kandidata pa očito treba Anu upisati na FER, a Ivu na PMF, ali gornji algoritam će naprosto stati jer nijedna nije unutar odgovarajuće kvote.

Postoje, naravno, i složeniji primjeri. Ako u takvoj situaciji pokušamo nekog kandidata upisati na njegov prvi studij neovisno o kvoti, možda ćemo pogriješiti. Primjerice, ako to učinimo s Markom koji preferira FER, ali je na FER-ovoj listi ispod Ane i Ive. Tu se sada možemo zapitati zašto je točno taj izbor pogrešan, što točno želimo postići, kako precizno definirati problem.

Netko će reći – dat ćemo prednost Ani nad Markom jer oboje imaju prvi izbor FER ali je Ana tamo bolja iako nijedno nije u kvoti. Ali što ako je Ani FER drugi izbor nakon KIF-a gdje ne može upasti (ali ga ne može ni obrisati jer ni na KIF-u nije ispunjena kvota)? Koga onda upisati na FER? Kao što rekoh, nije trivijalno…

Ne sjećam se koje smo rješenje tada smislili, ali sjećam se da je upisivanje u praksi išlo tako da su bile objavljene sve rang liste i postojao je određeni rok (dva ili tri dana) u kojem su kandidati sami trebali odabrati studij (od onih gdje su bili unutar kvote na rang listi), čime su oslobađali mjesta drugim kandidatima na drugim listama. Algoritam je, dakle, bio delegiran nama učenicima! Ne znam kako je tu riješen gornji problem kad je svatko unutar kvote radije htio neki drugi studij – jesu li malo povećali kvote (barem privremeno) da bi to riješili, ili su ostavili to ograničenje pa su Ana i Iva iz gornjeg primjera morale izabrati lošije od optimalnog? I što ako su neki kandidati bili spori pa su neki drugi zakasnili jer su ih morali čekati? Ne znam, ali čini mi se da je sada to riješeno pametnije, sudeći po onome što piše na https://www.studij.hr/sve-o-prijavama:

Rang-liste kandidata po studijskim programima formiraju se računalnim algoritmom koji za svakoga kandidata pronalazi studij na kojemu može ostvariti pravo upisa, u ovisnosti o postavljenim prioritetima.

Kandidati kad vide preliminarne liste, mogu mijenjati svoje liste prioriteta i tako utjecati na ishod, ali zadnju riječ očito ima računalo. Odlično! Ali još uvijek ne piše koji algoritam se koristi.

Kako god bilo, riječ je o poznatom problemu iz naslova ovog posta, koji neki zovu i Hospitals/Residents Problem, a rješava se Gale-Shapleyevim algoritmom iz 1962. Izgleda da popisu zemalja koje ga koriste treba dodati i Hrvatsku:

Roth [19] discovered that the very same method had already been implemented in 1952 in the National Resident Matching Program, the centralised matching scheme that coordinates junior doctor recruitment in the US. Since then, similar matching schemes have been organised in many countries to allocate graduating medical students to hospital posts (hence the alternative name for the problem), and these matching schemes are widely used for other professions as well. Gusfield and Irving [12] and Roth and Sotomayor [22] provide the classical results and background material for this problem. Regarding the original context, the Gale–Shapley algorithm is also used in handling higher education admissions in a number of countries, including Spain [18], Turkey [4] and Hungary [5] (whilst a different method is used for medicine and related subjects in Germany [7]). Moreover, the same kinds of admission system have been introduced for secondary schools in, amongst others, Boston [2], New York [1] and again Hungary [5]. [izvor]

A za one koji još nisu uspjeli definirati problem, evo spoilera. Rješenje je stabilno ako ne postoji par (kandidat A, studij B) gdje i A i B “preferiraju” jedan drugoga u odnosu na rješenje, tj. A preferira B nad studijem gdje je upisan (ili nije nigdje upisan) dok je na B upisan neki student koji je na toj rang listi lošiji od A. Postoji više stabilnih rješenja, ali samo jedno resident-optimalno, što znači da je svaki kandidat upisan na studij koji mu je najbolji u svim stabilnim rješenjima, ili nije nigdje upisan ni u jednom stabilnom rješenju. Spomenuti algoritam daje to rješenje (Theorem 1).

Neke od vas moglo bi zanimati (kao što je mene zanimalo) koliko će vam znanje algoritama, napose onih s natjecanja, pomoći u “stvarnom svijetu” tj. u radu u znanosti ili softverskoj industriji. Dok je grubi i vrlo načelan odgovor taj da će pomoći jako, ali možda više neizravno (u načinu razmišljanja i programiranja) nego izravno, za primjenu u znanosti odgovorit ću navodeći primjere onih svojih članaka koji su s takvim, kombinatornim algoritmima povezani na očitiji način. Krenimo redom, kronološki.

1. Još 2012., kao student preddiplomskog studija na PMF-u, s profesorom Željkom Ilićem s FER-a napisao sam članak iz telekomunikacija gdje smo definirali odgovarajući problem tako da se može riješiti dinamičkim programiranjem. Evo ukratko o čemu se radi. U nekim bežičnim mrežama (OFDMA) signal se šalje većem broju korisnika na način da ga svaki korisnik sluša na svojim frekvencijskim potkanalima. Postavlja se pitanje podjele potkanala na korisnike (za svaki potkanal odlučiti kojem korisniku ide) ako znamo koliko kojem korisniku “paše” neki potkanal (kapacitet/brzina tj. data rate); te podatke možemo promatrati kao matricu dimenzija broj potkanala × broj korisnika. E sad, uvedemo li ograničenje da svaki korisnik mora dobiti uzastopni niz potkanala ili slot (što se opravdava potrebom za manjom količinom signalizacije i realnom sličnošću vrijednosti susjednih potkanala), ukupni maksimum dobije se jednostavnom dinamikom gdje dp(k, m) označava optimalnu podjelu prvih m potkanala na prvih k korisnika, gdje su korisnici prethodno heuristički sortirani.
2. Drugi članak s istom tematikom radio sam s još jednim algoritmašem, prijateljem Marinom Smiljanićem (i spomenutim prof. Ilićem). Ovdje smo razmatrali i fairness tj. potrebu da korisnici budu zadovoljeni u određenim omjerima, što smo riješili pohlepnom heuristikom – evo “screenshota” iz članka (chunk je unaprijed fiksiran skup uzastopnih potkanala): Potom treba rasporediti snagu po potkanalima da se maksimizira ukupna brzina. Nakon malo matematike to se svodi na jednadžbu oblika f(x) = P, gdje je P ukupna snaga koju raspoređujemo. Budući da je f rastuća, jednadžba se riješi binarnim pretraživanjem.
3. Navest ću i konferencijski članak čiji sam koautor, a glavni je i najzaslužniji autor moj kolega Petar Afrić. Riječ je o kombinatornom problemu vezanom uz grafove, tzv. school bus routing problem, gdje (pojednostavljeno rečeno) učenici trebaju biti dodijeljeni potencijalnim autobusnim postajama te se trebaju konstruirati rute autobusa tako da se svi učenici prevezu do škole uz što manju ukupnu udaljenost. Problem u praksi nije optimalno rješiv jer je NP-težak. Afrić je smislio vrlo zanimljiv heuristički algoritam; ovdje ga ne opisujem jer bi zauzeo previše mjesta.
4. U članku koji je dio mog doktorata (pod mentorstvom prof. Marina Šilića) bavim se problemom odabira instanci web usluga u oblaku: koja instanca će odgovoriti na koji zahtjev (request) u određenom trenutku, a da se nijedna ne preoptereti i da se zadovolje određena ograničenja na kvalitetu usluge? Vrlo pojednostavljeno, to je nekakav višekriterijski matching. Taj sam problem, uz određene heurističke definicije cijene i drugih varijabli, sveo na kombinatorni transportation problem koji je poseban slučaj minimum-cost maximum-flow problema i rješava se poznatim algoritmima.

Nije mi poznato primjenjuje li se neki od ovih algoritama u praksi: znanost predlaže modele, a industrija ih može i ne mora pratiti i implementirati. U nedostatku aktualne primjene valja se prisjetiti da je doprinos znanosti vrlo rijetko izravan: jedan rad se nadovezuje na drugi, drugi na treći, treći na četvrti i tako dalje, u nadi za konvergencijom u nešto što će ljudima olakšati život. Ako vam to ne zvuči uvjerljivo, možda biste trebali ići u industriju; tamo je i više novaca. Zbog uobičajene politike znanstvenih časopisa koji zarađuju na pretplatama, ovi članci nisu javno dostupni pa ih ne smijem ni javno objaviti. Ako je netko zainteresiran da ih pročita, neka mi se slobodno javi preko kontakt forme. Ono što mogu objaviti je prezentacija u kojoj je velik dio posvećen radu pod brojem 4, te Afrićeva prezentacija o radu pod brojem 3.

Ovu anegdotu o podjeli troškova zapisao sam prije pet ili više godina, a inspirirana je stvarnim događajem.

Mirko i Slavko taksijem su se vraćali iz kazališta kući. Kako Mirko živi bliže kazalištu nego Slavko, taksi je prvo vozio do Mirkova doma. Kad je stigao, na taksimetru je pisalo 40 kuna. Mirko je izašao, a taksi je vozio dalje do Slavkova doma: kad je stigao, na taksimetru je pisalo 70 kuna. Cijeli račun platio je Slavko. 

Sljedećeg dana nastala je rasprava oko pitanja: koliko je Mirko dužan Slavku? Drugim riječima, od ukupno 70 kuna za taksi, koliko treba platiti Mirko, a koliko Slavko?

Slavko: Da nam bude lakše razmišljati, pretpostavimo da je jedna kuna cijena jedne minute vožnje.

Mirko: U redu. Stvar je onda jednostavna: ja sam se vozio 40 minuta, a ti 70 minuta. Jasno je da cijenu valja dijeliti u omjeru 40 : 70. Kada to izračunamo, dobivamo da ja trebam platiti 25.45 kuna, a ti 44.55 kuna.

Slavko: Ni slučajno! Ja sam se zaista vozio 70 minuta, ali samo zato što je taksi prvo tebe vozio kući, pa je zato do moje kuće vozio duljim putem. Da je taksi najprije vozio mene, vozio bih se samo 50 minuta!

Mirko: Ne možeš razmatrati tu mogućnost jer se nije dogodila. Ona bi nam bila skuplja jer bi tada ukupna cijena bila 80 kuna (50 minuta do tvoje i još 30 minuta do moje kuće). Odabrali smo povoljniju mogućnost i samo nju treba razmatrati.

Slavko: U redu; evo jednog primjera kojim ću pokazati da ti zaključivanje ne valja. Pretpostavimo da ja živim jednako udaljen od kazališta kao i ti. Pratiš li me?

Mirko: Pratim.

Slavko: Kad bi taksi najprije vozio do tebe 40 minuta i potom do mene još 5 minuta, u kojem bismo onda omjeru dijelili cijenu?

Mirko: 40 : 45.

Slavko: A u drugom slučaju, kad bi taksi najprije mene doveo kući, a tek onda tebe?

Mirko: U tom bi slučaju bilo obrnuto: ja bih platio dulji put, a ti kraći. Dakle, 45 : 40.

Slavko: Ali ukupna cijena bila bi ista u oba slučaja. To znači da bi naša podjela ovisila o odabiru između dviju jednako povoljnih mogućnosti i počeli bismo se svađati oko pitanja koga bi taksi trebao dovesti prvoga. Ne bi li onda jednostavno bilo najpravednije da platimo jednaku cijenu, tj. da omjer bude 1 : 1?

Mirko: U redu, u tom slučaju bi bilo.

Slavko: Slažeš li se onda da u našem, stvarnom slučaju, cijenu trebamo dijeliti u omjeru udaljenosti od kazališta – 40 : 50? Jer ja bih se vozio 50 minuta, mnogo kraćim putem, da taksi nije najprije tebe odvezao.

Mirko: I dalje se ne slažem jer u našem slučaju mogućnosti nisu jednako povoljne.

Slavko: U redu, promotrimo malo drugačiji primjer. Pretpostavimo da sam ja udaljen od kazališta 41 minutu, samo jednu više nego ti (ali u drugom smjeru). Kad bi taksi najprije vozio do tebe 40 minuta i potom do mene još 30 minuta, u kojem bismo onda omjeru dijelili cijenu?

Mirko: Opet 40 : 70. Ali u tom slučaju ti bi platio više nego da si sam išao taksijem, pa se tebi taksi ne bi isplatilo uzimati.

Slavko: E tu sam te čekao! Jer ako bismo tada dijelili trošak u omjeru najkraćih putova, dakle 40 : 41, taksi bi se isplatilo uzeti i meni i tebi. Slažeš li se onda da je taj omjer bolji?

Mirko: Da, u tom slučaju jest. Ali ovo nije takav slučaj, ovdje se tebi taksi isplatio čak i ako se složiš s omjerom 40 : 70 za koji mislim da je ispravan. Dopusti da i ja tebi predstavim jedan primjer. Pretpostavimo da si od kazališta udaljen 70 minuta najkraćim putem, ali u istom smjeru kao ja, tako da bi taksi vozio 40 minuta do mene i potom 30 minuta do tebe kao u našem slučaju. Bi li se onda složio s omjerom 40 : 70?

Slavko: Da, točno tada bih se s njime složio.

Mirko: Ali u čemu je razlika između tog slučaja i našeg, stvarnog, ako su cijene potpuno iste? Kakve veze ima najkraći put od kazališta do tvoje kuće ako taksi tim putem nije vozio? Važan je stvarni put koji je taksi prešao jer je na temelju njega određena ukupna cijena koju plaćamo. Jedine udaljenosti koje valja uračunati su one koje je taksi zaista prešao, a to su udaljenost od kazališta do moje kuće, te udaljenost od moje do tvoje kuće.

Slavko: To nije pravedno: do svoje kuće računaš najkraći put, a do moje ne računaš nakraći, nego znatno dulji put.

Mirko: Ali taksi je do tvoje kuće morao ići duljim putem.

Slavko: Da, zbog tebe! Ja sam ti učinio uslugu: taksi je do moje kuće išao duljim putem samo zato da usput doveze i tebe. Umjesto da mi ta činjenica ide u prilog, ti mi tu uslugu još naplaćuješ!

Mirko: I ja sam tebi učinio uslugu, jer da si taksijem išao sam, platio bi 50 kuna, a ovako smo dio cijene podijelili te zapravo trebaš platiti manje!

Slavko: Ne slažem se. Kao što rekoh, ispravan omjer je 40 : 50, što znači da ti trebaš platiti 31.11, a ja 38.89 kuna.

Tko je u pravu?

U pretprošloj objavi bila je riječ o igrama botova i AISportsu. Ovdje se prisjećam HSIN-ove Zimske škole informatike u Krapini 2011. godine kada smo Ivica Kičić i ja organizirali jednu takvu igru. Nije to bio prvi put da se na kampu radi igra botova, Kalinovčić i ekipa organizirali su nešto slično na nekim još davnijim kampovima, mislim da je u pitanju bila neka inačica igre Achtung, die Kurve!. Naša je igra bila drugačija, jednostavnija i možda manje zanimljiva za gledanje sa strane. Na turniru je pobijedio Tomislav Tunković.

O toj igri napisao sam članak za Matematičko-fizički list koji možete pronaći ovdje. Taj članak i nije naročito stručan jer tada nisam znao za teoriju igara, miješane strategije, strojno učenje i slično. Vjerojatno postoje i bolje strategije od navedenih.

Je li vam se ikada dogodilo da vas na Messengeru kontaktira nepoznata cura/mladić te vas vrbuje za nekakav navodno dobro plaćen studentski posao, vezan za promociju neke nove firme ili proizvoda koji je navodno u velikom usponu? Meni se to dogodilo dvaput, a prijatelja su i na ulici zaustavili za tako nešto i gnjavili desetak minuta. Srećom, odgovaranje na spam može biti zabavno: odlučio sam uzvratiti istom mjerom i ponašati se upravo poput osobe koja me gnjavi. Neće ona mene vrbovati, vrbovat ću ja nju, ponudit ću joj posao iz snova. Umjesto odgovora na njezino pitanje, napisao sam joj sljedeće:

Moji prijatelji i ja želimo pokrenuti Matematički radio, a to bi bio radio s matematičkim emisijama, zadatcima, vijestima iz teorijske matematike i slično. U procesu smo traženja frekvencije i treba nam osoba koja će to handlati. Osim toga tražimo spikere, spikerice, urednike (ne nužno s matematičkom pozadinom), osobe za promociju na društvenim mrežama, osobe za brandiranje i stvaranje branda, dizajnere logotipa i vizualnog identiteta, kao i osobe koje će promocijom na društvenim mrežama uvjeriti “običnu” publiku da matematika nije bauk i da slušanje matematičkog radija može biti izvrsno za opuštanje tijekom radnog dana ili prilikom putovanja u školu, faks ili posao, tijekom vožnje automobilom, tramvajem, autobusom, brodom…

Emisije koje smo već osmislili uključuju “Buđenje uz kombinatornu geometriju”, “Jutarnje vijesti iz teorijske matematike”, “Zadatak dana”, “Vježba iz diferencijalne topologije”, “Stanje u prometu”, “Celebrity kutak: vijesti s matematičke estrade” i “Večer uz harmonijsku analizu”.

Pa kako ti to zvuči?

Cura je to pristojno odbila, ali nisam odmah odustao, možda je privuku još neke emisije…

Ubacit ćemo i Nagradne zadatke iz normiranih prostora i Kviz iz numeričke analize. Jer želimo privući što više slušatelja.

No reply.

Možda kasno navečer “Opuštanje uz dvostruke integrale”.

No reply.

I “Zadatak za laku noć”.

No reply, kao što bi rekli Beatlesi. Nema veze, ja sam svoje napravio. Ali dužan sam objasniti što je Matematički radio i je li to zbilja samo neozbiljna šala ili možda i nešto više.

Kako je sve počelo

Kao što se, recimo, hrvatski jezik u povijesti prvi put spominje u nekom dokumentu na glagoljici, tako se Matematički radio prvi put spominje u jednom informatičkom zadatku. Riječ je o tekstu zadatka Dom (HONI 2012.). U toj priči vlada pokušava zadržati mlade genijalce da ne odlaze u inozemstvo tako što im šalje subliminalne poruke putem matematičkog radija. Nije rečeno kakav je to matematički radio, ali pretpostavlja se da ga mladi genijalci slušaju. Bilo bi odlično, pomislio sam, kad bi zaista postojao takav radio. Slijedeći savjet iz jedne pjesme U2-a (“You can dream, so dream out loud”), odlučio sam o toj ideji i manje-više javno govoriti.

Odakle krenuti? Sjećate se kad su Kumerle i Irena, u odličnoj seriji Bitange i princeze, odlučili krenuti u glazbene vode i napraviti hit pjesmu? Sve je bilo spremno za snimanje golišavog spota, redatelj je zatražio CD da posluša pjesmu prije snimanja, a oni su rekli da još nemaju pjesmu. Redatelj je poludio: kako nemate pjesmu? Zašto onda snimate spot? A Kumerle je mudro odbrusio: Pa moraš od nečeg počet!

E tako sam i ja odlučio krenuti od logotipa. Nacrtao sam ga u stanovitom grafičkom alatu (nije sada važno u kojem) i odmah stavio na fejs:

Reakcije su bile, recimo to tako, nejasne (mixed reactions). Zaključio sam da mi očito treba bolji logotip, pa sam napravio još tri prijedloga, a usput definirao i radijsku frekvenciju:

Rekli su mi da trebam smisliti i slogan. Budući da je riječ o edukativnom radiju, predložio sam jednostavno: Matematički radio: slušaj i uči.

Na to mi je prijatelj odgovorio da je bolje Slušaj, šuti i uči. Ili, još bolje: Slušaj i šuti.

Matematički radio: slušaj i šuti

Zadnji update u vezi Matematičkog radija dogodio se kad sam napokon osmislio jedan dnevni program i odlučio ga objaviti.

Možda ste primijetili, a možda i niste, da je post objavljen prvoga travnja. Ispada da je sve šala i zajebancija, zar ne? To je samo dio istine. Matematički radio jest šala i zajebancija, ali on je i mnogo više od toga. Matematički radio je ideja, koncept čija je ljepota očigledna onima koji žive za matematiku i slične znanosti. To je nešto što bi u raju (ako ga ima) sigurno postojalo: Bog ne bi matematičare poslao u raj u kojemu nema Matematičkog radija. To je radijska postaja koju bi većina čitatelja ovog bloga (ako ih ima) sigurno palila prije svih ostalih. To je svjetiljka svoj onoj djeci koju roditelji tjeraju da se idu vani igrati s prijateljima dok im na stolu stoji neriješena nejednakost s državnog 2001. ili sa shortlista 1996. To je ideja koja je sasvim bizarna – matematika je u praksi vizualna, ona se čita/piše, može se i gledati na youtube videima, no vrlo ju je teško samo slušati na nekakvom radiju – ali ta bizarnost Matematičkom radiju daje nadnaravni duh. Poanta radija i jest u njegovoj nevidljivosti i nematerijalnosti, što vrijedi i za matematiku.

Matematički radio trebamo pokrenuti kao spomenik matematici i zato ovo neće biti posljednji post o toj ideji. Prvoaprilske šale mogu potrajati: i ovaj blog (Blogaritam) pokrenut je na prvi april. A čuo sam da je, prema nekim izračunima, i naš svemir nastao na prvi april. Možda je sve ovo jedan veliki Matematički radio.