Základy diskrétní matematiky

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra matematiky

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.

Požadavky:

Předpokládané znalosti jsou standardní znalosti získané ukončeným středním vzděláním.

Osnova 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.

Osnova 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.

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.

Studijní materiály:

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

Poznámka:

Další informace:

https://math.fel.cvut.cz/en/people/tiser/vyuka.html

Pro tento předmět se rozvrh nepřipravuje

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

• Softwarové inženýrství a technologie (povinný předmět programu)
• Softwarové inženýrství a technologie - specializace Enterprise systémy (povinný předmět programu)
• Softwarové inženýrství a technologie - specializace Technologie pro multimédia a virtuální realitu (povinný předmět programu)
• Softwarové inženýrství a technologie - specializace Business informatics (povinný předmět programu)
• Softwarové inženýrství a technologie - specializace Technologie internetu věcí (povinný předmět programu)
• Softwarové inženýrství a technologie - společný 1. ročník (povinný předmět programu)