Subjects

Hello,

On Monday, April 28 after 5 pm, some of the university's information systems will be unavailable due to maintenance work.

Affected systems are the Education Information System, Financial IS (iFIS), MIS/OBD/Verso, Kopla and related agendas.

It is anticipated that everything should be back online and running by Tuesday morning.

Work with e-mail or shared drives will not be affected.

Computer center

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Discrete Optimalization - D413004

Title:	Diskrétní optimalizace
Guaranteed by:	Department of Mathematics (413)
Faculty:	Faculty of Chemical Engineering
Actual:	from 2011 to 2020
Semester:	winter
Points:	winter s.:0
E-Credits:	winter s.:0
Examination process:	winter s.:
Hours per week, examination:	winter s.:0/0, other [HT]
Capacity:	unknown / unknown (unknown)
Min. number of students:	unlimited
Qualifications:
State of the course:	taught
Language:	Czech
Teaching methods:	full-time
Level:
Note:	course is intended for doctoral students only can be fulfilled in the future

Guarantor:	Turzík Daniel doc. RNDr. CSc.

Examination dates Schedule

Annotation - Czech

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.

Last update: Turzík Daniel (01.10.2015)

Literature - Czech

Alexander Schrijver: A Course in Combinatorial Optimization

Last update: Turzík Daniel (01.10.2015)

Syllabus - Czech

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.

Last update: Turzík Daniel (01.10.2015)

Learning outcomes - Czech

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í.

Last update: Turzík Daniel (01.10.2015)

Registration requirements - Czech

Matematika I. a Matematika II.

Last update: Turzík Daniel (01.10.2015)