470-6301/02 – Metody diskrétní matematiky (MDM)

Garantující katedraKatedra aplikované matematikyKredity10
Garant předmětudoc. Mgr. Petr Kovář, Ph.D.Garant verze předmětudoc. Mgr. Petr Kovář, Ph.D.
Úroveň studiapostgraduálníPovinnostpovinně volitelný typu B
RočníkSemestrzimní + letní
Jazyk výukyangličtina
Rok zavedení2015/2016Rok zrušení
Určeno pro fakultyUSP, FEIUrčeno pro typy studiadoktorské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
KOV16 doc. Mgr. Petr Kovář, Ph.D.
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zkouška 28+0
kombinovaná Zkouška 28+0

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

Student by měl - analyzovat podstatu reálné úlohy - přeformulovat je do řeči diskrétní matematiky - vyřešit příslušný problém užitím postupů diskrétní matematiky - interpretovat teoretické výsledky v kontextu původní úlohy Současně je nutno kriticky zhodnotit meze použitelnosti ideálního řešení v reálné situaci.

Vyučovací metody

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

Anotace

Obsahem kurzu jsou vybraná témata z kombinatoriky, teorie grafů a kombinatorických designů. Současně jsou podány aplikace těchto disciplín v jiných oblastech diskrétní matematiky (např. teorie kódování při konstrukci samoopravných kódů) i při řešení některých praktických problémů.

Povinná literatura:

D.B. West, Introduction to graph theory - 2nd ed., Prentice-Hall, Upper Saddle River NJ, (2001). Hill: A First Course in Coding Theory, Clarendon Press, Oxford, reprinted 2009. C.C. Lindner, C.A. Rodger, Design Theory second edition, CRC Press, Boca Raton FL, (2009)

Doporučená literatura:

Rosen K.: Discrete Mathematics and Its Applications - 6th ed., McGraw-Hill NY, 2007, 0-07-288008-2

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

Aktivní účast na přednáškách a cvičeních. Konzultace projektu. Zkouška má písemnou a ústní část.

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

Náplň přednášek Vybíráme v následujících témat: 1) Množiny, relace, funkce a základní početní metody. Algoritmy a jejich složitost. Metoda matematické indukce. Permutace a kombinace, binomické koeficienty a kombinatorické identity. Přerovnávání. Princip inkluze a exkluze. 2) Rekurentní vztahy. Použití, konstrukce a řešení rekurentních vztahů. Vytvořující funkce. 3) Dirichletův princip a jeho aplikace. Příklady grafů, definice. 4) Základní pojmy z teorie grafů a způsoby reprezentace grafů. 5) Komunikační sítě, nejkratší a nejširší cesty, jejich spolehlivost a toky v sítích. Bipartitní grafy. Stromy a kostry grafu. Prohledávání stromů - metody a algoritmy. Mosty a artikulace. Vrcholová a hranová souvislost grafů. Bloky. Konstrukce spolehlivých komunikačních sítí. Orientované a ohodnocené grafy. Sítě a toky v sítích. Řezy, věta o maximálním toku a minimálním řezu. Algoritmy na hledání maximálního toku v síti. 6) Planární a neplanární grafy. Rovinné a planární graf. Kritérium planarity grafu. Míra neplanarity grafu. Souvislost a navrhování obvodů. 7) Hlavní problém teorie kódování. Ekvivalence kódů, nutná a postačující podmínka existence (n, M, d) - kódů, Hammingova hranice, perfektní kódy. 8) Konečná tělesa a vektorové prostory. Ortogonální latinské čtverce, projektivní a afinní roviny. 9) Kódy a latinské čtverce. Latinské čtverce a vzájemně ortogonální latinské čtverce, užití latinských čtverců v kódování. 10) Základní pojmy teorie kombinatorických designů. Symetrické designy. Využití v teorii kódování. 11) Steinerovy systémy trojic. Konstrukce a vztah k faktorizaci grafů. V průběhu semestru vypracuje student jeden nebo dva samostatné písemné projekty.

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

Kombinovaná forma (platnost od: 2015/2016 zimní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodů
Zkouška Zkouška  
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
2020/2021 (P0541D170006) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný typu B stu. plán
2020/2021 (P0541D170006) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný typu B stu. plán
2020/2021 (P0613D140006) Informatika P angličtina Ostrava povinně volitelný typu B stu. plán
2020/2021 (P0613D140006) Informatika K angličtina Ostrava povinně volitelný typu B stu. plán
2020/2021 (P0613D140021) Výpočetní vědy K angličtina Ostrava povinně volitelný typu B stu. plán
2020/2021 (P0613D140021) Výpočetní vědy P angličtina Ostrava povinně volitelný typu B stu. plán
2020/2021 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný stu. plán
2020/2021 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný stu. plán
2020/2021 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P angličtina Ostrava povinně volitelný stu. plán
2020/2021 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K angličtina Ostrava povinně volitelný stu. plán
2020/2021 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy P angličtina Ostrava povinně volitelný stu. plán
2020/2021 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy K angličtina Ostrava povinně volitelný stu. plán
2019/2020 (P0613D140006) Informatika P angličtina Ostrava povinně volitelný typu B stu. plán
2019/2020 (P0541D170006) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný typu B stu. plán
2019/2020 (P0541D170006) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný typu B stu. plán
2019/2020 (P0613D140006) Informatika K angličtina Ostrava povinně volitelný typu B stu. plán
2019/2020 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný stu. plán
2019/2020 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný stu. plán
2019/2020 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P angličtina Ostrava povinně volitelný stu. plán
2019/2020 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K angličtina Ostrava povinně volitelný stu. plán
2019/2020 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy P angličtina Ostrava povinně volitelný stu. plán
2019/2020 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy K angličtina Ostrava povinně volitelný stu. plán
2019/2020 (P0613D140021) Výpočetní vědy P angličtina Ostrava povinně volitelný typu B stu. plán
2019/2020 (P0613D140021) Výpočetní vědy K angličtina Ostrava povinně volitelný typu B stu. plán
2018/2019 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný stu. plán
2018/2019 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P angličtina Ostrava povinně volitelný stu. plán
2018/2019 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný stu. plán
2018/2019 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K angličtina Ostrava povinně volitelný stu. plán
2018/2019 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy P angličtina Ostrava povinně volitelný stu. plán
2018/2019 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy K angličtina Ostrava povinně volitelný stu. plán
2017/2018 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný stu. plán
2017/2018 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P angličtina Ostrava povinně volitelný stu. plán
2017/2018 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný stu. plán
2017/2018 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K angličtina Ostrava povinně volitelný stu. plán
2017/2018 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy P angličtina Ostrava povinně volitelný stu. plán
2017/2018 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy K angličtina Ostrava povinně volitelný stu. plán
2016/2017 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný stu. plán
2016/2017 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P angličtina Ostrava povinně volitelný stu. plán
2016/2017 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný stu. plán
2016/2017 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K angličtina Ostrava povinně volitelný stu. plán
2016/2017 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy P angličtina Ostrava povinně volitelný stu. plán
2016/2017 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy K angličtina Ostrava povinně volitelný stu. plán
2015/2016 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný stu. plán
2015/2016 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný stu. plán
2015/2016 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P angličtina Ostrava povinně volitelný stu. plán
2015/2016 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K angličtina Ostrava povinně volitelný stu. plán
2015/2016 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy P angličtina Ostrava povinně volitelný stu. plán
2015/2016 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy K angličtina Ostrava 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