|
|
Text clustering and classification /(Klastrování a klasifikace textů)
Gabašová, Evelina ; Vomlelová, Marta (vedoucí práce) ; Hric, Jan (oponent)
Klastrování a klasi kace textů jsou důležitými úlohami strojového učení. V této práci je prezentována kombinace jejich přístupů. Hlavním účelem bylo automaticky připravit množinu klastrů (nebo obecně konceptů), které by následně sloužily jako trénovací data pro naučení klasi fikátoru. Tato práce zahrnuje teoretické pozadí, detaily implementace a výsledky experimentů pro klastrování a klasifi kaci textových dokumentů. Trénovací soubor dokumentů je nejprve hierarchicky klastrování algoritmem bisecting k-means. Výsledek tohoto procesu je možné upravovat a vylepšovat s využitím expertní znalosti. Tímto způsobem vytvořená hierarchická struktura je použita pro naučení naivního bayesovského klasifi kátoru, který je následně využit k roztřídění testovací množiny dokumentů. Pro tyto účely byl vyvinut program, jehož výsledky jsou zhodnoceny a porovnány při zpracování českých a anglických dokumentů.
|
|
|
Konfigurovatelné vyhledávání entit
Koval, Petr ; Hric, Jan (vedoucí práce) ; Kopecký, Michal (oponent)
Predložená bakalárská práce se zabývá úlohou extrakce informací. Predmetem práce je implementace systému pro extrakci informací, který bude zameren na ceské texty. Vytvorený systém nejprve na základe tréninkových príkladu automaticky zkonstruuje množinu extrakcních vzoru. Následne je systém schopen s využitím získaných extrakcních vzoru nalézt relevantní entity v predložených kolekcích textu. Návrh systému umožnuje využít vytvorenou množinu extrakcních vzoru jak pri doménovém vyhledávání, tak i pri vyhledávání bez doménového rozlišení. Práce rovnež obsahuje popis obdobných systému pracujících s anglickými texty.
|
|
|
Sub-optimální algoritmy pro řešení úloh o přesouvání kamenů
Michalík, Petr ; Surynek, Pavel (vedoucí práce) ; Hric, Jan (oponent)
Název práce: Sub-optimální algoritmy pro řešení úloh o přesouvání kamenů Autor: Petr Michalík Katedra (ustav): Katedra teoretické informatiky a matematické logiky Vedoucí diplomové práce: RNDr. Pavel Surynek, Ph.D. e-mail vedoucího: Pavel.Surynek@mff.cuni.cz V předložené práci jsou studovány přístupy k řešení úloh o přesouvání kamenů, které generují optimální nebo sub-optimální řešení. Práce se speciálně zaměřuje na na úlohy typu (n^2-1)-puzzle a příslušné řešící algoritmy. Práce představuje a porovnává existující metody řešení pro tento typ problému. Vybraná metoda je pak podrobena podrobnější analýze složitosti a je zároveň implementována, aby mohly být porovnány teoretické a experimentální výsledky. Je navrhnut alternativní sub-optimální řešící algoritmus a provedena jeho teoretická analýza. V rámci práce je tento algoritmus rovněž implementován a porovnán se srovnatelným existujícím algoritmem. Teoretická analýza i výsledky testů ukážou, že pomocí tohoto alternativního algoritmu lze často nalézat lepší (kratší) řešení.
|
|
|
Umělá inteligence pro strategické hry
Hubík, Tomáš ; Sýkora, Ondřej (vedoucí práce) ; Hric, Jan (oponent)
V předložené práci se zabývám návrhem jednoduché tahové strategické hry a implementací platformy na testování algoritmů pro tuto hru. Další částí práce je implementace několika různých algoritmů pro tuto platformu. Naimplementoval jsem jeden algoritmus založený na principu analýzy mapy a herního prostředí bez jakékoliv predikce a prohledávání stavového prostoru. Dále dva algoritmy založené na prohledávání a rozhodování s pomocí upraveného Minimaxového algoritmu. Poslední dva algoritmy jsou inspirované metodou Monte Carlo plánování.
|
|
|
Life/death analysis in Go (Analyzátor života skupiny v Go)
Kozelek, Tomáš ; Vomlelová, Marta (vedoucí práce) ; Hric, Jan (oponent)
V této práci jsem se zaměřil na studium problematiky řešení úloh "života a smrti" v Go, jež je jednou ze základních dovedností které by měl program hrající Go zvládnout. Jako součást práce vznikl program TGA, řešící tyto úlohy. Program je postaven na základních algoritmech prohledávání stavového prostoru z teorie her (např. alfa beta prořezávání, transpoziční tabulky) v kombinaci s metodami využívajícími znalosti hry Go (heuristiky a ořezávací metody). Pro účely programu jsem mimo jiné vytvořil "blokové orientovanou" prezentaci pozice, implementoval jsem zjednodušenou statickou analýzu života a smrti skupiny a navrhl jsem sadu heuristik, které nejen významně zrychlují výpočet programu ale také umožňují řešit obtížné úlohy typu "under the stones". Program je určen k řešení převážně uzavřených úloh a umí si poradit s různými specialitami problematiky života a smrti v Go (např. různe druhy ko, seki, "bent four in the corner"). Co se výkonnosti týče, sílu programu v řešení specifikovaných Go úloh odhaduji na 1 dan, což je srovnatelné s velmi pokročilým lidským hráčem.
|
|
|
POMDPs for dynamic troubleshooting
Krč, Pavel ; Vomlelová, Marta (vedoucí práce) ; Hric, Jan (oponent)
Pojmem dynamický troubleshooting se označuje proces analýzy bezpečnostního systému v reálním čase, predikce a detekce možných problémů, řešení problémů a předchzení jejich výskytu. Je-li tento proces realizován počítačem, pak se ve své nejobecnější podobě jedná o problém optimálního rozhování. Koncep částečně pozorovatelných Markovských rozhodovacích procesů (POMDP)je pro tento druh problémů velmi vhodný, nebot' umožňuje modelovat jak nejistotu ohledně budoucího vývoje procesu, tak neúplnou znalost aktuálního stavu systému aumožńuje počítat s velastními budoucími rozhodnutími, které systém ovlivňují či přispívají k získávání informací o jeho stavu. V rámci této práce autor poskytuje úvod do teorie POMDPs a popisuje současné algoritmy řešení POMDP s přihlédnutím k jejich použitelnosti pro dynamický troubleshooting. Dále autor představuje konkrétní problém dynamického roubleshootingu, řeší jej pomocí obecných řešení POMDP a navrhuje pro něj vslatní heuristiku, která je snadno zobecnitelná i na širší třídu řešení POMDP, implementuje do něj změněné algoritmy a testuje je na představeném problému.
|
|
|
Scrabble
Dvořák, Filip ; Babilon, Robert (vedoucí práce) ; Hric, Jan (oponent)
Tématem předkládané práce je studie deskové hry Scrabble a její převedení do elektronické podoby. Cílem práce je představení možných a používaných přístupů k implementaci systémů realizujících Scrabble a popsání a zhodnocení datových struktur a algoritmů v těchto systémech využívaných. Součástí práce je implementace zvolených řešení. Po stručném seznámení se s pravidly Scrabble a základní analýze problému jsou v jednotlivých kapitolách teoretické části představeny datové struktury používané k uložení slovníku, algoritmy pro vyhledávání tahů a možné přístupy k herním strategiím. Praktická část práce pojednává o zvolených přístupech a zdůvodněních jejich volby. V závěru práce jsou shrnuty možné přínosy vzniklého systému a jeho další případná rozšíření.
|
|
|
Efektivní algoritmy oveřování cílů v počítačových hrách
Suda, Martin ; Hric, Jan (vedoucí práce) ; Majerech, Vladan (oponent)
Tato práce se zabývá neuniformními metodami prohledávání stromů her dvou hráčů s úplnou informací. Konkrétně je zkoumána neuniformita založená na hrozbách realizovaná v podobě algoritmů lambda search a dual-lambda search. Hrozby, defi nované jakožto útočné tahy, po kterých, když se obránce svého tahu vzdá, bude již s jistotou poražen, umožňují zredukovat prohledávaný prostor při zachování korektnosti výsledku. Práce dále popisuje novou metodu konstrukce tzv. zón relevance, tj. seznamů tahů resp. míst na hrací ploše, které jedině mohou mít vliv na výsledek. S pomocí těchto zón je možné výše jmenované algoritmy značně urychlit. V práci jsou též popsány tři hry, AtariGo, Hex a Piškvorky, a je rozebrána jejich vhodnost pro aplikaci zkoumané metody. Součástí práce je též implementace metody pro tyto hry s využitím známých technik (transpoziční tabulky, history heuristika).
|
|
|
Řešení problémů pomocí MCTS
Malý, Dominik ; Hric, Jan (vedoucí práce) ; Majerech, Vladan (oponent)
Název práce: Řešení problémů pomocí MCTS Autor: Dominik Malý Katedra (ústav): Katedra teoretické informatiky a matematické logiky Vedoucí diplomové práce: RNDr. Jan Hric E-mail vedoucího: Jan.Hric@mff.cuni.cz Abstrakt: MCTS (Monte Carlo Tree Search) techniky jsou v současné době nejlepšími známými algoritmy pro počítačové řešení strategické deskové hry Go. Vzhledem k univerzálnosti a úspěšnosti těchto technik se však nabízí možnost užití i v jiných úlohách. Úkolem této práce je prozkoumat vhodnost MCTS pro řešení jiných problémů, konkrétně her jednoho hráče, jakými jsou například Sudoku nebo SameGame. Naprogramoval jsem počítačového hráče založeného na MCTS, který dokáže řešit úlohy tohoto typu a aplikoval ho na Sudoku a SameGame. Experimentálně jsem ověřil vhodnost různých rozšíření MCTS algoritmu na řešení těchto her a pomocí rozsáhlého testování porovnal také úspěšnost konkrétních nastavení výběrových UCT funkcí a užitých heuristik. V případě hry SameGame jsem navíc svůj algoritmus porovnal s jinými publikovanými výsledky zabývajícími se stejnou problematikou. Popsal jsem, jaké problémy musí programy řešící hry jednoho hráče pomocí MCTS překonávat, a jakými vlastnostmi by takovéto problémy obecně měly disponovat, aby na ně byly Monte Carlo techniky s úspěchem použitelné. Klíčová slova: MCTS, Go, Sudoku,...
|
|
|
Detecting elementary particles with Timepix3 detector
Meduna, Lukáš ; Mráz, František (vedoucí práce) ; Hric, Jan (oponent)
Detekování elementárních částic a pozorování doprovodných jevů v části- cových detektorech je jedním z důležitých směrů současného výzkumu v částicové fyzice. TimePix a jeho nástupce TimePix3 jsou typy detektorů, které jsou mimo jiné v experimentu ATLAS vedené Evropskou organizací pro jaderný výzkum. Tyto detektory mohou vyprodukovat velké množství dat o prolétajících nabitých částicích. Cílem práce je vyvinout metody na detekování a klasifikaci elementárních částic pozorovaných detektorovou sítí ATLAS-TPX3. Vhodné metody klastro- vání anebo klasifikace založené na částečně označených datech budou identi- fikovány anebo vyvinuty. Navržené metody budou implementovány a jejich kva- lita a přesnost na reálných datech bude změřena. Výsledky budou také zahrnovat implementovaný framework na předzpracování nízkoúrovňových dat z detekto- rové sítě ATLAS-TPX3 v reálném čase a vhodné výstupy pro následnou analýzu budou zvoleny (např. ROOT framework soubory) včetně navržených nebo bu- doucích metod klasifikace částic. 5
|
host ::
RSS.