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	2+2	česky

Přednášející:

Karel Klouda, Josef Kolář (gar.)

Cvičící:

Karel Klouda, Josef Kolář (gar.), Peter Franek, Petr Matyáš, Štěpán Starosta

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:

Rozsah=prednasky+proseminare+cviceni:2p+2c

Rozvrh na zimní semestr 2011/2012:

	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 TK:BS Kolář J. 09:15–10:45 (přednášková par. 1) Dejvice NTK Ballingův sálmístnost T9:301 Starosta Š. 14:30–16:00 (přednášková par. 1 paralelka 103) Dejvice NBFIT učebnamístnost T9:301 Starosta Š. 16:15–17:45 (přednášková par. 1 paralelka 104) Dejvice NBFIT učebnamístnost T9:301 18:00–19:30 (přednášková par. 1 paralelka 110) Dejvice NBFIT učebna místnost TK:BS Klouda K. 14:30–16:00 (přednášková par. 2) Dejvice NTK Ballingův sál
Út	místnost T9:344 07:30–09:00 (přednášková par. 1 paralelka 101) Dejvice NBFIT ucebnamístnost T9:344 Matyáš P. 09:15–10:45 (přednášková par. 1 paralelka 102) Dejvice NBFIT ucebnamístnost T9:344 Matyáš P. 11:00–12:30 (přednášková par. 2 paralelka 211) Dejvice NBFIT ucebnamístnost T9:344 Matyáš P. 16:15–17:45 (přednášková par. 2 paralelka 206) Dejvice NBFIT ucebnamístnost T9:344 Matyáš P. 18:00–19:30 (přednášková par. 2 paralelka 207) Dejvice NBFIT ucebna
St	místnost T9:344 Franek P. 11:00–12:30 (přednášková par. 2 paralelka 203) Dejvice NBFIT ucebnamístnost T9:344 Franek P. 12:45–14:15 (přednášková par. 1 paralelka 105) Dejvice NBFIT ucebnamístnost T9:344 Franek P. 14:30–16:00 (přednášková par. 2 paralelka 205) Dejvice NBFIT ucebna
Čt	místnost T9:344 07:30–09:00 (přednášková par. 2 paralelka 201) Dejvice NBFIT ucebnamístnost T9:344 Starosta Š. 09:15–10:45 (přednášková par. 2 paralelka 202) Dejvice NBFIT ucebnamístnost T9:344 Starosta Š. 11:00–12:30 (přednášková par. 2 paralelka 204) Dejvice NBFIT ucebnamístnost T9:344 Starosta Š. 12:45–14:15 (přednášková par. 1 paralelka 106) Dejvice NBFIT ucebnamístnost T9:344 Klouda K. 14:30–16:00 (přednášková par. 1 paralelka 107) Dejvice NBFIT ucebnamístnost T9:344 Franek P. 16:15–17:45 (přednášková par. 1 paralelka 108) Dejvice NBFIT ucebnamístnost T9:344 Franek P. 18:00–19:30 (přednášková par. 1 paralelka 109) Dejvice NBFIT ucebna
Pá	místnost T9:344 07:30–09:00 (přednášková par. 2 paralelka 208) Dejvice NBFIT ucebnamístnost T9:344 Klouda K. 09:15–10:45 (přednášková par. 2 paralelka 209) Dejvice NBFIT ucebnamístnost T9:344 Klouda K. 11:00–12:30 (přednášková par. 2 paralelka 210) Dejvice NBFIT ucebna

Rozvrh na letní semestr 2011/2012:

Rozvrh není připraven

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

Teoretická informatika - verze pro ty, kteří se zapsali v roce 2009 a 2010 (povinný předmět programu)
Počítačové inženýrství - verze pro ty, kteří se zapsali v roce 2009 a 2010 (povinný předmět programu)
Softwarové inženýrství - verze pro ty, kteří se zapsali v roce 2009 a 2010 (povinný předmět programu)
Web a multimedia - verze pro ty, kteří se zapsali v roce 2009 a 2010 (povinný předmět programu)
Informační systémy a management - verze pro ty, kteří se zapsali v roce 2009 a 2010 (povinný předmět programu)
Informační technologie - verze pro ty, kteří se zapsali v roce 2009 a 2010 (povinný předmět programu)
Informatika, plán pro fázi studia bez oboru - verze pro ty, kteří se zapsali v roce 2009 a 2010 (povinný předmět programu)
Informatika, plán pro fázi studia bez oboru - verze pro ty, kteří se zapsali v roce 2011 a 2012 (povinný předmět programu)
Informační systémy a management - verze pro ty, kteří se zapsali v roce 2011 a 2012 (povinný předmět programu)
Informační technologie - verze pro ty, kteří se zapsali v roce 2011 a 2012 (povinný předmět programu)
Počítačové inženýrství - verze pro ty, kteří se zapsali v roce 2011 a 2012 (povinný předmět programu)
Softwarové inženýrství - verze pro ty, kteří se zapsali v roce 2011 a 2012 (povinný předmět programu)
Teoretická informatika - verze pro ty, kteří se zapsali v roce 2011 a 2012 (povinný předmět programu)
Web a multimedia - verze pro ty, kteří se zapsali v roce 2011 a 2012 (povinný předmět programu)