Předmět je základní jednotka výuky, jejímž prostřednictvím si student osvojí ucelenou část souboru znalostí a dovedností, potřebnou pro zvládnutí studijního oboru/specializace. Za věcný obsah předmětu zodpovídá garant předmětu. Časovou náročnost předmětu zhruba vyjadřuje atribut předmětu rozsah kontaktní výuky. Například rozsah = 2+2 značí, že předmět bude mít týdně dvě hodiny přednášek a dvě hodiny cvičení týdně. Na závěr semestru musí vyučující provést vyhodnocení, nakolik si ten který student osvojil poznatky a dovednosti, kterých měl během výuky nabýt. Jakým způsobem toto hodnocení vyučující provedou určuje atribut způsob zakončení. U předmětu lze definovat, že předmět je zakončen pouze zápočtem(Z), klasifikovaným zápočtem(KZ), pouze zkouškou(ZK), nebo zápočtem a zkouškou(Z,ZK). Náročnost úspěšného absolvování předmětu je vyjádřena ECTS kreditními body. Výuka předmětu probíhá během semestru. Opakovaně se předmět vyučuje vždy v zimním(Z), nebo v letním(L) semestru každého akademického roku. Výjimečně může předmět být nabízen studentům v obou semestrech(Z,L). Za organizační zajištění výuky zodpovídá přiřazená katedra, která zejména vytvoří časový rozvrh předmětu a zajistí pro předmět vyučující. Někteří přednáší a zkouší, jiní vedou cvičení a udělují zápočty.
Obsahová náplň a další organizační informace, týkající se předmětu je popsána pomocí různých popisných textů(anotace, týdenní osnova, literatura, apod.)
$DODATEK_POPIS
BIK-ZDM | Základy diskrétní matematiky | Rozsah kontaktní výuky: | 13KP+4KC | ||
---|---|---|---|---|---|
Vyučující: | Pernecká E. | Způsob zakončení: | Z,ZK | ||
Zodpovědná katedra: | 18105 | ECTS Kredity: | 5 | Semestr: | Z |
Anotace:
Studenti získají jak solidní matematický základ, tak současně i praktickou početní zběhlost v oblasti kombinatoriky, odhadu hodnot a aproximace funkcí, postupů pro řešení rekurentních rovnic a základů teorie grafů.
Osnovy přednášek:
1. | Množiny a jejich mohutnost, spočetné množiny, potenční množina konečné množiny a její mohutnost. Potenční množina množiny přirozených čísel - nespočetná množina. | |
2. | Základy kombinatoriky. Princip inkluze a exkluze - využití pro výpočet mohutností. "Pigeon-hole principle", počet struktur, tj. počet zobrazení, relací, stromů (vše na konečných strukturách). | |
3. | Odhady funkcí (např. faktoriálu, binomických koeficientů). Relace a relace ekvivalence (např. ekvivalence souvislé/silně souvislé komponenty). | |
4. | Matice relací, relační databáze. Matematická indukce jako nástroj pro zjištění počtu konečných objektů. | |
5. | Matematická indukce jako nástroj pro důkaz správnosti algoritmů. Matematická indukce jako nástroj pro řešení úloh rekurzí. | |
6. | Strukturální indukce. Výpočet časové náročností rekursivních algoritmů - řešení rekurentních rovnic s konstantními koeficienty - homogenní rovnice. | |
7. | Řešení nehomogenních rekurentních rovnic s konstantními koeficienty. |
Osnovy cvičení:
1. | Výpočty mohutností množin. Spočetnost a nespočetnost. Princip inkluze a exkluze. Počty struktur na konečných množinách. Asymptotické chování funkcí. | |
2. | Relace a orientované grafy. Základní důkazy indukcí. Aplikace důkazů indukcí v kombinatorice. Aplikace důkazů indukcí v programování. Indukce a rekursivní algoritmy. | |
3. | Využití indukce v teorii formálních jazyků. Výpočty časové složitosti. Řešení lineárních rekurentních rovnic. Rezerva. |
Literatura:
Nešetřil, J., Matoušek, J. "Kapitoly z diskrétní matematiky". Praha: Karolinum, 2007. ISBN 978-80-246-1411-3.
Johnsonbaugh, R. "Discrete Mathematics (4th Edition)". Prentice Hall, 1998. ISBN 0130805505.
Rosen, K. H. "Discrete Mathematics and its Applications". McGraw-Hill, 1998. ISBN 0072899050.
Cormen, T. H., Leiserson, C. E., Rivest, R. L. "Introduction to Algorithms". The MIT Press, 2001. ISBN 0262032937.
Požadavky:
Předpokládá se zvládnutí základních pojmů matematiky a matematické logiky v rozsahu daném obsahem předmětů BIK-ZMA, BIK-MLO a BIK-LIN.
|
Předmět je zahrnut do těchto studijních plánů:
Stránka vytvořena 24. 4. 2024, semestry: L/2020-1, L/2019-20, L/2023-4, Z,L/2022-3, L/2021-2, Z/2019-20, Z/2024-5, Z/2023-4, Z/2020-1, Z/2021-2, připomínky k informační náplni zasílejte správci studijních plánů | Návrh a realizace: J. Novák, I. Halaška |