|
|
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...
|
|
| |
|
|
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.
|
|
|
Výpočetní složitost v teorii grafů
Ondráčková, Eva ; Kratochvíl, Jan (vedoucí práce) ; Sgall, Jiří (oponent)
Seidelovo přepnutí je grafová operace, která změní hrany vycházející z daného vrcholu tak, aby sousedil s právě těmi vrcholy, které původně nebyly jeho sousedy; zbytek grafu zůstane nezměněn. Dva grafy nazveme ekvivalentní v přepnutí, pokud lze pomocí posloupnosti přepnutí jeden z nich převést na izomorfní tomu druhému. V této práci studujeme výpočetní složitost problému S(P) pro určitou grafovou vlastnost P: je daný graf G ekvivalentní v přepnutí nějakému grafu, který má vlastnost P? Neprve podáváme přehled známých výsledků, vlastností P, pro které je problém S(P) polynomiální, i těch, pro které je NP-úplný. Poté ukážeme NP-úplnost následujícího problému pro každé c (0; 1): lze daný graf G přepnout tak, aby obsahoval kliku velikosti alespoň cn, kde n je počet vrcholů grafu G? Zabýváme se také problémem pro pevně zvolený graf H rozhodnout, zda je daný graf G ekvivalentní v přepnutí nějakému H-prostému grafu. Ukážeme, že je-li H izomorfní spáru, tento problém je polynomiální. Dále podáváme charakterizaci grafů, které jsou ekvivalentní v přepnutí nějakému K1;2-prostému grafu, pomocí deseti zakázaných indukovaných podgrafů, z nichž každý má pět vrcholů.
|
|
| |
|
|
Online competitive algorithms for maximizing weighzed throughput of unit jobs. ITI Series 2003-172
Bartal, Y. ; Chin, F. Y. L. ; Chrobak, M. ; Fung, S. P. Y. ; Jawor, W. ; Lavi, R. ; Sgall, Jiří ; Tichý, Tomáš
We study an online buffer management problem for networks supporting Quality-of-Service (QoS) applications, equivalently as an online scheduling problem forunit-length jobs, where each job is specified by its release time, deadline, and a nonnegative weight (QoS value). The goal is to maximize the emph{weighted throughput}, that is the total weight of scheduled jobs.
|
|
| |
|
| |
|
| |
|
| |
host ::
RSS.