Hromatska svojstva konačnih grupa
Veljko Toljić (2003) učenik 4. razreda Gimnazije "Svetozar Marković", Niš Mentorstvo: Branislav Šobot, diplomirani matematičar
Svakoj grupi se mogu pridružiti takozvani Kejlijevi grafovi koji čuvaju dosta kombinatorno-geometrijskih informacija o njoj i u ovom radu se bavimo proučavanjem hromatskih svojstava ovih grafova. Hromatski broj grafa je najmanji broj k takav da svakom čvoru možemo dodeliti jednu od k boja, a da nikoja dva suseda nisu obojena istom bojom. Pokazujemo da svaka konačna grupa ima Kejlijev graf hromatskog broja ne većeg od 3. Zatim, primenjujemo ono što je poznato o hromatskom broju grupe da pokažemo da grupa ima podgrupu indeksa 2 ako i samo ako ima prezentaciju u kojoj je svaka reč parne duzine. Nakon toga, uvodimo hromatski indeks grupe kao najmanji hromatski indeks nekog njenog Kejlijevog grafa i izračunavamo ga za sve konačne proste grupe, simetrične, slobodne i ciklične grupe, kao i za sve konačne abelove grupe. Pored toga, dajemo ekvivalentan uslov da je hromatski indeks grupe jednak 2. Uz to, kao glavni rezultat, pokazujemo da svaka konačna abelova grupa ima Kejlijev graf koji u isto vreme dostiže hromatski broj, hromatski indeks i najmanji moguć stepen čvora. Konačno, dajemo neka propratna ograničenja kojima je moguće oceniti hromatski indeks grupe. Jedan neformalni zaključak ovog rada je to da je hromatski indeks grupe lako izračunati kada je data konkretna konačna grupa koja ima male generatorne skupove sa puno elemenata čiji je kvadrat neutral.
Pakovanje figurica pomoću veštačke inteligencije
Andrija Živadinović (2005) učenik 3. razreda Gimnazije "Svetozar Marković", Niš Aleksa Đorđević (2003) učenik 4. razreda Gimnazije "Svetozar Marković", Niš Đorđe Stevanović (2003) učenik 4. razreda Gimnazije "Svetpzar Marković", Niš Veljko Toljić (2003) učenik 4. razreda Gimnazije "Svetozar Marković", Niš Mentorstvo: dr Bojan Bašić, Univerzitet u Novom Sadu, Prirodno-matematički fakultet
Problem pakovanja podrazumeva pakovanje određenog broja figura unapred zadatog oblika u što manju figuru unapred zadatog oblika. Do sada poznata najoptimalnija pakovanja mogu se naći na linku: https://erich-friedman.github.io/packing/ . Projekat se bavi problemom pakovanja određenog broja identičnih figura oblika L (nalik kvadratu kome fali jedna četvrtina) u što manji kvadrat. Cilj projekta je pronalaženje heurističkog algoritma koji bi mogao da dostigne poznata optimalana pakovanja pronađena drugim heurističkim algoritmima, ili da ih poboljša u idealnom slučaju. Posmatrajući do sada najbolja poznata pakovanja pretpostavili smo da se ona mogu postići raspoređivanjem figura na neki način u oblast u koju se pakuju figure i potom sabijanjem te figure dokle je fizički moguće. Naš model veštačke inteligencije uspeo je da konstruiše već poznata najbolja pakovanja, kao i šuštinski različita pakovanja koja dostižu rezultate blizu najboljih poznatih. Algoritam se bazira na postavljanju figurica u kvadratnu mrežu (posebnim odabirom za koji je odgovorana neuralna mreža) pod određenim uglovima i fizičkoj simulaciji sabijanja kvadrata oko njih. Algoritam veštačke inteligencije je ”deep cross-enthropy method” i ”reinforcment learning”, a biblioteka korišćena za fizičke simulacije u python-u je ”pymunk”. Kako je naš model veštačke inteligencije uspeo da dostigne već poznata optimalna pakovanja uz početne heurističke pretpostavke otvaraju se ideje za dalji rad: matematički dokazati da heuristika dostiže optimalna pakovanja, uopštiti model tako da radi za proizvoljne figure, pokušati drugačije modele veštačke inteligencije itd.
O nekim problemima popločavanja
Aleksa Džuklevski (2003) učenik 4. razreda Gimnazije "Jovan Jovanović Zmaj", Novi Sad Mentorstvo: dr Bojan Bašić, Univerzitet u Novom Sadu, Prirodno-Matematički fakultet
U ovom radu predstavljamo rešenje problema vezanog za izoedarski broj protoskupa, dokazujući da za svaki prirodan broj k ≥ 2 i sve prirodne brojeve n postoji protoskup koji se sastoji od k protopločica, i čiji je izoedarski broj n. Takođe uvodimo novu definiciju izoedarskog broja protoskupa za koju mislimo da je odgovarajući analogon definiciji izoedarskog broja pločice. Pored toga konstruišemo pločicu koja popločava ravan na prebrojivo mnogo načina, a koja ima negeometrijske uslove uklapanja, i pritom predstavljamo tri konstrukcije od kojih se jedna može smatrati neortodoksnom, jedna granično ortodoksnom, a jedna u potpunosti ortodoksnom, gde se ova poslednja dobija malom modifikacijom jedne Šmitove konstrukcije. Takođe ukazujemo na to da se malom modifikacijom druge Šmitove konstrukcije može dobiti m-morfna pločica koja ima negeometrijske uslove uklapanja, za svaki prirodan broj m.
Pozicione igre izbegavanja
Strahinja Gvozdić (2002) učenik 4. razreda Jovan Ludaić (2003) učenik 3. razreda Tehničke škola, Kikinda Mentorstvo: dr Kristina Ago-Balog, Prirodno-matematički fakultet, Novi Sad
Pozicione igre predstavljaju klasu kombinatornih igara u kojima dva igrača naizmenično bojeći polja neke table nastoje da prvi zauzmu sva polja nekog od podskupova koji su označeni kao pobednički. Nakon kratkog osvrta na različite varijacije igre i argument krađe strategije koji je od velikog značaja za teoriju pozicionih igara, detaljnije ćemo se posvetili igrama izbegavanja, u kojima igrači nastoje da izbegnu zauzimanje svih polja nekog gubitničkog podskupa. Kako se u klasičnim pozicionim igrama pokazuje da prvi igrač uvek sebi može da osigura bar nerešeno, postavlja se pitanje da li to važi i za drugog igrača u igrama izbegavanja, koje deluju suprotno klasičnim pozicionim. Ovo se, ipak, ispostavlja kao netačno, zbog čega ćemo se u radu pre svega baviti konstrukcijom igara izbegavanja u kojima pobeđuje prvi. Izuzetno, interesovaće nas tranzitivne igre izbegavanja, u kojima su sva polja identična, te nijedno samo po sebi ne donosi prednost onome ko ga zauzme. Nakon pregleda prethodno poznatih značajnih rezultata, dokazaćemo da za složene neparne veličine table postoji tranzitivna igra izbegavanja u kojoj se boje dva polja po potezu, a u kojoj pobeđuje prvi igrač. Slično ćemo uraditi i za određenu klasu tabli za veći broj bojenja po potezu. Konačno, postavićemo otvorena pitanja o vrednostima praga za broj bojenja po potezu, prelaženjem kojih prvi ili drugi igrač dobijaju pobedničku strategiju, te prodiskutovati naše rezultate u okvirima tih pitanja. Na taj način ćemo predstaviti okvire i za neka buduća istraživanja.
