|
|
Search Strategies for Scheduling Problems
Kypta, Tomáš ; Barták, Roman (vedoucí práce) ; Čepek, Ondřej (oponent)
V předložené práci porovnávám prohledávací strategie pro řešení rozvrhovacích problémů z pohledu programování s omezujícími podmínkami. Těžiště práce je věnováno rozvrhovacím problémům obsahujícím alternativní úlohy. V práci jsou jednak rozebrány různé již publikované způsoby modelování těchto problémů, dále pak jsou popsány a experimentálně porovnány prohledávací strategie pracující s těmito modely. Porovnáván je zejména vliv strategií na rychlost práce řešiče v závislosti na typu a velikosti dat. Jako vedlejší efekt práce studuje možnosti řešení rozvrhovacích problémů obsahujících alternativní úlohy pomocí řešiče Choco, který byl pro implementaci experimentů použit.
|
|
|
Globální podmínky s cenou
Hejna, Martin ; Barták, Roman (vedoucí práce) ; Čepek, Ondřej (oponent)
Plánovací problémy tvoří velice důležiotou aplikační oblast oboru programování s omezujícími podmínkami. Častý způsob reprezentace plánovacích problémů představují temporální sítě, kde uzly reprezentují jednotlivé časové okamžiky a hrany reprezentují časové podmínky, které mezi těmito okamžiky platí. Řešením temporální sítě je nalezení hodnot pro atributy uzlů tak, aby byly splněny všechny podmínky. Vnořený časový graf je temporální síť, která má omezenou strukturu tak, aby byla stále dostatečná pro praktické účely, ale zároveň umožňila použití efektivnějších metod pro hledání řešení. V této práci jsme zavedli vnořený časový graf a rozebrali jeho vlastnosti. Je zde uvedena polynomiálně složitá metoda pro globální konzistenci alternativ a důkaz NP-úplnosti globální konzistence vnořeného časového grafu. Pokud existuje více než jedno řešení, je vhodné mít metody k jejich porovnávní. Obvyklá metoda je použití cenové funkce. Cílem je nalézt takové řešení, které bude mít nejmenší cenu. V práci je pro hledání optimálního řešení předvedeno použití metody Branch and Bound a je zde představen nový filtrační algoritmus, který využívá specifické struktury vnořeného časového grafu.
|
|
|
Kompilace KNF do backdoor decomposable monotone circuit
Illner, Petr ; Kučera, Petr (vedoucí práce) ; Čepek, Ondřej (oponent)
NNF obvod je zakořeněný orientovaný acyklický graf (DAG), který v listech obsahuje true/false nebo literály a má dva typy vnitřních uzlů, a to konjunkci (∧) a disjunkci (∨). Decomposable NNF (DNNF) je NNF, který navíc splňuje podmínku decomposa- bility pro všechny konjunktivní uzly. C-BDMC je jazyk, který zobecňuje DNNF jazyk. V C-BDMC mohou listy obsahovat i výrokové formule v CNF z nějaké třídy C. V této práci se zaměříme pouze na skrytě hornovské výrokové formule. Experimentálně porov- náme velikosti reprezentací d-BDMC a d-DNNF obvodů. Představíme nový experimen- tální kompilátor CaraCompiler, který kompiluje výrokové formule v CNF do d-BDMC nebo (c)d-DNNF obvodu. CaraCompiler je založený na nejmodernějším kompilátoru D4. Také zmíníme rozšíření pro kompilátor D4 jako například kešování řezů hypergrafů, které vede k rychlejším kompilacím. 1
|
|
|
Vlastnosti intervalových booleovských funkcí
Hušek, Radek ; Čepek, Ondřej (vedoucí práce)
Tato práce řeší problém rozpoznávání k-intervalových boolovských funkcí. Na vstup bo- olovské funkce můžeme nahlížet jako na binární zápis přirozeného čísla. Funkce je k- intervalová, pokud - při takto interpretovaném vstupu - nabývá hodnoty jedna právě pro vstupy z daných nejvýše k intervalů. Tento problém je pro obecné boolovské funkce zadané DNF coNP-těžký. Proto se zabýváme případem, kdy DNF náleží do dané řešitelné třídy (třída je řešitelná, pokud pro DNF z ní umíme řešit falsifikovatelnost v polynomiál- ním čase a je uzavřená na částečná dosazení), a ukazujeme, že v tomto případě je úloha pro pevné k řešitelná v polynomiálním čase. 1
|
|
|
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...
|
|
|
Vlastnosti intervalových booleovských funkcí
Hušek, Radek ; Čepek, Ondřej (vedoucí práce)
Tato práce řeší problém rozpoznávání k-intervalových boolovských funkcí. Na vstup bo- olovské funkce můžeme nahlížet jako na binární zápis přirozeného čísla. Funkce je k- intervalová, pokud - při takto interpretovaném vstupu - nabývá hodnoty jedna právě pro vstupy z daných nejvýše k intervalů. Tento problém je pro obecné boolovské funkce zadané DNF coNP-těžký. Proto se zabýváme případem, kdy DNF náleží do dané řešitelné třídy (třída je řešitelná, pokud pro DNF z ní umíme řešit falsifikovatelnost v polynomiál- ním čase a je uzavřená na částečná dosazení), a ukazujeme, že v tomto případě je úloha pro pevné k řešitelná v polynomiálním čase. 1
|
|
| |
|
|
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)
|
host ::
RSS.