SubjectsSubjects(version: 853)
Course, academic year 2019/2020
  
Discrete Optimalization - D413004
Title: Diskrétní optimalizace
Guaranteed by: Department of Mathematics (413)
Actual: from 2011
Semester: winter
Points: winter s.:0
E-Credits: winter s.:0
Examination process: winter s.:
Hours per week, examination: winter s.:0/0 other [hours/week]
Capacity: unknown / unknown (unknown)
Min. number of students: unlimited
Language: Czech
Teaching methods: full-time
Level:  
For type:  
Note: course is intended for doctoral students only
can be fulfilled in the future
Guarantor: Turzík Daniel doc. RNDr. CSc.
Is interchangeable with: AP413004, P413004
Annotation - Czech
Last update: Turzík Daniel doc. RNDr. CSc. (01.10.2015)
Studenti se seznámí se základními pojmy teorie grafů. Probírají se základní úlohy kombinatorické optimalizace jako úloha nejkratší cesty, úlohy o párování, barvení grafu apod. Mnohé úlohy jsou formulovány jako úlohy lineárního programování, či úlohy celočíselného lineárního programování. Ukazuje význam duality pro řešení těchto úloh. Dále se probírá výpočetní složitost vyšetřovaných úloh. Zkoumá se vztah polynomiálně a nedeterministicky polynomiálně řešitelných úloh.
Aim of the course - Czech
Last update: Turzík Daniel doc. RNDr. CSc. (01.10.2015)

Studenti porozumí základním algoritmům diskrétní optimalizace, jejich složitosti a možnosti aplikací. Naučí se popis kombinatorických úloh pomocí lineárního programování.

Literature - Czech
Last update: Turzík Daniel doc. RNDr. CSc. (01.10.2015)

Alexander Schrijver: A Course in Combinatorial Optimization

Syllabus - Czech
Last update: Turzík Daniel doc. RNDr. CSc. (01.10.2015)

1. Základní pojmy teorie grafů.

2. Konvexní množiny polyedry a polytopy.

3. Lineární programování. Dualita.

4. Úloha nejkratší cesty.

5. Stromy. Minimální kostra grafu.

6. Párování a pokrytí v bipartitních grafech.

7. Vážené párování. Polytop párování.

8. Toky v sítích.

9. Maximální tok a algoritmy pro jeho nalezení.

10. Slova, problémy, algoritmy.

11. Výpočetní složitost.Třídy P, NP, co-NP.

12. NP-úplné problémy. Redukce.

13. Matroidy. Příklady a základní vlastnosti.

14. Hladový algoritmus.

Registration requirements - Czech
Last update: Turzík Daniel doc. RNDr. CSc. (01.10.2015)

Matematika I. a Matematika II.

 
VŠCHT Praha