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 = 2⁶, š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 2¹⁰ š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.

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 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 . 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 bolji od algoritma iz članka koji se izvorno bavi tim praktičnim problemom.

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).