Fakulta informačních technologií VUT v Brně

Detail předmětu

Matematické struktury v informatice

MAT Ak. rok 2006/2007 zimní semestr 5 kreditů

Formální teorie, predikátová logika, intuicionistická, modální a temporální logika, algebraické struktury s jednou a dvěma binárními operacemi, univerzální algebry, topologické a metrické prostory, Banachovy a Hilbertovy prostory, neorientované grafy, orientované grafy a sítě, základní pojmy z teorie kategorií.

Garant předmětu

Jazyk výuky

česky

Zakončení

zkouška (písemná)

Rozsah

39 hod. přednášky, 13 hod. cvičení

Bodové hodnocení

80 zkouška, 20 půlsemestrální test

Přednášející

Získané dovednosti, znalosti a kompetence z předmětu

Studenti prohloubí své znalosti z oblasti matematických struktur využívaných v informatice. 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.

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 klasických algebraických struktur budou podrobněji vyloženy základy matematické logiky, teorie Banachových a Hilbertových prostorů a teorie grafů. Probrán bude také úvod do teorie kategorií.

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

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

Osnova přednášek

  • Predikáty, kvantifikátory, termy, formule, jazyk 1. řádu a jeho interpretace, modely formulí.
  • Predikátový počet 1. řádu a jeho vlastnosti, věty o úplnosti a kompaktnosti, rozšíření teorie.
  • Prenexové normální tvary, skolemizace a Herbrandova věta, základy intuicionistické, modální a temporální logiky.
  • Univerzální algebry a jejich typy, podalgebry a homomorfismy, kongruence a faktorové algebry, součiny, termy a volné algebry.
  • Parciální a vícedruhové algebry, hyperalgebry, grupoidy, podgrupoidy a homomorfismy, kartézský součin, faktorové a volné grupoidy.
  • Pologrupy a volné pologrupy, grupy, podgrupy a homomorfismy, faktorové a cyklické grupy, volné a permutační grupy.
  • Okruhy, ideály, homomorfismy, obory integrity a tělesa.
  • Konečná tělesa, polynomy a dělitelnost.
  • Topologické a 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, sítě, problém kritické cesty (Dijkstraův a Floyd-Warshallův algoritmus), dopravní sítě, toky a řezy.
  • Kategorie a konkrétní kategorie, podobjekty, faktorové a volné objekty, součiny a sumy, funktory a přirozené transformace.

Průběžná kontrola studia

Test během semestru a odevzdání domácí úlohy.

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

Nahoru