Matematické struktury v informatice (v angličtině)

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

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

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

• Procházka, L.: Algebra, Academia, Praha, 1990
• Lang, S.: Undergraduate Algebra, Springer-Verlag, New York - Berlin - Heidelberg, 1990, ISBN 038797279
• 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
• Cameron, P.J.: Sets, Logic and Categories, Springer-Verlag, 2000, ISBN 1852330562

• 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, Banachova věta o pevném bodě 
• Normované a Banachovy prostory, unitární a Hilbertovy prostory.
• Neorientované grafy, stromy a kostry, minimální kostra (Kruskalův a Primův algoritmus).
• Eulerovské a hamiltonovské grafy, vybarvování uzlů grafu, planarita. 
• Orientované grafy, orientované eulerovské grafy, cesta minimální délky (Dijkstrův a Floyd-Warshallův algoritmus).

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