Předmět Discrete Structures (KMI / DSA)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu KMI / DSA - Discrete Structures, Ekonomická fakulta, Jihočeská univerzita v Českých Budějovicích (JU).

Materiál	Typ	Datum	Počet stažení

Obsah

Tematické celky:1. Základní diskrétní struktury (relační struktury, grafy, stromy, ohodnocené grafy, hypergrafy) a jejich možné algebraické reprezentace.2. Shrnutí potřebných pojmů z teorie množin a teorie grafů.3. Datové struktury a možnosti jejich implementace v prostředí software MAPLE.4. Časová a paměťová náročnost výpočtu.5. Vyhledávací a třídící algoritmy.6. Polynomiální algoritmy 1 (cesty, kostry, toky v sítích).7. Polynomiální algoritmy 2 (párování, rovinnost a vlastnosti rovinných grafů).8. NP-úplné problémy 1 (barvení grafu, hledání nezávislé množiny).9. NP-úplné problémy 2 (pokrývání množin, problém obchodního cestujícího)10. Heuristické metody 1 (barvení, hamiltonovská cesta a kružnice).11. Heuristické metody 2 (problém obchodního cestujícího, izomorfismus grafů).12. Pravděpodobnostní testování algoritmů.13. Shrnutí: typologie algoritmů na diskrétních strukturách z pohledu výpočetní složitosti.

Získané způsobilosti

Schopnost algoritmizace pro vybranou třídu úloh z praxe. Využití výpočetní techniky pro řešení úloh s diskrétní strukturou. Student je schopen komunikovat v anglickém jazyce.

Literatura

KUČERA, L. Kombinatorické algoritmy. Praha, 1983. MONAGAN, M. B. et al. Maple V Programing Guide. New York, 1996. KREHER, L. D. Combinatorial Algorithms. New York, 1999. GAREZ, M. R. a D. S. JOHNSON. Computers and Intractibility. New York, 1979.

Požadavky

Vypracování všech 10 krátkodobých úkolů (z týdne na týden). Vypracování a prezentace závěrečného projektu, zpracovaného pomocí programování v pseudokódu software MAPLE.

Garant

doc. RNDr. Václav Nýdl, CSc.

Vyučující

doc. RNDr. Václav Nýdl, CSc.