|
|
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.
|
|
|
Globální podmínky s cenou
Hejna, Martin ; Čepek, Ondřej (oponent) ; Barták, Roman (vedoucí práce)
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.
|
|
|
Interval Representations of Boolean Functions
Kronus, David ; Čepek, Ondřej (vedoucí práce) ; Sgall, Jiří (oponent) ; Savický, Petr (oponent)
This thesis is dedicated to a research concerning representations of Boolean functions. We present the concept of a representation using intervals of integers. Boolean function f is represented by set I of intervals, if it is true just on those input vectors, which correspond to integers belonging to intervals in I, where the correspondence between vectors and integers depends on the ordering of bits determining their significancies. We define the classes of k-interval functions, which can be represented by at most k intervals with respect to a suitable ordering of variables, and we provide a full description of inclusion relations among the classes of threshold, 2-monotonic and k-interval Boolean functions (for various values of k). The possibility to recognize in polynomial time, whether a given function belongs to a specified class of Boolean functions, is another fundamental and practically important property of any class of functions. Our results concerning interval functions recognition include a proof of co-NP- hardness of the general problem and polynomial-time algorithms for several restricted variants, such as recognition of 1-interval and 2-interval positive functions. We also present an algorithm recognizing general 1-interval functions provided that their DNF representation satisfies several...
|
|
|
Aproximace obtížných rozvrhovacích úloh
Lisý, Viliam ; Vlach, Milan (oponent) ; Čepek, Ondřej (vedoucí práce)
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ě.
|
|
|
Horn Formulas
Bigoš, Štefan ; Kučera, Petr (oponent) ; Čepek, Ondřej (vedoucí práce)
Jednou z aktuálne najštudovanejších podmnožín Booleovských funkcií sú Hornovské funkcie. V nich je mnoho nezodpovedaných otázok v probléme ich minimalizácie (nájdenie najkompaktnejšej ekvivalentnej reprezentácie). Tak ako Kronus [11] rozšíril poznatky v oblasti Hornovských formulí o neobvyklú mieru počtu zdrojových množin na základe teórie z relačných databáz, tak táto práca posúva jeho snahu o krok d'alej a tentokrát na základe teórie z hypergrafov zadefiuje d'alšie tri bežne nepoužívané miery a odvodí ich súvislosti a vlastnosti. Dalším sledovaným problémom je zložitost' Hornovskej minimalizácie pri obmedzení počtu literálov v terme. Doteraz najsilnejším tvrdením bol d^okaz o tom, že NP-ťažkost' sa zachováva aj ked' obmedzíme tento počet na tri. Okrem nájdenia nezrovnalosti v d^okaze a jeho podrobnému rozobraniu, zadefinujem aj problém ktorý je ekvivalentný tomu, ktorý sa nachádza v čláanku. Tým dám priestor na prrípadnů opravu d^okazu v budúcnosti. Najvetším prínosom by potom malo byt' vyplnenie vzniknutej medzery dokázaním o čosi slabšieho tvrdenia. Totiž, že problém Hornovskej minimalizácie zostáva NP-ťažký aj pri obmedzení počtu literálov v terme na 4.
|
|
|
Temporal networks
Vlk, Rudolf ; Čepek, Ondřej (oponent) ; Barták, Roman (vedoucí práce)
Integrace plánování rozvrhování vyžaduje hledání nových přístupů problému rozvrhování. Rozvrhovací systém musí být schopen poskytnout užitečné informace plánovači, aby se zabránilo vytvářní neuskutečnitelných plánů. Pro rozvrhování založené na splňování omezujících podmínek je možné de novat vlastní fi ltrační pravidla a tak zefektivnit řešící algoritmus. Pokud filtrační pravidla využívají informace sdělené plánovačem a rozvrhovacím systémem (např. precedenční a nebo temporální podmínky), výstup těchto pravidel je mozné poskytnout plánovači, který je může s výhodou využít. V této práci je navržena filtrační metoda, která využívá temporální vztahy mezi aktivitami alokovanými na jeden nebo více disjunktivních zdrojů. Práce také popisuje sadu propagačnch pravidel založených na kombinaci ruzných fi ltračních technik.
|
|
|
Třídy Booleovských formulí s efektivně řešitelným SATem.
Vlček, Václav ; Kučera, Petr (oponent) ; Čepek, Ondřej (vedoucí práce)
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.
|
|
|
Třídy Booleovských funkcí umožňující efektivní hledání minimálních reprezentací.
Kuřík, Stanislav ; Gregor, Petr (oponent) ; Čepek, Ondřej (vedoucí práce)
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.
|
|
|
Právní a systémová analýza e-Governmentu
Rieger, Pavel ; Mates, Pavel (vedoucí práce) ; Polčák, Radim (oponent) ; Čepek, Ondřej (oponent)
Cílem této práce je analyzovat různé právní, technické a ekonomické otázky, které mají souvislosti s budováním e-Governmentu v České republice a vyvodit obecné předpoklady pro úspěšný rozvoj služeb e-Governmentu. Práce obsahuje přehled právní úpravy, která má přímý či nepřímý dopad na rozvoj e-Governmentu. Týká se to hlavně právní úpravy elektronického podpisu, informačních systémů veřejné správy, obecných předpisů o správním řízení a řady dalších speciálních zákonů. V textu práce jsou podrobně analyzovány aktuálně realizované projekty e-Governmentu, zejména kontaktní místa veřejné správy (Czech POINT), datové schránky, autorizovaná konverze dokumentů a základní registry veřejné správy. Zvláštní pozornost je v práci věnována také ochraně osobních údajů v informačních systémech. Možné dopady elektronizace veřejné správy jsou hodnoceny také s ohledem na adresáty veřejné správy, především občany a právnické osoby. Pro měření pokroků v realizaci dílčích projektů e-Governmentu jsou navrhovány měřitelné ukazatele (metriky), společně s postupem jejich výpočtu. Práce dochází k závěru, že pro spolehlivější měření efektivnosti je potřebné určovat kvantifikovatelné ukazatele na straně nákladů i na straně užitků. Tyto ukazatele by měly být orientovány nejen na nákladové hledisko, ale také na plnění konkrétních cílů veřejné správy. Co se týká metodologie, v textu práce jsou použity obvyklé metody výzkumu v oblasti právních věd. Dále jde o procesní analýzy, nákladové analýzy a analýzu metrik, jejichž metodologie vychází především z oborů ekonomie, managementu či informačního managementu. K plnění cílů práce a k ověřování hypotéz byly použity také případové studie.
|
host ::
RSS.