Hra minolovka - výpočetní složitost a implementace hledání řešení

• Název práce v češtině: Hra minolovka - výpočetní složitost a implementace; hledání řešení
• Název v anglickém jazyce: Minesweeper game - computational complexity and solver implemetation
• Akademický rok vypsání: 2006/2007
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: doc. RNDr. Jiří Fiala, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 05.10.2006
• Datum zadání: 05.10.2006
• Datum a čas obhajoby: 25.06.2007 00:00
• Datum odevzdání elektronické podoby: 25.06.2007
• Datum proběhlé obhajoby: 25.06.2007
• Oponenti: RNDr. Ondřej Pangrác, Ph.D.

Zásady pro vypracování

Cílem práce je klasifikovat konfigurace hry minolovka a to podle výpočetní složitosti problému určení rozmístění min. Je známo, že tento problém je v obecnosti NP-úplný, a proto by primárním cílem bylo navrhnout některé podmínky za nichž by se stal řešitelný v polynomiálním čase.
Očekává se i implementace navržených algoritmů.

Seznam odborné literatury

Kaye R, Minesweeper is NP-complete, Math. Intell. 22 (2) 9--15 (2000)

M. R. Garey and D. S. Johnson. Computers and Intractability. Freeman,
1979.

L. Kučera, Kombinatorické algoritmy, SNTL 1983, 1991.

časopisecká literatura dle doporučení vedoucího

Předběžná náplň práce

Práce se zabývá konfiguracemi hry minolovka a to podle výpočetní složitosti problému určení rozmístění min.

Předběžná náplň práce v anglickém jazyce

The thesis explores positions of the minesweeper game according to computational complexity of the mine location problem.