|
|
Aproximace obtížných rozvrhovacích úloh
Lisý, Viliam ; Čepek, Ondřej (vedoucí práce) ; Vlach, Milan (oponent)
Tato práce zkoumá rozvrhování problémů typu "shop". Po zavedení notace a základních definic používaných v rozvrhování přinášíme přehled známých výsledků o výpočetní složitosti různých rozvrhovacích problémů typu "open shop", "flow shop" a "job shop". Později se soustředíme na "open shop" a hlavně na podtřídu této třídy problémů, která povoluje jenom dvě operace nenulové délky na úlohu. Ve standardní notaci je označovaná Om|mj = 2|Cmax. Mimo několik méně významných lemmat a pozorování přinášíme čtyři významné výsledky o této podtřídě. Prvním je pozorování, že každý rozvrh v této podtřídě lze transformovat na rozvrh stejné délky s jediným intervalem nečinnosti na každém stroji. Druhý je důkaz známé domněnky o takzvaných hustých rozvrzích pro tuto podtřídu. Třetí je modifikace známého hladového algoritmu, aby produkoval rozvrhy ne více jak 1.5 krát delší než optimální délka, a poslední významný výsledek je modifikace známého polynomiálního schématu, která garantuje lepší vlastnosti na zmíněné podtřídě.
|
|
|
Konstrukce minimálních DNF reprezentací 2-intervalových funkcí.
Dubovský, Jakub ; Čepek, Ondřej (vedoucí práce) ; Kučera, Petr (oponent)
Název práce: Konstrukce minimálních DNF reprezentací 2-intervalových funkcí Autor: Jakub Dubovský Katedra: Katedra teoretické informatiky a matematické logiky Vedoucí diplomové práce: doc.RNDr.Ondřej Čepek, Ph.D. Abstrakt: Tato práce se věnuje intervalovým boolovským funkcím. Je zaměřena na konstrukci jejich reprezentací pomocí disjunktivních normálních forem s co nej- menším počtem termů. Shrnuje známé výsledky v této oblasti pro 1-intervalové funkce. Ukazuje, že používanou metodu důkazu nelze obecně použít pro dva a více intervalové funkce. Pokouší se rozšířit tyto poznatky na 2-intervalové funkce. Je navrhnut optimalizační algoritmus pro speciální podtřídu 2-intervalových funkcí. Dokazuje se přesný odhad chyby pro jednoduchý aproximační algoritmus. Sou- částí práce je softwerová utilita pro experimentování s intervalovými funkcemi. Klíčová slova: boolovská funkce, intervalová funkce, konstrukce reprezentace, aproximace 1
|
|
|
Třídy Booleovských formulí s efektivně řešitelným SATem.
Vlček, Václav ; Čepek, Ondřej (vedoucí práce) ; Kučera, Petr (oponent)
Práce se zabývá třídami Booleovských formulí, pro které je problém splnitelnosti (SAT) řešitelný v polynomiálním čase. Zkoumá chování těchto tříd vzhledem k základním operacím s formulemi (komplementaci literálu, komplementaci proměnné, odebrání literálu nebo klauzule, částečné dosazení a spojení formulí). Dále se zabývá problémem rozpoznávání náležení formule do dané třídy, rozpoznávání splnitelnosti dané formule a vzájemnými vztahy těchto tříd vzhledem k inkluzi.
|
|
|
Vlastnosti intervalových booleovských funkcí
Hušek, Radek ; Čepek, Ondřej (vedoucí práce) ; Kučera, Petr (oponent)
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
|
|
|
Time complexity of Boolean minimization.
Gurský, Štefan ; Čepek, Ondřej (vedoucí práce) ; Kučera, Petr (oponent)
Práca sa zaoberá časovou zložitostou problému minimalizácie formúl reprezentujúcich Booleovské funkcie. Prezentuje základné koncepty z oblastí Booleovských funkcií, ich zápisu v normálnych formách a minimalizácie týchto zápisov. Celá kapitola je venovaná Umansovym [13] dôkazom 2 úplností minimalizácie DNF formúl pre obe základné používané miery minimality všeobecných funkcií. Pre triedu formulí nazývané Matched prináša nové výsledky, ktoré ukazujú, že aj ked je pre Matched formule jednoduchý problém splnitelnosti (tažký pre všeobecné formule), problémy spojené s minimalizáciou a aj samotná minimalizácia je pre ne rovnako tažká ako pre všeobecné formule.
|
|
|
Properties of k-interval Boolean functions
Gál, Pavol ; Čepek, Ondřej (vedoucí práce) ; Kučera, Petr (oponent)
Táto práca je zameraná predovšetkým na intervalové booleovské funkcie. Práca prezentuje základné znalosti o booleovských funkciach, ich reprezentáciach a hlavne sa koncentruje na pozitívne booleovské funkcie. Práca cituje viacero známych výsledkov o intervalových funkciách, ako sú ich rozne vlastnosti, niektoré rozpoznávacie algoritmy a ich zložitost. Práca dalej zavadza komutatívne booleovské funkcie a študuje vlastnosti komutatívnych pozitívnych booleovských funkcií a niektorých odvodených foriem. Práca formuluje viacero tvrdení o ich štruktúre a počte intervalov. Novým a najdoležitejším výsledkom je algoritmus na rozpoznávanie pozitívnych 3-intervalových funkcií. Na záver práca analyzuje štruktúru a počet intervalov niektorých konkrétnych všeobecných booleovskýcch funkcií.
|
|
|
Constrained activity sequencing
Nguyen, Son Tung ; Barták, Roman (vedoucí práce) ; Čepek, Ondřej (oponent)
Mnoho rozvrhovacích problémů lze považovat za problémy s hledáním posloupností aktivit splňujících určité podmínky a omezení. Typickým příkladem je rozvrhování letů v leteckém průmyslu, kde úlohou je přiřazení segmentů letů a servisních aktivit k jednotlivým letadlům. Tato diplomová práce se zaměřuje na hledání takovýchto omezených posloupností aktivit. Cílem práce je navrhnout formální model problému, včetně přesné specifikace podmínek a účelové funkce, schopný najít (sub)optimální posloupnosti aktivit. Navrhovaný model je založen na technikách Programování s omezujícími podmínkami.
|
|
|
Třídy Booleovských funkcí umožňující efektivní hledání minimálních reprezentací.
Kuřík, Stanislav ; Čepek, Ondřej (vedoucí práce) ; Gregor, Petr (oponent)
Tématem práce je problém minimalizace Booleovských funkcí. Rozebírá složitost minimalizace v obecném případě pro různé vstupní reprezentace a protože ve všech zde uvažovaných případech jde o NP-úplný problém, následuje přehled několika důležitých tříd funkcí, pro něž je řešitelný efektivně. Těžištěm práce je difinice nové třídy Booleovských funkcí spolu s prezentací algoritmu, který pro funkce této třídy nalezne minimální reprezentaci v polynomiálním čase. Nakonec je diskováno zobecnění této třídy a jeho vlastnosti vzhledem k minimalizaci.
|
|
|
Algoritmy pro rozvrhování s konflikty
Zajíček, Ondřej ; Sgall, Jiří (vedoucí práce) ; Čepek, Ondřej (oponent)
Problém rozvrhování s konflikty předpokládá graf konfliktů, jehož vrcholy reprezentují stroje a hrany reprezentují konflikty mezi nimi. Každý stroj může být vypnutý nebo zapnutý. Stroje, které jsou v konfliktu, nemohou být zároveŇ zapnuté. Na jednotlivé stroje čas od času přicházejí úlohy a řadí se do vstupních front jednotlivých strojů. Zapnuté stroje průběžně úlohy zpracovávají a vyprazdňují tak své fronty. Algoritmus rozhoduje o vypínání a zapínání jednotlivých strojů, přičemž musí dodržet omezení vyplývající z grafu konfliktů. Cílem je najít takový rozvrh, který minimalizuje maximální dosaženou délku vstupních front. Problém je online, algoritmus tedy musí reagovat průběžně, přičemž neví, jaké úlohy se objeví později. Navrhl jsem algoritmus založený na maximalizaci skalárního součinu pracovního vektoru (vektoru, reprezentujícího konfiguraci jednotlivých strojů) a vektoru délek front. V této práci dokazuji, že tento algoritmus je dobře de finován, je vždy konečný a pro konkrétní graf (cestu délky 3) je jeho kompetitivní poměr 7=3. Dále v práci rozebírám možnosti implementace tohoto algoritmu.
|
|
|
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.