Moodle FEL ČVUT
Diskrétní matematika
B241 - Zimní 24/25
Diskrétní matematika - B4B01DMA
| Kredity | 5 |
| Semestry | zimní |
| Zakončení | zápočet a zkouška |
| Jazyk výuky | čeština |
| Rozsah výuky | 2P+2S |
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.
Cíle studia
None
Osnovy 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.
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.
Osnovy 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.
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.
Literatura
[1] P. Habala: Diskétní matematika, on-line.
Požadavky
Středoškolská matematika a schopnost myslet.