470-8728/01 – Diskrétní matematika (DIM AVAT)

Garantující katedraKatedra aplikované matematikyKredity4
Garant předmětudoc. Mgr. Petr Kovář, Ph.D.Garant verze předmětudoc. Mgr. Petr Kovář, Ph.D.
Úroveň studiapregraduální nebo graduálníPovinnostpovinně volitelný
Ročník3Semestrzimní
Jazyk výukyčeština
Rok zavedení2015/2016Rok zrušení
Určeno pro fakultyUSPUrčeno pro typy studiabakalářské
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 10+10

Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi

Předmět seznamuje studenty se základními pojmy diskrétní matematiky a teorie grafů, se kterými se nejčastěji pracuje v různých oblastech teoretické a aplikované informatiky. Na přednáškách budou vždy definovány a vysvětleny základní používané pojmy matematické teorie vztahující se k dané kapitole. Do každé kapitoly jsou zařazeny praktické aplikace probírané látky. V dalším budou vymezeny základní a nejdůležitější vlastnosti nadefinovaných pojmů (objektů) ve formě tvrzení, přičemž některá z nich budou dokázána. Důraz je kladen na konstruktivní důkazy. Po absolvování přednášky by tedy student měl umět: - reprodukovat, ekvivalentně přeformulovat, popřípadě zobecnit dané definice, - rozpoznat a odlišovat objekty reálného světa a poznaných matematických teorií, které definici vyhovují, a které ne, - klasifikovat tyto objekty dle předem známých a řádně objasněných vlastností, - shrnout poznatky dané kapitoly. Cvičení by mělo u studenta rozvinout tyto schopnosti: - formulovat úlohu slovy probrané matematické teorie, - aplikovat teoretické poznatky na řešení konkrétních praktických úloh a problémů, - navrhnout více metod řešení a tyto porovnávat a kriticky vyhodnocovat, - přezkoumat správnost výběru metody řešení, - přenášet či přenést metodu řešení jedné úlohy na úlohy jiné.

Vyučovací metody

Přednášky
Individuální konzultace
Cvičení (v učebně)
Projekt

Anotace

Předmět seznamuje studenta se základními pojmy, konstrukcemi a postupy 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:

M.Kubesa, Základy diskrétní matematiky, elektronický učební text, 2011, on-line. P.Kovář, Algoritmizace diskrétních struktur, elektronický učební text, 2016, on-line. P.Kovář, Úvod do teorie grafů, elektronický učební text, 2011, on-line.

Doporučená literatura:

J.Matoušek, J.Nešetřil. Kapitoly z diskrétní matematiky, Karolinum Praha 2000. (Konkrétně: Kapitoly 1,2 a část kapitoly 9 pro Část I přednášky. Kapitoly 3,4,5 pro Část II přednášky.)

Forma způsobu ověření studijních výsledků a další požadavky na studenta

Semestrální písemky. Každý týden v semestru (s výjimkou prvních dvou týdnů) se na cvičeních budou psát krátké zápočtové písemky (deset písemek, každá za 2 nebo za 3 body). Během písemek není možné používat literaturu, ani zápisky. Na konci semestru cvičící sečte body ze čtyř "nejlepších" dvoubodových a čtyř nejlepších tříbodových písemek. Maximum je 20 bodů. Témata písemek jsou vždy vyvěšena na stránkách diskrétní matematiky (resp. garanta předmětu), minimálně týden před písemkou. Na písemky budou zadány příklady obdobné. Samostatný projekt. Bude zadán v druhé půli semestru. Běžný projekt bude obsahovat několik příkladů, přičemž zhruba polovina bude z kombinatoriky a polovina z teorie grafů. Příklady budou hodnoceny buď 0-2 nebo 0-3 body (dle obtížnosti) tak, aby byl celkový maximální součet 10 bodů. Na webu mohou být také uveřejněny projekty pro zájemce, které budou obsahovat dva obtížnější úkoly (kombinatorika + teorie grafů). Každý student má možnost přidělený běžný projekt zaměnit za některý z projektů pro zájemce. Projekt pro zájemce bude mít úkoly hodnoceny 0/3/5 bodů, v případě výjimečně pěkného řešení až 10 bodů. Zkouška. Ke zkoušce můžete student jít, pokud získal zápočet. Hlavní součástí zkoušky je písemná práce zhruba na 75 minut. Na písemné zkoušce můžete získat až 70 bodů. Během zkoušky můžete používat také jedinou stranu A4 rukou psaných poznámek. Na tomto "zlegalizovaném taháku" mohou být definice, věty, vztahy. ALE NE ŘEŠENÉ PŘÍKLADY!!! Podmínky udělení zápočtu: Získat během semestru alespoň 10 bodů a samostatný referát musí být PŘIJAT. Referát bude přijat, pokud bude splňovat formální podmínky, tj. formát, úvodní stranu atd. Přijat může být i projekt, který je obsahově na 0 bodů.

