|
|
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.
|
|
|
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.
|
host ::
RSS.