Předmět: 457-519/1: Diskrétní matematika (DIM)
Garant: RNDr. Michael Kubesa, Ph.D.
Rozsah: 6 kreditů (2/2)
Akademický rok: 2006/2007

Osnova předmětu Diskrétní matematika na Katedře aplikované matematiky Fakulty elektrotechniky a informatiky.
Garantem předmětu je Michael Kubesa.

Anotace

Předmět seznamuje studenty se základními pojmy teorie množin a diskrétní matematiky, se kterými se nejčastěji pracuje v různých oblastech teoretické a aplikované informatiky. Cílem je naučit se používat tyto pojmy při exaktní formulaci a řešení praktických úloh.

Slovo "diskrétní" v názvu je míněno jako opak "spojitého"; tj. předmět se zabývá těmi oblastmi matematiky, kde uvažujeme celá čísla a jednotlivé konečné objekty. Diskrétní objekty jsou prezentovány převážně pomocí konečných grafů a množin.

Průběh přednášek

K dispozici je přehled látky probrané v jednotlivých týdnech včetně elektronické prezentace. Rozpis přednášek se shoduje s plánem z předchozích let 2005/2006 a 2004/2005.

Část I - Úvod do diskrétní matematiky

• Zaměření a cíle diskrétní matematiky. Množiny, prvky a podmnožiny, úvodní kombinatorické pojmy. Kombinace a permutace, vzorce na jejich počet. Výběry prvků s opakováním.
• Konečná pravděpodobnost, hody mincí a kostkou, náhodné výběry, míchání karet. Pojem pravděpodobnosti, prostoru a jevu. Náhodná čísla v počítači.
• Přirozená čísla a matematická indukce. Pojem matematického důkazu. Počty podmnožin, důkazy vzorců pro kombinace a permutace.
• Formální základy diskrétní matematiky: pojmy relace, zobrazení, ekvivalence, uspořádání, částečné uspořádání. (Princip inkluze a exkluze.)
• Algoritmické aspekty: praktická implementace množin, zobrazení a relací. Algoritmy generování podmnožin a permutací.

Část II - Úvod do teorie grafů

• Pojem grafu, jeho souvislost s relacemi. Podgrafy, isomorfizmus, stupně vrcholů, indukované podgrafy. Realizace grafu, orientovaný graf.
• Souvislost grafu, algoritmy procházení do hloubky a do šířky. Vícenásobná souvislost, hranová souvislost. (Mengerova věta.) Eulerovské grafy - kreslení jedním tahem.
• Vzdálenost v grafu, Dijkstrův algoritmus pro hledání nejkratší cesty. Metrika grafu a její výpočet.
• Stromy a jejich charakterizace, isomorfizmus stromů. Kořenové stromy. Kostra grafu, (počet koster), problém minimální kostry. Aplikace na hledání minimální kostry, algoritmy Jarníka a Borůvky.
• Rovinné kreslení grafu, Eulerův vztah. Barvení grafů, bipartitní grafy a jejich rozeznávání.
• Toky v sítích: definice a modelované problémy. Ford-Fulkersonův algoritmus pro nalezení maximálního toku. Aplikace na párování a různé reprezentanty.
• Praktická realizace grafů v počítači, různé způsoby realizace a jejich výhody. Ohodnocení vrcholů a hran. Realizace kořenových stromů a planárních grafů. (Vizualizace grafů včetně nerovinných.)

Hodnocení

Účast na přednáškách i na cvičeních formálně není povinná, nicméně vřele se doporučuje pro úspěšné zvládnutí studia. Při případné neúčasti máte možnost sami na webu zjistit, co bylo probráno.

Samostatné referáty (2×10 bodů)

Během semestru dostanete (ve dvou vlnách) témata na samostatné písemné referáty, ze kterých si libovolně vyberete v KatISu (až do nastavených limitů). Celkem máte možnost vyřešit dva referáty během celého semestru, jeden v každé vlně. Pro získání zápočtu je nutno mít alespoň jeden referát správně. Referát se hodnotí buď za 0 nebo za 10 bodů, stylem ANO/NE. V případě mimořádně kvalitního referátu lze udělit i 20 bodů.

