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

• 39 hod. přednášky
• 13 hod. seminář

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

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.

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

• Propositional logic, formulas and their truth, formal system of propositional logic, provability, completeness theorem. 
• Language of predicate logic (predicates, kvantifiers, terms, formulas) and its realization, truth and validity of formulas.
• Formal system of 1st order predicate logic, correctness, completeness and compactness theorems, prenex  form of formulas.
• Universal algebras and their basic types: groupoids, semigroups, monoids, groups, rings, integral domains, fields, lattices and Boolean lattices.
• Basic algebraic methods: subalgebras, homomorphisms and isomorphisms, congruences and direct products of algebras.
• Congruences on groups and rings, normal subgroups and ideals.
• Polynomial rings, divisibility in integral domains, Gauss and Eucledian rings.
• Field theory: minimal fields, extension of fields, finite fields. 
• Metric spaces, completeness, normed and Banach spaces.
• Unitar and Hilbert spaces, orthogonality, closed orthonormal systems and Fourier series.
• Trees and spanning trees, minimal spanning trees (the Kruskal's and Prim's algorithms), vertex and edge colouring.
• Directed graphs, directed Eulerian graphs, networks, the critical path problem (Dijkstra's and Floyd-Warshall's algorithms).
• Networks, flows and cuts in networks, maximal flow and minimal cut problems, circulation in networks.

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