Detail předmětu
Matematické struktury v informatice (v angličtině)
FIT-MATeAk. rok: 2024/2025
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ě.
Jazyk výuky
angličtina
Počet kreditů
5
Garant předmětu
Zajišťuje ústav
Pravidla hodnocení a ukončení předmětu
Půlsemestrální písemný test.
Učební cíle
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.
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.
Základní literatura
Biggs, N.L.: Discrete Mathematics, 2nd ed., Oxford University Press, 2003, ISBN 978-0198507185 (EN)
Mendelson, E.: Introduction to Mathematical Logic, Chapman and Hall/CRC, 2015, ISBN 9781482237726 (EN)
Robinson, J.C.: An Introduction to Functional Analysis, Cambridge University Press, 2020, ISBN 9781139030267 (EN)
Mendelson, E.: Introduction to Mathematical Logic, Chapman and Hall/CRC, 2015, ISBN 9781482237726 (EN)
Robinson, J.C.: An Introduction to Functional Analysis, Cambridge University Press, 2020, ISBN 9781139030267 (EN)
Doporučená literatura
Farenick, D.: Fundamentals of Functional Analysis, Springer-Verlag, 2016, ISBN 978-3-319-45633-1 (EN)
Lang, S.: Undergraduate Algebra, Springer-Verlag, New York , 2005, ISBN 978-0-387-22025-3 (EN)
Nerode, A., Shore, R.A.: Logic for Applications, 2nd. ed., Springer-Verlag, 1997, ISBN 978-0-387-94893-5 (EN)
Shoham, Y.: Reasoning about Change, MIT Press, Cambridge, 1988, ISBN 0262192691 (EN)
Van der Waerden, B.L.: Algebra I, II, Springer-Verlag, Berlin - Heidelberg - New York, 1971, Algebra I. ISBN 0387406247, Algebra II. ISBN 0387406255 (EN)
Lang, S.: Undergraduate Algebra, Springer-Verlag, New York , 2005, ISBN 978-0-387-22025-3 (EN)
Nerode, A., Shore, R.A.: Logic for Applications, 2nd. ed., Springer-Verlag, 1997, ISBN 978-0-387-94893-5 (EN)
Shoham, Y.: Reasoning about Change, MIT Press, Cambridge, 1988, ISBN 0262192691 (EN)
Van der Waerden, B.L.: Algebra I, II, Springer-Verlag, Berlin - Heidelberg - New York, 1971, Algebra I. ISBN 0387406247, Algebra II. ISBN 0387406255 (EN)
Zařazení předmětu ve studijních plánech
- Program MIT-EN magisterský navazující 1 ročník, zimní semestr, povinný
Typ (způsob) výuky
Přednáška
39 hod., nepovinná
Vyučující / Lektor
Osnova
- 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.
Seminář
13 hod., povinná
Vyučující / Lektor
Osnova
- 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.