|
|
Distinguishing pairs of words using finite automata
Bilan, Daria ; Koucký, Michal (vedoucí práce) ; Šámal, Robert (oponent)
V této práci se zaměřujeme na jeden ze základních otevřených problémů v in- formatice - rozlišování dvou slov pomocí deterministického konečného automatu s co nejmenším počtem stavů. Nejprve představíme existující výzkum, kde se prokázané dolní a horní meze vzhledem k délce slov liší exponenciálně. Následně empiricky zkoušíme dva dosud neprozkoumané přístupy: analýzu rozlišujících množin a použití náhodně generovaných automatů. Ukážeme, že první přístup nepřispívá ke zlepšení mezí pro daný problém, zatímco náhodné automaty mo- hou být úspěšné pro náhodně vybrané páry slov, avšak ne pro všechny. Kom- binace náhodně generovaného automatu s již známým nenáhodným přístupem však pomáhá snížit průměrný počet stavů o několik řádů. Na základě získaných experimentálních výsledků navrhujeme několik témat pro další výzkum. 1
|
|
|
Coloring triangle-free graphs on the torus
Urmanov, Eldar ; Dvořák, Zdeněk (vedoucí práce) ; Šámal, Robert (oponent)
Pekárek and Dvořák (2021) popsali algoritmus rozhodující 3-obarvitelnost grafu bez trojúhelníků nakreslených na toru v lineárním čase. Tato práce popisuje efektivní implementaci algoritmu a vyhodnocení jejího výkonu na přirozené tridě grafů. Pekárek and Dvořák (2021) proposed a linear-time algorithm to decide 3-colorability of triangle-free graphs drawn on the torus. We implemented this algorithm efficiently and evaluated its performance on a natural class of graphs. 1
|
|
|
Structure of flow-continuous mappings in algebraic context
Hušek, Radek ; Šámal, Robert (vedoucí práce) ; Bonamy, Marthe (oponent) ; Kaiser, Tomáš (oponent)
- Structure of Flow-continuous Mappings in Algebraic Context Radek Hušek Práce zkoumá strukturu prostoru cyklů v grafech - speciálně otázky o nikde-nulových tocích a dvojpokrytích cykly. Nejprve ukážeme, že existují hranově 2-souvislé grafy, které rozlišují Z2 2 a Z4 grupovou souvislost (grupová souvislost je zesílením nikde-nulových toků). Poté zkoumáme domněnku Matta DeVose o existenci toků v grafech za podmínky, že existuje grafový homomorfismus mezi vhodnými Cayleyho grafy. Formulujeme zesílení této domněnky, které nazýváme "strong homomorphism property" (SHP), které nám dovolí rozdělovat vrcholy vyššího stupně (a tedy redukovat problém na kubické grafy). Předkládáme hypotézu, že SHP platí pro každý graf a nejmenší grupu, v níž má tento graf nikde-nulový tok. Také ukazujeme, že jak SHP, tak původní domněnka implikují existenci dvojpokrytí cykly s malým počtem cyklů. Následně se zabýváme počítáním objektů na grafech - speciálně dvojpokrytí kružnicemi. Ukazujeme téměř exponenciální dolní odhad pro grafy s vhodným nakreslením na plochu, ale taktéž nahlédneme, že tento odhad se nevztahuje na Flower snarky, které žádné takové nakreslení nemají. Následně ukazujeme asymptoticky těsný odhad na počet CDC Flower snarků a taktéž vylepšujeme dolní odhad pro rovinné grafy na exponenciální. Na závěr...
|
|
|
Structural properties of graphs---probabilistic and deterministic point of view
Hladký, Jan ; Šámal, Robert (vedoucí práce) ; Pawlas, Zbyněk (oponent)
V práci zkoumáme bipartitní podgrafy náhodného kubického grafu. Ukážeme, že hranově maximální bipartitní podgraf náhodného kubického grafu na n vrcholech má asymptoticky skoro jistě méně než 3 2 ·0.9351n hran. Dále ukážeme, že počet vrcholů vrcholově maximálního indukovaného bipartitnho podgrafu náhodného kubického grafu asymptoticky skoro jistě leží v intervalu [0.75n; 0.9082n]. K získání dolního odhadu zkonstruujeme randomizovaný algoritmus na hledání velkého indukovaného biparitního podgrafu v náhodném kubickém grafu. V závěru práce diskutujeme důsledky pro grafové homomorfismy, zejména pro Nešetřilovu Pětiúhelníkovou domněnku.
|
|
|
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
|
|
|
Generalized Moran process
Svoboda, Jakub ; Šámal, Robert (vedoucí práce) ; Balko, Martin (oponent)
Moránův proces je model používaný k simulaci evolučních dynamik. Ve struk- turované populaci se objeví lépe přizpůsobený jedinec, mutant. Evoluce je simu- lována v krocích. V jednom kroku, jedinec je vybrán proporcionálně ke své fitness a rozšíří se na místo svého souseda. V této práci, vysvětlujeme Moránův proces, prezentujeme základní výsledky a definujeme vlastní variantu. Pracujeme v prostředí, kde každý jedinec má fitness v závislosti na svém typu a vrcholu, který obývá. V modifikovaném modelu dokážeme dvě věty o počtu kroků, který proces udělá než se dostane do stabilního stavu. Ukážeme, že na úplném grafu proces udělá polynomiálně mnoho kroků. Najdeme také graf, kde proces udělá expo- nenciálně mnoho kroků ale v normálním modelu jich udělá stejně jako v úplném grafu. 1
|
|
|
Generating random pattern-avoiding matrices
Kučera, Stanislav ; Jelínek, Vít (vedoucí práce) ; Šámal, Robert (oponent)
Binární matice neobsahující menší matici jako podmatici se stávají zajímavým tématem. V mé práci uvádím dva nové algoritmy pro testování, zda velká čtvercová binární matice obsahuje menší binární matici, a randomizovaný proces, který aproximuje uniformní náhodnou matici neobsahující danou matici. Toto umožní vědeckým pracovníkům testovat jejich hypotézy na náhodných maticích. Proto moje práce také obsahuje efektivní přenositelnou implementaci všech zmíněných algoritmů. Powered by TCPDF (www.tcpdf.org)
|
|
|
Implementace hry Dots and Boxes
Balko, Martin ; Pangrác, Ondřej (vedoucí práce) ; Šámal, Robert (oponent)
Název práce: Implementace hry Dots and Boxes Jméno autora: Martin Balko Katedra (ústav): Katedra aplikované matematiky Vedoucí bakalářské práce: RNDr. Ondřej Pangrác, Ph.D. e-mail vedoucího: pangrac@kam.mff.cuni.cz Abstrakt: Předložená práce se zabývá analýzou populární logické hry Dots and Boxes a jejích zobecněných verzí. Zaměřuje se také na nejrůznější metody a algoritmy řešení umělé inteligence protivníků. Výsledkem práce je implementace rozšířené verze této hry, ve které je možné editovat vlastní hrací plochy, hrát proti více soupeřům na několika úrovních obtížnosti a používat různá ohodnocení map. Klíčová slova: Dots and Boxes, Nimstring, Pokročilé počítání řetězů
|
|
|
Grupová souvislost grafů
Mohelníková, Lucie ; Šámal, Robert (vedoucí práce) ; Pangrác, Ondřej (oponent)
Název práce: Grupová souvislost graf· Autor: Lucie Mohelníková Katedra: Informatický ústav Univerzity Karlovy Vedoucí diplomové práce: Mgr. Robert 'ámal,Ph.D., Informatický ústav Univerzi- ty Karlovy Abstrakt: Zabývali jsme se grupovou souvislostí graf·, zejména pak Z2 2- a Z4- souvislostí. Implementovali jsme v jazyce C++ test, zda je graf grupově souvislý a pomocí něho hledáme grafy, které jsou grupově souvislé v jedné ze zkoumaných grup a v druhé nikoliv. Zkoumali jsme grafy, které vzniknou podrozdělením hran několika speciálních graf· např. K4 a krychle. Hlavním přínosem této práce je nalezení dvou graf·, které jsou Z4-souvislé a nejsou Z2 2-souvislé. Pomocí druhé nezávislé implementace testu na grupovou souvislost napsané v jazyce Prolog s využitím CSP jsme ověřili, že tyto grafy jsou Z4-souvislé. Analyticky jsme dokázali, že jeden z nalezených graf· není Z2 2-souvislý. Klíčová slova: grupová souvislost, toky, grupa
|
|
|
Graph coloring problems
Lidický, Bernard ; Fiala, Jiří (vedoucí práce) ; Paulusma, Daniel (oponent) ; Šámal, Robert (oponent)
Název práce: Varianty problému obarvení Autor: Bernard Lidický Katedra: Katedra aplikované matematiky Vedoucí disertační práce: doc. RNDr. Jiří Fiala, Ph.D. Abstrakt: V této práci studujeme barvení grafů. Práce je rozdělena do tří částí, kde každá část se zabývá jinou variantou barvení. V první části se zabýváme 6-kritickými grafy na plochách a 6-kritickými grafy s malým počtem křížení. Hlavními výsledky jsou kompletní seznam 6-kritických grafů na Kleinově láhvi a 6-kritických grafů s křížícím číslem nejvýše čtyři. Druhá část je věnována vybíravosti rovinných grafů bez krátkých cyklů. Ukazu- jeme, že rovinné grafy bez 3-,7- a 8-cyklů jsou 3-vybíravé a že rovinné grafy bez trojúhelníků a s jistým omezením na 4-cykly jsou též 3-vybíravé. V poslední části se zaměřujeme na novější variantu barvení - vlnové barvení. Jde o koncept, který je motivovaný přiřazováním frekvencí a má zohlednit, že různé frekvence mají různý dosah. Zabýváme se pak zlepšováním odhadů nutného počtu barev k obarvení čtvercové a šestiúhelníkové mřížky. Klíčová slova: kritické grafy, seznamové barvení, vlnové barvení, rovinné grafy, krátké cykly
|
host ::
RSS.