Čudesni svijet teorije grafova
Teorija grafova je grana matematike koja se razvila iz problema Konigsbergških mostova: može li građanin grada Konigsberga (današnji Kaliningrad, Rusija) prošetati svojim gradom tako da svaki most obiđe točno jednom?
Ovaj problem riješio je poznati matematičar Leonhard Euler 1736, a njegovo rješenje smatra se začetkom teorije grafova.
Graf je uređeni par (V,E), gdje je V skup vrhova, a E je kolekcija bridova: uređenih parova (v1,v2), gdje su v1, v2 (ne nužno različiti) vrhovi iz V. Kažemo da su v1 i v2 susjedni vrhovi, a broj susjeda vrha v zovemo stupnjem vrha v.
Euler je formirao graf čiji vrhovi su područja grada omeđena mostovima u kojem su dva vrha susjedna ako i samo ako su povezana mostom. Koristeći taj graf, zaključio da ne postoji tražena šetnja gradom.
Teorija grafova pruža moćne alate za modeliranje i rješavanje problema koji uključuju odnose, povezanost i kretanje unutar složenih sustava.
Jedna od njezinih najvažnijih primjena je transport i logistika, gdje se cestovne, željezničke i zračne mreže predstavljaju kao grafovi. Algoritmi poput Dijkstrinog algoritma najkraćeg puta pomažu u određivanju najbrže ili najjeftinije rute između odredišta, poboljšavajući navigacijske sustave i planiranje dostave.
U računalnim i komunikacijskim mrežama, grafovi modeliraju veze između računala, poslužitelja i usmjerivača. Koriste se za dizajniranje učinkovitih mrežnih struktura, otkrivanje ranjivosti i optimizaciju prijenosa podataka. Internetski protokoli usmjeravanja uvelike se oslanjaju na metode temeljene na grafovima.
Teorija grafova također igra središnju ulogu u analizi društvenih mreža. Pojedinci su predstavljeni kao vrhovi, a njihove interakcije kao bridovi. To omogućuje identifikaciju utjecajnih korisnika, otkrivanje zajednica i analizu informacija koje se šire na platformama društvenih medija.
U biologiji i medicini, grafovi se koriste za modeliranje interakcija gena, proteinskih mreža i neuronskih veza u mozgu. Takvi modeli pomažu istraživačima da razumiju biološke procese, identificiraju gene povezane s bolestima i proučavaju strukturu složenih bioloških sustava.
Druga važna primjena je raspoređivanje i alokacija resursa. Tehnike bojanja grafova koriste se za rješavanje problema rasporeda, poput dodjeljivanja sveučilišnih kolegija vremenskim terminima bez sukoba. Slične metode primjenjuju se u dodjeljivanju frekvencija za bežične komunikacijske mreže.
Teorija grafova također se široko koristi u robotici i umjetnoj inteligenciji.
Karte okoliša, labirinti i navigacijski problemi mogu se predstaviti kao grafovi, što robotima omogućuje planiranje putova, istraživanje nepoznatih područja i koordinaciju djelovanja više agenata. Igre izbjegavanja potjere poput Policajaca i Razbojnika su modeli teorije grafova koji se koriste za proučavanje strategija pretraživanja i hvatanja.
Ovi primjeri pokazuju kako teorija grafova pruža zajednički matematički okvir za rješavanje problema koji uključuju mreže, interakcije i optimizaciju u znanosti, inženjerstvu i svakodnevnom životu.
Autori teksta: Vedrana Mikulić Crnković, Bojan Crnković i Ivona Traunkar, Fakultet za matematiku, Sveučilište u Rijeci
Autori slike: Slika je generirana pomoću alata umjetne inteligencije
Kakvu poruku poslati?
Znate li razliku između kodiranja i šifriranja? Iako se često ti pojmovi poistovjećuju, radi se potpuno različitim procesima sa različitom namjenom u svakodnevnom životu. Upustite se s nama u priču o kodovima i priču o šiframa.
Priča o kodovima
Matematička priča o kodiranju započinje sredinom 20. stoljeća. Priča započinje dolaskom matematičara Richarda Hamminga u Laboratorij Bell. Hamming je bio član odjela koji se je bavio matematičkim istraživanjima. Iako je, kako sam kaže, bio prvorazredni “troublemaker” te nije pristupao rješavanju problemima na do tada uobičajene načine imao je značajne rezultate te ga je uprava tolerirala. Iako je prvenstveno bio angažiran za rješavanje problema vezanih za elastičnost, provodio je mnogo vremena razmišljajući o problemima kojima se prethodno bavio, a koji su vezani uz IBM stroj za računanje rješenja diferencijalnih jednadžbi koje su proizašle iz fizikalnih problema.
Priča o kodovima započinje sasvim slučajno jednog petka popodne 1947. godine. Tog je petka Hamming namjestio svoj stroj za računanje da preko vikenda odradi dugačak i zahtjevan slijede izračuna. Ali… u ponedjeljak je shvatio da je došlo do pogreške u ranoj fazi izračuna i posao od cijelog vikend je propao. Stoj je zapisivao informaciju u obliku niza nula i jedinica te ako je na bilo kojoj poziciji došlo do promjene 0 u 1 ili obrnuto cijela je informacija, pa samim time i cijeli izračun, bila kriva. Prvi pokušaj detektiranje pogreške je bio bitom za provjeru parnosti.
Hamming je razmišljao na sljedeći način: ako bi stroj znao da je do pogreške došli sigurno bi se mogao smisliti i neki način da se ta pogreška ispravi. Hamming si je zadao zadatak da riješi taj problem. Bio je svjestan da bi rješenje takvog problema zasigurno imalo brojne primjene za posljedicu.
Već 1950. godine Hamming je objavio rad u kojem uvodi osnovne pojmove teorije kodiranja (npr. udaljenost između dva niza koja se njemu u čast zove Hammingova udaljenost) i familiju kodova koji mogu detektirati i ispraviti pogreške koji se njemu u čast zovu Hammingovi kodovi. Taj se rad smatra začetkom teorije kodiranja.
Primjeri:
1. Kod s ponavljajućim bitovima. Pretpostavimo da želimo prenijeti informaciju zapisanu binarnim nizom duljine jedan, npr. 1. S ciljem efikasnog otkrivanja i ispravljanja greške, pošaljimo niz duljine osam: 11111111. Na ovaj način moći ćemo otkriti najviše 7 pogrešaka te ispraviti najviše 3 pogreške.
2. Kod s provjerom parnosti. Pretpostavimo da želimo prenijeti informaciju zapisanu binarnim nizom duljine sedam, npr. 1110001. Pri prijenosu ćemo dodati i 8. član niza a: a = 0 ako početni niz ima paran broj jedinica, a = 1 ako početni niz ima neparan broj jedinica. U primjeru to znači da šaljemo niz: 11100010. Na ovaj način moći ćemo otkriti neparan broj pogrešaka u prijenosu ali nećemo moći ispraviti niti jednu pogrešku.
U dva smo primjera koristili binarne nizove duljine 8 u prijenosu informacija. U prvom smo prenijeli manje informacija uz veću mogućnost otkrivanja i ispravljanja greške dok smo u drugom primjeru prenijeli više informacija uz manju mogućnost otkrivanja i ispravljanja greške.
Osnovni problem teorije kodiranja je naći kod kojim možemo prenijeti zadovoljavajuću količinu informacije uz zadovoljavajuću mogućnost detekcije i ispravljanja greške.
Hammingov kolega u Laboratoriju Bell je bio Clauda Shannon, matematičar, inženjer, kriptograf, čiji rad A Mathematical Theory of Communication iz 1948. godine se smatra začetkom teorije informacija. Shannon je dokazao da za dani epsilon > 0 i R konačan broj postoji kod koji prenosi R informacija uz vjerojatnost greške manju od epsilon te je na matematičarima da osmišljavaju kodove koji će nam omogućiti svakodnevnu nesmetanu komunikaciju.
Od tada se teorija kodiranja brzo razvija, a sve s ciljem konstrukcija kodova s dobrim svojstvima, kodova koji mogu prenijeti puno informacija, detektirati i ispraviti što veći broj riječi, brzo dekodirati primljenu poruku… Razvoj teorije kodiranja motiviranje je i njezinom veliko primjenom u svakodnevnom životu: svakodnevna komunikacija, prijenos informacija iz svemira, pohranjivanje podataka….
Što je zapravo kod? Kod je skup riječi (nizova simbola) koje koder kreira i šalje u komunikacijski kanal. Svaka riječ koda nastala je od ulazne poruke (informacije) koju zapravo želimo poslati. Iako ova naša priča o kodiranju započinje tek sredinom 20. stoljeća, ljudi su se susreli sa sličnim problemima i njihovim rješenjima puno, puno prije toga… Primjer: Morsov kod: 1835. konstruiran je Morsov telegraf koji je koristio Morsov kod.
Ali još puno, puno prije toga ljudi su počeli razvijati jezik za međusobnu komunikaciju. Naši su jezici napravljeni tako da naš mozak, najbolji dekoder koji postoji, uspije detektirati i ispraviti brojne pogreške koje se događaju u komunikaciji (npr. gutanje slova u izgovoru, frfljanje, lapsusi u pisanom tekstu, ….). Uočimo da bi se sve riječi u hrvatskom jeziku, kojih ima oko pola milijuna, mogle napisati sa 4 ili manje slova. Međutim, u tom slučaju jako puno riječi bi se razlikovalo samo za jedno slovo (kao npr. KIST i LIST) te bi bilo jako lako dolazilo do pogreške, npr. pri pisanju, te bi se te pogreške teško ispravljale. Puno bismo lakše uočavali i ispravljali lapsuse kad bi svaka riječ imala npr. 10 ili više slove. Međutim, to bi nam bilo jako nepraktično kako u pisanju tako i u govoru.
Vizualno šifriranje
Šifriranje je postupak kojim skrivamo naše poruke tako da ih ne može bilo tko pročitati.
Kako sakriti odnosno na siguran nacin sifrirati sliku? Je li moguce na siguran nacin podijeliti tajnu sliku prijateljima koji ju nece moci samostalno vidjeti vec tek nakon sto se svi sastanu na jednom mjestu? Vizualno sifriranje je metoda dijeljenja tajne slike na odgovarajuci broj sudionika tako da niti jedan sudionik samostalno ne moze otkriti tajnu. Kod vizualnog sifriranja tajna se informacija na siguran nacin sifrira tako da se njezino desifriranje moze izvrsiti koristeci iskljucivo ljudski vid. Ljepota i jednostavnost takvog sifriranja je u nacinu sifriranja i desifriranja tajnih podataka koje ne zahtijeva posebno znanje o sifriranju niti zahtjevno racunanje. Vizualno sifriranje uveli su Adi Shamir i Moni Naor 1994. godine nakon cega se ubrzano razvija. Osim za distribuciju i zastitu tajnih podataka, vizualno sifriranje danas se koristi za identi kaciju/autenti kaciju, sprecavanje plagiranja materijala, izradu i citanje QR kodova i slicno.
Matematičari su osmislili mnoge načine šifriranja koji danas uspješno čuvaju naše tajne. Pred matematičarima danas stoji izazov osmišljavanja načina šifriranja koje kvantno računalo ne može lako probiti.
Autori teksta: Vedrana Mikulić Crnković, Bojan Crnković i Ivona Traunkar, Fakultet za matematiku, Sveučilište u Rijeci
Autori slike: Slika je generirana pomoću alata umjetne inteligencije