456-0533/01 – Diskrétní matematika (DIM)
| Garantující katedra | Katedra informatiky | Kredity | 6 |
| Garant předmětu | RNDr. Michael Kubesa, Ph.D. | Garant verze předmětu | RNDr. Michael Kubesa, Ph.D. |
| Úroveň studia | pregraduální nebo graduální | Povinnost | povinný |
| Ročník | 1 | Semestr | zimní |
| | Jazyk výuky | čeština |
| Rok zavedení | 2003/2004 | Rok zrušení | 2006/2007 |
| Určeno pro fakulty | FEI | Určeno pro typy studia | bakalářské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
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 studenty používat tyto pojmy při exaktní formulaci a řešení praktických úloh.
Vyučovací metody
Přednášky
Individuální konzultace
Cvičení (v učebně)
Projekt
Anotace
Předmět seznamuje studenta se základy teorie množin a základními konstrukcemi diskrétní matematiky v oblasti kombinatoriky a teorie grafů. (Slovo "diskrétní" je v názvu míněno jako opak "spojitého".)
Povinná literatura:
P.Hliněný, Diskrétní matematika pro studenty informatiky, elektronický učební text, 2004, zde.
J.Matoušek, J.Nešetřil. Kapitoly z diskrétní matematiky, Karolinum Praha 2000.
(Konkrétně: 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, ale prodejna skript ji neprodává. Knihu by mělo být možné koupit v knihkupectví Profesio v centru Ostravy, Hollarova ulice naproti ČSOB.
Doporučená literatura:
L.Kučera, Kombinatorické Algoritmy, SNTL, Praha, 1983.
Další studijní materiály
Forma způsobu ověření studijních výsledků a další požadavky na studenta
E-learning
Další požadavky na studenta
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Přednášky:
Čá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.
Přirozená čísla a matematická indukce. Pojem matematického důkazu.
Počty podmnožin, důkazy vzorců pro kombinace a permutace.
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.
Formální základy diskrétní matematiky: pojmy relace, zobrazení, eqivalence,
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í.
(Odhady růstu funkcí faktoriál a kombinační číslo.)
Část II -- Úvod do teorie grafů
Pojem grafu, jeho souvislost s relacemi.
Podgrafy, izomorfismus, 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. (Tranzitivní uzávěr.)
Stromy a jejich charakterizace, izomorfismus stromů.
Kořenové stromy.
Kostra grafu, (počet koster), problém minimální kostry.
Definice matroidu přes nezávislé množiny.
Vektorový a grafový matroid, hladový algoritmus.
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í.
(Průsečíkové číslo.)
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.)
Aktuální průběh přednášek a promítané přednášky.
Cvičení:
Procvičení věcí z přednášky.
Projekty:
Vypracování samostatých písemných referátů, viz zadaná témata s termíny úkolů v KatISu.
(Na témata se přihlašujte před odevzdáním, už to funguje.)
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky
Předmět neobsahuje žádné hodnocení.