|
|
Off-diagonal ordered Ramsey numbers
Poljak, Marian ; Balko, Martin (vedoucí práce) ; Hubička, Jan (oponent)
V práci studujeme uspořádaná Ramseyova čísla, která jsou analogií klasických Ram- seyových čísel pro grafy s lineárně uspořádanými vrcholy. Motivováni problémem od autorů Conlon, Fox, Lee a Sudakov se zabýváme uspořádanými Ramseyovými čísly pro uspořádaná párování M< vůči trojúhelníku. Zobecníme jejich dolní odhad čísla r<(M< , K< 3 ) pro uspořádaná párování s libovolným pevně zvoleným intervalovým chro- matickým číslem. Také zlepšíme horní odhad čísla r<(M< , K< 3 ) pro téměř všechna uspořádaná párování s intervalovým chromatickým číslem 2, který dokázal Rohatgi, z O(n24/13 ) na O(n7/4 ). 1
|
|
|
Konvexní mnohoúhelníky v hustotně omezených bodových množinách
Zálešák, Ondřej ; Valtr, Pavel (vedoucí práce) ; Balko, Martin (oponent)
Pro A, konečnou množinu bodů v Rd , nechť ∆(A) značí rozpětí A a je rovno poměru mezi maximální a minimální vzdáleností mezi dvěma body z A. Valtr (1992) dokázal, že pro množiny bodů v rovině a rozpětím rovným Θ(n 1 2 ) je veli- kost jejich největší podmnožiny v konvexní pozici Θ(n 1 3 ) v nejhorším případě. Ve stejném článku také uvádí rozšířený horní odhad na zaručenou velikost podmno- žiny v konvexní pozici pro množiny s asymptoticky vyšším rozpětím než n 1 2 , a stručnou konstrukci důkazu. Tato práce se věnuje konstrukci této detailně. Dále navazuje na nedávné výsledky pro množiny ve vyšších dimenzích, specificky pro- bírá, jestli by bylo možné rozšířit horní odhad v trojrozměrném prostoru pro vyšší rozpětí podobnou technikou, jako v rovinném případě. 1 Seznam použité literatury Valtr, P. (1992). Convex independent sets and 7-holes in restricted planar point sets. Discrete & Computational Geometry, 7(2), 135-152. 2
|
|
|
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
|
|
|
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ů
|
|
| |
|
|
Implementation of the Sprouts game
Čížek, Tomáš ; Balko, Martin (vedoucí práce) ; Pangrác, Ondřej (oponent)
Sprouts je hra pro dva hráče s tužkou a papírem, kterou vymysleli John Conway a Michael Paterson v roce 1967. Hráči se v ní střídají ve spojování teček pomocí křivek podle jednoduchých pravidel, dokud jeden z hráčů nemůže udělat tah. Přestože je Sprouts velice populární a zdánlivě jednoduchá, nejsou dostupné téměř žádné UI hrající Sprouts. Tento nedostatek počítačových protivníků je způsobený tím, že hra skrývá překvapivě vysokou kombinatorickou složitost a její implementace zahrnuje fascinující programovací výzvy. Podařilo se nám překonat všechny tyto implementační bariéry a po 50 letech existence hry jsme vytvořili první uživatelsky přívětivou aplikaci Sprouts, která obsahuje silnou umělou inteligenci. Zkombinovali jsme zejména výsledky teorie nimberů s novými meto- dami, které jsou založené na Delaunayových triangulacích a force-directed algoritmech zachovávající počet křížení, abychom dokázali vytvořit UI hráče, který hraje perfektně až na jedenácti bodech. 1
|
|
|
Generating simple drawings of graphs
Čermák, Filip ; Balko, Martin (vedoucí práce) ; Valtr, Pavel (oponent)
V této práci se zabýváme průsečíkovými čísly úplných grafů. Nejprve uvedeme dlouhou historii velmi starého problému týkajícího se určení průsečíkového čísla Kn a poté ukážeme současný pokrok v Hararyho-Hillově domněnce postupným procházením jejích důkazů pro speciální třídy nakreslení Kn. Vytvoříme program pro generování databáze všech jednoduchých nakreslení Kn, kde n ≤ 8. Rovněž implementujeme program vizualizující tato nakreslení a umožňující uživateli vytvořit vlastní jednoduchá nakreslení obecných grafů. Vizualizér navíc zachycuje strukturu průsečíků zobrazených nakreslení. Naše pro- gramy využijeme k ověření domněnky Balka, Fulka a Kynčla pro malé případy a odhalíme chybu v článku autorů Mutzela a Oettershagena. 1
|
|
|
Ramsey-type results for ordered hypergraphs
Balko, Martin ; Valtr, Pavel (vedoucí práce)
Ramseyovské výsledky pro uspořádané hypergrafy Martin Balko Abstract Představíme uspořádaná Ramseyova čísla, která jsou obdobou Ramseyových čísel pro grafy s lineárně uspořádanými vrcholy. Studujeme růst uspořádaných Ramseyových čísel uspořádaných grafů vzhledem k počtu vrcholů. Nalezneme uspořádaná párování se superpolynomiálními uspořádanými Ramseyovými čísly. Ukážeme, že uspořádaná Ramseyova čísla uspořádaných grafů s omezenou dege- nerovaností a intervalovým chromatickým číslem jsou nanejvýš poly- nomiální. Dokážeme, že uspořádaná Ramseyova čísla jsou nanejvýš polynomiální pro uspořádané grafy s omezenými délkami hran. Nalezne- me 3-regulární grafy se superlineárními uspořádanými Ramseyovými čísly nad všemi uspořádáními. Poslední dva výsledky řeší problémy od autorů Conlon, Fox, Lee a Sudakov. Odvodíme přesnou formuli pro uspořádaná Ramseyova čísla mono- tónních cyklů a použijeme ji k získání přesné formule pro geomet- rická Ramseyova čísla cyklů, která byla představena Károlyim a spol. Vyvrátíme domněnku Peterse a Szekerese o zesílení slavné Erd˝osovy- Szekeresovy domněnky nad uspořádanými hypergrafy. Dokážeme přesnou formuli pro minimální počet...
|
|
|
Odhady počtu prázdných čtyřstěnů a ostatních simplexů
Reichel, Tomáš ; Valtr, Pavel (vedoucí práce) ; Balko, Martin (oponent)
Mějme v jednotkové krychli konečnou množinu M uniformně náhodně zvolených bodů. Každá čtveřice bodů z M má jakožto čtyřstěn buď uvnitř nějaký bod z množiny M, nebo je prázdná. V této práci předvedeme horní odhad střední hodnoty počtu těchto prázdných čtyřstěnů vzhledem k velikosti množiny M a ukážeme, jak je odhad nejspíše vzdálen od aproximace střední hodnoty, kterou necháme přímočarým algoritmem spočí- tat počítač. Nakonec pak opustíme trojrozměrný případ a budeme se věnovat obecnější úloze v libovolné dimenzi d, kde namísto prázdných čtyřstěnů v krychli budou figurovat prázdné d-simplexy v d-dimenzionální krychli. Horní odhad pro d-dimenzionální případ pak porovnáme s výsledky z jiného článku o stejném tématu. 1
|
|
|
Computing and estimating ordered Ramsey numbers
Poljak, Marian ; Balko, Martin (vedoucí práce) ; Hubička, Jan (oponent)
Zabýváme se uspořádanými Ramseyovými čísly, která představují analogii klasick- ých Ramseyových čísel pro uspořádané grafy. Zlepšíme některé již dosažené výsledky pro speciální třídu uspořádaných párování a vyvrátíme platnost Rohatgiho domněnky. Rozšíříme klasický pojem Ramsey dobrosti pro uspořádaný případ a pokusíme se charak- terizovat všechny Ramsey dobré souvislé uspořádané grafy. Nastíníme, jak lze Ramseyova čísla odhadnout výpočetně a popíšeme naši utilitu založenou na SAT řešičích, která byla pro tento účel vyvinuta a kterou mohou využít další výzkumníci zabývající se tímto té- matem. 1
|
host ::
RSS.