456-0533/01 – Diskrétní matematika (DIM)

Garantující katedraKatedra informatikyKredity6
Garant předmětuRNDr. Michael Kubesa, Ph.D.Garant verze předmětuRNDr. Michael Kubesa, Ph.D.
Úroveň studiapregraduální nebo graduálníPovinnostpovinný
Ročník2Semestrzimní
Jazyk výukyčeština
Rok zavedení2003/2004Rok zrušení2006/2007
Určeno pro fakultyFEIUrčeno pro typy studiabakalářské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
KOH053 Ing. Ondřej Kohut
KON422 Mgr. Lukáš Konečný
KOT06 Ing. Martin Kot, Ph.D.
KOV16 doc. Mgr. Petr Kovář, Ph.D.
KUB59 RNDr. Michael Kubesa, Ph.D.
SOM025 Mgr. Miroslav Sommer
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 2+2
kombinovaná Zápočet a zkouška 2+2

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.

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

Kombinovaná forma (platnost od: 1960/1961 letní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodů
Zápočet a zkouška Zápočet a zkouška 100 (145) 51
        Zkouška Zkouška 100  0
        Zápočet Zápočet 45  0
Rozsah povinné účasti:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2005/2006 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 1 povinný stu. plán
2005/2006 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2005/2006 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2005/2006 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 1 povinný stu. plán
2005/2006 (B2646) Informační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2005/2006 (B2646) Informační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2004/2005 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 1 povinný stu. plán
2004/2005 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2004/2005 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2004/2005 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 1 povinný stu. plán
2004/2005 (B2646) Informační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2004/2005 (B2646) Informační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2003/2004 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 1 povinný stu. plán
2003/2004 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2003/2004 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2003/2004 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 1 povinný stu. plán

Výskyt ve speciálních blocích

Název blokuAkademický rokForma studiaJazyk výuky RočníkZLTyp blokuVlastník bloku