457-0927/01 – Metody diskrétní matematiky (MDM)

Garantující katedraKatedra aplikované matematikyKredity0
Garant předmětudoc. RNDr. Dalibor Fronček, CSc., Ph.D.Garant verze předmětudoc. RNDr. Dalibor Fronček, CSc., Ph.D.
Úroveň studiapostgraduálníPovinnostpovinně volitelný
RočníkSemestrzimní + letní
Jazyk výukyčeština
Rok zavedení1995/1996Rok zrušení2005/2006
Určeno pro fakultyUrčeno pro typy studiadoktorské
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 2+0
kombinovaná Zápočet a zkouška 2+0

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

Zvládnutí látky uvedené v osnovách.

Vyučovací metody

Anotace

Obsahem kurzu jsou vybraná témata z kombinatoriky, teorie grafů a kombinatorických designů. Současně jsou podány aplikace těchto discilí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:

Norman L. Biggs: Diskrete Mathematics Revised Edition, Oxford University Press, 1994, ISBN 019-853427-2 Anderson I.: A First Course in Combinatorial Mathematics, Clarendon Press, Oxford, 1989, ISBN 019-869673-1 Ryser H. J.: Combinatorial Mathematics, The Mathematical Association of America, 1963, ISBN 0-88385-000-1 Niven I.: Mathematics of Choice, The Mathematical Association of America, 1965, ISBN 0-88385-615-8

Doporučená literatura:

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: 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 zapojení a vypojení. Rekurentní vztahy a základní pojmy z teorie grafů. Použití, konstrukce a řešení rekurentních vztahů. Dirichletův princip a jeho aplikace. Příklady grafů, definice. Způsoby a reprezentace grafů. Cesty, cykly a souvislost. Algoritmus na hledání nejkratší cesty v komunikační síti. Komunikační sítě, jejich spolehlivost a toky v sítích. Biparitní grafy. Stromy a kostra grafu. Prohledávání stromů - metody a algoritmy. Hledání nejlevnější kostry v grafu. 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. Planární a neplanární grafy. Rovinné a planární graf. Kritérium planarity grafu. Míra neplanarity grafu. Souvislost a navrhování obvodů. Adresování v grafech a kombinatorické obvody. Problém adresování. Souvislost s komunikačními sítěmi. Minimální adresy v sítích. Vlastnosti kombinatorických obvodů. Přepínačové obvody. Boolovské algebry. Boolovské funkce a syntéza obvodů.

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

Prezenční forma (platnost od: 1960/1961 letní semestr, platnost do: 2012/2013 letní 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 (145) 51 3
        Zkouška Zkouška 100  0 3
        Zápočet Zápočet 45  0 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ý rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2004/2005 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2612V015) Elektronika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2612V045) Technická kybernetika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2642V004) Elektrické stroje, přístroje a pohony P čeština Ostrava povinně volitelný stu. plán
2004/2005 (P2645) Elektrotechnika, sdělovací a výpočetní technika (3907V001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2612V045) Technická kybernetika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2612V015) Elektronika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2642V004) Elektrické stroje, přístroje a pohony P čeština Ostrava povinně volitelný stu. plán
2003/2004 (P2645) Elektrotechnika, sdělovací a výpočetní technika (3907V001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (P2645) Elektrotechnika, sdělovací a výpočetní technika (2612V045) Technická kybernetika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (P2612) Elektrotechnika a informatika (2612V015) Elektronika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (P2612) Elektrotechnika a informatika (2612V045) Technická kybernetika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (P2612) Elektrotechnika a informatika (2642V004) Elektrické stroje, přístroje a pohony P čeština Ostrava povinně volitelný stu. plán
2002/2003 (P2612) Elektrotechnika a informatika (3907V001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (P2612) Elektrotechnika a informatika (2612V015) Elektronika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (P2612) Elektrotechnika a informatika (2612V045) Technická kybernetika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (P2612) Elektrotechnika a informatika (2642V004) Elektrické stroje, přístroje a pohony P čeština Ostrava povinně volitelný stu. plán
2001/2002 (P2612) Elektrotechnika a informatika (3907V001) Elektroenergetika P češ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

Hodnocení Výuky

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