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

Detail předmětu

Matematické struktury v informatice

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

Aktuální akademický rok

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, anglicky

Zakončení

zkouška (písemná)

Rozsah

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

Bodové hodnocení

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

Zajišťuje ústav

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

Požadované prerekvizitní znalosti a dovednosti

Základy diskrétní matematiky.

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

Testy během semestru.
Nahoru