|
|
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.
|
|
|
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
|
|
|
The complexity of constrained graph drawing
Hora, Martin ; Jelínek, Vít (vedoucí práce) ; Fink, Jiří (oponent)
Označkované nakreslení rovinného grafu G je uspořádaná dvojice (G, g) sklá- dající se z rovinného nakreslení G grafu G a z funkce g, jež přiřazuje popisky (barvy) jeho stěnám. V práci se zabýváme problémem Embedding Restriction Satisfiability (ERS), který řeší, zda má daný graf označkované nakreslení splňující předepsanou sadu podmínek. ERS je relativně nový problém, a tak se toho o něm zatím mnoho neví. Nicméně má velký potenciál. Zobecňuje totiž několik problémů hledajících specifická nakreslení grafů, jako je například problém částečně vno- řené rovinnosti (Partially Embedded Planarity). ERS se tedy může stát jedním z ústředích problémů v oblasti kreslení rovinných grafů. V této práci zkoumáme výpočetní složitost ERS. Jednak ukážeme, že ERS je NP-úplné, a poté vyšetříme složitost několika omezených verzí tohoto problému. Cílem je najít hranici mezi NP-těžkými a polynomiálními variantami. 1
|
|
|
Worst case driver for Top trees
Ondráček, Lukáš ; Majerech, Vladan (vedoucí práce) ; Fink, Jiří (oponent)
Top strom je datová struktura řešící jednu z nejobecnějších variant pro- blému dynamických stromů, který spočívá v udržování lesa spolu s urči- tými souhrnnými informacemi na cestách nebo v jednotlivých stromech bě- hem přidávání a odebírání hran. Jednoduché rozhraní odděluje aplikaci od vnitřní struktury top stromu i od ovladače, který zajišťuje jeho logaritmic- kou hloubku a určuje celkovou efektivitu datové struktury. Ovladač popsaný v této práci je založen na biased trees a využívá techniky z worst-case verze link/cut stromů a amortizovaného ovladače top stromů: Vstupní les je roz- ložen na těžké cesty a mezilehlé vrcholy; obojí je reprezentováno jako biased trees, jejichž spojením vznikne struktura top stromu. Ovladač by měl být efektivnější alternativou k původně navrženému ovladači a srovnatelnou al- ternativou k ovladači, který navrhl Renato Werneck. Jejich experimentální srovnání může být předmětem dalšího výzkumu.
|
|
|
Optimization of a circulating multi-car elevator system
Pantůčková, Kristýna ; Fink, Jiří (vedoucí práce) ; Matzner, Filip (oponent)
Cirkulující výtahový systém obsahuje několik kabin ve dvou šachtách. V jedné šachtě se kabiny pohybují směrem nahoru, ve druhé směrem dolů. Tento sys- tém se podobá páternosteru, kabiny ale musí pro naložení a vyložení pasažérů zastavit a otevřít dveře. Kromě mnoha technických výzev tento systém přináší algoritmické otázky ohledně efektivního řízení všech kabin. Tato práce studuje off- line optimalizační problém hledání nejefektivnějšího řízení výtahového systému pro pevně danou množinu pasažérů. Za tímto účelem byl vytvořen počítačový program obsahující implementaci genetického algoritmu pro hledání nejefektiv- nějšího řízení a diskrétní simulaci pro vyhodnocování efektivity řízení. Program poskytuje grafické uživatelské rozhraní pro zadávání parametrů, generování pasa- žérů a zobrazování výsledků. 1
|
|
| |
|
|
Rozšíření frameworku Machinations
Guth, Robert ; Gemrot, Jakub (vedoucí práce) ; Fink, Jiří (oponent)
Framework Machinations je nástroj pro reprezentaci mechanik deskových a některých počítačových her. Jeho hlavním účelem je umožnit návrhářům otestovat a ladit parametry hry před jejím vydáním. Modely některých herních mechanik ale framework neumožňuje vytvořit a nutí své uživatele ke zjednodušování modelů. Cílem této práce je rozšíření frameworku Machinations tak, aby vznikl nástroj schopný simulování mechanik deskových her bez nutnosti jejich zjednodušování. Součástmi práce jsou program pro práci s rozšířeným frameworkem a příkladová studie rozebírající implementaci deskové hry Doba kamenná v rozšířeném frameworku.
|
|
|
Prediction of energy load profiles
Bartoš, Samuel ; Fink, Jiří (vedoucí práce) ; Van Leeuwen, Richard (oponent)
Predikce profilů spotřeby elektrické energie je důležitým tématem Smart Grid technologií. Přesné předpovědi mohou vést redukci cen a snížení závislosti na komerčních dodavatelích energie pomocí adaptace na ceny na energetickém trhu, efektivního využití solární a větrné energie a promyšleného plánování spotřeby. Tato diplomová práce porovnává různé statistické modely s metodami strojového učení, a také jejich schopnost předpovídat profily spotřeby elektrické energie na celý den rozdělený do 48 půlhodinových časových intervalů. Dále se věnujeme různým metodám předzpracování dat a jejich vlivu na přesnost modelů. Navíc také porovnáváme rozličné metody imputace dat, které rekonstruuji chybějící pozorování častokrát přítomné v datech energetické spotřeby.
|
|
|
Konstrukce Grayových kódů se speciálními vlastnostmi
Novotný, Tomáš ; Dvořák, Tomáš (vedoucí práce) ; Fink, Jiří (oponent)
(Cyklický) Grayův kód řádu n je (cyklická) posloupnost všech n- bitových řetězců, v nichž se sousední řetězce liší vždy v jediném bitu. Ruskey a Savage v roce 1993 publikovali otázku, zdali lze každé párování v hyperkrychli rozšířit na cyklický Grayův kód. Problém je stále otevřený, pozitivní řešení je však známo pro každé perfektní párování (Fink, 2007). Hlavním výsledkem práce je zobecnění Finkova výsledku na Grayův kód s předepsanými koncovými vrcholy. Charakterizace takto rozšiřitelných perfektních párování je pro n = 5 ověřena na počítači, tento výsledek slouží jako báze induktivního důkazu tvrzení pro vyšší dimenze. Druhá část práce se soustředí na problém maximálních párování v hy- perkrychlích co nejmenší velikosti, která jsou perspektivním kandidátem na ne- gativní řešení problému Ruskey-Savage. Je zde navržena nová metoda, která dává především pro malé dimenze párování menší velikosti nežli klasická asymptoticky optimální konstrukce (Forcade, 1973). Upravený program z první části je následně využit k testování problému Ruskey-Savage pro tato párování, rozšiřující Grayův kód je však vždy nalezen. 1
|
|
|
Evolutionary algorithms and active learning
Repický, Jakub ; Holeňa, Martin (vedoucí práce) ; Fink, Jiří (oponent)
Názov práce: Evoluční algoritmy a aktivní učení Autor: Jakub Repický Katedra: Katedra teoretické informatiky a matematické logiky Vedúci diplomovej práce: doc. RNDr. Ing. Martin Holeňa, CSc., Ústav informa- tiky, Akademie věd České republiky Abstrakt: Vyhodnotenie ciel'ovej funkcie v úlohách spojitej optimalizácie často do- minuje výpočtovej náročnosti algoritmu. Platí to najmä v prípade black-box fun- kcií, t. j. funkcií, ktorých analytický popis nie je známy a ktoré sú vyhodnocované empiricky. Témou urýchl'ovania black-box optimalizácie s pomocou náhradných modelov ciel'ovej funkcie sa zaoberá vel'a autorov a autoriek. Ciel'om tejto dip- lomovej práce je vyhodnotit' niekol'ko metód, ktoré prepájajú náhradné modely založené na Gaussovských procesoch (GP) s Evolučnou stratégiou adaptácie ko- variančnej matice (CMA-ES). Gaussovské procesy umožňujú aktívne učenie, pri ktorom sú body pre vyhodnotenie vyberané s ciel'om zlepšit' presnost' modelu. Tradičné náhradné modely založené na GP zah'rňajú Metamodelom asistovanú evolučnú stratégiu (MA-ES) a Optimalizačnú procedúru pomocou Gaussovských procesov (GPOP). Pre účely tejto práce boli oba prístupy znovu implementované a po prvý krát vyhodnotené na frameworku Black-Box...
|
host ::
RSS.