|
|
Rozšíření matched formulí
Chromý, Miloš ; Kučera, Petr (vedoucí práce) ; Babka, Martin (oponent)
S KNF formulí můžeme asociovat incidenční graf. Tento graf je bipartitní a jedna partita zastupuje proměnné a druhá klauzule. Díky tomu můžeme definovat nové třídy KNF formulí, jimiž jsou matched formule a biklikově splnitelné formule. Obě tyto třídy mají tu vlastnost, že formule, které do nich patří jsou splnitelné i po změně polarity libovolného literálu. Takovým formulím říkáme var-splnitelné. V této práci uvažujeme práci Stefana Szeidera, která popisuje parametrizo- vaný algoritmus s pevným parametrem řešící problém matched formulí s malou deficiencí, což je rozdíl počtu klauzulí a počtu proměnných. Ukázali jsme, proč tento přístup nejde přímo zobecnit pro biklikově splnitelné formule. Vzhledem k tomu, že testování toho, je-li formule biklikově splnitelná, je NP- úplné, popsali jsme heuristiku, která hledá biklikové pokrytí v čase O(n2 e), kde n je počet proměnných ve formuli a e je délka formule. Provedli jsme experimenty na náhodných formulích. Z výsledků těchto experimentů lze usuzovat, že existuje fázový přechod ve výsledcích heuristiky. Dále jsme provedli experimenty, které ověřují existenci fázového přechodu matched formulí. Tyto výsledky jsme porov- nali s výsledky experimentů provedených s heuristikou. Výsledky experimentu provedeném na matched formulí jsme též porovnali s teoretickou hranicí...
|
|
|
Boolean techniques in Knowledge representation
Chromý, Miloš ; Čepek, Ondřej (vedoucí práce)
Název: Booleovské techniky v Reprezentaci znalostí Autor: Miloš Chromý Katedra: Katedra teoretické matematiky a matematické logiky Vedoucí práce: Doc. RNDr. Ondřej Čepek, Ph.D., Katedra teoretické matem- atiky a matematické logiky Abstrakt: V této práci zkoumáme switch-list reprezentace Booleovských funkcí a biklikově splnitelné formule. Reprezentace booleovské funkce f pomocí switch-listu je tvořena seznamem ohod- nocení z pravdivostní tabulky, jejichž funkční hodnota se liší od hodnoty před- cházející, tedy f(x) ̸= f(x − 1). V této práci se zaměříme na zahrnutí tohoto typu reprezentace do mapy kompilace znalostí (Knowledge Compilation Map, [Darwiche and Marquis, 2002]). Ukážeme, že switch-list reprezentace může být vhodným cílovým jazykem pro kompilaci znalostí. Nejprve provedeme srovnání relativní velikosti switch-list reprezentace s některými zavedenými reprezentacemi booleovských funkcí (například CNF, DNF nebo OBDD). Součástí této analýzy je i odpověď na dlouho otevřenou otázku položenou v [Darwiche and Marquis, 2002] ohledně neporovnatelnosti jazyků MODS (seznam modelů) a PI (seznam primárních implikátů). Popíšeme také polynomiální algoritmus, který kompiluje switch-list reprezentaci do OBDD. Nakonec se budeme věnovat tomu, které z dotazů a transformací uvažovaných v knowledge compilation map...
|
|
|
Boolean techniques in Knowledge representation
Chromý, Miloš ; Čepek, Ondřej (vedoucí práce)
Název: Booleovské techniky v Reprezentaci znalostí Autor: Miloš Chromý Katedra: Katedra teoretické matematiky a matematické logiky Vedoucí práce: Doc. RNDr. Ondřej Čepek, Ph.D., Katedra teoretické matem- atiky a matematické logiky Abstrakt: V této práci zkoumáme switch-list reprezentace Booleovských funkcí a biklikově splnitelné formule. Reprezentace booleovské funkce f pomocí switch-listu je tvořena seznamem ohod- nocení z pravdivostní tabulky, jejichž funkční hodnota se liší od hodnoty před- cházející, tedy f(x) ̸= f(x − 1). V této práci se zaměříme na zahrnutí tohoto typu reprezentace do mapy kompilace znalostí (Knowledge Compilation Map, [Darwiche and Marquis, 2002]). Ukážeme, že switch-list reprezentace může být vhodným cílovým jazykem pro kompilaci znalostí. Nejprve provedeme srovnání relativní velikosti switch-list reprezentace s některými zavedenými reprezentacemi booleovských funkcí (například CNF, DNF nebo OBDD). Součástí této analýzy je i odpověď na dlouho otevřenou otázku položenou v [Darwiche and Marquis, 2002] ohledně neporovnatelnosti jazyků MODS (seznam modelů) a PI (seznam primárních implikátů). Popíšeme také polynomiální algoritmus, který kompiluje switch-list reprezentaci do OBDD. Nakonec se budeme věnovat tomu, které z dotazů a transformací uvažovaných v knowledge compilation map...
|
|
|
Boolean techniques in Knowledge representation
Chromý, Miloš ; Čepek, Ondřej (vedoucí práce) ; Mengel, Stefan (oponent) ; Kofroň, Jan (oponent)
Název: Booleovské techniky v Reprezentaci znalostí Autor: Miloš Chromý Katedra: Katedra teoretické matematiky a matematické logiky Vedoucí práce: Doc. RNDr. Ondřej Čepek, Ph.D., Katedra teoretické matem- atiky a matematické logiky Abstrakt: V této práci zkoumáme switch-list reprezentace Booleovských funkcí a biklikově splnitelné formule. Reprezentace booleovské funkce f pomocí switch-listu je tvořena seznamem ohod- nocení z pravdivostní tabulky, jejichž funkční hodnota se liší od hodnoty před- cházející, tedy f(x) ̸= f(x − 1). V této práci se zaměříme na zahrnutí tohoto typu reprezentace do mapy kompilace znalostí (Knowledge Compilation Map, [Darwiche and Marquis, 2002]). Ukážeme, že switch-list reprezentace může být vhodným cílovým jazykem pro kompilaci znalostí. Nejprve provedeme srovnání relativní velikosti switch-list reprezentace s některými zavedenými reprezentacemi booleovských funkcí (například CNF, DNF nebo OBDD). Součástí této analýzy je i odpověď na dlouho otevřenou otázku položenou v [Darwiche and Marquis, 2002] ohledně neporovnatelnosti jazyků MODS (seznam modelů) a PI (seznam primárních implikátů). Popíšeme také polynomiální algoritmus, který kompiluje switch-list reprezentaci do OBDD. Nakonec se budeme věnovat tomu, které z dotazů a transformací uvažovaných v knowledge compilation map...
|
|
|
Logická hra založená na celulárním automatu
Škopková, Věra ; Trunda, Otakar (vedoucí práce) ; Chromý, Miloš (oponent)
Tato práce se zabývá využitím celulárního automatu pro vytvoření logické hry. Popisuje klady a zápory jednotlivých typů celulárních automatů a jejich potenciál pro použití v logické hře. Dále se věnuje podrobnému návrhu pravidel hry a tvorbě uživatelského rozhraní. Vytvořená hra podporuje jednorozměrné celulární automaty o dvou až deseti stavech a umí pracovat jak s klasickými, tak s totalistickými přechodovými funkcemi. Cílem hry je odhalit hodnoty buněk, které vygeneroval celulární automat, na základě pravidel přechodové funkce, která jsou hráči známa. Hra je velmi variabilní, nabízí uživateli herní i vizuální parametry, které lze měnit. Navíc hra poskytuje dva nástroje pro vytváření nových celulárních automatů. Prvním z nich je vizuální editor, ve kterém lze pohodlně vytvářet nové či upravovat stávající celulární automaty. Druhým je generátor, který je schopný nalézt pravidla a ohodnocení výchozí generace buněk, z nichž lze vygenerovat konkrétní obrazce.
|
|
|
Rozšíření matched formulí
Chromý, Miloš ; Kučera, Petr (vedoucí práce) ; Babka, Martin (oponent)
S KNF formulí můžeme asociovat incidenční graf. Tento graf je bipartitní a jedna partita zastupuje proměnné a druhá klauzule. Díky tomu můžeme definovat nové třídy KNF formulí, jimiž jsou matched formule a biklikově splnitelné formule. Obě tyto třídy mají tu vlastnost, že formule, které do nich patří jsou splnitelné i po změně polarity libovolného literálu. Takovým formulím říkáme var-splnitelné. V této práci uvažujeme práci Stefana Szeidera, která popisuje parametrizo- vaný algoritmus s pevným parametrem řešící problém matched formulí s malou deficiencí, což je rozdíl počtu klauzulí a počtu proměnných. Ukázali jsme, proč tento přístup nejde přímo zobecnit pro biklikově splnitelné formule. Vzhledem k tomu, že testování toho, je-li formule biklikově splnitelná, je NP- úplné, popsali jsme heuristiku, která hledá biklikové pokrytí v čase O(n2 e), kde n je počet proměnných ve formuli a e je délka formule. Provedli jsme experimenty na náhodných formulích. Z výsledků těchto experimentů lze usuzovat, že existuje fázový přechod ve výsledcích heuristiky. Dále jsme provedli experimenty, které ověřují existenci fázového přechodu matched formulí. Tyto výsledky jsme porov- nali s výsledky experimentů provedených s heuristikou. Výsledky experimentu provedeném na matched formulí jsme též porovnali s teoretickou hranicí...
|
|
|
Vylepšení algoritmu BIBOX
Chromý, Miloš ; Surynek, Pavel (vedoucí práce) ; Koubková, Alena (oponent)
Algoritmus BIBOX je z rodiny algoritmů kooperativního hledání cest. Tento algoritmus je rychlý a suboptimální. I přes svou rychlost obsahuje několik nedeterministických rozhodnutí. Jeden z nedeterminismů je rozebrán v této práci a je jím předzpracování grafu na ucha. Cílem je pomocí analýzy algoritmu získat různá rozložení grafu, která budou mít různé vlivy na běh a výsledek algoritmu, experimentálně vyhodnotit výkon algoritmu na zvolených rozloženích a nalézt rozložení grafu na ucha, na kterém bude algoritmus nejvýkonnější. Powered by TCPDF (www.tcpdf.org)
|
host ::
RSS.