|
|
Boolean methods in knowledge compilation
Kaleyski, Nikolay Stoyanov ; Čepek, Ondřej (vedoucí práce) ; Gregor, Petr (oponent)
V rámci práce je vyřešen otevřený problém o relativní úspornosti jazyků PI a MODS. Ukazuje se, že PI není alespoň tak úsporný jako MODS tím, že se konstruuje třída Booleovských funkcí s počtem primárních implikantů který je superpolynomiální vzhledem k počtu nulových bodů zkonstruovaných funkcí. Odvozuje se dolní mez (čím se dokazuje, že PI není alespoň tak úsporný jako MODS), horní mez (která ukazuje, že zkonstruovaný protipříklad nemůže poskytnout exponenciální separaci PI a MODS) a vzorec pro přesný počet primárních implikantů zkonstruovaných funkcí. Powered by TCPDF (www.tcpdf.org)
|
|
|
Rozklady propojovacích sítí na dlouhé cesty
Měkuta, Kryštof ; Gregor, Petr (vedoucí práce) ; Dvořák, Tomáš (oponent)
◆á③❡✈ ♣rá❝❡✿ ❘♦③❦❧❛❞② ♣r♦♣♦❥♦✈❛❝í❝❤ sítí ♥❛ ❞❧♦✉❤é ❝❡st② ❆✉t♦r✿ ❑r②➨t♦❢ ▼➙❦✉t❛ ❑❛t❡❞r❛✿ ❑❛t❡❞r❛ t❡♦r❡t✐❝❦é ✐♥❢♦r♠❛t✐❦② ❛ ♠❛t❡♠❛t✐❝❦é ❧♦❣✐❦② ❱❡❞♦✉❝í ❜❛❦❛❧á➦s❦é ♣rá❝❡✿ ▼❣r✳ P❡tr ●r❡❣♦r✱ P❤✳❉✳✱ ❑❚■▼▲ ❆❜str❛❦t✿ ❱ tét♦ ♣rá❝✐ ❥s♦✉ s❤r♥✉t② ✈❧❛st♥♦st✐ ✈②❜r❛♥ý❝❤ ♣r♦♣♦❥♦✈❛❝í❝❤ sítí✱ ❥✐♠✐➸ ❥s♦✉ ♠♦❞✐✜❦❛❝❡ ❤②♣❡r❦r②❝❤❧❡✳ ❑♦♥❦rét♥➙ st✉❞✉❥❡♠❡ t♦❧❡r❛♥❝✐ ❦ ❝❤②❜á♠ ✈ t③✈✳ ❛✉❣♠❡♥t♦✈❛♥ý❝❤ ❦r②❝❤❧í❝❤ s ♦❤❧❡❞❡♠ ♥❛ ❡①✐st❡♥❝✐ ❤❛♠✐❧t♦♥♦✈s❦ý❝❤ ❦r✉➸♥✐❝✳ ❚❛❦é ♣➦❡❞✈❡❞❡♠❡ ♠❡t♦❞✉ ♣♦✉➸í✈❛❥í❝í ❥❡❞♥♦❞✉❝❤é ♣r♦st➦❡❞❦② ❧✐♥❡ár♥í ❛❧❣❡❜r②✱ ♣♦♠♦❝í ❦t❡ré ❧③❡ ③❦♦♥str✉♦✈❛t ✈❡❧❦é ♠♥♦➸st✈í ♣♦❞❣r❛❢➲ n✲❞✐♠❡♥③✐♦♥á❧♥í ❛✉❣♠❡♥t♦✈❛♥é ❦r②❝❤❧❡ AQn ✐③♦♠♦r❢♥í❝❤ n✲❞✐♠❡♥③✐♦♥á❧♥í ❤②♣❡r❦r②❝❤❧✐ Qn✳ ❉♦❦á➸❡♠❡✱ ➸❡ AQn s f ✈❛❞♥ý♠✐ ❤r❛♥❛♠✐ ♦❜s❛❤✉❥❡ ❦♦♣✐✐ Qn s ♥❡❥✈ý➨❡ n 2n−1 f ✈❛❞♥ý♠✐ ❤r❛♥❛♠✐✳ P♦♠♦❝í t♦❤♦t♦ ✈ýs❧❡❞❦✉ ❥s♠❡ s❝❤♦♣♥✐ ♥➙❦t❡ré ✈❧❛st♥♦st✐ Qn s ✈❛❞♥ý♠✐ ❤r❛♥❛♠✐ ♣➦❡♥ést ♥❛ AQn s ✭✈í❝❡✮ ✈❛❞♥ý♠✐ ❤r❛♥❛♠✐✳ P♦❞♦❜♥ý♠ ③♣➲s♦❜❡♠ t❛❦é ❞♦❦á➸❡♠❡✱ ➸❡ ❥❡st❧✐➸❡ f ≤ 3n − 7 ❛ ❦❛➸❞ý ✈r❝❤♦❧ AQn s♦✉s❡❞í ❛s♣♦➡ s❡ ❞✈➙♠❛ ③❞r❛✈ý♠✐ ❤r❛♥❛♠✐✱ ♣❛❦ AQn ♦❜s❛❤✉❥❡ ❤❛♠✐❧t♦♥♦✈s❦♦✉ ❦r✉➸♥✐❝✐ t✈♦➦❡♥♦✉ ♣♦✉③❡ ③❞r❛✈ý♠✐ ❤r❛♥❛♠✐✳ ◆❛✈í❝ ❞♦❦á➸❡♠❡✱ ➸❡ ❦❛➸❞é ❞✈❛ ♠♦♥♦♠♦r✜s♠② G1 ❞♦ AQn ❛ G2 ❞♦ AQm ❧③❡ s❧♦➸✐t ♥❛ ♠♦♥♦♠♦r✜s♠✉s ❦❛rté③s❦é❤♦ s♦✉↔✐♥✉ G1 G2 ❞♦ AQn+m✳ ❑❧í↔♦✈á s❧♦✈❛✿ ❤②♣❡r❦r②❝❤❧❡✱ ❛✉❣♠❡♥t❡❞ ❝✉❜❡✱ ❤❛♠✐❧t♦♥♦✈s❦é ❦r✉➸♥✐❝❡✱ ✈❛❞♥é ❤r❛✲ ♥②
|
|
|
Analýza GPS dat v orientačních sportech
Picek, Štěpán ; Gregor, Petr (vedoucí práce) ; Kučera, Petr (oponent)
V orientačních sportech nalezneme mnoho analytických nástrojů pro zjišťo- vání výkonnosti závodníků a vizualizaci tras. Žádný z těchto nástrojů však ne- poskytuje automatické porovnávání a následnou analýzu proběhnutých postupů závodníků mezi jednotlivými kontrolami. Cílem této práce je využití Needleman- Wunschova bioinformatického algoritmu pro porovnávání GPS dat a jejich vizua- lizaci v rámci webové aplikace. Aplikace poskytuje uživatelům nejen porovnávání svých postupů s ostatními uživateli, ale i analýzu výkonnosti a propojení s dalšími nástroji. Postavena je na platformě ASP.NET Core a návrhovém vzoru Model- View-Controller s použitím dalších technologií jako HTML, CSS a TypeScript.
|
|
|
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.
|
|
|
Parity vertex colorings
Soukup, Jan ; Gregor, Petr (vedoucí práce) ; Kučera, Petr (oponent)
Paritní cesta ve vrcholovém barvení grafu G je cesta ve které je každá barva použita sudě-krát. Paritní vrcholové barvení je barvení, které nemá žádnou paritní cestu. Nechť χp(G) je minimální počet barev v paritním bar- vení grafu G. Je známo, že χp(Bn) ≥ √ n, kde Bn je úplný binární strom s n vrstvami. Dokážeme, že platí ostrá nerovnost, a pomocí tohoto odhadu dokážeme nový odhad χp(T) > 3 √ log n, kde T je libovolný binární strom s n vrcholy. Dále se zabýváme časovou složitostí výpočtu paritního chromatického čísla χp(G). Dokážeme, že ověřování korektnosti paritního vrcholového bar- vení je coNP-úplné a popíšeme exponenciální algoritmus, který ho počítá. Dále pomocí Courcelleho věty dokážeme že existuje FPT algoritmus parame- trizovaný počtem barev k a stromovou šířkou grafu G ověřující že χp(G) ≤ k. Navíc popíšeme náš vlastní FPT algoritmus řešící tento problém. Tento al- goritmus běží v polynomiálním čase pro omezené k a stromovou šířku G. Na- konec zkoumáme příbuznost tohoto barvení s dalšími barveními, konkrétně s unique maximum, conflict free a parity edge barveními.
|
|
|
Genetic Approach To Hypercube Problems
Kuboň, David ; Gregor, Petr (vedoucí práce) ; Pilát, Martin (oponent)
Objektem zájmu práce jsou hyperkrychle. V její první části je představíme coby zajímavou třídu grafů, která má praktické použití v sítích a distribuovaném počítání. Kvůli jejich rozličným aplikacím tato práce popisuje problémy z teorie grafů týkající se hyperkrychlí, jako jsou hledání objížďkových spannerů, minimalizace největšího stuně vrcholu a hledání vícero hranově disjunktních spannerů. Práce též podává přehled aktuálních výsledků pro některé hyperkrychové problémy a navrhuje jejich řešení pomoc genetického algoritmu. Genetický algoritmus je navržem, implementován a jeho výkon je vyhodnocen. Závěrem je, že aplikace genetického algoritmu na některý hyperkrychlový problém je možná, ale nikoli nejeefektivnější metoda.
|
|
|
Hamiltonovské kružnice v Kneserových grafech
Hulcová, Tereza ; Šámal, Robert (vedoucí práce) ; Gregor, Petr (oponent)
V této práci se budeme zabývat existencí hamiltonovských kružnic v Kneserových grafech: graf K(n, k) obsahující jako množinu vrcholů všechny k-tice z n prvků. Hranou jsou spojeny pouze disjunktní dvojice. Lovászova hypotéza o vrcholově tranzitivních gra- fech implikuje hamiltonovskost K(n, k) pro n ≥ 2k + 1. Chen ukázala, že K(n, k) jsou hamiltonovské pro n ≥ 3k, později vylepšila svůj výsledek na n ≥ 2.6k + 1. V obou pří- padech použila Baranyaiho rozklad. Nedávný důkaz hypotézy středních vrstev umožnil dokázat, že bipartitní Kneserovy grafy obsahují hamiltonovskou kružnici. S některými ze zmíněných důkazů seznámíme čtenáře podrobněji.
|
|
|
Boolean methods in knowledge compilation
Kaleyski, Nikolay Stoyanov ; Čepek, Ondřej (vedoucí práce) ; Gregor, Petr (oponent)
V rámci práce je vyřešen otevřený problém o relativní úspornosti jazyků PI a MODS. Ukazuje se, že PI není alespoň tak úsporný jako MODS tím, že se konstruuje třída Booleovských funkcí s počtem primárních implikantů který je superpolynomiální vzhledem k počtu nulových bodů zkonstruovaných funkcí. Odvozuje se dolní mez (čím se dokazuje, že PI není alespoň tak úsporný jako MODS), horní mez (která ukazuje, že zkonstruovaný protipříklad nemůže poskytnout exponenciální separaci PI a MODS) a vzorec pro přesný počet primárních implikantů zkonstruovaných funkcí. Powered by TCPDF (www.tcpdf.org)
|
|
|
Hamiltonicity of hypercubes without k-snakes and k-coils
Pěgřímek, David ; Gregor, Petr (vedoucí práce) ; Fink, Jiří (oponent)
Had (cívka) je indukovaná cesta (cyklus) v hyperkrychli. Jsou známí především problé- mem hada v krabici (cívky v krabici) snažící se najít nejdelšího hada (cívku) v hyperkrychli. Jejich zobecnění k-hadi (k-cívky) zachovávají vzdálenosti mezi každými dvěma svými vr- choly, které jsou vzdálené nejvýše k−1 v hyperkrychli. Studujeme je v souvislosti s Lockeho hypotézou. Ta říká, že vyvážené množině F ⊆ V (Qn) vadných vrcholů v hyperkrychli veli- kosti 2m se lze vyhnout Hamiltonovským cyklem pokud n ≥ m+2 a m ≥ 1. My ukazujeme, že pokud S je k-had (k-cívka) pro n ≥ k ≥ 6 (n ≥ k ≥ 7), pak Qn −V (S) je Hamiltonovsky laceabilní. Pro fixované k může být počet vrcholů k-cívky až exponenciální vzhledem k n. Představujeme pojem draka, což je indukovaný strom v hyperkrychli a jeho zobecnění na k-draka, který zachovává vzdálenost mezi každými dvěma svými vrcholy, které jsou vzdá- lené nejvýše k − 1 v hyperkrychli. Dokazujeme specifické lemma které bylo v Bakalářské práci pouze ověřeno počítačem a dokončuje tak důkaz tvrzení o Hamiltonovské laceabilitě hyperkrychlí bez n-draků.
|
|
|
Minimální reprezentace víceintervalových booleovských funkcí
Bártek, Filip ; Kučera, Petr (vedoucí práce) ; Gregor, Petr (oponent)
Pokud interpretujeme vstupní vektory booleovské funkce jako binárně zapsaná čísla, intervalovou booleovskou funkci fn [a,b] definujeme tak, že fn [a,b](x) = 1 právě tehdy když a ≤ x ≤ b. Disjunktivní normální forma je jeden z běžných způsobů reprezentace booleovských funkcí. Minimalizaci DNF reprezentace 1-intervalové booleovské funkce zadané okrajovými hodnotami intervalu lze provést v lineárním čase. Zobecnění na k-intervalové funkce se zdá být složitější. V této diplo- mové práci diskutujeme komplikace s hledáním optimální DNF reprezentace k- intervalové funkce a představíme 2k-aproximační algoritmus pro tento problém.
|
host ::
RSS.