Detail předmětu

Matematické struktury v informatice

MAT Ak. rok 2023/2024 zimní semestr 5 kreditů

Předmět není v tomto roce otevřen

Formální teorie, výroková logika, predikátová logika, univerzální algebra, algebraické struktury s jednou a dvěma binárními operacemi, topologické a metrické prostory, Banachovy a Hilbertovy prostory, neorientované grafy, orientované grafy a sítě.

Garant předmětu

Koordinátor předmětu

Jazyk výuky

česky, anglicky

Zakončení

zkouška (písemná)

Rozsah

  • 39 hod. přednášky
  • 13 hod. cvičení

Bodové hodnocení

  • 80 bodů závěrečná zkouška
  • 20 bodů půlsemestrální test

Zajišťuje ústav

Cíle předmětu

Cílem předmětu je prohloubit u studentů znalosti základních matematických struktur, které jsou často využívány v různých oblastech informatiky. Vedle základů univerzální algebry a klasických algebraických struktur budou podrobněji vyloženy základy matematické logiky, teorie Banachových a Hilbertových prostorů a teorie neorientovaných i orientovaných grafů.
Studenti prohloubí své znalosti z oblasti matematických struktur, které jsou nejčastěji využívány v informatice. Jedná se o matematickou logiku, algebru, funkcionální analýzu a teorii grafů. To jim pak umožní nejen lépe porozumět teoretickým základům informatiky, ale také se aktivně zapojit do výzkumu v tomto oboru.

Literatura studijní

  • Birkhoff, G., MacLane, S.: Aplikovaná algebra, Alfa, Bratislava, 1981
  • 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
  • Nerode, A., Shore, R.A.: Logic for Applications, Springer-Verlag, 1993, ISBN 0387941290
  • Cameron, P.J.: Sets, Logic and Categories, Springer-Verlag, 2000, ISBN 1852330562
  • Mendelson, E.: Introduction to Mathematical Logic, Chapman Hall, 1997, ISBN 0412808307

Osnova přednášek

  1. Výroková logika, výrokové formule a jejich pravdivost, formální systém výrokové logiky, dokazatelnost ve výrokové logice, věta o úplnosti.
  2. Jazyk predikátové logiky (predikáty, kvantifikátory, termy, formule) a jeho realizace, pravdivost a splňování formulí.
  3. Formální systém predikátové logiky 1. řádu, věty o korektnosti, úplnosti a kompaktnosti, prenexní tvar formulí. 
  4. Univerzální algebry a jejich základní typy: grupoidy, pologrupy, monoidy, grupy, okruhy, obory integrity, tělesa, svazy a Booleovy svazy.  
  5. Základní algebraické metody: podalgebry, homomorfismy a izomorfismy, kongruence a přímé součiny algeber.
  6. Relace kongruence na grupách a okruzích, normální podgrupy a ideály.
  7. Okruhy polynomů, dělitelnost v oborech integrity, Gaussovy a Eukleidovy okruhy.
  8. Teorie polí: minimální pole, rozšíření polí, konečná pole.
  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.

Průběžná kontrola studia

Půlsemestrální písemný test.

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

Nahoru