PředmětyPředměty(verze: 922)
Předmět, akademický rok 2022/2023
  
--:--
 
 Hledání ... Moje předměty Vyučující Katedry Nastavení
 
 
 
 Detail
 
 
 
 
Deterministické a stochastické diskrétní systémy - P413004
Anglický název: Deterministic and stochastic discrete systems
Zajišťuje: Ústav matematiky, informatiky a kybernetiky (446)
Fakulta: Fakulta chemicko-inženýrská
Platnost: od 2021
Semestr: oba
Body: 0
E-Kredity: 0
Způsob provedení zkoušky:
Rozsah, examinace: 3/0, Jiné [HT]
Počet míst: zimní:neurčen / neurčen (neurčen)
letní:neurčen / neurčen (neurčen)
Minimální obsazenost: neomezen
Jazyk výuky: čeština
Způsob výuky: prezenční
Úroveň:  
Pro druh: doktorské
Poznámka: předmět je určen pouze pro doktorandy
student může plnit i v dalších letech
předmět lze zapsat v ZS i LS
Garant: Turzík Daniel doc. RNDr. CSc.
Kříž Pavel Ing. Mgr. Ph.D.
Záměnnost : D413004
Je záměnnost pro: AP413004
Anotace -
Poslední úprava: Kříž Pavel Ing. Mgr. Ph.D. (03.10.2018)
Studenti se seznámí se základními pojmy a koncepty teorie grafů a diskrétních náhodných procesů (náhodná procházka, markovský proces, martingal). Studují se základní vlastnosti těchto procesů, zejména jejich dynamika a limitní chování (limitní rozdělení a jeho výpočet). Dále se probírají 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 či celočíselného programování. Ukazuje se 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.
Výstupy studia předmětu -
Poslední úprava: Kříž Pavel Ing. Mgr. Ph.D. (03.10.2018)

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í. Dále pochopí základní koncepty pro modelování náhodných procesů s diskrétní množinou stavů a naučí se počítat základní vlastnosti těchto modelů.

Literatura -
Poslední úprava: Kříž Pavel Ing. Mgr. Ph.D. (12.10.2018)

Z: Daniel Turzík: Matematika III - Základy optimalizace, Vydavatelství VŠCHT, 1999. ISBN 80-7080-363-0

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

D: Alexander Schrijver: A Course in Combinatorial Optimization (2017)
Studijní opory -
Poslední úprava: Kříž Pavel Ing. Mgr. Ph.D. (03.10.2018)

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

https://web.ma.utexas.edu/users/gordanz/notes/discrete_martingales.pdf
Metody výuky -
Poslední úprava: Kříž Pavel Ing. Mgr. Ph.D. (03.10.2018)

Samostudium, konzultace
Požadavky ke kontrole studia -
Poslední úprava: Kříž Pavel Ing. Mgr. Ph.D. (03.10.2018)

Kontrola studia se provádí během pravidelných konzultací v průběhu semestru.
Sylabus -
Poslední úprava: Kříž Pavel Ing. Mgr. Ph.D. (03.10.2018)

1. Základní pojmy teorie grafů.

2. Diskrétní náhodná procházka

3. Diskrétní markovské procesy – markovská vlastnost, matice přechodu, limitní rozdělení

4. Diskrétní martingaly – markovský čas, problém optimálního zastavení

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

6. Základní úlohy kombinatorické optimalizace (úloha nejkratší cesty, minimální kostra grafu, párování a pokrytí v bipartitních grafech, toky v sítích atp.)

7. Slova, problémy, algoritmy.

8. Výpočetní složitost.Třídy P, NP, co-NP. NP-úplné problémy. Redukce.

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

10. Hladový algoritmus.

Studijní prerekvizity -
Poslední úprava: Mareš Jan doc. Ing. Ph.D. (03.10.2018)

nejsou
Podmínky zakončení předmětu -
Poslední úprava: Kříž Pavel Ing. Mgr. Ph.D. (03.10.2018)

Ústní zkouška
 
VŠCHT Praha