## Circuit Theoretical Foundations of Computer Science

Subcategories:- Graph Theory
- Topological graph theory
- Structural Theory of Graphs
- Parametrized complexity
- Fundamentals of Probability Theory
- Markov chains with discrete and continuous time
- Computational complexity
- Algorithm for difficult problems

### Graph Theory

**Annotation:**

Graphs are one of the most used mathematical structures in computer science. The candidate will study in depth all the fundamental areas of graph theory. The theme is suitable for all students without a theoretical focus.

**Warp:**

Basic concepts, pairing and coverage, context, planar graphs, color of graphs, flow in charts.

**Basic study material:**

Reinhard Diestel, Graph Theory , 4th edition 2010, Springer-Verlag, Heidelberg Graduate Texts in Mathematics, Volume 173, ISBN 978-3-642-14278-9, Chapters 1-6, 167 pages (including basic passages in the Master's degree program).

**Tutor:**prof. Petr Hlineny, PhD. Jan Obdržálek

**Other Recommended Literature:**

Matoušek, J., Nešetřil, J .: Chapters from Discrete Mathematics. Karolinum, Prague 2009

### Topological graph theory

**Annotation:**

The topological graph theory (in short, drawing graphs) evolved from the effort to solve the problem of four colors to a relatively extensive discipline, and later proved extremely important in graph minors and derived algorithms.

This specialized topic covers an overview of the basic knowledge and techniques of working in topological charts according to the really great monograph of Mohar and Thomassen. It also shows how graph theory provides a new and more accessible view of classical topological knowledge of the Jordanian theorem or the classification of areas.

**Warp:**

Fundamentals of planar topology, Jordan theorem, planar graphs, Kuratowski theorem, basic classification of surfaces, plotting of surfaces, graph genus, combinational description of graph drawing, edge-width and face-width

**Basic study material:**

Bojan Mohar, Carsten Thomassen: Graphs on Surfaces, Johns Hopkins University Press, 2001, Chapters 1-4, 5.1, 5.5, 136 pages

**Tutor:**prof. Petr Hlineny

**Other Recommended Literature:**

Matoušek, J., Nešetřil, J .: Chapters from Discrete Mathematics. Karolinum, Prague 2009

Reinhard Diestel: Graph Theory , Springer-Verlag, 2010

### Structural Theory of Graphs

**Annotation:**

Structural graph theory provides deep mathematical knowledge with direct application in many new sophisticated algorithms (eg tree decomposition or Graph Minors Theorem). This special subchapter allows insight into the depths of structural graph theory in the presentation of the well-known Diestell's monograph and show an overview of the most important results and evidence techniques.

*Alternatively*: Focusing on the new Sparsity theory and Ussel de Mendez, shallow minors, depth of graphs and characterization of thin classes of graphs.

**Warp:**

Link of graphs (multiple), extreme theory of graphs, minors, Hadwiger hypothesis, tree decomposition, forbidden minors, good quasi-arrangement.

*Alternatively*, shallow minors, tree depths, sparse graphs, and their characterization.

**Basic study material:**

Reinhard Diestel, Graph Theory , 4th edition 2010, Springer-Verlag, Heidelberg Graduate Texts in Mathematics, Volume 173, ISBN 978-3-642-14278-9, Chapters 1,3,7,12, 136 pages.

*Alternatively*: J. Nešetřil and P. Ossona de Mendez, Sparsity, Springer, 2012, ISBN 978-3-642-27874-7. Chapters 1-7, 170 pages.

**Tutor:**prof. Petr Hlineny, PhD. Jan Obdržálek

**Other Recommended Literature:**

Matoušek, J., Nešetřil, J .: Chapters from Discrete Mathematics. Karolinum, Prague 2009

### Parametrized complexity

**Annotation:**

Parametrized complexity deals with the study and classification of computational problems according to their "difficulty" depending on more than one input parameter. The complexity of the problem is then expressed as a function of these parameters. For example, this approach makes it possible to fine-tune NP-difficult problems according to their "real" complexity.

**Warp:**

Parameterized problems, fixed-parameter tractability, FPT and XP classes, W [i] hierarchies and W [1] -complete kerneling problems.

**Basic study material:**

J. Flum and M. Grohe, Parameterized Complexity Theory, Springer, 2006.

Chapters 1-6.1 (pp.1-114), 9.1-9.3 (pp. 207-222)

**Tutor:**prof. Petr Hlineny, Dr. Jan Obdržálek

**Other Recommended Literature:**

R. Downey and M. Fellows, Parameterized Complexity, Springer, 1999.

R. Downey and M. Fellows, Fundamentals of Parameterized Complexity, Springer, 2013.

R. Niedermayer, Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006.

### Fundamentals of Probability Theory

**Annotation:**

The general theory of probability is built on the basis of the theory of measure and integrity. The candidate will get acquainted with the general introduction of basic concepts (probability space, random variable, mean value, etc.) and selected probability theory tools, which are often used in practice.

**Warp:**

Lebesgue measure, measurable function, random variable; Lebesgue integral, mean value; the law of large numbers and its variants; Borel-Cantelli lema, Kolmogorov's 0-1 law.

**Basic study material:**

JS Rosenthal, A First Look at Rigorous Probability Theory, World Scientific, 2000, Chapters 1-7 (pp. 1-67).

**Tutor:**doc. Tomáš Brázdil, prof. Antonín Kučera

**Other Recommended Literature:**

P. Billingsley. Probability and Measure, Wiley, 1995.

### Markov chains with discrete and continuous time

**Annotation:**

Markov chains are an essential tool for modeling and analyzing random processes in both the natural and technical sciences, including computer science. The candidate will get acquainted with the basics of Markov chains with discrete and continuous time.

**Warp:**

Recurrent and transient states, probability and mean return time, invariant probability distribution, Ergodic theorem.

**Basic study material:**

JR Norris, Markov chains, Cambridge Univ. Press, 1997, Chapters 1-3 (pp. 1-125).

**Tutor:**doc. Tomáš Brázdil, prof. Antonín Kučera, dr. Vojtěch Řehák

**Other Recommended Literature:**

W. Feller. An Introduction to Probability Theory and Its Applications, Wiley, 1966 (Volume I, II).

John G. Kemeny, J. Laurie Snell, Anthony W. Knapp. Denumerable Markov Chains. Springer, 1976.

### Computational complexity

**Annotation:**

The student will get acquainted with basic methods and techniques in the field of computational complexity and possibilities of their use in other fields of informatics.

**Warp:**

Computational models and computational complexity, Complexity classes and their difficult and complete problems. Method of diagonalization and separation of class complexities. Space complexity. Polynomial hierarchy and alternation. Logic circuits. Random Calculations, Interactive Evidence Systems. Lower estimates for specific computational models. Communication complexity. PCP and unapplicable.

**Basic study material:**

The examiner determines the selection of chapters in the range of 100-200 pages of S. Arora, B. Barak, Computational Complexity: A Modern Approach. Cambridge University Press, 2009

**Tutor:**prof. Ivana Černá

**Other Recommended Literature:**

D. Kozen, Theory of Computation. Springer, 2006.

### Algorithm for difficult problems

**Annotation:**

tudent acquaint with methods and techniques for solving (not only NP) difficult problems. The techniques are applied in the design of specific algorithms from different application areas.

**Warp:**

Deterministic approaches (pseudopolynomic and parameterized algorithms, low-exponential algorithms). Approximate techniques (combinatorial approach, approach based on linear and semilinear programming, random access). Random algorithms (classification, techniques, data structures design, graph algorithms). Heuristic methods (local search, simulated annealing and others).

**Basic study material:**

The examiner determines the selection of chapters in the range of 100-200 pages from the textbook J. Hromkovič, Algorithmics for Hard Problems. 2nd Edition. Spinger, 2006.

**Tutor:**prof. Ivana Černá

**Other Recommended Literature:**

V. Vazirani, Approximation Algorithms. Springer, 2001.

R. Motwani, P. Raghava, Randomized Algorithms. Cambridge University Press, 1995.