Predstavljajmo si, da je več divizij bizantinske vojske obkolilo sovražno mesto in vsako divizijo vodi svoj general. Slednji lahko med seboj komunicirajo le preko kurirja. Sprva si sovražnika dobro ogledajo, nato pa morajo narediti skupen načrt za napad. Dodatni problem je, da so med generali lahko tudi izdajalci, ki želijo preprečiti zvestim generalom, da bi dosegli enoten dogovor. Za potrebe generalov torej potrebujemo poseben algoritem, ki poskrbi za naslednja dva pogoja (recimo jima A in B).
A: Vsi zvesti generali se po določenem usklajevalnem času odločijo za isti načrt.
Zvesti generali se bodo vsi odločili na podlagi rezultatov algoritma, izdajalci pa se bodo odločili po svoje. Pri tem mora algoritem zagotoviti pogoj A, ne glede na dejanja izdajalcev. Ker pa ni dovolj, da se zvesti generali le strinjajo med sabo, ampak je pomembno tudi to, da je načrt za katerega se odločijo smiseln, je potrebno zagotoviti tudi to, da:
B: majhna številka izdajalcev ne more povzročiti, da bi zvesti generali prevzeli slab načrt.
Zgornji Problem Bizantinskih generalov je namenoma zastavljen zelo široko in očitno je, da bi za natančno matematično formulacijo potrebovali vsaj definicijo pojmov, kaj je slab načrt, kaj pomeni majhna številka izdajalcev, na kakšen način poteka komunikacija preko kurirjev. Spodaj je naveden na prvi pogled popolnoma drugačen problem, ki pa je v svojem bistvu zelo podoben zgornjemu:
V zloglasnem zaporu Alcatraz so ujetniki ves čas zaprti v svoji celici, brez medsebojne komunikacije. Nekega dne se po zvočniku zasliši naslednje obvestilo glavnega nadzornika:
Spoštovani zaporniki!
Od danes naprej bomo v zaporu igrali ti. »igro devetih barv«. Za naš zapor sem pripravil veliko vrečo kroglic v devetih različnih barvah, ki so v tem trenutku v barvnem razmerju 2:1:1:1:1:1:1:1:1 – prve barve je torej na začetku malo več, vendar ne veste katere.
Vsako uro bo v vašo celico paznik prinesel to vrečo, pri čemer lahko vsakič na slepo izvlečete novo kroglico, jo (po dogovoru s paznikom) zamenjate s poljubno drugo barvo, ter jo nato vrnete nazaj v vrečo.
Po nekaj dneh bo vsak od vas poskusil uganiti začetno dominantno barvo. Tistim ki uspe, bodo izpuščeni.
Izkaže se, da lahko tudi v primeru ko je zapor še tako velik, po nekaj dnevih vsi ujetniki z visoko verjetnostjo uganejo pravo barvo, vendar je pot do rešitve vse prej kot majhen matematični trik. Kljub vsemu je družina teh in podobnih problemov izjemnega pomena v sodobnem času, uporablja se že pri sinhronizaciji vsakega več-jedrnega procesorja, v poraz- deljenih podatkovnih bazah, doseganju skupinskih konsenzov, ter nenazadnje v tehnologiji veriženja blokov (Blockchain), na kateri temelji večina poznanih kriptovalut.
Pri igranju z omenjenimi problemi bomo spoznali osnove verjetnosti, tj. veja matematike ki preučuje verjetnost, da se zgodi naključni dogodek. Pri računanju verjetnosti nam pogosto pomaga kombinatorika. Za lažjo analizo se bomo morali poglobiti med drugim tudi v teorijo grafov. Ta zavzema koristne tehnike za reševanje različnih optimizacijskih problemov, ter pogosto nudi nov pogled na izbrani problem. Z grafi lahko opazujemo povezanost stvari med seboj in tudi interakcijo med njimi. Velik plus za spopad s problemom pa je seveda poznavanje osnov programiranja.
Mentor: dr. Matjaž Krnc, Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijsko tehnologijo
E-Pošta: matjaz.krnc@upr.si