|
Artificial Intelligence for the Unstable Unicorns Game
Kodad, Michal ; Pilát, Martin (vedoucí práce) ; Fink, Jiří (oponent)
Tato práce zkoumá umělou inteligenci pro hru Unstable Unicorns. Tato hra začala na Kickstarteru a v průběhu let tvůrci hry vydali několik rozší- ření. Tato práce si klade za cíl naimplementovat herní simulátor pro tuto hru, analyzovat hru a navrhnout umělé inteligence. Nejprve budeme analyzovat pravidla hry, herní mechaniky a zkoumání umělých inteligencí v podobných hrách. Naimplementovali jsme herní simulátor co nejblíže původním pra- vidlům. Poté jsme vyvinuli tři různé umělé inteligence. Jedná se o agenty založené na pravidlech, agenty Monte Carlo a evoluční agenty. Nakonec jsme provedli experimenty a srovnávací testy s implementovanými agenty. Nejlépe fungující agent je evoluční agent. Je rychlý s největší výherností.
|
|
Optimalizace rozmístění stanic pro nabíjení elektrických vozidel
Beinhauer, David ; Pilát, Martin (vedoucí práce) ; Fink, Jiří (oponent)
S rostoucím počtem elektrických vozidel roste i potřeba vytvořit vhod- nou infrastrukturu pro jejich nabíjení. K řešení tohoto problému může vý- razně napomoci použití vhodných optimalizačních metod. V práci jsme im- plementovali zjednodušený simulátor dopravy sloužící jako vhodný nástroj pro jejich analýzu. Analyzovali jsme také optimalizační metody tzv. hlado- vým algoritmem, genetickým algoritmem a algoritmem k-means. Na základě experimentů vykazovala prokazatelně lepší výsledky optimalizace za využití genetického algoritmu a hladová optimalizace. K-means optimalizace nevy- kazovala známky lepších výsledků oproti náhodnému přístupu.
|
|
Vizualizace dostupnosti veřejnou dopravou
Fürst, Jan ; Pilát, Martin (vedoucí práce) ; Fink, Jiří (oponent)
Mnoho lidí jezdí denně veřejnou dopravou a mnohým z nich by pomohlo, kdyby byd- leli na místě ze kterého se dopraví rychleji na jimi často navštěvovaná místa. Problém však je, jak takové místo k bydlení najít. To řešíme v naší webové aplikaci, ve které zo- becňujeme klasické vyhledávání cest v jízdních řádech a umožňujeme tak vyhodnocovat dostupnost z uživatelem zadaných míst na všechna ostatní místa. Pro snadné vyhledá- vání vizualizujeme, na všech dostupných místech, vypočtenou dostupnost v interaktivní mapě. Naše webová aplikace pracuje s interní knihovnou, která zpřístupňuje funkcionalitu potřebnou pro vyhodnocení dostupnosti. Tuto knihovnu lze využít samostatně a řešit tak jiné problémy, které vyžadují vyhodnocení dostupnosti veřejnou dopravou. 1
|
|
Probabilistic Methods in Discrete Applied Mathematics
Fink, Jiří ; Loebl, Martin (vedoucí práce) ; Koubek, Václav (oponent) ; Sereni, Jean-Sébastein (oponent)
Jedním ze základních problémů moderní statistické fyziky je snaha porozumět \mbox{frustraci} a chaosu. Základním modelem je konečně dimenzionální Edwards-Anderson Ising model. V této práci zavádíme zobecnění tohoto modelu. Studujeme množinové systémy uzavřené na symetrické rozdíly. Ukážeme, že významnou otázku, zda groundstate v Ising modelu je jednoznačný, lze studovat v těchto množinových systémech. Krewerasova hypotéza říká, že každé perfektní párování v hyperkrychli $Q_n$ lze rozšířit na Hamiltonovskou kružnici. Tuto hypotézu jsme dokázali. Matching graf $\mg{G}$ grafu $G$ má za vrcholy perfektní párování v $G$ a hranami jsou spojeny ty dvojice perfektních párování, jejichž sjednocení tvoří Hamiltonovskou kružnici v $G$. Dokážeme, že matching graf $\mg{Q_n}$ je bipartitní a souvislý pro $n \ge 4$. Toto dokazuje Krewerasovu hypotézu, že graf $M_n$ je souvislý, kde $M_n$ vznikne z grafu $\mg{Q_n}$ kontrakcí vrcholů $\mg{Q_n}$, které odpovídají izomorfním perfektním párováním. Cesta v $Q_n$ vyhýbající se zadaným $f$ chybným vrcholům se nazývá dlouhá, jestliže její délka je alespoň $2^n - 2f - 2$. Analogicky kružnice je dlouhá, pokud její délka je alespoň $2^n - 2f$. Pokud jsou všechny chybné vrcholy ze stejné bipartitní třídy $Q_n$, pak jsou tyto délky nejlepší možné. Dokážeme, že pro každou množinu...
|
|
Anomaly Detection Using Generative Adversarial Networks
Měkota, Ondřej ; Fink, Jiří (vedoucí práce) ; Pilát, Martin (oponent)
Generativní adversariální sítě (GAN) jsou schopny naučit se distribuci svých vstupů. Používají se pro naučení se distribuce normálních dat a pak je lze využít pro detekci i velmi vzácných anomálií, např. Schlegl a spol. (2017) navrhl metodu pro detekci anomálií - AnoGAN. Problémem metody GAN je ovšem nestabilita během tréninku. Proto Arjovsky a spol. (2017) navrhl novou verzi nazvanou Wasserstein GAN (WGAN). Cílem této práce je navrhnout model používající WGAN pro detekci podvodných transakcí kreditními kartami. Vyvinuli jsme novou metodu, nazvanou AnoWGAN+e, částečně založenou na AnoGANu a porovnáváme ji s One Class Support Vector Machi- nes (OC-SVM) (Schölkopf a spol. (2001)), k-Means ensemble (Porwal a spol. (2018)) a dalšími metodami. Kvalita studovaných metod je měřena pomocí plochy pod křivkou přesnosti a výtežnosti (AUPRC) a pomocí přesnosti v různých úrovních výtěžnosti na kolekci dat obsahující transakce kreditních karet (Pozzolo (2015)). AnoWGAN+e dosáhl nejvyšší hodnoty AUPRC, o 12% více než druhá nejlepší metoda OC-SVM. Náš model má přesnost 20% při 80 % výtěžnosti ve srovnání s 8% u OC-SVM; a 89% přesnost při 10 % výtěžnosti, oproti 79% u k-Means ensemblu. 1
|
| |
|
Evolutionary Algorithms for the Design of Luminaire Optics
Drázdová, Zuzana ; Pilát, Martin (vedoucí práce) ; Fink, Jiří (oponent)
Cílem této práce bylo zkoumat možnosti využití evolučních algoritmů pro návrh komponenty s velmi specifickým účelem. Zabývali jsme se procesem návrhu optimálního tvaru pro reflektorky z vysoce odrazivého plechu. Takový reflektorek slouží ke správnému směrování světla z LED. Vytvořili jsme zjednodušený model prostředí, ve kterém se tato komponenta používá. Poté jsme použili evolucí inspirovaný přístup k nalezení vhodného tvaru reflektorku do již existujícího svítidla. Na základě jednoho řešení jsme vyrobili prototyp a změřili jeho vlastnosti. Také jsme použili vyvinutý program k návrhu vhodné optické části do úplně nového zařízení. Oba úkoly byly doprovázeny množstvím problémů, které vzešly z nepřesného zadání a obecně z rozdílů mezi evolučním přístupem a tradičním vývojem průmyslových komponent. V práci jsme zahrnuli i analýzu problémů, na které jsme narazili, a ukázali řešení, která lze použít i pro podobné úkoly.
|
|
Optimization and Statistics
Fink, Jiří ; Loebl, Martin (vedoucí práce)
CONTENTS Nazev prace: Autor: Katedra. (ustav-): Vedouci diplomove prace: E-mail vedouci'ho: Klicova slova: Abstrakt: Optimization and Statistics Jifi Fink Katedra aplikovane matematiky Doc. RNDr. Martin Loebl, CSc. loebl@kam.mff,cuni.cz Edwards-Anderson Ising model, Teorie grafu, T-join, Gaussovska distribuce Jedmm ze zakladnich problemu modern! statisticke fyziky je'snada porozumet frus- traci a chaosu. Zakladnim modelem je konecne dimenzionalni Edwards-Anderson Ising model. V optimalizaci to odpovida zkournani minimalnich T-joinu v konecnych mfizkach s nahodnymi vahami na hranach. V teto praci studujeme "random join", coz je nahodna cesta mezi dvema pevne danymi vrcholy. Puvodni definice je pfilis slozita, a tak jsme ukazali jednodussi. Tato deiinice je pouzita k pfesnemu vypoctu "random join" na kruznici. Take jsme ukazali specialni algoritmus, ktery hleda cestu v mrizce s danymi hranami. Tento algoritmus muze byt pouzit k experimentalnimu stu.dovani "random join". Title: Author: Department: Supervisor: Supendsor's e-mail address: Keywords: Abstract: Optimization and Statistics Jiff Fink Department of Applied Mathematics Doc. RNDr. Martin Loebl: CSc. loebl@kam.mff.cuni.cz Edwards-Anderson Ising model, Graph theory, T-join, the Gaussian distribution One of the basic streams of modern statistics physics is...
|
|
Searching Image Collections Using Deep Representations of Local Regions
Bátoryová, Jana ; Lokoč, Jakub (vedoucí práce) ; Fink, Jiří (oponent)
V úlohe "hľadanie známeho objektu" sa zameriavame na nájdenie vopred známeho obrázku v multimediálnej databáze. V tejto práci sa zameriavame na dva prístupy k riešeniu tohto problému, ktoré sú založené na vizuálnej podobnosti s hľadaným obrázkom. V prvom prístupe užívateľ vytvára koláž obrázkov (obrázky získa napríklad z dostupných vyhľadávačov obrázkov). Na základe tejto koláže naše riešenie poskytne užívateľovi prehľad najpodobnejších obrázkov. Z našich výsledkov vyplýva, že spracovanie obrázkov delením do niekoľkých častí je systém schopný poskytnúť lepšie výsledky v porovnaní so systémom, ktorý nezohľadňuje pozíciu obrázkov v koláži, či prístup, ktorý ďalej upravuje vrstvu v neurónovej sieti. Druhá časť našej práce sa zameriava na možnosť vyhľadávania v databáze na základe obrázkov tvári ľudí. V práci ďalej skúmame využitie reprezentácii, vytvorených hlbokými neurónovými sieťami k zotriedeniu tvárí na základe ich podobností. Ďalej prezentujeme jednoduchú štruktúru na prezeranie väčšieho súboru tvárí. Práca zahrňuje program, ktorý prezentuje obe techniky.
|
|
Applications of Gray codes in cache-oblivious algorithms
Mička, Ondřej ; Fink, Jiří (vedoucí práce) ; Gregor, Petr (oponent)
Moderní počítače využívají sofistikovanou hierarchii keší, aby snížily latenci přístupů k paměti. Tento fakt vedl ke vzniku cache-oblivious algoritmů, jejichž cílem je dosáhnout co nejlepšího výkonu na takovýchto paměťových hierarchiích, a to s pouze minimální znalostí přesných parametrů dané hierarchie. Při návrhu cache-oblivious algoritmů je velmi často využívána metoda rozděl a panuj, založená na rekurzi. V této práci předvedeme alternativní techniku návrhu cache- oblivious algoritmů, založenou na Grayových kódech. Ukážeme, jak pomocí binárního reflektovaného Grayova kódu procházet pole způsobem, který je přívětivý ke keším. To nám umožní vytvořit alternativní algoritmy pro problémy jako transpozice matice, naivní násobení matic či naivní konvoluce, jež mají stejnou asymptotickou složitost jako je jejich na rekurzi založené protějšky. Výhodou našeho přístupu je, že umožňuje implementovat algoritmy bez rekurze (či rekurzi simulujícího zásobníku) pomocí loopless algoritmu. Taktéž v navrhneme variantu binárního reflektovaného Grayova kódu, upravenou speciálně pro použití v naší technice a téměř loopless algoritmus pro generování tohoto kódu. Kromě teoretické analýzy naší techniky zkoumáme její chování na reálných počítačích, a to konkrétně na problému transpozice matice.
|