Detail předmětu

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

FIT-MATeAk. rok: 2022/2023

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

prof. RNDr. Josef Šlapal, CSc.

Zajišťuje ústav

ÚM-odbor algebry a diskrétní matematiky (ÚM OAAG)

Výsledky učení 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.

Způsob a kritéria hodnocení

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

Základní literatura

Mendelson, E.: Introduction to Mathematical Logic, Chapman and Hall/CRC, 2015, ISBN 9781482237726 (EN)
Biggs, N.L.: Discrete Mathematics, 2nd ed., Oxford University Press, 2003, ISBN 978-0198507185 (EN)
Robinson, J.C.: An Introduction to Functional Analysis, Cambridge University Press, 2020, ISBN 9781139030267 (EN)

Doporučená literatura

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)
Farenick, D.: Fundamentals of Functional Analysis, Springer-Verlag, 2016, ISBN 978-3-319-45633-1 (EN)
Nerode, A., Shore, R.A.: Logic for Applications, 2nd. ed., Springer-Verlag, 1997, ISBN 978-0-387-94893-5 (EN)

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

  • Program IT-MGR-2 magisterský navazující

    obor MGMe , 1. ročník, zimní semestr, povinný

  • 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

prof. RNDr. Josef Šlapal, CSc.

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.

Cvičení odborného základu

13 hod., povinná

Vyučující / Lektor

prof. RNDr. Josef Šlapal, CSc.

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.