|
|
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ů.
|
|
|
Artificial intelligence in abstract 2-player games
Veselý, Pavel ; Valla, Tomáš (vedoucí práce) ; Baudiš, Petr (oponent)
V této práci se zaměříme na algoritmy pro hledání nejlepšího tahu v~zadané pozici abstraktní strategické hry dvou hráčů. Popíšeme algoritmy Alfa-beta a Proof-number search včetně jejich vylepšení a přispějeme novými nápady na jejich zrychlení. Rovněž navrhneme postup, jak vybírat náhod\-ně mezi tahy ne o moc horšími než nejlepší nalezený a jak hrát v prohraných pozicích. Algoritmy nasadíme na hru Tzaar, která je zvláštní velkým počtem možných tahů, což ji dělá obtížnou pro počítač. Naším cílem je vytvořit co nejlepšího robota na hraní Tzaaru. Ukážeme, že naše umělá inteligence dokáže hrát na úrovni nejlepších lidských i~počítačových hráčů na internetu. Také na základě experimentů rozebereme, jak jednotlivá vylepšení algoritmů pomáhají v zrychlení výpočtů u~této hry.
|
|
|
Algorithms for solving strong positional games with high symmetry
Novotná, Jitka ; Valla, Tomáš (vedoucí práce) ; Kit, Michal (oponent)
V této práce představujeme několik algoritmů pro počítačové řešení silných pozičních her a to především algoritmů založených na algoritmu PN-search. Zaměřujeme se na hry s vysokou symetrií herního plánu. Spojováním mnoha izomorfních pozic jsme dosáhli velkého zmenšení části herního strumu, kterou je potřeba prohledat. Představujeme již známa vylepšení a také navrhujeme vlastní. Ověřujeme jak tyto heuristiky funguji na příkladu klikové hry. K práci je přiložen software pro řešení silné klikové hry pro K=4 a N=5...8. Software zvládl vyřešit (6,4) a (7,4)-klikovou hru a dokázal, že druhý hráč má neprohrávající strategii, což se očekávalo, ale dosud nebylo potvrzeno.
|
|
|
Plánovací algoritmy a simulace plánu v logistické doméně
Štefan, Zdeněk ; Toropila, Daniel (vedoucí práce) ; Valla, Tomáš (oponent)
Bakalářská práce se zabývá porovnáním některých technik pro řešení plánování v logistické doméně. Její cílem je porovnání schopností těchto technik z umělé inteligence řešit zadaný problém z hlediska optimality nejen mezi sebou, ale i s plány navrženými lidmi. Protože ne všechny plánovače vrací paralelní plány, je potřeba tyto plány paralelizovat. Práce ukazuje, že některé algoritmy dosahují dobré výsledky ve srovnání s lidskými plány, bohužel však kvůli časové a paměťové náročnosti nemůžou být v dnešní době běžně používány pro řešení náročnějších úkolů.
|
|
|
PNS for the game Arimaa
Majerech, Ondřej ; Hric, Jan (vedoucí práce) ; Valla, Tomáš (oponent)
Arimaa je strategická desková hra, kterou se stále počítačům nepovedlo pokořit. Problematický je zejména velký větvící faktor stromu hry a celková její charakteristika, díky které je obtížné sestrojit vhodnou ohodnocovací heuristiku pro alfa-beta prohledávání. Proof-Number Search je algoritmus nezávislý na dobré ohodnocovací heuristice, který byl již úspěšně použit na řešení koncovek jiných deskových her. V této práci jsme adaptovali a implementovali algoritmus Proof-Number Search pro hru Arimaa.
|
|
|
Visualisation of algorithms
Bašista, Peter ; Valla, Tomáš (oponent) ; Mareš, Martin (vedoucí práce)
Cieľom práce je navrhnúť program pre vizualizáciu činnosti algoritmov pri výuke. Užívateľ vytvorí algoritmus a pripojí k jeho datovým štruktúram pripravené vizualizačné komponenty. Program potom zaznamená priebeh výpočtu algoritmu a zobrazí ho ako interaktívnu animáciu, prípadne vytvorí súbor PDF zachytávajúci kľúčové body výpočtu. V predloženej práci sa zameriavame na predstavenie knižnice Algorithm Animation Library. Táto knižnica bola navrhnutá tak, aby umožnila užívateľovi pokiaľ možno čo najväčšiu flexibilitu pri tvorbe animácií, a zároveň tak, aby jej ovládanie bolo používateľsky čo najprijateľnejšie. V práci vysvetlíme základné princípy jej fungovania a používania, v krátkosti ju porovnáme s alternatívami a vyslovíme závery o tom, kedy je vhodné knižnicu Algorithm Animation Library použiť.
|
|
| |
|
|
Music effects
Marko, Matej ; Valla, Tomáš (oponent) ; Bálek, Martin (vedoucí práce)
Názov práce: Hudobné efekty Autor: Matej Marko Katedra (ústav): Katedra aplikovanej matematiky Vedúci baklárskej práce: Mgr. Martin Bálek e-mail vedúceho: Martin.Balek@mff.cuni.cz Abstrakt: Efekty zohrávajú v procese tvorby hudby významnú úlohu. Pomáhajú doplniť a obohatiť aranžmán skladby. Cieľom práce je vyvinúť aplikáciu, ktorá umožní užívateľovi prehrať zvukový súbor a v reálnom čase na prehrávaný obsah aplikovať zvolené efekty. Každá zmena v nastavení efektov sa tak ihneď prejaví na výslednom zvuku a užívateľ ju môže okamžite posúdiť. Konkrétne nastavenie môže užívateľ aplikovať na celý vstupný súbor a tento výsledok uložiť. Súčasťou aplikácie je tiež implementácia vybraných efektov. V texte práce sa potom zameriavame na postupy, ktoré sú použité pri implementovaní týchto efektov. Kľúčové slová: efekty, hudba, zvuk
|
host ::
RSS.