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

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

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

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

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

Osnova


  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.