| Název: | Matematické struktury v informatice |
|---|
| Zkratka: | MAT |
|---|
| Ak.rok: | 2011/2012 |
|---|
| Semestr: | zimní |
|---|
| Studijní plán: | |
|---|
| Vyučovací jazyk: | čeština |
|---|
| Kredity: | 5 kreditů |
|---|
| Ukončení: | zkouška (písemná) |
|---|
| Výuka: | | hod./sem | přednáška | sem./cvičení | lab. cvičení | poč. cvičení | jiná |
|---|
| Rozsah: | 39 | 13 | 0 | 0 | 0 |
|---|
| | zkouška | testy | cvičení | laboratoře | ostatní |
|---|
| Body: | 80 | 20 | 0 | 0 | 0 |
|---|
|
|---|
| Garant: | Šlapal Josef, prof. RNDr., CSc., ÚM OADM |
|---|
| Fakulta: | Fakulta strojního inženýrství VUT |
|---|
| Pracoviště: | Ústav matematiky - odbor algebry a diskrétní matematiky FSI VUT |
|---|
| Prerekvizity: | |
|---|
| | | 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ů. | | Anotace: |
|---|
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ískané dovednosti, znalosti a kompetence: |
|---|
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. | | 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, konečná tělesa.
- 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.
| | 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
| | 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
| | Průběžná kontrola studia: |
|---|
Půlsemestrální písemný test. | | |
|
Fakulta informačních technologií