Předmět Základy diskrétní matematiky (KAG / SZZDM)
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 KAG / SZZDM - Základy diskrétní matematiky, Přírodovědecká fakulta, Univerzita Palackého v Olomouci (UP).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Obsah
1. Obecné kombinatorické principy.2. Variace, permutace, kombinace (s opakováním), polynomická věta.3. Princip inkluze a exkluze.4. Kombinatorické identity a jejich aplikace.5. Dirichletův princip a jeho aplikace.6. Kombinatorika rozkladů, rozklady přirozených čísel a množin. Ferrerův graf, Bellova čísla, Euler-Legendreova věta.7. Speciální vlastnosti permutací, grafy permutací, stupeň permutace, aplikace.8. Rekurentní vztahy v kombinatorice, řešení lineárních rekurentních vztahů.9. Vytvořující funkce.10. Úvod do kombinatorické geometrie. Polymina.11. Kombinatorika konvexních mnohoúhelníků, Cayleyho problém.12. Rekurentní metody v kombinatorické geometrii.13. Deterministické a nedeterministické automaty, jazyk rozpoznatelný automatem.14. Minimální automat regulárního jazyka.15. Syntaktický monoid jazyka.16. Uzávěrové vlastnosti regulárních jazyků, Kleeneova věta.17. Gramatiky (generativní), jazyk generovaný gramatikou. Chomského hierarchie.18. Regulární jazyky a regulární gramatiky. Lineární gramatiky.19. Bezkontextové gramatiky, redukovaná bezkontextová gramatika.20. Zásobníkové automaty a bezkontextové jazyky.21. Chomského normální forma bezkontextové gramatiky, Pumping Lemma.22. Uzávěrové vlastnosti bezkontextových jazyků.23. Homomorfismy grafů. Homomorfismy; hranové, resp. vrcholové monomorfismy a epimorfismy; isomorfismy; vnoření; části grafu a podgrafy.24. Stromy. Charakteristika stromů, kódování stromů, problém isomorfismu pro stromy.25. Kreslení grafů. Kreslení na rovinu, sféru, torus a jiné plochy; rovinné grafy a jejich charakteristika; pravidelné rovinné grafy.26. Souvislost grafů: Slabá a silná souvislost; acyklické grafy, kondenzace.27. Možnosti popisu grafu: Znaménkové matice, matice sousednosti, Laplaceovy matice, matice vzdáleností, matice incidence apod. Vlastnosti a využití těchto matic.
Získané způsobilosti
1. Znalosti: Porozumět základním pojmům předmětů zkoušky ve vzájemných souvislostech.
Literatura
litratura předmětů SZZ.
Požadavky
Orientace v problematice s důrazem na souvislosti.\\Složení ústní zkoušky.\\Studenti si musí zapsat předměty KAG/SZZA, KAG/SZZG, KAG/SZZMA, KAG/SZZDM současně a první termín SZZ z těchto předmětů konat ve stejný den.
Garant
prof. Mgr. Radomír Halaš, Dr.