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
BI-ZDM | Základy diskrétní matematiky | Rozsah kontaktní výuky: | 2P+2C | ||
---|---|---|---|---|---|
Vyučující: | Legerský J., Scholtzová J. | 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. | |
2. | Potenční množina množiny přirozených čísel - nespočetná množina. | |
3. | Základy kombinatoriky. Princip inkluze a exkluze - využití pro výpočet mohutností. | |
4. | "Pigeon-hole principle", počet struktur, tj. počet zobrazení, relací, stromů (vše na konečných strukturách). | |
5. | Odhady funkcí (např. faktoriálu, binomických koeficientů). | |
6. | Relace a relace ekvivalence (např. ekvivalence souvislé/silně souvislé komponenty). | |
7. | Matice relací, relační databáze. | |
8. | Matematická indukce jako nástroj pro zjištění počtu konečných objektů. | |
9. | Matematická indukce jako nástroj pro důkaz správnosti algoritmů. | |
10. | Matematická indukce jako nástroj pro řešení úloh rekurzí. | |
11. | Strukturální indukce. | |
12. | Výpočet časové náročností rekursivních algoritmů - řešení rekurentních rovnic s konstantními koeficienty - homogenní rovnice. | |
13. | Řešení nehomogenních rekurentních rovnic s konstantními koeficienty. |
Osnovy cvičení:
1. | Výpočty mohutností množin. | |
2. | Spočetnost a nespočetnost. | |
3. | Princip inkluze a exkluze. | |
4. | Počty struktur na konečných množinách. | |
5. | Asymptotické chování funkcí. | |
6. | Relace a orientované grafy. | |
7. | Základní důkazy indukcí. | |
8. | Aplikace důkazů indukcí v kombinatorice. | |
9. | Aplikace důkazů indukcí v programování. | |
10. | Indukce a rekursivní algoritmy. | |
11. | Využití indukce v teorii formálních jazyků. | |
12. | Výpočty časové složitosti. | |
13. | Řešení lineárních rekurentních rovnic. |
Literatura:
1. | Nešetřil, J., Matoušek, J. Kapitoly z diskrétní matematiky. Praha: Karolinum, 2007. ISBN 978-80-246-1411-3. |
Požadavky:
Předpokládá se zvládnutí základních pojmů matematiky a matematické logiky v rozsahu daném obsahem předmětů BI-ZMA, BI-MLO a BI-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 |