Základy diskrétní matematiky

Vztahy:

Předmět BI-ZDM nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět BI-DML.21 (vztah je symetrický)

Předmět BI-ZDM nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět BI-DML.21 (vztah je symetrický)

Předmět je ekvivalentní s BIE-ZDM,BIK-ZDM .

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra aplikované matematiky

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ů.

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.

Osnova 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.

Osnova 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.

Cíle studia:

Cílem předmětu je naučit studenty postupům kombinatoriky, asymptotické matematiky a matematické indukce jako základního nástroje pro dokazování správnosti či odvozování složitosti algoritmů.

Studijní materiály:

1. Nešetřil, J., Matoušek, J. Kapitoly z diskrétní matematiky. Praha: Karolinum, 2007. ISBN 978-80-246-1411-3.

Poznámka:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/BI-ZDM/

Další informace:

https://courses.fit.cvut.cz/BI-ZDM/

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Bc. program Informatika, pro fázi studia bez oboru, 2015-2020 (povinný předmět programu)
• Bc. obor Bezpečnost a informační technologie, 2015-2020 (povinný předmět programu)
• Bc. obor Teoretická informatika, 2015-2020 (povinný předmět programu)
• Bc. obor Počítačové inženýrství, 2015-2020 (povinný předmět programu)
• Bc. obor Informační systémy a management, 2015-2020 (povinný předmět programu)
• Bc. obor Webové a softwarové inženýrství, zaměření Softwarové inženýrství, 2015-2020 (povinný předmět programu)
• Bc. obor Webové a softwarové inženýrství, zaměření Webové inženýrství, 2015-2020 (povinný předmět programu)
• Bc. obor Webové a softwarové inženýrství, zaměření Počítačová grafika, 2015-2020 (povinný předmět programu)
• Bc. obor Znalostní inženýrství, 2018-2020 (povinný předmět programu)