Detail předmětu

Seminář matematických struktur

FIT-SMTAk. rok: 2017/2018

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.

Jazyk výuky

čeština

Počet kreditů

2

Garant předmětu

prof. Ing. Tomáš Vojnar, Ph.D.

Zajišťuje ústav

Ústav inteligentních systémů (UITS)

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í.

Prerekvizity

Nejsou žádné prerekvizity.

Způsob a kritéria hodnocení

Výuka není kontrolována.

Osnovy výuky

    Osnova přednášek:
    1. Výroková logika, syntax, sémantika, formální systém výrokové logiky, dokazatelnost ve výrokové logice, ukázky důkazů.
    2. Predikátová logika, syntax, sémantika, transformace formulí.
    3. Predikátová logika, formální systém, ukázky důkazů. 
    4. Univerzální algebry, podalgebry a homomorfismy, kongruence a faktorové algebry, přímé součiny algeber.
    5. Grupoidy, pologrupy, grupy: vlastnosti, příklady.
    6. Svazy, Booleovy algebry: vlastnosti, příklady.
    7. Okruhy, ideály, tělesa: vlastnosti příklady.
    8. Okruhy polynomů, obory integrity a dělitelnost, konečná tělesa: vlastnosti, příklady.
    9. Metrické prostory, úplnost, normované a Banachovy prostory.
    10. Unitární a Hilbertovy prostory, ortogonalita, uzavřené ortonormální systémy a Fourierovy řady.
    11. Stromy a kostry, minimální kostra (Kruskalův a Primův algoritmus), vybarvování uzlů a hran grafu.
    12. Orientované grafy, orientované eulerovské grafy, problém kritické cesty (Dijkstrův a Floyd-Warshallův algoritmus).
    13. 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.

Učební cíle

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.

Základní literatura

Mendelson, E.: Introduction to Mathematical Logic, Chapman Hall, 1997, ISBN 0412808307 Biggs, N.L.: Discrete Mathematics, Oxford Science Publications, 1999, ISBN 0198534272

Doporučená 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

Zařazení předmětu ve studijních plánech

  • Program IT-MGR-2 magisterský navazující

    obor MMI , 0 ročník, zimní semestr, volitelný
    obor MBI , 0 ročník, zimní semestr, volitelný
    obor MSK , 0 ročník, zimní semestr, volitelný
    obor MMM , 0 ročník, zimní semestr, volitelný
    obor MBS , 0 ročník, zimní semestr, volitelný
    obor MPV , 0 ročník, zimní semestr, volitelný
    obor MIS , 0 ročník, zimní semestr, volitelný
    obor MIN , 1 ročník, zimní semestr, volitelný
    obor MGM , 0 ročník, zimní semestr, volitelný