SubjectsSubjects(version: 853)
Course, academic year 2019/2020
  
Deterministic and stochastic discrete systems - P413004
Title: Deterministické a stochastické diskrétní systémy
Guaranteed by: Department of Mathematics (413)
Actual: from 2019
Semester: both
Points: 0
E-Credits: 0
Examination process:
Hours per week, examination: 3/0 other [hours/week]
Capacity: winter:unknown / unknown (unknown)
summer:unknown / unknown (unknown)
Min. number of students: unlimited
Language: Czech
Teaching methods: full-time
Level:  
For type: doctoral
Note: course is intended for doctoral students only
can be fulfilled in the future
you can enroll for the course in winter and in summer semester
Guarantor: Turzík Daniel doc. RNDr. CSc.
Kříž Pavel Mgr. Ing. Ph.D.
Interchangeability : D413004
Is interchangeable with: AP413004
Annotation -
Last update: Kříž Pavel Mgr. Ing. Ph.D. (03.10.2018)
Students will learn basic concepts of graph theory and discrete random processes (random walk, Markov chains, martingales). Fundamental properties (especially dynamics and limiting behaviour) of such processes are studied. The basic combinatorial optimization tasks (the shortest path, matching, coloring, etc.) are discussed. Many tasks are formulated as linear programming problems or integer linear programming problems. The importance of duality to solve these problems is shown. Further, the computational complexity of the investigated tasks is discussed. The relation of polynomially and non-deterministically polynomially solved problems is investigated.
Aim of the course -
Last update: Kříž Pavel Mgr. Ing. Ph.D. (03.10.2018)

Students will understand basic algorithms of discrete optimization, their complexity and applications. They will learn the description of combinatorial tasks using linear programming. Further, students will get familiar with basic concepts for modelling random processes with discrete set of states and will be able to determine/calculate basic properties of these models.

Literature -
Last update: Kříž Pavel Mgr. Ing. Ph.D. (12.10.2018)

A: Alexander Schrijver: A Course in Combinatorial Optimization (2017)

Z: Nicolas Privault: Understanding Markov Chains - Examples and Applications (Springer Singapore, 2013)

Learning resources -
Last update: Kříž Pavel Mgr. Ing. Ph.D. (03.10.2018)

https://www.emse.fr/~xie/SJTU/Ch4DMC.ppt

https://web.ma.utexas.edu/users/gordanz/notes/discrete_martingales.pdf

Teaching methods -
Last update: Kříž Pavel Mgr. Ing. Ph.D. (03.10.2018)

Self-study, consultations

Requirements to the exam -
Last update: Kříž Pavel Mgr. Ing. Ph.D. (03.10.2018)

The progress of students is checked within regular consultations during the semester.

Syllabus -
Last update: Kříž Pavel Mgr. Ing. Ph.D. (03.10.2018)

1. Basic concepts of graph theory.

2. Discrete random walk.

3. Discrete Markov chains – Markov property, transition matrix, limiting distribution.

4. Discrete martingales – stopping time, optional stopping theorem.

5. Linear programming. Duality.

6. Combinatorial optimization problems (The task of the shortest route, Minimum spanning tree, Matching and Covering in Bipartite Charts, Flows in networks etc.)

7. Words, problems, algorithms.

8. Computational complexity. Class P, NP, co-NP. NP-complete problems. Reduction.

9. Matroids. Examples and basic features.

10. Greedy search.

Registration requirements -
Last update: Mareš Jan doc. Ing. Ph.D. (03.10.2018)

none

Course completion requirements -
Last update: Kříž Pavel Mgr. Ing. Ph.D. (03.10.2018)

Oral exam

Coursework assessment
Form Significance
Oral examination 100

 
VŠCHT Praha