|
|
Ramseyova teorie a kombinatorické hry
Valla, Tomáš ; Nešetřil, Jaroslav (vedoucí práce)
Ramseyova teorie studuje vnitřní homogenitu matematických struktur (grafů, číselných oborů), jejichž části (podgrafy, podmnožiny) jsou libovolně obarveny. Často platí, že je-li studovaný objekt dostatečně velký, lze v něm najít určitý jednobarevný podobjekt. Kombinatorické hry jsou hry dvou hráčů s plnou informací, kde záleží pouze na jejich inteligenci. Teorie kombinatorických her studuje především otázky existence vyhrávajících či neprohrávajících strategií. Vezmeme-li ramseyovskou větu a nechámeli objekt, který tato věta studuje, střídavě barvit dvěma hráči, jejichž cílem je vytvořit určitý monochromatický podobjekt, dostaneme kombinatorickou hru. Předmětem našeho zájmu je jednak nejmenší velikost objektu, při které platí ramseyovská věta, tzv. ramseyovské číslo, a jednak nejmenší velikost téhož objektu, při které má první hráč vyhrávající strategii v příslušné kombinatorické hře, tzv. herní číslo. V této práci popisujeme takové ramseyovské věty, u nichž je ramseyovské číslo podstatně větší než číslo herní. To znamená, že podáváme důkazy existence vyhrávajících strategií prvního hráče spolu s horními odhady na ramseyovská a herní čísla a obě čísla porovnáváme.
|
|
|
Dětské vozítko poháněné akuvrtačkou
Valla, Tomáš ; Böhm, Michael (oponent) ; Štětina, Josef (vedoucí práce)
Tato bakalářská práce se zabývá návrhem dětského vozítka na aku pohon. Aku vrtačka musí zůstat použitelná i pro běžné používání. Teoretická část se zabývá popisem historického vývoje dětských autíček od prvních vyrobených modelů až po moderní šlapací a elektrická vozítka. V další části je popsán vznik aku vrtaček. Následující část zobrazuje dnešní možnosti nakoupení dětských vozítek. Je vidět, že trh se značně obohatil a prakticky není možné si nevybrat. Konstrukční část je zaměřena na návrh jednotlivých komponent a výpis nakoupených dílů. Zahrnuje i základní výpočty pro vybraný řetěz a navrhnutou konstrukci.
|
|
|
Poziční hry s efektivní vítěznou strategií
Svoboda, Jakub ; Šámal, Robert (vedoucí práce) ; Valla, Tomáš (oponent)
V práci zkoumáme hry, ve kterých dva hráči obarvují hrany nekonečného úplného grafu a snaží se vytvořit určitý, cílový, podgraf obarvený svou barvou. Nejprve se budeme uvažovat situaci, kdy cílový podgraf je úplným grafem a uká- žeme, že první hráč má vyhrávající strategii, když je cílový podgraf úplný graf na nejvýše třech vrcholech. Potom lehce změníme podmínky hry a ukážeme, že první hráč má vyhrávající strategii, pokud může omezit graf, na kterém se hraje, nebo zahrát několik tahů navíc. Nakonec budeme uvažovat hru, v níž musí být minorem cílového podgrafu úplný graf. Ukážeme vyhrávající strategii pro malou velikost úplného grafu, který musí být minorem cílového podgrafu a zamyslíme se nad důvody, proč by první hráč měl vyhrát jakoukoliv hru tohoto typu. 1
|
|
|
Cooperative interval games
Bok, Jan ; Hladík, Milan (vedoucí práce) ; Valla, Tomáš (oponent)
V této práci studujeme kooperativní intervalové hry, zobecněný model kooperativních her ve kterém hodnota každé koalice koresponduje s uzavřeným intervalem, reprezentujícím všechny možné výsledky jejich kooperace. Nejprve dáváme stručné úvody do klasické kooperativní teorie her a intervalové analýzy a následně uvádíme čtenáře do kooperativních intervalových her, a to se speciálním důrazem na selekce, což jsou všechny možné výsledky hry ve kterých už není žádná další neurčitost. Představujeme nové třídy her podle vlastností jejich selekcí a dokazujeme jejich charakterizace a vztahy s již existujícími třídami. Ukazujeme nové výsledky týkající se imputací a jader. Zavádíme definici silné imputace a silného jádra a zkoumáme problém rovnosti dvou různých typů jader -- hlavního stabilního řešení kooperativních intervalových her. Nakonec ukazujeme nová pozorování ohledně Shapleyho hodnoty intervalových her.
|
|
|
Online Ramsey Theory
Dvořák, Pavel ; Valla, Tomáš (vedoucí práce) ; Koucký, Michal (oponent)
Online Ramseyho hra je hra dvou hráčů, označovanými jako Builder a Painter. V každém kole Builder postaví hranu grafu a Painter ji nabarví červeně nebo modře. Builder vyhraje, pokud se po nějakém kole objeví v nabarveném grafu jednobarevná kopie daného grafu H, jinak vyhraje Painter. V této práci zkoumáme výpočetní složitost odvozeného rozhodovacího problém a ukážeme, že je PSPACE-úplný. Navíc se zabýváme verzí hry, kdy Builder může stavět jen rovinné grafy, a zobecněním hry pro hypergrafy. Nalezli jsme novou třídu grafů nevyhnutelných na rovinných grafech. Ukázali jsme, že Builder vyhraje online Ramseyho hru na 3-uniformních hyperlesech, pokud je cílový graf H je 1-degenerovaný. 1
|
|
|
Desktop client for open social networks
Kasinec, Maroš ; Valla, Tomáš (vedoucí práce) ; Vaner, Michal (oponent)
Sociálne siete zažívajú v poslednej dekáde obrovský romach a ovplyvnili nielen spôsob on-line komunikácie a sociálnej interakcie ale tiež oblasť obchodu, médií či vládnych inštitúcií. Avšak ich hlavný nedostatok, uzvretý a centralizovaný charakter, ostáva nepovšimnutý medzi širokou verejnosťou. Táto práca pojednáva a hodnotí ich otvorené a decentralizované alternatívy a súčasne sa zameriava na jednu konkrétnu - buddycloud. Vďaka využitiu XMPP protokolu, buddycloud a jeho protokol Channel sa javí ako sľubný prístup pre otvorenie ekosystému sociálnych sietí. Umožňuje im komunikovať federatívnym spôsobom ako funguje dnes e-mailová sieť. Ako príspevok do projektu buddycloud táto práca predstavuje aplikáciu SocialDesktopClient, desktopový klient pre širokú škálu sociálnych sietí. Bližšie sa zaoberá modulárnym návrhom klienta a implementáciou protokolu Channel ako prvej sociálnej sieti.
|
|
|
Advanced methods of searching the game tree of 3-dimensional Tic-Tac-Toe
Dvořák, Pavel ; Valla, Tomáš (vedoucí práce) ; Šámal, Robert (oponent)
V této práci zkoumáme poziční hry, zejména pak vícerozměrné piškvorky. Porovnáváme existující pokročilé algoritmy (Pn-search, Db-Search, λ-search) pro řešení pozic v pozičních hrách. Algoritmy nasazujeme na domény her 43 a 53 , což jsou první netriviální připady trojrozměrných piškvorek. Paralelizujeme Pn-search pro případ, kdy existuje více počátečních pozic. Pn-search aplikujeme jako jed- novláknovou úlohu a řešíme, jak sdílet transpoziční tabulku s vyřešenými poz- icemi. Hlavním a čistě teoretickým výsledkem je charakterizace grupy auto- morfismů kombinatorické krychle nd se stejnou množinou linií jako vícerozměrné piškvorky. Toto je zobecnění Silvera [The American Mathematical Monthly, Vol. 74, No. 3, 1967], který popsal automorfismy hry 43 . 1
|
|
|
Rozpoznávání znaků v digitalizovaných matematických výrazech
Haas, František ; Valla, Tomáš (vedoucí práce) ; Mareš, Martin (oponent)
Cílem bakalářské práce je nalezení vhodných metod a algoritmů pro segmentaci textu a rozpoznávání symbolů pomocí umělých neuronových sítí. Nejdříve se práce věnuje základním principům umělého neuronu a umělých neuronových sítí, struktuře konvolučních neuronových sítí a zejména pak algoritmu zpětného šíření a stochastického algoritmu Levenberga-Marquardta. Dále se pak práce věnuje zpracování obrazu a jeho segmentaci na jednotlivé symboly pomocí grafových algoritmů. Součástí této práce je i implementace těchto metod a algoritmů v aplikaci, která zpracovává digitalizované matematické výrazy a převádí je do vektorového formátu.
|
|
|
Combinatorial Games Theory
Valla, Tomáš ; Nešetřil, Jaroslav (vedoucí práce) ; Sgall, Jiří (oponent) ; Spirakis, Paul (oponent)
Název práce: Kombinatorická teorie her Autor: Tomáš Valla Katedra / Ústav: IUUK MFF UK Vedoucí doktorské práce: Prof. RNDr. Jaroslav Nešetřil, DrSc., IUUK MFF UK Abstrakt: Tématem dizertační práce je studium složitosti, která vzniká, pokud k urči- tému prostředí či procesu uvážíme jeho kompetitivní variantu, a to především pomocí metod algoritmické teorie her, teorie složitosti, a dalších nástrojů. Například v prostředí Internetu je vyloučeno aplikovat na graf propojených počítačů libovolný klasický gra- fový algoritmus, protože ten zpravidla vyžaduje existenci centrální autority, která s grafem manipuluje. V této práci popisujeme distribuovanou a lokálně definovanou hru, která v kompetitivním prostředí bez centrální autority simuluje výpočet váženého vr- cholového pokrytí grafu, včetně zobecnění na tzv. hitting set a submodulární váhovací funkci. Dokážeme, že tato hra má vždy Nashovo ekvilibrium a každé toto ekvilibrium dá stejně dobrou aproximaci optimálního pokrytí, jakou lze dosáhnout nejlepšími zná- mými aproximačními algoritmy. Přesněji, tzv. cena anarchie naší hry je stejná jako faktor u nejlepšího známého aproximačního algoritmu. Dosavadní výsledky v této ob- lasti neměly cenu anarchie omezenu ani konstantou. Kromě toho v práci předkládáme i výsledky z oblasti her tzv. grafových prohledávacích her a...
|
|
|
Competitive filling of a plane region
Slabý, David ; Valtr, Pavel (vedoucí práce) ; Valla, Tomáš (oponent)
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ů.
|
host ::
RSS.