Predslike 2D celičnih avtomatovJERAS, IZTOK (Avtor) Šter, Branko (Mentor) celični avtomatipredslikepredhodnikiračunska zahtevnostreverzibilnostrajski vrtConwayeva igra življenjatridquadMedtem ko je računanje predslik 1D celičnih avtomatov dobro raziskan in podrobno dokumentiran problem, je to področje pri 2D celičnih avtomatih manj raziskano. Za 1D problem poznamo algoritme za štetje in izpis predslik s procesno zahtevnostjo linearno odvisno od velikosti problema. Možno je tudi določiti, ali je 1D celični avtomat reverzibilen in kakšen je regularen jezik vseh stanj brez predslik. Pri 2D problemu sicer poznamo nekaj algoritmov za iskanje predslik, vendar so slabo teoretično raziskani. Vemo tudi, da je problem reverzibilnosti 2D celičnih avtomatov na splošno neodločljiv. Mreža predslik, ki sem jo razvil za potrebe analize predslik 1D celičnih avtomatov, se je izkazala za praktično orodje pri razlagi algoritmov in pri dokazovanju njihove pravilnosti. Tukaj opišem, kako se mrežo predslik tvori za 2D celične avtomate. Če je bila ta mreža za 1D problem navaden graf, je za 2D problem razširjena v tretjo dimenzijo. Predslike so namesto poti v grafu ploskve na mreži. Robni pogoj se spremeni iz uteži za vozlišča, ki zaključujejo pot v 1D problemu, v uteži za sklenjeno pot okoli ploskve predslike v 2D problemu. Pri razvoju algoritma se je izkazalo, da štetja predslik 2D celičnega avtomata ni mogoče izvesti v linearni odvisnosti od velikosti problema. Zahtevnost podanega algoritma narašča eksponentno z velikostjo problema v eni dimenziji. Podani algoritem se ne razlikuje dosti od obstoječih. Celični avtomat razdeli na vrstice in išče predslike za posamezno vrstico od prve do zadnje. Vrstične rezultate nato združi v rešitev za celoten 2D problem. Podobno kakor pri algoritmu za 1D probleme, je analiza razdeljena v dva prehoda. V prvem prehodu po vrsticah algoritem prešteje predslike, v drugem opcijskem prehodu pa predslike izpiše. Drugi prehod poteka v obratni smeri kakor prvi prehod, tudi procesiranje posamezne vrstice poteka iz drugega zornega kota. Glavni napredek algoritma vidim v uporabi učinkovitih rešitev za 1D problem pri analizi vrstic ter v uporabi progresivnega kodiranja vmesnih rezultatov, kar lahko zmanjša porabo pomnilnika.20162016-09-30 13:00:08Magistrsko delo85959sl