Detail předmětu

Diskrétní matematika

FP-DMAk. rok: 2020/2021

Základní teoretické prostředky aplikované informatiky - matematická logika, relace, teorie grafů a teorie formálních jazyků a automatů.

Jazyk výuky

čeština

Počet kreditů

5

Zajišťuje ústav

Výsledky učení předmětu

Získané vědomosti budou využity při řešení problémů spojených s využitím informatiky při manažérském rozhodování.

Prerekvizity

Středoškolská matematika a informatika.

Plánované vzdělávací činnosti a výukové metody

Jednohodinová přednáška a dvouhodinové cvičení. Přednáška kombinující teorii a ilustrativní řešené příklady. Cvičení jsou zaměřená na zvládnutí početních úloh.

Způsob a kritéria hodnocení

Požadavky pro udělení zápočtu:
- aktivní účast ve cvičeních, účast ve cvičeních je povinná
- získání klasifikace alespoň "vyhovující" (55% bodů) ze dvou písemných semestrálních testů

Zkouška je písemná a trvá 1 hodinu. Může obsahovat tyto typy úloh :
1. Úloha na verbálně formulované výroky a operace s nimi
2. Úloha na aplikaci zákonů výrokové logiky
3. Úloha na Booleovu funkci (vyjádření výroku jako Booleovy funkce, tabulka
pravdivostních hodnot,realizace obvodem, úplný normální tvar apod.)
4. Úloha na relace
5. Úloha na základní vlastnosti a klasifikaci grafů
6. Definice pojmů nebo formulace vlastností z teorie grafů nebo matematické logiky
7. Úloha na nalezení jazyka gramatiky

Celkové hodnocení:
Písemná část je hodnocena bodově součtem bodů z jednotlivých úloh. Nedosáhne-li student alespoň 50 z celkového počtu 100 dosažitelných bodů, je celá zkouška hodnocena stupněm "F" (nevyhovující).

Osnovy výuky

Lineární algebra - matice, determinanty, soustavy lineárních rovnic
Matematická logika - konstanty, proměnné, výroky, operace s výroky, zákony výrokové logiky, Booleovy algebry a funkce, reprezentace Booleových funkcí, aplikace při konstrukci logických obvodů.
Relace - relace na množině, vlastnosti relací, tolerance, ekvivalence, uspořádání.
Grafy - základní druhy grafů, základní poznatky o neorientovaných grafech, orientované grafy, ohodnocené grafy, Dijkstrův algoritmus nejkratší cesty, Kruskalův algoritmus.
Jazyky, gramatiky, automaty - pojem jazyka a gramatiky, Chomského hierarchie, konečný automat, Kleeneho charakterizace

Učební cíle

Cílem předmětu je seznámit se se základními pojmy a vztahy matematické logiky, relací, teorie grafů a principy teorie jazyků a automatů, s možnostmi jejich aplikací v oboru.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

Prezence ve cvičení je povinná a je systematicky kontrolována. Pokud v účasti ve výuce brání studentovi závažné překážky, lze požádat učitele o omluvu. Je plně v kompetenci učitele posoudit důvod neúčasti a rozhodnout o omluvě. Formy nahrazení zameškané výuky stanoví učitel individuálně.

Základní literatura

1) Mezník, I: Diskrétní matematika. FP VUT v Brně v Akademickém nakladatelství CERM, s.r.o. Brno, Brno 2004. ISBN 80-214-2754-X. (CS)

Doporučená literatura

Wiitala, S. A: Discrete Mathematics. McGraw-Hill, New York 1987 (EN)
Šlapal, J.: Metody diskrétní matematiky. FSI VUT v Brně, Brno 2001 (CS)

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

Osnova

Tematicý obsah přednášek:
-matematická logika,
-grafy,
-jazyky a automaty.

Cvičení

13 hod., povinná

Vyučující / Lektor

Osnova

-procvičování přednášených témat,
-samostatné zpracování souvisejících úkolů.