Předmět: 456-533: Diskrétní matematika (DIM)
Garant: Doc. RNDr. Petr Hliněný, Ph.D.
Rozsah: 6 kreditů (2/2/0/0/2)
Akademický rok: 2005/2006

Osnova předmětu Diskrétní matematika na Katedře informatiky Fakulty elektrotechniky a informatiky.
Garantem předmětu je Petr Hliněný, můžete se podívat na jeho stránky věnované předmětu Diskrétní matematika z podzimu 2003 a 2004.

Anotace

Předmět seznamuje studenta se základními konstrukcemi diskrétní matematiky. (Slovo "diskrétní" je v názvu 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.
Cílem předmětu je naučit se používat základní pojmy a konstrukce diskrétní matematiky při exaktní formulaci a řešení praktických úloh.

Průběh přednášek

Přehled látky probrané v jednotlivých týdnech včetně slidů.

Předběžný průběh přednášek se shoduje s plánem z předchozího akademického roku 2004.

• Čá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á, ale vřele se doporučuje pro úspěšné zvládnutí studia. Při případné neúčasti máte možnost na webu sami 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ě zvolíte 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 musíte mít alespoň jeden referát správně. Referát se hodnotí buď za 0 nebo 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 vše 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 vyhlašovateli tématu e-mailem nebo na papíře. Cvičící vás může vyzvat k ústnímu 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á 4.11.2005   18:00 hod	Pá 25.11.2005   18:00 hod
Druhá sada zadání	Pá 16.12.2005   18:00 hod	Pá 6.1.2006   18:00 hod

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

Semestrální písemka se bude psát zhruba v polovině semestru (první nebo druhý týden listopadu hromadně na přednáškách). K vyřešení dostanete 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ů. V případě neúčasti bude možno po domluvě písemku nahradit vypracováním samostatného referátu navíc, mimo obvyklé termíny a bez omezení výběru témat. Tento náhradní referát bude ohodnocen body 0 až 20 podle kvality. (Tato náhrada se automaticky týká studentů kombinovaného studia.)

Semestrální písemka	Datum a čas	Místnost
na přednášce	Po 14.11.2005   8:00-9:30	C3

Zkouška (60 bodů)

Ke zkoušce můžete jít, jestliže správně vypracujete alespoň jeden samostatný referát! Hlavní součástí zkoušky je písemná práce zhruba na 75 minut. Na rozdíl od semestrální písemky bude písemná zkouška obtížnější a budete při ní moci používat vedle vlastní hlavy pouze jednu stranu A4 rukou psaných poznámek o předmětu (jakoby "zlegalizovaný tahák"). Na písemné zkoušce získat až 60 bodů. 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, na opravu pokažené písemky musíte jít na další termín písemky!

Data a místnosti zkušebních termínů.

Můžete se podívat na vzorovou zkouškovou písemku ve formátu ps i 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é věci 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 2005/2006 jsou přednášky z Diskrétní matematiky pro skupiny LB275, LB284-LB289 každé pondělí 8:00-9:30 na C3. Následuje rozvrh cvičení.