Detail předmětu

Diskrétní matematika

FEKT-TDMAPovinnýBakalářský (první cyklus)Ak. rok: 2015/2016Letní semestr1 ročník6  kreditů

Množina, relace a zobrazení. Ekvivalence a rozklady. Uspořádání. Struktury s jednou a dvěma operacemi. Svazy a Boolovy algebry. Sémantika a syntaxe výrokového počtu. Normální tvary formulí. Základní pojmy teorie grafů. Souvislost grafů. Podgrafy a morfismy grafů. Problém rovinnosti. Stromy a jejich vlastnosti. Jednoduché grafové algoritmy.

Zajišťuje ústav

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

Studenti získají potřebné znalosti z diskrétní matematiky a schopnost orientace v souvisejících matematických strukturách.

Prerekvizity

Je požadováno zvládnutí učiva předmětu BMA1 Matematika 1. Absolvování předmětu BMAS Matematický seminář je doporučeno.

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

Metody vyučování závisejí na způsobu výuky a jsou popsány článkem 7 Studijního a zkušebního řádu VUT.

Způsob a kritéria hodnocení

Hodnocení studia je založeno na bodovacím systému. Pro úspěšné absolvování předmětu je nutno dosáhnout 50 bodů.

Jazyk výuky

čeština

Osnovy výuky

Formální jazyk matematiky. Intuitivní množinové pojmy. Základní množinové operace. Množinové mohutnosti. Číselné množiny. Kombinatorické vlastnosti množin. Princip inkluze a exkluze. Techniky důkazů a jejich ilustrace.
Binární relace a zobrazení. Skládání relací a zobrazení. Vlastnosti zobrazení. Indexované systémy množin a jejich zobrazení. Abstraktní prostory. Reálné funkce a jejich vlastnosti. Spojitost a nespojitost. Rekurzívně definované funkce.
Další vlastnosti binárních relací. Reflexivní, symetrický a transitivní uzávěr. Ekvivalence a rozklady. Uspořádání, zvláště svazové. Hasseovské diagramy.
Algebry s jednou a dvěma operacemi a jejich morfismy. Grupy a tělesa. Svaz jako množina se dvěma operacemi. Booleova algebra.
Hlavní vlastnosti a zákony Boolových algeber. Dualita a množinová reprezentace konečných Boolových algeber.
Formule a sémantika výrokového počtu. Interpretace a klasifikace formulí. Boolova algebra neekvivalentních formulí. Syntaxe výrokového počtu. Věta o kompaktnosti. Normální tvary formulí.
Grafy a jejich různé reprezentace. Sledy, tahy a cesty. Algoritmus nalezení nejkratší cesty. Souvislost grafů.
Podgrafy. Izomorfismus a homeomorfismus grafů. Eulerovské a hamiltonovské grafy. Problém rovinnosti.
Stromy, kostry a jejich vlastnosti. Binární stromy a jejich prohledávání. Tok v orientovaném grafu.

Cíl

Předmět poskytuje základní znalosti z matematiky potřebné pro řadu navazujících předmětů. Studenti se seznámí s elementárními poznatky z algebry a diskrétní matematiky, s důrazem na matematické struktury, které jsou potřebné pro pozdější aplikace v informačních a komunikačních technologiích.

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

Absolvování cvičení ve stanoveném rozsahu.

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

Cvičení odb. zák.

26 hod., povinná

Vyučující / Lektor