Poziční hry s efektivní vítěznou strategií
| Název práce v češtině: | Poziční hry s efektivní vítěznou strategií |
|---|---|
| Název v anglickém jazyce: | Positional games with efficient winning strategy |
| Klíčová slova: | poziční hry;silné hry;efektivní strategie |
| Klíčová slova anglicky: | positional games;strong games;efficient strategy |
| Akademický rok vypsání: | 2016/2017 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | čeština |
| Ústav: | Informatický ústav Univerzity Karlovy (32-IUUK) |
| Vedoucí / školitel: | doc. Mgr. Robert Šámal, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 12.05.2017 |
| Datum zadání: | 12.05.2017 |
| Datum potvrzení stud. oddělením: | 19.05.2017 |
| Datum a čas obhajoby: | 06.09.2017 00:00 |
| Datum odevzdání elektronické podoby: | 20.07.2017 |
| Datum odevzdání tištěné podoby: | 21.07.2017 |
| Datum proběhlé obhajoby: | 06.09.2017 |
| Oponenti: | doc. RNDr. Tomáš Valla, Ph.D. |
| Zásady pro vypracování |
| Poziční hry jsou důležitým předmětem výzkumu: dva hráči střídavě obsazují vrcholy daného hypergrafu, vyhraje ten, kdo první obsadí celou hranu hypergrafu.
Častý argument při zkoumáních pozičních her je argument kradení strategie: druhý hráč nemůže vyhrát, protože jinak by jeho strategii mohl použít první a vyhrát dříve. Tento argument je však principiálně neefektivní, neposkytuje efektivní odhad na čas, který hra trvá. Student prozkoumá různé hry z tohoto pohledu, tj. pokusí se hledat efektivní odhady na rychlost výhry prvního hráče. Zejména se bude jednat o klikovou hru, kde hráči barví hrany grafu, a první hráč, který obarví hrany úplného grafu dané velikosti, vyhrává. Dále se práce zaměří na příklady her, kde efektivní výhra není možná a pokusí se porozumět tomu, co odlišuje hry efektivní od neefektivních. |
| Seznam odborné literatury |
| József Beck, Combinatorial Games: Tic-Tac-Toe Theory, Encyclopedia of Mathematics and Its Applications 114, Cambridge University Press, 2008.
Elwyn R. Berlekamp, John H. Conway, Richard K. Guy: Winning Ways for your Mathematical Plays, Academic Press, 1982 A další podle doporučení školitele. |