Diskrétní matematika

Garant předmětu:

Petr Habala

Přednášející:

Petr Habala

Cvičící:

Petr Habala

Předmět zajišťuje:

katedra matematiky

Anotace:

V předmětu se studenti seznámí s částí významných témat zahrnovaných tradičně do oboru diskrétní matematika, zejména jde o dělitelnost a počítání modulo, diofantické rovnice, binární relace, zobrazení, mohutnost množin, indukci a rekurentní rovnice. Druhým cílem kpředmětu je naučit studenty jazyk matematiky, pasivně i aktivně, a představit jim matematiku jako vědu.

Požadavky:

Středoškolská matematika a schopnost myslet.

Osnova přednášek:

1. Dělitelnost, Eukleidův algoritmus.

2. Počítání modulo, prostory Zn zbytkových tříd.

3. Diofantické rovnice, kongruenční rovnice a soustavy.

4. Binární relace a jejich základní vlastnosti.

5. Speciální relace: částečné uspořádání a ekvivalence.

6. Zobrazení. Mohutnost množin, spočetné a nespočetné množiny.

7. Matematická indukce a její využití.

8. Posloupnosti a součty, asymptotický růst.

9. Lineární rekurentní (rekursivní) rovnice.

10. Výpočet časové náročnosti rekursivních algoritmů, Master theorem.

11. Princip inkluze a exkluze.

Osnova cvičení:

1. Dělitelnost, Eukleidův algoritmus.

2. Počítání modulo, prostory Zn zbytkových tříd.

3. Diofantické rovnice, kongruenční rovnice a soustavy.

4. Binární relace a jejich základní vlastnosti.

5. Speciální relace: částečné uspořádání a ekvivalence.

6. Zobrazení. Mohutnost množin, spočetné a nespočetné množiny.

7. Matematická indukce a její využití.

8. Posloupnosti a součty, asymptotický růst.

9. Lineární rekurentní (rekursivní) rovnice.

11. Výpočet časové náročnosti rekursivních algoritmů, Master theorem.

12. Princip inkluze a exkluze.

Cíle studia:

Studijní materiály:

[1] P. Habala: Diskétní matematika, on-line.

Poznámka:

Další informace:

https://math.fel.cvut.cz/cz/lide/habala/teaching/dma.html

Rozvrh na zimní semestr 2023/2024:

	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 T2:C3-51 Habala P. 09:15–10:45 (přednášková par. 1 paralelka 104) Dejvice T2:C3-51místnost T2:C3-51 Habala P. 14:30–16:00 (přednášková par. 1 paralelka 101) Dejvice T2:C3-51místnost T2:C3-51 Habala P. 16:15–17:45 (přednášková par. 1 paralelka 102) Dejvice T2:C3-51 místnost T2:C3-51 Habala P. 09:15–10:45 (přednášková par. 1 paralelka 107) Dejvice T2:C3-51místnost T2:C3-51 Habala P. 11:00–12:30 (přednášková par. 1 paralelka 103) Dejvice T2:C3-51místnost T2:C3-51 Habala P. 14:30–16:00 (přednášková par. 1 paralelka 105) Dejvice T2:C3-51místnost T2:C3-51 Habala P. 16:15–17:45 (přednášková par. 1 paralelka 108) Dejvice T2:C3-51 místnost T2:C3-51 Habala P. 11:00–12:30 (přednášková par. 1 paralelka 106) Dejvice T2:C3-51místnost T2:C2-82 Habala P. 12:45–14:15 (přednášková par. 1 paralelka 109) Dejvice T2:C2-82 místnost T2:C2-82 Habala P. 12:45–14:15 (přednášková par. 1 paralelka 110) Dejvice T2:C2-82
Út	místnost KN:E-107 Habala P. 11:00–12:30 (přednášková par. 1) Karlovo nám. Zengerova posluchárna K1místnost 12:45–14:15 (přednášková par. 1 paralelka 111) místnost KN:E-128 16:15–17:45 (přednášková par. 1 paralelka 112) Karlovo nám. Cvičebna K3 místnost T2:D3-309 Habala P. 11:00–12:30 (přednášková par. 1) Dejvice T2:D3-309
St
Čt
Pá

Rozvrh na letní semestr 2023/2024:

Rozvrh není připraven

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

• Otevřená informatika - Informatika a počítačové vědy 2016 (povinný předmět programu)
• Otevřená informatika - Internet věcí 2016 (povinný předmět programu)
• Otevřená informatika - Software 2016 (povinný předmět programu)
• Otevřená informatika - Počítačové hry a grafika 2016 (povinný předmět programu)
• Otevřená informatika - před rozřazením do oborů (povinný předmět programu)
• Otevřená informatika - před rozřazením do specializací (povinný předmět programu)
• Otevřená informatika - Základy umělé inteligence a počítačových věd 2018 (povinný předmět programu)
• Otevřená informatika - Internet věcí 2018 (povinný předmět programu)
• Otevřená informatika - Software 2018 (povinný předmět programu)
• Otevřená informatika - Počítačové hry a grafika 2018 (povinný předmět programu)