ČeskyEnglish

Popis předmětu - B6B01ZDM

Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
B6B01ZDM Základy diskrétní matematiky Rozsah výuky:2+2+2
Garanti:Tišer J. Role:P Zakončení:Z,ZK
Vyučující:Tišer J.
Zodpovědná katedra:13101 Kreditů:5 Semestr:Z

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 k formální výstavbě výrokového a 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 výrokové a predikátové logiky.

Osnovy přednášek:

1. Základní kombinatorické vztahy. Typy výběrů, binomická věta.
2. Princip inkluze a exkluze, aplikace.
3. Základní pojmy teorie grafů. Souvislé grafy.
4. Eulerovské grafy, stromy a jejich vlastnosti.
5. Ohodnocení grafu, algoritmus pro minimální kostru grafu.
6. Bipartitní graf, párování v bipartitních grafech.
7. Binární relace na množině, ekvivalence.
8. Relace uspořádání, minimální a maximální prvky.
9. Základy teorie množin. Mohutnost, spočetné množiny a jejich vlastnosti.
10. Nespočetné množiny, Cantorova věta.
11. Abeceda a formule výrokové logiky, pravdivostní ohodnocení.
12. Sémantický důsledek, booleovské funkce.
13. Disjunktivní a konjunktivní normální formy, splnitelné množiny formulí a rezoluční metoda.
14. Jazyk a formule predikátové logiky, logická struktura a formalizace výroků.

Osnovy cvičení:

1. Základní kombinatorické vztahy. Typy výběrů, binomická věta.
2. Princip inkluze a exkluze, aplikace.
3. Základní pojmy teorie grafů. Souvislé grafy.
4. Eulerovské grafy, stromy a jejich vlastnosti.
5. Ohodnocení grafu, algoritmus pro minimální kostru grafu.
6. Bipartitní graf, párování v bipartitních grafech.
7. Binární relace na množině, ekvivalence.
8. Relace uspořádání, minimální a maximální prvky.
9. Základy teorie množin. Mohutnost, spočetné množiny a jejich vlastnosti.
10. Nespočetné množiny, Cantorova věta.
11. Abeceda a formule výrokové logiky, pravdivostní ohodnocení.
12. Sémantický důsledek, booleovské funkce.
13. Disjunktivní a konjunktivní normální formy, splnitelné množiny formulí a rezoluční metoda.
14. Jazyk a formule predikátové logiky, logická struktura a formalizace výroků.

Literatura:

Povinná literatura:
1. Demlová, Pondělíček: Matematická logika, skripta ČVUT.
Doporučená literatura:
2. J. Demel: Grafy a jejich aplikace, Academia 2002.
3. K.H. Rosen: Discrete mathematics and its applications, 7th edition, McGraw-Hill, 2012.

Požadavky:

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

Webová stránka:

http://math.feld.cvut.cz/bohata/zdm.html

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr
BPSIT Před zařazením do oboru P 1


Stránka vytvořena 24.3.2017 18:00:25, semestry: Z,L/2016-7, Z,L/2017-8, Z/2018-9, připomínky k informační náplni zasílejte správci studijních plánů Návrh a realizace: I. Halaška (K336), J. Novák (K336)
Za obsah odpovídá: doc. Ing. Ivan Jelínek, CSc.