Detail předmětu

Matematické struktury v informatice

FIT-MATAk. rok: 2019/2020

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

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.

Literatura

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

Způsob a kritéria hodnocení

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

Jazyk výuky

čeština, angličtina

Cíl

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

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

  • Program MITAI magisterský navazující

    specializace NBIO , libovolný ročník, zimní semestr, 5 kreditů, volitelný
    specializace NISD , libovolný ročník, zimní semestr, 5 kreditů, volitelný
    specializace NISY , libovolný ročník, zimní semestr, 5 kreditů, volitelný
    specializace NIDE , libovolný ročník, zimní semestr, 5 kreditů, volitelný
    specializace NCPS , libovolný ročník, zimní semestr, 5 kreditů, volitelný
    specializace NSEC , libovolný ročník, zimní semestr, 5 kreditů, volitelný
    specializace NMAT , libovolný ročník, zimní semestr, 5 kreditů, volitelný
    specializace NGRI , libovolný ročník, zimní semestr, 5 kreditů, volitelný
    specializace NNET , libovolný ročník, zimní semestr, 5 kreditů, volitelný
    specializace NVIZ , libovolný ročník, zimní semestr, 5 kreditů, volitelný
    specializace NSEN , libovolný ročník, zimní semestr, 5 kreditů, volitelný
    specializace NMAL , libovolný ročník, zimní semestr, 5 kreditů, volitelný
    specializace NHPC , libovolný ročník, zimní semestr, 5 kreditů, volitelný
    specializace NVER , libovolný ročník, zimní semestr, 5 kreditů, volitelný
    specializace NEMB , libovolný ročník, zimní semestr, 5 kreditů, volitelný
    specializace NADE , libovolný ročník, zimní semestr, 5 kreditů, volitelný
    specializace NSPE , libovolný ročník, zimní semestr, 5 kreditů, volitelný

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

    obor MBS , 1. ročník, zimní semestr, 5 kreditů, povinný
    obor MBI , 1. ročník, zimní semestr, 5 kreditů, povinný
    obor MIS , 1. ročník, zimní semestr, 5 kreditů, povinný
    obor MIN , 1. ročník, zimní semestr, 5 kreditů, povinný
    obor MMI , 1. ročník, zimní semestr, 5 kreditů, povinný
    obor MMM , 1. ročník, zimní semestr, 5 kreditů, povinný
    obor MGM , 1. ročník, zimní semestr, 5 kreditů, povinný
    obor MPV , 1. ročník, zimní semestr, 5 kreditů, povinný
    obor MSK , 1. ročník, zimní semestr, 5 kreditů, 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

Lukáš Duránik
doc. Mgr. Jaroslav Hrdina, Ph.D.
Mgr. Jan Pavlík, Ph.D.
prof. RNDr. Josef Šlapal, CSc.