|
|
Aproximace obtížných rozvrhovacích úloh
Lisý, Viliam ; Čepek, Ondřej (advisor) ; Vlach, Milan (referee)
This thesis deals with shop scheduling problems. After introducing the basic denitions and notation, we continue with a short survey of known complexity results for open shop, ow shop and job shop scheduling problems. Then we focus more on open shop and especially on a subclass of open shop with at most two non-zero length operations per job denoted Om|mj = 2|Cmax in standard notation. Besides some minor lemmas and observations, four major new results concerning this subclass are presented. The rst one is an observation, that any schedule in this class can be transformed in polynomial time to a schedule with same length and only one idle interval on each machine. The second one is a proof of a well known conjecture about so-called dense schedules for the subclass. The third one is modication of a known greedy algorithm to obtain schedules no longer then 3/2 of the optimal length, and the last one is a modication of a known polynomial approximation scheme which guarantees a better performance for instances from the above described subclass.
|
|
|
Konstrukce minimálních DNF reprezentací 2-intervalových funkcí.
Dubovský, Jakub ; Čepek, Ondřej (advisor) ; Kučera, Petr (referee)
Title: A construction of minimum DNF representations of 2-interval functions Author: Jakub Dubovský Department: Dep. of Theoretical Computer Science and Mathematical Logic Supervisor: doc.RNDr.Ondřej Čepek, Ph.D. Abstract: The thesis is devoted to interval boolean functions. It is focused on construction of their representation by disjunctive normal forms with minimum number of terms. Summary of known results in this field for 1-interval functions is presented. It shows that method used to prove those results cannot be in general used for two or more interval functions. It tries to extend those results to 2-interval functions. An optimization algorithm for special subclass of them is constructed. Exact error estimation for approximation algorithm is proven. A command line software for experimentation with interval function is part of the thesis. Keywords: boolean function, interval function, representation construction, ap- proximation 1
|
|
|
Classes of Boolean Formulae with effectively soluable SAT.
Vlček, Václav ; Čepek, Ondřej (advisor) ; Kučera, Petr (referee)
This work studies classes of Boolean formulae with polynomially solvable satsiability problem (SAT). It investigates the behavior of these classes with respect to basic operation with formulae (variable and literal complementation, deletition of a literal or a clause, partial assignment and joining formulae). Furthermore the work studies recognition problems for a formula and a given class of functions, satisability testing, and mutual relations of the studied classes with respect to inclusion.
|
|
|
Properties of interval Boolean functions
Hušek, Radek ; Čepek, Ondřej (advisor) ; Kučera, Petr (referee)
Boolean function f is k-interval if - input vector viewed as n-bit number - f is true for and only for inputs from given (at most) k intervals. Recognition of k-interval fuction given its DNF representation is coNP-hard problem. This thesis shows that for DNFs from a given solvable class (class C of DNFs is solvable if we can for any DNF F ∈ C decide F ≡ 1 in polynomial time and C is closed under partial assignment) and fixed k we can decide whether F represents k-interval function in polynomial time. 1
|
|
|
Time complexity of Boolean minimization.
Gurský, Štefan ; Čepek, Ondřej (advisor) ; Kučera, Petr (referee)
This thesis deals with the time complexity of Boolean minimization - minimization of formulae that represent Boolean functions. It presents basic concepts from the area of Boolean functions, of their normal form representations and of minimization of these representations. A whole chapter is dedicated to Umans's [13] proofs of 2 completeness of minimization of general DNF formulae for both common measures of minimality. For a class of formulae called Matched this thesis presents new results that show that although satisfiability problem is easy for Matched formulae (difficult for an arbitrary formula), problems connected to minimization and minimization itself is as hard for Matched formulae as it is for general formulae.
|
|
|
Properties of k-interval Boolean functions
Gál, Pavol ; Čepek, Ondřej (advisor) ; Kučera, Petr (referee)
The main focus of this thesis is on interval Boolean functions. The thesis presents some fundamental knowledge about Boolean functions, their representations and, in particular, concentrates on positive boolean functions. The thesis quotes several known results about interval functions, such as their various properties, some recognition algorithms and their complexity. Then the thesis introduces commutative Boolean functions and studies the properties of commutative positive Boolean functions and some derived forms. The thesis formulates several propositions about their structure and number of intervals. The most important and new result is the algorithm for recognition of positive 3-interval functions. Finally the thesis analyzes the structure and number of intervals of a few particular general Boolean functions.
|
|
|
Constrained activity sequencing
Nguyen, Son Tung ; Barták, Roman (advisor) ; Čepek, Ondřej (referee)
Many scheduling problems can be seen as activity sequencing problems, where the activity sequence in demand satisfies certain constraints. A typical example is scheduling in the airline industry where the task is to assign to each aircraft a segment of flight and nonflight activities while guaranteeing certain required properties. This diploma thesis deals with such type of constrained activity sequencing. The aim is to propose a formal model of the problem, including specification of all constraints and objectives, capable of finding (near)optimal sequences of activities. The proposed model is based on Constraint programming techniques.
|
|
|
Třídy Booleovských funkcí umožňující efektivní hledání minimálních reprezentací.
Kuřík, Stanislav ; Čepek, Ondřej (advisor) ; Gregor, Petr (referee)
This thesis deals with the Boolean minimization problem. We discuss its time complexity in the general case for various representations of the input. Since this problem is known to be NP-complete, a survey of some of important classes for which it is polynomially solvable follows. The main part of this thesis presents a definition of a new class of Boolean functions, along with an algorithm for finding a minimal representation of a given function from this class in polynomial time. Finally, a generalization of this class is obtained and its minimization-related properties are discussed.
|
|
|
Algorithms for scheduling with conflicts
Zajíček, Ondřej ; Sgall, Jiří (advisor) ; Čepek, Ondřej (referee)
Scheduling with conflicts supposes graph of conflicts. Vertices of that graph represent machines and edges represent conflicts between them. Every machine can be switched on or switched off . Two conflicting machines cannot be both switched on at the same time. At certain times new tasks arrive to speci c machines and enqueue to its input buff ers. Each machine continuously processes tasks from its input bu ffer whenever it is switched on. An algorithm decides which machines should be switched on or switched o ff at any time, obeying conflict constraints. The objective is to schedule machine switching to minimize the maximum bu er size of all processors. The problem is online, so an algorithm has to make decisions about current con ffiguration without knowledge of future tasks. In this thesis I consider the algorithm based on maximization of scalar product of work vector (vector describing con guration of machines) and vector of bu ffer lengths. I prove that this algorithm is well de ffined, finite on every input and for speciffi c graph (path of length 3) it has competitive ratio of 7=3. Further I consider possibilities of implementation of that algorithm.
|
|
|
Boolean methods in knowledge compilation
Kaleyski, Nikolay Stoyanov ; Čepek, Ondřej (advisor) ; Gregor, Petr (referee)
The open problem in knowledge compilation of whether the language PI is at least as succinct as MODS is answered in the negative. For this purpose a class of Boolean functions with a number of prime implicants that is superpolynomial in their number of false points is constructed. A lower bound (proving that PI is not at least as succinct as MODS), an upper bound (proving that the counterexample cannot yield an exponential separation of PI and MODS) and the precise number of the prime implicants of these functions is computed. Powered by TCPDF (www.tcpdf.org)
|
guest ::