E-learning

Další požadavky na studenta

Žádné další požadavky na studenta nejsou kladeny.

Prerekvizity

Předmět nemá žádné prerekvizity.

Korekvizity

Předmět nemá žádné korekvizity.

Osnova předmětu

Přednášky a cvičení: Část I - Úvod do diskrétní matematiky Zaměření a cíle diskrétní matematiky. Výpočetní metody: Kombinatorické výběry, jejich aplikace. Dirichletův princip. Geometrická a aritmetická posloupnost. Princip inkluze a exkluze, binomická věta a jejich využití. Konečná pravděpodobnost: Pojem pravděpodobnosti, pravděpodobnostního prostoru a náhodného jevu. Náhodná čísla v počítači. Rekurentní rovnice, jejich aplikace a příklady řešení. Modulární aritmetika. Algoritmické aspekty: implementace diskrétních struktur. Algoritmy generování a procházení všech základních kombinatorických výběrů. Část II - Úvod do teorie grafů Pojem grafu, jeho souvislost s relacemi. Podgrafy, isomorfizmus, stupně vrcholů. Metody zadání grafu, orientované grafy. Pojem souvislosti grafu, algoritmy procházení struktury grafu do hloubky a do šířky. Vyšší stupně souvislosti. Eulerovské grafy - kreslení jedním tahem, využití, hamiltonovské grafy a jejich využití. Vzdálenost v grafu, Dijkstrův algoritmus pro hledání nejkratší cesty. Metrika grafu a její určení. Stromy a jejich charakterizace, kořenové stromy, isomorfizmus stromů. Kostra grafu, (počet koster), problém minimální kostry. Aplikace problému minimální kostry, klasické algoritmy. Rovinné kreslení grafu, Eulerův vztah a jeho důsledky. 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í největšího toku. Další využití algoritmu (párování a systém reprezentantů).

Podmínky absolvování předmětu

Prezenční forma (platnost od: 2015/2016 zimní 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 (100) 51
        Zápočet Zápočet 30 (30) 10
                Projekt DIM Semestrální projekt 10  0
                Zápočtové písemky Písemka 20  0
        Zkouška Zkouška 70  21
Rozsah povinné účasti: účast na cvičeních je povinná, jsou akceptovány 2 omluvy účast na přednáškách je předpokládaná

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.FormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2018/2019 (B3968) Aplikované vědy a technologie (3901R076) Aplikované vědy a technologie P čeština Ostrava 3 povinně volitelný stu. plán
2017/2018 (B3968) Aplikované vědy a technologie (3901R076) Aplikované vědy a technologie P čeština Ostrava 3 povinně volitelný stu. plán
2016/2017 (B3968) Aplikované vědy a technologie (3901R076) Aplikované vědy a technologie P čeština Ostrava 3 povinně volitelný stu. plán
2015/2016 (B3968) Aplikované vědy a technologie (3901R076) Aplikované vědy a technologie P čeština Ostrava 3 povinně volitelný stu. plán

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

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