Detail předmětu
Matematické struktury v informatice
MAT Ak. rok 2019/2020 zimní semestr 5 kreditů
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
Zakončení
Rozsah
- 39 hod. přednášky
- 13 hod. cvičení
Bodové hodnocení
- 80 bodů závěrečná zkouška (písemná část)
- 20 bodů půlsemestrální test (písemná část)
Zajišťuje ústav
Přednášející
Cvičící
Hrdina Jaroslav, doc. Mgr., Ph.D. (ÚM OAAG)
Pavlík Jan, Mgr., Ph.D. (ÚM OAAG)
Šlapal Josef, prof. RNDr., CSc. (ÚM OAAG)
Získané dovednosti, znalosti a kompetence z předmětu
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.
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ů.
Literatura studijní
- 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, M.: Introduction to Mathematical Logic, Chapman Hall, 1997, ISBN 0412808307
- Cameron, P.J.: Sets, Logic and Categories, Springer-Verlag, 2000, ISBN 1852330562
- Biggs, N.L.: Discrete Mathematics, Oxford Science Publications, 1999, ISBN 0198534272
Osnova přednášek
- 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.
- Jazyk predikátové logiky (predikáty, kvantifikátory, termy, formule) a jeho realizace, pravdivost a splňování formulí.
- Formální systém predikátové logiky 1. řádu, věty o korektnosti, úplnosti a kompaktnosti, prenexní tvar formulí.
- Univerzální algebry a jejich základní typy: grupoidy, pologrupy, monoidy, grupy, okruhy, obory integrity, tělesa, svazy a Booleovy svazy.
- Základní algebraické metody: podalgebry, homomorfismy a izomorfismy, kongruence a přímé součiny algeber.
- Relace kongruence na grupách a okruzích, normální podgrupy a ideály.
- Okruhy polynomů, dělitelnost v oborech integrity, Gaussovy a Eukleidovy okruhy.
- Teorie polí: minimální pole, rozšíření polí, konečná pole.
- 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.
Průběžná kontrola studia
Půlsemestrální písemný test.
Zařazení předmětu ve studijních plánech