Moodle FEL ČVUT
Základy diskrétní matematiky
B242 - Letní 24/25
Základy diskrétní matematiky - B6B01ZDM
| Kredity | 5 |
| Semestry | zimní |
| Zakončení | Zápočet a zkouška |
| Jazyk výuky | čeština |
| Rozsah výuky | 2P+2S+2D |
Anotace
Začátek je věnován tématům, která nepotřebují pokročilé znalosti a složité matematické pojmy. Na tématech z kombinatoriky a teorie grafů se vybuduje dostatečná zásoba ilustrativních příkladů, které usnadní přechod k více abstraktním pojmům jako relace a mohutnost množin. S touto průpravou pak bude možné přistoupit ke stručné formální výstavbě predikátového počtu.
Cíle studia
Cílem je rozvinout schopnosti logické argumentace a rozboru logické struktury výroků. Rovněž se studenti seznámí se základy kombinatoriky a teorie grafů a se základními metodami formalizace predikátové logiky.
Osnovy přednášek
1. Základní kombinatorické vztahy. Binomická věta a Pascalův trojúhelník.
2. Typy výběrů, princip inkluze a exkluze, aplikace.
3. Základy teorie množin. Mohutnost, spočetné množiny a jejich vlastnosti.
4. Nespočetné množiny, Cantorova věta.
5. Binární relace na množině, ekvivalence.
6. Relace uspořádání, minimální a maximální prvky.
7. Základní pojmy teorie grafů. Souvislé grafy.
8. Eulerovské grafy a jejich charakterizace.
9. Stromy, základní vlastnosti.
10. Ohodnocení grafu, algoritmus pro minimální kostru grafu.
11. Bipartitní graf, párování v bipartitních grafech.
12. Abeceda a formule výrokové logiky, pravdivostní ohodnocení.
13. Jazyk a formule predikátové logiky, logická struktura a formalizace výroků.
14. Rezerva.
2. Typy výběrů, princip inkluze a exkluze, aplikace.
3. Základy teorie množin. Mohutnost, spočetné množiny a jejich vlastnosti.
4. Nespočetné množiny, Cantorova věta.
5. Binární relace na množině, ekvivalence.
6. Relace uspořádání, minimální a maximální prvky.
7. Základní pojmy teorie grafů. Souvislé grafy.
8. Eulerovské grafy a jejich charakterizace.
9. Stromy, základní vlastnosti.
10. Ohodnocení grafu, algoritmus pro minimální kostru grafu.
11. Bipartitní graf, párování v bipartitních grafech.
12. Abeceda a formule výrokové logiky, pravdivostní ohodnocení.
13. Jazyk a formule predikátové logiky, logická struktura a formalizace výroků.
14. Rezerva.
Osnovy cvičení
1. Základní kombinatorické vztahy. Binomická věta a Pascalův trojúhelník.
2. Typy výběrů, princip inkluze a exkluze, aplikace.
3. Základy teorie množin. Mohutnost, spočetné množiny a jejich vlastnosti.
4. Nespočetné množiny, Cantorova věta.
5. Binární relace na množině, ekvivalence.
6. Relace uspořádání, minimální a maximální prvky.
7. Základní pojmy teorie grafů. Souvislé grafy.
8. Eulerovské grafy a jejich charakterizace.
9. Stromy, základní vlastnosti.
10. Ohodnocení grafu, algoritmus pro minimální kostru grafu.
11. Bipartitní graf, párování v bipartitních grafech.
12. Abeceda a formule výrokové logiky, pravdivostní ohodnocení.
13. Jazyk a formule predikátové logiky, logická struktura a formalizace výroků.
14. Rezerva.
2. Typy výběrů, princip inkluze a exkluze, aplikace.
3. Základy teorie množin. Mohutnost, spočetné množiny a jejich vlastnosti.
4. Nespočetné množiny, Cantorova věta.
5. Binární relace na množině, ekvivalence.
6. Relace uspořádání, minimální a maximální prvky.
7. Základní pojmy teorie grafů. Souvislé grafy.
8. Eulerovské grafy a jejich charakterizace.
9. Stromy, základní vlastnosti.
10. Ohodnocení grafu, algoritmus pro minimální kostru grafu.
11. Bipartitní graf, párování v bipartitních grafech.
12. Abeceda a formule výrokové logiky, pravdivostní ohodnocení.
13. Jazyk a formule predikátové logiky, logická struktura a formalizace výroků.
14. Rezerva.
Literatura
1. Demlová, Pondělíček: Matematická logika, skripta ČVUT.
2. J. Demel: Grafy a jejich aplikace, Academia 2002.
3. K.H. Rosen: Discrete mathematics and its applications, 7th edition, McGraw-Hill, 2012.
https://math.fel.cvut.cz/en/people/tiser/vyuka.html
2. J. Demel: Grafy a jejich aplikace, Academia 2002.
3. K.H. Rosen: Discrete mathematics and its applications, 7th edition, McGraw-Hill, 2012.
https://math.fel.cvut.cz/en/people/tiser/vyuka.html
Požadavky
Předpokládané znalosti jsou standardní znalosti získané ukončeným středním vzděláním.