Nonogrami

magistrsko delo

Aljaž Ferk (Avtor), Andrej Taranenko (Mentor)

Povzetek

Nonogram je uganka, s katero lahko ob njenem reševanju narišemo sliko. Magistrsko delo je namenjeno algoritmičnemu reševanju črno-belih nonogramov. S temi algoritmi lahko preverjamo pravilnost rešitve nonograma in jih lahko uporabljamo tudi kot pomoč pri človeškem reševanju. Najprej je predstavljen algoritem, ki lahko reši le nekatere nonograme, kasneje je ta algoritem nadgrajen tako, da najde vse možne rešitve. Odgovori tudi vprašanje, kako dober je prvoten algoritem ob večanju dimenzij naključnih nonogramov. Predstavimo tudi hiter način barvanja kotov nekaterih nonogramov. Na koncu je predstavljen tudi vpliv nekaterih komponent na čas reševanja nonograma.

Ključne besede

magistrska dela;nonogram;Chernoffova meja;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2022
Tipologija:	2.09 - Magistrsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[A. Ferk]
UDK:	51:793.7(043.2)
COBISS:	127463427
Št. ogledov:	4
Št. prenosov:	1
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Nonograms
Sekundarni povzetek:	A nonogram is a puzzle, with which we can draw a picture, while solving it. The thesis provides algorithmic solutions to black-and-white nonograms. With these algorithms we can check the correctness of the nonogram's solutions, and we can also use them as an aid for human solving. First, an algorithm is presented that can solve only some nonograms, and later on this algorithm is improved so it finds all possible solutions. The question of how good the first algorithm is when increasing the dimensions of random nonograms is also answered. A quick way to paint the corners of some nonograms is also presented. Lastly, the influence of some components on the time it takes to solve a nonogram puzzle is presented.
Sekundarne ključne besede:	master theses;nonogram;Chernoff bound;Algoritmi;Naloge, vaje itd.;Univerzitetna in visokošolska dela;
Vrsta dela (COBISS):	Magistrsko delo/naloga
Komentar na gradivo:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani:	55 str.
ID:	15955275