Název:

Matematické struktury v informatice

Zkratka:MAT
Ak.rok:2014/2015
Semestr:zimní
Studijní plán:
ProgramOborRočníkPovinnost
IT-MGR-2MBI1.povinný
IT-MGR-2MBS1.povinný
IT-MGR-2MGM1.povinný
IT-MGR-2MIN1.povinný
IT-MGR-2MIS1.povinný
IT-MGR-2MMI1.povinný
IT-MGR-2MMM1.povinný
IT-MGR-2MPV1.povinný
IT-MGR-2MSK1.povinný
Vyučovací jazyk:čeština
Kredity:5 kreditů
Ukončení:zkouška (písemná)
Výuka:
hod./sempřednáškasem./cvičenílab. cvičenípoč. cvičeníjiná
Rozsah:3913000
 zkouškatestycvičenílaboratořeostatní
Body:8020000
Garant:Šlapal Josef, prof. RNDr., CSc., UM OADM
Přednášející:Šlapal Josef, prof. RNDr., CSc., UM OADM
Cvičící:Hrdina Jaroslav, doc. Mgr., Ph.D., UM OADM
Šlapal Josef, prof. RNDr., CSc., UM OADM
Fakulta:Fakulta strojního inženýrství VUT
Pracoviště:Ústav matematiky - odbor algebry a diskrétní matematiky FSI VUT
 
Cíle předmětu:
  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ů.
Anotace:
  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.
Získané dovednosti, znalosti a kompetence:
  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.
Osnova přednášek:
 
  • 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 typy, podalgebry a homomorfismy, kongruence a faktorové algebry, přímé součiny algeber.
  • Grupoidy a pologrupy, podgrupoidy, homomorfismy,  faktorové a volné grupoidy a pologrupy.
  • Grupy, podgrupy a homomorfismy, faktorové a cyklické grupy, volné a permutační grupy.
  • Okruhy, homomorfismy, ideály, kongruence na okruzích, tělesa.
  • Okruhy polynomů, obory integrity a dělitelnost, teorie polí, konečná (Galoisova) pole.
  • Metrické prostory, úplnost, normované a Banachovy prostory.
  • Unitární a Hilbertovy prostory, ortogonalita, uzavřené ortonormální systémy a Fourierovy řady.
  • Obyčejné grafy, souvislost, stromy a kostry, minimální kostra (Kruskalův a Primův algoritmus).
  • Eulerovské a hamiltonovské grafy, obarvitelnost, planarita.
  • Orientované grafy, orientované eulerovské a hamiltonovské grafy, turnaje, problém kritické cesty (Dijkstrův a Floyd-Warshallův algoritmus).
Literatura referenční:
 
  • Mendelson, E.: 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
  • Štěpánek, P.: Predikátová logika, MFF UK Praha, 2000 (učební text)
  • Kolmogorov, A.N., Fomin, S.V.: Základy teorie funkcí a funkcionální analýzy, SNTL, Praha, 1975, ISBN 04-014-75
  • Nešetřil J., Teorie grafů, SNTL, 1978 
Literatura studijní:
 
  • 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
  • Bondy J.A, Murty U.S.R, Graph Theory with Applications, North Holland, New York-Amsterdam-Oxford, 1979, ISBN 0444194517 
Průběžná kontrola studia:
  Půlsemestrální písemný test.