Detail předmětu
Seminář matematických struktur
FIT-SMTAk. rok: 2018/2019
Výuka probíhá formou demonstračních cvičení s aktivním podílem studentů na řešení konkrétních problémů a příkladů z oblastí matematických struktur významných pro informatiku. Řešené problémy a příklady spadají do oblasti výrokové logiky, predikátové logiky, univerzální algebry, algebraických struktur s jednou a dvěma binárními operacemi, topologických a metrických prostorů, Banachových a Hilbertových prostorů, neorientovaných grafů, orientovaných grafů a sítí. Aplikační oblasti jdou napříč informatikou a zahrnují mj. analýzu a verifikaci, optimalizaci kódu, automatické usuzování, analýzu rozsáhlých dat, teorii kódů, počítačovou grafiku, zpracování obrazu a zvuku, algoritmy spojené s implementací počítačových sítí atd.
Garant předmětu
Zajišťuje ústav
Výsledky učení předmětu
Hlubší pochopení vybraných kapitol z matematiky, konkrétně matematické logiky, algebry, funkcionální analýzy a teorie grafů, a schopnost jejich aplikace při řešení praktických i teoretických problémů z oblasti informatiky.
Rozšíření a zkvalitnění schopností systematického a logického myšlení a přesného vyjadřování.
Doporučená nebo povinná literatura
- Birkhoff, G., MacLane, S.: Aplikovaná algebra, Alfa, Bratislava, 1981
- Procházka, L.: Algebra, Academia, Praha, 1990
- Lang, S.: Undergraduate Algebra, Springer-Verlag, New York - Berlin - Heidelberg, 1990, ISBN 038797279
- Polimeni, A.D., Straight, H.J.: Foundations of Discrete Mathematics, Brooks/Cole Publ. Comp., Pacific Grove, 1990, ISBN 053412402X
- Shoham, Y.: Reasoning about Change, MIT Press, Cambridge, 1988, ISBN 0262192691
- Van der Waerden, B.L.: Algebra I, II, Springer-Verlag, Berlin - Heidelberg - New York, 1971, Algebra I. ISBN 0387406247, Algebra II. ISBN 0387406255
- Nerode, A., Shore, R.A.: Logic for Applications, Springer-Verlag, 1993, ISBN 0387941290
- Mendelson, E.: Introduction to Mathematical Logic, Chapman Hall, 1997, ISBN 0412808307
- Biggs, N.L.: Discrete Mathematics, Oxford Science Publications, 1999, ISBN 0198534272
Jazyk výuky
čeština
Osnovy výuky
- Osnova přednášek:
- Výroková logika, syntax, sémantika, formální systém výrokové logiky, dokazatelnost ve výrokové logice, ukázky důkazů.
- Predikátová logika, syntax, sémantika, transformace formulí.
- Predikátová logika, formální systém, ukázky důkazů.
- Univerzální algebry, podalgebry a homomorfismy, kongruence a faktorové algebry, přímé součiny algeber.
- Grupoidy, pologrupy, grupy: vlastnosti, příklady.
- Svazy, Booleovy algebry: vlastnosti, příklady.
- Okruhy, ideály, tělesa: vlastnosti příklady.
- Okruhy polynomů, obory integrity a dělitelnost, konečná tělesa: vlastnosti, příklady.
- Metrické prostory, úplnost, normované a Banachovy prostory.
- Unitární a Hilbertovy prostory, ortogonalita, uzavřené ortonormální systémy a Fourierovy řady.
- Stromy a kostry, minimální kostra (Kruskalův a Primův algoritmus), vybarvování uzlů a hran grafu.
- Orientované grafy, orientované eulerovské grafy, problém kritické cesty (Dijkstrův a Floyd-Warshallův algoritmus).
- Sítě, toky a řezy v sítích, problémy maximálního toku a minimálního řezu, cirkulace v sítích.
Cíl
Rozšíření schopností aplikovat poznatky z oblasti matematických struktur významných pro informatiku a schopností řešit konkrétní teoretické i praktické problémy s využitím těchto struktur. Předmět pokrývá, procvičuje a ilustruje na příkladech obecných i informatických všechny oblasti diskutované v předmetu Matematické struktury v informatice, tj. univerzální algebry, klasické algebraické struktury, základy matematické logiky, teorie Banachových a Hilbertových prostorů a teorie neorientovaných i orientovaných grafů.
Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky
Kontrola účasti, maximálně dvě neomluvené absence.
Zařazení předmětu ve studijních plánech
- Program IT-MGR-2 magisterský navazující
obor MBS , libovolný ročník, zimní semestr, 2 kredity, volitelný
obor MBI , libovolný ročník, zimní semestr, 2 kredity, volitelný
obor MIS , libovolný ročník, zimní semestr, 2 kredity, volitelný
obor MMI , libovolný ročník, zimní semestr, 2 kredity, volitelný
obor MMM , libovolný ročník, zimní semestr, 2 kredity, volitelný
obor MGM , libovolný ročník, zimní semestr, 2 kredity, volitelný
obor MPV , libovolný ročník, zimní semestr, 2 kredity, volitelný
obor MSK , libovolný ročník, zimní semestr, 2 kredity, volitelný
obor MIN , 1. ročník, zimní semestr, 2 kredity, volitelný
Typ (způsob) výuky
Cvičení odborného základu
26 hod., nepovinná
Vyučující / Lektor
Osnova
- Výroková logika, syntax, sémantika, formální systém výrokové logiky, dokazatelnost ve výrokové logice, ukázky důkazů.
- Predikátová logika, syntax, sémantika, transformace formulí.
- Predikátová logika, formální systém, ukázky důkazů.
- Univerzální algebry, podalgebry a homomorfismy, kongruence a faktorové algebry, přímé součiny algeber.
- Grupoidy, pologrupy, grupy: vlastnosti, příklady.
- Svazy, Booleovy algebry: vlastnosti, příklady.
- Okruhy, ideály, tělesa: vlastnosti příklady.
- Okruhy polynomů, obory integrity a dělitelnost, konečná tělesa: vlastnosti, příklady.
- Metrické prostory, úplnost, normované a Banachovy prostory.
- Unitární a Hilbertovy prostory, ortogonalita, uzavřené ortonormální systémy a Fourierovy řady.
- Stromy a kostry, minimální kostra (Kruskalův a Primův algoritmus), vybarvování uzlů a hran grafu.
- Orientované grafy, orientované eulerovské grafy, problém kritické cesty (Dijkstrův a Floyd-Warshallův algoritmus).
- Sítě, toky a řezy v sítích, problémy maximálního toku a minimálního řezu, cirkulace v sítích.