|
|
Marxism, neo-marxism - views of education
Kratochvíl, Jan ; Kopecký, Martin (advisor) ; Mužík, Jaroslav (referee)
The work talks about education in a sociological and philosophical context. It is based on the Marxist, or rather Neomarxist, point of view, introduced in the first part of the work. It mainly focuses on Marx's historical theory and the alienation of man in capitalism. Furthermore, the works of certain authors, who wrote about these topics, as well as criticised some of the features of the late capitalistic society are briefly discussed. The term education is then put in a social context and introduced in different culturally dependent variations. The goal of this section of the work is to show the dependence of the perception of education on the current historical and social context and to elaborate on its perception in the late capitalistic society. Then a certain theoretical definition is formed, which could be essential in solving certain problems based on the current structure of social relationships. The final part investigates school and reveals it as a certain institucional conservant of the current understanding of education. It shows that even school tuition depends on the historically and socially conditioned values and therefore cannot become the primary source for redefining the meaning of education, so that it could aid in solving some of the structural problems of society.
|
|
|
Structural and complexity questions of graph theory
Gavenčiak, Tomáš ; Kratochvíl, Jan (advisor) ; Hliněný, Petr (referee) ; Fomin, Fedor (referee)
DOCTORAL THESIS ABSTRACT Tomáš Gavenčiak Structural and complexity questions of graph theory The original cops and robber game, proposed in 1983 by Nowakowski and Winkler, and independently by Quilliot, is a two-player combinatorial pursuit game on a graph. Many related games have been introduced and studied since then, both with a purely game theoretic motivation and for their applications in graph theory and connections with graph width parameters. We give an overview of the field and present three particular results: We show bounds on the required number of cops for various connected intersection graph classes, most notably we show that on connected string graphs 15 cops always win. We show the game of cops and fast robber to be polynomially decidable on interval graphs and as a tool we generalise the problem of defensive domination and show a polynomial algorithm for interval graphs. Finally we propose and examine generalisations of tree-depth, marshals and robber games, and minors to hypergraphs and hypergraph pairs.
|
|
|
Hry na grafech ve vztahu k zdvihovým parametrům grafů
Gavenčiak, Tomáš ; Kratochvíl, Jan (advisor) ; Smrž, Otakar (referee)
We consider a variant of a cop and robber game with an in nitely fast robber and its relations to other similar games. We compare the helicopter game characterizing tree-width, the classical cop and robber game and its versions with various speeds of the robber. We study the complexity of the in nitely fast robber variant and give an explicit characterization of all the graphs where one cop can win. As the main result, we show a polynomial time algorithm deciding the game on interval graphs. This answers a question from the paper Fomin et al.: On tractability of Cops and Robbers game, IFIP TCS 2008, 171-185. To show the polynomiality of the game on interval graphs, we introduce a new auxiliary game on an interval representation of the graph and show the polynomiality of that game. Then we use game strategy reductions to show the equivalence of the two games.
|
|
|
Numerical simulations of flows of visco-elastic fluid-like materials, as asphalt in particular
Kratochvíl, Jan ; Málek, Josef (advisor) ; Rajagopal, K.R. (referee)
In this thesis we deal with numerical simulations for flows of viscoelastic fluids. First, we introduce two models for viscoelastic fluids: (i) the Oldroyd-B, which is a classical model for viscoelastic fluids and (ii) a new nonlinear model which might be thought of as a generalization of Oldroyd-B to the case of large elastic deformations. Then, the flow at three different situations is discussed. The first of them is stress relaxation in parallel plate flow, which is an example of a 1D problem. The second one is a 4:1 planar contraction flow, which is a standard benchmark for viscoelastic flows. The third problem is stress relaxation in axially symmetric cylinder flow, which is solved as a 1D as well as a 2D problem. If it is possible, the problems are solved analytically, otherwise they are solved numerically with the aid of the finite element method using the software Comsol Multiphysics 3.3. Experimental data that document the stress relaxation of asphalt are available in the cylindrical geometry. Thus, finally, these data are fitted using both considered models.
|
|
|
Parameterized Complexity
Suchý, Ondřej ; Kratochvíl, Jan (advisor) ; Telle, Jan Arne (referee) ; Obdržálek, Jan (referee)
Title: Parameterized Complexity Author: Ondřej Suchý Department: Department of Applied Mathematics Advisor: Prof. RNDr. Jan Kratochvíl, CSc. Advisor's e-mail address: honza@kam.mff.cuni.cz Abstract: This thesis deals with the parameterized complexity of NP-hard graph problems. We explore the complexity of the problems in various scenarios, with respect to miscellaneous parameters and their combina- tions. Our aim is rather to classify in this multivariate manner whether the particular parameters make the problem fixed-parameter tractable or intractable than to present the algorithm achieving the best running time. In the questions we study typically the first-choice parameter is unsuccessful, in which case we propose to use less standard ones. The first family of problems investigated provides a common general- ization of many well known and studied domination and independence problems. Here we suggest using the dual parameterization and show that, in contrast to the standard solution-size, it can confine the in- evitable combinatorial explosion. Further studied problems are ana- logues of the Steiner problem in directed graphs. Here the parameter- ization by the number of terminals to be connected seems to be previ- ously unexplored in the directed setting. Unfortunately, the problems are shown to be...
|
|
| |
|
|
Computational complexity in Graph Theory
Herman, Jan ; Kratochvíl, Jan (advisor) ; Flusser, Jan (referee)
Seidel's switching is a graph operation , which for a given graph G and one of its vertices v gives the graph derived from G by replacing edges adjacent to v by non-edges and vice-versa. A graph H is called a switch of G, if H can be obtained from G by a sequence of switches of its vertices. In the thesis we introduce known results ab out computational complexity of problems if for a given graph G t here exists its switching lying in a given graph class (}. For different graph classes g, we later study a characterization of the class of all graphs, which can be switched into g, in terms of minimal forbidden induced subgraphs. We introduce a full characterization of a class of graphs switchable to a disjoint union af cutworms, respectively partial pairings by forbidden subgraphs. We also prove that a class of graphs switchable to chordal has infinit ely many non-isomorphic forbidden subgraphs. At the end we deal with the relationship between swit ching and other graph operations and graph classes operations.
|
|
|
Drawing geometric graphs on red-blue point sets
Soukup, Jan ; Kynčl, Jan (advisor) ; Kratochvíl, Jan (referee)
Consider a set B of blue points and a set R of red points in the plane such that R ∪ B is in general position. A graph drawn in the plane whose edges are straight-line segments is called a geometric graph. We investigate the problem of drawing non-crossing properly colored geometric graphs on the point set R ∪ B. We show that if ||B| − |R|| ≤ 1 and a subset of R forms the vertices of a convex polygon separating the points of B, lying inside the polygon, from the rest of the points of R, lying outside the polygon, then there exists a non-crossing properly colored geometric path on R∪B covering all points of R ∪ B. If R∪B lies on a circle, the size of the longest non-crossing geometric path is related to the size of the largest separated matching; a separated matching is a non-crossing properly colored geometric matching where all edges can be crossed by a line. A discrepancy of R ∪ B is the maximal difference between cardinalities of color classes of intervals on the circle. When the discrepancy of R ∪ B is at most 2, we show that there is a separated matching covering asymptotically 4 5 of points of R ∪ B. During this proof we use a connection between separated matchings and the longest common subsequences between two binary sequences where the symbols correspond to the colors of the points.
|
|
|
Partial representation extension for subclasses of interval graphs
Onduš, Daniel ; Kratochvíl, Jan (advisor) ; Jelínek, Vít (referee)
The problem of extending partial representations for an interval graph asks, whether it is possible to extend a given representation of some vertices to a valid representation of the entire graph. In this thesis we extend the recent result of Klavík et al. who proved REPEXT can be decided for proper and unit interval graphs in polynomial time. We describe properties of PI± and U± graphs and their representations and present algorithms deciding REPEXT for these classes in polynomial time. In the process, we characterize relations between the K1,3's in a graph and show that we can decide the open vertex of every K1,3. We also define notions of representation of the same order type and locally similar representations as well as intervals forced and locally forced to be closed (open) that are essential for extending partial representations when multiple types of intervals can occur in the same representation. We characterize intervals forced and locally forced to be closed (open) in a U± graph using integer gaps in the pre-representation and we construct lower bounds for the rightmost endpoint of a component in polynomial time.
|
|
|
Namesti Miru in Brno improvement and completion
Mikel, Jakub ; Štěpánek, Martin (referee) ; Kratochvíl, Jan (advisor)
Form and future utilization of Brno square Míru is on a long-term basis discussed topic for the general and the professional public. The discussion on the utilization of this significant area was accelerated after the Ministry of Defence transferred the possession of the unused military area to city of Brno in 2003. The residents of the Masaryk´s district, of which is the square Míru notional centre, have written many protest petitions and have held several meetings with suggesting outputs for municipal political authorities. Currently held urbanistic-architectural public tender, of which the results are to be announced in the term corresponding with the date of submission of this bachelor thesis, will be interesting confrontation of the students´ theses. The bachelor thesis will check student´s knowledge in the fields of designing public city areas, designing poly-functional buildings, interior design and technological and constructional solutions.
|
guest ::
RSS feed.