Každé téma referátu má pevně stanovený termín odevzdání, který musíte dodržet. Nenechávejte si práci na poslední chvíli, nepomohou výmluvy na nemoc či jinou mimořádnou událost před termínem odevzdání, neboť referát máte vypracovat s dostatečným předstihem!

Každý musí sepsat svůj referát sám, žádná spolupráce na výsledném textu referátu není dovolena. Na druhou stranu je dovoleno o zadání referátu volně diskutovat se spolužáky i na cvičeních, tedy vše kromě samotného vypracování. Referát odevzdáváte e-mailem nebo na papíře příslušnému vyučujícímu (kontakt je uveden u každého zadání). Cvičící vás může vyzvat k přednesení vašeho referátu během cvičení.

Referáty	Termín pro přihlášení	Termín pro odevzdání
První sada zadání	Pá 3.11.2006   18:00 hod	Pá 17.11.2006   18:00 hod
Druhá sada zadání	Pá 22.12.2006   18:00 hod	Po 15.1.2007   17:00 hod
Náhradní referát	Pá 2.2.2007   17:00 hod	Pa 9.2.2007   17:00 hod

Semestrální písemka (20 bodů)

Semestrální písemka se bude psát přibližně v polovině semestru (jakmile probereme Část I, první polovina listopadu na přednáškách). K vyřešení bude zhruba 45 minut, přičemž budete moci používat literaturu i zápisky z přednášek. Z písemky můžete získat 0 až 20 bodů.
Ve vyjmečných případech bude možno účast u písemky, po předchozí domluvě, nahradit vypracováním samostatného referátu navíc. Náhradní referát bude ohodnocen body 0 až 20.

Můžete se podívat na vzorovou semestrální písemku ve formátu ps i pdf: dim_vzorova_pisemka_sem.ps, dim_vzorova_pisemka_sem.pdf.

Zkouška (60 bodů)

Ke zkoušce můžete jít, jestliže máte nárok na zápočet (správně vypracujete alespoň jeden samostatný referát)! Hlavní součástí zkoušky je písemná práce zhruba na 75 minut. Na písemné zkoušce získat až 60 bodů.
Na rozdíl od semestrální písemky bude písemná zkouška obtížnější a nebude možnost používat literaturu. Kdo získá přes 50 bodů celkem, může ještě volitelně přijít na ústní zkoušku, při které je možno vyřešit nesrovnalosti a dle zjištěných znalostí může dojít k menší úpravě vašeho hodnocení oběma směry. Tj. na ústní zkoušku nejsou vyhrazeny žádné body. Pozor, oprava pokažené písemky znamená jít na další zkouškový termín!

Data a místnosti zkušebních termínů budou stanoveny koncem semestru.

Můžete se podívat na vzorovou zkouškovou písemku ve formátu ps i pdf: dim_vzorova_pisemka_zk.ps, dim_vzorova_pisemka_zk.pdf.

Literatura

• P. Hliněný. Diskrétní matematika, výukový text (online), FEI VŠB - TUO, 2004.
• J. Matoušek, J. Nešetřil. Kapitoly z diskrétní matematiky, Karolinum Praha 2000.
  (Kapitoly 1, 2 a kousek z 9 pro Část I přednášky. Kapitoly 3, 4, 5 pro Část II přednášky.)

10 výtisků knihy je v knihovně VŠB, prodejna skript ji neprodává. Knihu je možné koupit případně objednat v knihkupectví Profesio v centru Ostravy, Hollarova ulice naproti ČSOB. Vhodné zejména pro studenty s hlubším zájmem o předmět.

Literatura je doporučená, není povinná. Na přednáškách a cvičeních se dozvíte vše co je potřeba znát ke zkoušce.
Rozhodně není potřeba učit se nazpaměť pasáže z knih, látce je třeba rozumět!
Je možné používat i jiné úvodní knihy a skripta pro daný předmět, ovšem pozor: některé detaily na přednášce se mohou lišit od literatury (odchylky v definicích pojmů, které nejsou ustálené) a u zkoušky pak platí to, co bylo na přednášce.

Rozvrh

V zimním semestru 2006/2007 jsou přednášky z Diskrétní matematiky pro skupiny LB266, LB267, LB276-LB285 každý čtvrtek 9:00-10:30 na C3.