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

Garantující katedra	Katedra aplikované matematiky	Kredity	10
Garant předmětu	doc. Mgr. Petr Kovář, Ph.D.	Garant verze předmětu	doc. Mgr. Petr Kovář, Ph.D.
Úroveň studia	postgraduální	Povinnost	povinně volitelný typu B
Ročník		Semestr	zimní + letní
		Jazyk výuky	angličtina
Rok zavedení	2015/2016	Rok zrušení
Určeno pro fakulty	USP, FEI	Určeno pro typy studia	doktorské

Výuku zajišťuje
Os. čís.	Jméno	Cvičící	Přednášející
KOV16	doc. Mgr. Petr Kovář, Ph.D.

Rozsah výuky pro formy studia
Forma studia	Zp.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, Prentice-Hall, Upper Saddle River NJ, (2019). 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

Další studijní materiály

Studijní opory v systému E-výuka

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

Konzultace prostřednictvím MS Teams.

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 úlohy	Typ úlohy	Max. počet bodů (akt. za podúlohy)	Min. počet bodů	Max. počet pokusů
Zkouška	Zkouška			3

Rozsah povinné účasti:

Zobrazit historii

Podmínky absolvování předmětu a účast na cvičeních v rámci ISP:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rok	Program	Obor/spec.	Forma	Jazyk výuky	Konz. stř.	Typ povinnosti
2025/2026	(P0541D170006) Výpočetní a aplikovaná matematika		P	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2025/2026	(P0541D170006) Výpočetní a aplikovaná matematika		K	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2024/2025	(P0541D170006) Výpočetní a aplikovaná matematika		K	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2024/2025	(P0541D170006) Výpočetní a aplikovaná matematika		P	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2024/2025	(P0613D140006) Informatika		K	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2024/2025	(P0613D140006) Informatika		P	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2024/2025	(P0613D140021) Výpočetní vědy		P	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2024/2025	(P0613D140021) Výpočetní vědy		K	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2024/2025	(P0613D140033) Informatika a výpočetní vědy		K	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2024/2025	(P0613D140033) Informatika a výpočetní vědy		P	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2023/2024	(P0613D140021) Výpočetní vědy		P	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2023/2024	(P0613D140021) Výpočetní vědy		K	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2023/2024	(P0613D140033) Informatika a výpočetní vědy		K	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2023/2024	(P0613D140033) Informatika a výpočetní vědy		P	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2023/2024	(P0541D170006) Výpočetní a aplikovaná matematika		K	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2023/2024	(P0541D170006) Výpočetní a aplikovaná matematika		P	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2023/2024	(P0613D140006) Informatika		K	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2023/2024	(P0613D140006) Informatika		P	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2023/2024	(P1807) Informatika, komunikační technologie a aplikovaná matematika	(1801V001) Informatika	P	angličtina	Ostrava	povinně volitelný	stu. plán
2023/2024	(P1807) Informatika, komunikační technologie a aplikovaná matematika	(1801V001) Informatika	K	angličtina	Ostrava	povinně volitelný	stu. plán
2023/2024	(P1807) Informatika, komunikační technologie a aplikovaná matematika	(1103V036) Výpočetní a aplikovaná matematika	P	angličtina	Ostrava	povinně volitelný	stu. plán
2023/2024	(P1807) Informatika, komunikační technologie a aplikovaná matematika	(1103V036) Výpočetní a aplikovaná matematika	K	angličtina	Ostrava	povinně volitelný	stu. plán
2022/2023	(P1807) Informatika, komunikační technologie a aplikovaná matematika	(1103V036) Výpočetní a aplikovaná matematika	P	angličtina	Ostrava	povinně volitelný	stu. plán
2022/2023	(P1807) Informatika, komunikační technologie a aplikovaná matematika	(1103V036) Výpočetní a aplikovaná matematika	K	angličtina	Ostrava	povinně volitelný	stu. plán
2022/2023	(P1807) Informatika, komunikační technologie a aplikovaná matematika	(1801V001) Informatika	P	angličtina	Ostrava	povinně volitelný	stu. plán
2022/2023	(P1807) Informatika, komunikační technologie a aplikovaná matematika	(1801V001) Informatika	K	angličtina	Ostrava	povinně volitelný	stu. plán
2022/2023	(P2658) Výpočetní vědy	(2612V078) Výpočetní vědy	P	angličtina	Ostrava	povinně volitelný	stu. plán
2022/2023	(P2658) Výpočetní vědy	(2612V078) Výpočetní vědy	K	angličtina	Ostrava	povinně volitelný	stu. plán
2022/2023	(P0613D140006) Informatika		P	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2022/2023	(P0613D140006) Informatika		K	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2022/2023	(P0541D170006) Výpočetní a aplikovaná matematika		K	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2022/2023	(P0541D170006) Výpočetní a aplikovaná matematika		P	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2022/2023	(P0613D140021) Výpočetní vědy		P	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2022/2023	(P0613D140021) Výpočetní vědy		K	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2022/2023	(P0613D140033) Informatika a výpočetní vědy		P	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2022/2023	(P0613D140033) Informatika a výpočetní vědy		K	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2021/2022	(P0613D140021) Výpočetní vědy		P	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2021/2022	(P0613D140021) Výpočetní vědy		K	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2021/2022	(P0541D170006) Výpočetní a aplikovaná matematika		P	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2021/2022	(P0541D170006) Výpočetní a aplikovaná matematika		K	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2021/2022	(P0613D140006) Informatika		K	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2021/2022	(P0613D140006) Informatika		P	angličtina	Ostrava	povinně volitelný typu B	stu. plán
2021/2022	(P1807) Informatika, komunikační technologie a aplikovaná matematika	(1103V036) Výpočetní a aplikovaná matematika	P	angličtina	Ostrava	povinně volitelný	stu. plán
2021/2022	(P1807) Informatika, komunikační technologie a aplikovaná matematika	(1103V036) Výpočetní a aplikovaná matematika	K	angličtina	Ostrava	povinně volitelný	stu. plán
2021/2022	(P1807) Informatika, komunikační technologie a aplikovaná matematika	(1801V001) Informatika	P	angličtina	Ostrava	povinně volitelný	stu. plán
2021/2022	(P1807) Informatika, komunikační technologie a aplikovaná matematika	(1801V001) Informatika	K	angličtina	Ostrava	povinně volitelný	stu. plán
2021/2022	(P2658) Výpočetní vědy	(2612V078) Výpočetní vědy	P	angličtina	Ostrava	povinně volitelný	stu. plán
2021/2022	(P2658) Výpočetní vědy	(2612V078) Výpočetní vědy	K	angličtina	Ostrava	povinně volitelný	stu. plán
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 bloku	Akademický rok	Forma studia	Jazyk výuky	Ročník	Z	L	Typ bloku	Vlastník bloku

Hodnocení Výuky

Předmět neobsahuje žádné hodnocení.