|
|
Evoluční algoritmy v úloze booleovské splnitelnosti
Serédi, Silvester ; Vašíček, Zdeněk (oponent) ; Sekanina, Lukáš (vedoucí práce)
Cílem této diplomové práce je najít heuristiku řešící SAT problém pomocí evolučního algoritmu. Jsou zde uvedeny přístupy k řešení SAT problému a různé varianty k evolučním algoritmům, které jsou relevantní k danému tématu. Následně je popsaná implementace lineárního genetického programování hledající heuristiku pro řešení instancí SAT problému společne s vlastní implementací SAT solveru pracujíci s výstupem evolučně navrženého programu. Na závěr jsou shrnuty dosažené výsledky
|
|
|
Circle packing and Möbius transformations
Porvichová, Janka ; Zeman, Peter (vedoucí práce) ; Kratochvíl, Jan (oponent)
Graf lze reprezentovat různými geometrickými reprezentacemi. V této práci se věnujeme reprezentaci grafů pomocí circle packingu (dotykových kružnic). Roze- bereme důležité koncepty potřebné pro dokázání klíčových výsledků ohledně této reprezentace. Představíme konkrétní známý důkaz existence circle packingu pro rovinné grafy a existence primal-dual circle packingu pro 3-souvislé grafy. Dále se budeme zabývat složitostí problému rozšíření reprezentace při zadaném čás- tečném circle packingu. Rozebereme důkaz věty, která říká, že rozhodnout, zda lze nalézt takové rozšíření, je NP-těžký problém. Představíme vlastní teoretický algoritmus pro konstrukci rozšíření založený na real RAM stroji. 1
|
|
|
Implementation of operations in double-ended heaps
Bardiovský, Vojtech ; Koubek, Václav (vedoucí práce) ; Hubička, Jan (oponent)
Existuje viacero spôsobov ako vytvoriť dvojkoncovú haldu z dvoch klasických háld. V tejto práci rozšírime dvojkoncovú haldu založenú na prepojení listov a vytvoríme novú schému nazvanú L-korešpondencia. Táto schéma rozšíri triedu možných klasických háld použiteľných pre vytvorenie dvojkoncovej haldy (napr. Fibonacci halda, Rank-pairing halda). Ďalej umožní operácie ``Zníž prioritu'' a ``Zvýš prioritu''. Tento prístup ukážeme na troch konkrétnych haldách a odhadneme časovú zložitosť pre všetky operácie. Ďalším výsledkom je, že pre tieto tri konkrétne haldy, očakávaný čas operácií ``Zníž prioritu'' a ``Zvýš prioritu'' je obmedzený konštantou.
|
|
|
Evoluční algoritmy v úloze booleovské splnitelnosti
Serédi, Silvester ; Vašíček, Zdeněk (oponent) ; Sekanina, Lukáš (vedoucí práce)
Cílem této diplomové práce je najít heuristiku řešící SAT problém pomocí evolučního algoritmu. Jsou zde uvedeny přístupy k řešení SAT problému a různé varianty k evolučním algoritmům, které jsou relevantní k danému tématu. Následně je popsaná implementace lineárního genetického programování hledající heuristiku pro řešení instancí SAT problému společne s vlastní implementací SAT solveru pracujíci s výstupem evolučně navrženého programu. Na závěr jsou shrnuty dosažené výsledky
|
host ::
RSS.