Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2020/2021

Základy diskrétní matematiky

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
BI-ZDM Z,ZK 5 2P+2C česky
Přednášející:
Daniel Dombek, Josef Kolář (gar.), Jiřina Scholtzová
Cvičící:
Daniel Dombek, Josef Kolář (gar.), Luděk Kleprlík, Pavel Kůs, Jan Legerský, Petr Matyáš, Eva Pernecká, Jiřina Scholtzová, Jan Spěvák
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/
Rozvrh na zimní semestr 2020/2021:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
místnost T9:155
Dombek D.
14:30–16:00
(přednášková par. 1)
Dejvice
Posluchárna
místnost T9:155
Scholtzová J.
16:15–17:45
(přednášková par. 2)
Dejvice
Posluchárna
Út
místnost T9:346
Kleprlík L.
09:15–10:45
(paralelka 1)
Dejvice
NBFIT učebna
místnost T9:346
Kleprlík L.
11:00–12:30
(paralelka 3)
Dejvice
NBFIT učebna
místnost T9:346
Kleprlík L.
12:45–14:15
(paralelka 5)
Dejvice
NBFIT učebna
místnost TH:A-1242
Matyáš P.
16:15–17:45
(paralelka 6)
Thákurova 7 (FSv-budova A)
místnost TH:A-1242
Matyáš P.
18:00–19:30
(paralelka 7)
Thákurova 7 (FSv-budova A)
místnost T9:343
Kůs P.
09:15–10:45
(paralelka 2)
Dejvice
NBFIT učebna
místnost T9:343
Kůs P.
11:00–12:30
(paralelka 4)
Dejvice
NBFIT učebna
St
místnost TH:A-1442
Dombek D.
09:15–10:45
(paralelka 8)
Thákurova 7 (FSv-budova A)
místnost TH:A-1442
Dombek D.
14:30–16:00
(paralelka 12)
Thákurova 7 (FSv-budova A)
místnost TH:A-1442
Dombek D.
16:15–17:45
(paralelka 13)
Thákurova 7 (FSv-budova A)
místnost TH:A-1442
Dombek D.
11:00–12:30
(paralelka 9)
Thákurova 7 (FSv-budova A)
místnost TH:A-1442
Dombek D.
12:45–14:15
(paralelka 11)
Thákurova 7 (FSv-budova A)
Čt
místnost TH:A-1442
Spěvák J.
09:15–10:45
(paralelka 14)
Thákurova 7 (FSv-budova A)
místnost TH:A-1442
Spěvák J.
11:00–12:30
(paralelka 15)
Thákurova 7 (FSv-budova A)
místnost TH:A-1442
Spěvák J.
12:45–14:15
(paralelka 16)
Thákurova 7 (FSv-budova A)
místnost TH:A-1442
Spěvák J.
14:30–16:00
(paralelka 17)
Thákurova 7 (FSv-budova A)
místnost TH:A-1442
Matyáš P.
18:00–19:30
(paralelka 19)
Thákurova 7 (FSv-budova A)
místnost TH:A-1442
Matyáš P.
16:15–17:45
(paralelka 18)
Thákurova 7 (FSv-budova A)

místnost TH:A-1247
Scholtzová J.
07:30–09:00
(paralelka 20)
Thákurova 7 (FSv-budova A)
seminární místnost
místnost TH:A-1247
Scholtzová J.
09:15–10:45
(paralelka 21)
Thákurova 7 (FSv-budova A)
seminární místnost
místnost TH:A-1247
Scholtzová J.
11:00–12:30
(paralelka 23)
Thákurova 7 (FSv-budova A)
seminární místnost
Rozvrh na letní semestr 2020/2021:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 3. 12. 2020
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet1124106.html