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