Název: Competitive filling of a plane region
Překlad názvu: Competitive filling of a plane region
Autoři: Slabý, David ; Valtr, Pavel (vedoucí práce) ; Valla, Tomáš (oponent)
Typ dokumentu: Diplomové práce
Rok: 2012
Jazyk: eng
Abstrakt: [eng] [cze]
Two players take alternating turns filling a rectangular board with unit squares without rotation, but may be otherwise arbitrary. Squares may not overlap and the game ends when there is no space for the next one. The result of the game is the number of turns. The constructor aims to maximize this quantity while the destructor wants to minimize it. We would like to get close to this value, provided that both players use their optimal strategy. We prove some new lower and upper bound for the game. This thesis extends results given by Tamás Hubai in his paper Competitive rectangle filling. Furthermore, we have a look at other board shapes and shapes to fill with. Dva hráči se střídají v umisťování jednotkových čtverečků na obdélníkovou hrací plochu, bez otáčení, jinak mohou být umístěny libovolně. Čtverečky se nesmí překrývat a hra končí, když už se nedá umístit další. Výsledkem hry je počet tahů. Konstruktor se snaží tento výsledek maximalizovat a destruktor minimalizovat. Cílem této práce je co nejpřesněji určit výsledek hry za předpokladu, že oba hráči použijí optimální strategii. Zde dokážeme nové odhady výsledku hry. Tato práce rozšiřuje výsledky popsané v článku Competitive rectangle filling, jehož autorem je Tamás Hubai. Dále se zabýváme jinými tvary hracích ploch a pokládaných tvarů.
Klíčová slova: destruktor; geometrická hra; konstruktor; obdélník; čtverec; constructor; destructor; geometric game; rectangle; square

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/41588

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-305888


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce