470-2301/05 – Diskrétní matematika (DIM)

Garantující katedraKatedra aplikované matematikyKredity6
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ý typu B
Ročník1Semestrzimní
Jazyk výukyčeština
Rok zavedení2019/2020Rok zrušení
Určeno pro fakultyFEI, FSUrčeno pro typy studiabakalářské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
KOV16 doc. Mgr. Petr Kovář, Ph.D.
KOV74 Mgr. Tereza Kovářová, Ph.D.
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 http://homel.vsb.cz/~kov16/files/algoritmizace_diskretnich_struktur.pdf P.Kovář, Úvod do teorie grafů, elektronický učební text, 2011, on-line http://homel.vsb.cz/~kov16/files/uvod_do_teorie_grafu.pdf

Doporučená literatura:

P. Kovář, Řešené přı́klady k procvičenı́, cvičebnice, 2022, on-line http://homel.vsb.cz/~kov16/files/dim_priklady_resene.pdf 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.) P. Kovář: Lecture slides online http://homel.vsb.cz/~kov16/files/dim_kapitoly_all_en.pdf P. Kovář, T. Kovářová: Solved exercises http://homel.vsb.cz/~kov16/files/dim_solved_exercises.pdf

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: 2019/2020 zimní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodůMax. počet pokusů
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 Projekt 10  0
                Zápočtové písemky Písemka 20  0
        Zkouška Zkouška 70  21 3
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

Podmínky absolvování předmětu a účast na cvičeních v rámci ISP: Splnění všech povinných úkolů v individuálně dohodnutých termínech.

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2024/2025 (B0588A170003) Aplikované vědy a technologie MTM P čeština Ostrava 1 povinně volitelný typu A stu. plán
2024/2025 (B0588A170003) Aplikované vědy a technologie FYZ P čeština Ostrava 1 povinně volitelný typu B stu. plán
2024/2025 (B0588A170003) Aplikované vědy a technologie MAR P čeština Ostrava 1 povinně volitelný typu B stu. plán
2024/2025 (B0588A170003) Aplikované vědy a technologie MTR P čeština Ostrava 1 povinně volitelný typu B stu. plán
2024/2025 (B0588A170003) Aplikované vědy a technologie PRJ P čeština Ostrava 1 povinně volitelný typu B stu. plán
2024/2025 (B0541A170008) Výpočetní a aplikovaná matematika AM P čeština Ostrava 2 povinný stu. plán
2024/2025 (B0541A170008) Výpočetní a aplikovaná matematika AM K čeština Ostrava 2 povinný stu. plán
2023/2024 (B0588A170003) Aplikované vědy a technologie MTM P čeština Ostrava 1 povinně volitelný typu A stu. plán
2023/2024 (B0588A170003) Aplikované vědy a technologie FYZ P čeština Ostrava 1 povinně volitelný typu B stu. plán
2023/2024 (B0588A170003) Aplikované vědy a technologie MAR P čeština Ostrava 1 povinně volitelný typu B stu. plán
2023/2024 (B0588A170003) Aplikované vědy a technologie MTR P čeština Ostrava 1 povinně volitelný typu B stu. plán
2023/2024 (B0588A170003) Aplikované vědy a technologie PRJ P čeština Ostrava 1 povinně volitelný typu B stu. plán
2023/2024 (B0541A170008) Výpočetní a aplikovaná matematika AM P čeština Ostrava 2 povinný stu. plán
2023/2024 (B0541A170008) Výpočetní a aplikovaná matematika AM K čeština Ostrava 2 povinný stu. plán
2022/2023 (B0541A170008) Výpočetní a aplikovaná matematika AM K čeština Ostrava 2 povinný stu. plán
2022/2023 (B0541A170008) Výpočetní a aplikovaná matematika AM P čeština Ostrava 2 povinný stu. plán
2022/2023 (B0588A170003) Aplikované vědy a technologie MTM P čeština Ostrava 1 povinně volitelný typu A stu. plán
2022/2023 (B0588A170003) Aplikované vědy a technologie FYZ P čeština Ostrava 1 povinně volitelný typu B stu. plán
2022/2023 (B0588A170003) Aplikované vědy a technologie MAR P čeština Ostrava 1 povinně volitelný typu B stu. plán
2022/2023 (B0588A170003) Aplikované vědy a technologie MTR P čeština Ostrava 1 povinně volitelný typu B stu. plán
2022/2023 (B0588A170003) Aplikované vědy a technologie PRJ P čeština Ostrava 1 povinně volitelný typu B stu. plán
2021/2022 (B0588A170003) Aplikované vědy a technologie MTM P čeština Ostrava 1 povinně volitelný typu A stu. plán
2021/2022 (B0588A170003) Aplikované vědy a technologie FYZ P čeština Ostrava 1 povinně volitelný typu B stu. plán
2021/2022 (B0588A170003) Aplikované vědy a technologie MAR P čeština Ostrava 1 povinně volitelný typu B stu. plán
2021/2022 (B0588A170003) Aplikované vědy a technologie MTR P čeština Ostrava 1 povinně volitelný typu B stu. plán
2021/2022 (B0588A170003) Aplikované vědy a technologie PRJ P čeština Ostrava 1 povinně volitelný typu B stu. plán
2021/2022 (B0541A170008) Výpočetní a aplikovaná matematika AM P čeština Ostrava 2 povinný stu. plán
2021/2022 (B0541A170008) Výpočetní a aplikovaná matematika AM K čeština Ostrava 2 povinný stu. plán
2020/2021 (B0588A170003) Aplikované vědy a technologie MTM P čeština Ostrava 1 povinně volitelný typu A stu. plán
2020/2021 (B0588A170003) Aplikované vědy a technologie FYZ P čeština Ostrava 1 povinně volitelný typu B stu. plán
2020/2021 (B0588A170003) Aplikované vědy a technologie MAR P čeština Ostrava 1 povinně volitelný typu B stu. plán
2020/2021 (B0588A170003) Aplikované vědy a technologie MTR P čeština Ostrava 1 povinně volitelný typu B stu. plán
2020/2021 (B0588A170003) Aplikované vědy a technologie PRJ P čeština Ostrava 1 povinně volitelný typu B stu. plán
2020/2021 (B0541A170008) Výpočetní a aplikovaná matematika AM P čeština Ostrava 2 povinný stu. plán
2020/2021 (B0541A170008) Výpočetní a aplikovaná matematika AM K čeština Ostrava 2 povinný stu. plán
2019/2020 (B0541A170008) Výpočetní a aplikovaná matematika AM P čeština Ostrava 2 povinný stu. plán
2019/2020 (B0541A170008) Výpočetní a aplikovaná matematika AM K čeština Ostrava 2 povinný stu. plán
2019/2020 (B0588A170003) Aplikované vědy a technologie MTM P čeština Ostrava 1 povinně volitelný typu A stu. plán
2019/2020 (B0588A170003) Aplikované vědy a technologie FYZ P čeština Ostrava 1 povinně volitelný typu B stu. plán
2019/2020 (B0588A170003) Aplikované vědy a technologie MAR P čeština Ostrava 1 povinně volitelný typu B stu. plán
2019/2020 (B0588A170003) Aplikované vědy a technologie MTR P čeština Ostrava 1 povinně volitelný typu B stu. plán
2019/2020 (B0588A170003) Aplikované vědy a technologie PRJ P čeština Ostrava 1 povinně volitelný typu B stu. plán

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

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

Hodnocení Výuky



2023/2024 zimní
2022/2023 zimní
2021/2022 zimní
2020/2021 zimní