Matematické základy informatiky (FSI-VZI)

Akademický rok 2025/2026
Garant: doc. Ing. Jakub Kůdela, Ph.D.  
Garantující pracoviště: ÚAI všechny předměty garantované tímto pracovištěm
Jazyk výuky: čeština
Cíle předmětu:
 
Výstupy studia a kompetence:
 
Prerekvizity:
 
Obsah předmětu (anotace):
 
Metody vyučování:
 
Způsob a kritéria hodnocení:
 
Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky:
 
Typ (způsob) výuky:
    Přednáška  13 × 3 hod. nepovinná                  
    Cvičení s počítačovou podporou  13 × 2 hod. povinná                  
Osnova:
    Přednáška 1. Úvod.
2. Seznam, fronta, zásobník, návrhy reprezentace a implementace.
3. Prohledávání grafu do šířky, do hloubky, smíšené prohledávání; využití fronty a zásobníku. rámcově použití. AND-OR grafy.
4. Eulerovské tahy, hamiltonovské cesty.
5. Nejkratší cesta, minimální kostra.
6. Toky v sítích, barvení grafu.
7. Voroného diagramy a Delaunayho triangulace.
8. Formální jazyky a gramatiky, Chomského klasifikace.
9. Regulární gramatiky a konečné automaty.
10. Bezkontextové gramatiky a zásobníkové automaty.
11. Turingův stroj, vyčíslitelnost, složitost algoritmu.
12. Třídicí/řadicí algoritmy
13. Shrnutí probírané látky.
    Cvičení s počítačovou podporou 1. Zásady zvýšení bezpečnosti kódu, oddělení režijních a datových tříd.
2. Implementace seznamu.
3. Implementace fronty a zásobníku.
4. Implementace stromu.
5. Implementace obecného orientovaného grafu, prohledávání I.
6. Implementace obecného orientovaného grafu, prohledávání II, hledání cesty.
7. Implementace ohodnocení grafu; příklady využití.
8. Prohledávání speciálních grafových topologií; příklady využití.
9. Návrh řešení jednoduchých problémů realizovaných prohledáváním orientovaného ohodnoceného grafu.
10. Implementace konečného automatu bez zásobníku.
11. Implementace konečného automatu se zásobníkem.
12. Implementace lingvistické proměnné, implikace.
13. Zápočet.
Literatura - základní:
1. Češka, M., Vojnar, T.: Studijní text k předmětu Teoretická informatika, 2020 (http://www.fit.vutbr.cz/study/courses/TIN/public/Texty/TIN-studijni-text.pdf).
2. Sipser, M.: Introduction to the Theory of Computation, 3rd edition. Cengage Learning, 2013.
3. Jungnickel, D: Graphs, networks and algorithms, 4th edition. Springer Berlin, Heidelberg, 2013.
4. Greenshaw, R. and Hoover, H.J.: Fundamentals of the Theory of Computation Principle and Practice. Morgan Kaufmann, 1998.
5. Meduna, A., Švec, M.: Grammars with context conditions and their applications. Wiley, 2005.
6. Matoušek, J., Nešetřil, J.: Kapitoly z diskrétní matematiky. 3., upr. a dopl. vyd. V Praze: Karolinum, 2007.
Literatura - doporučená:
1. Meduna, A.: Formal Languages and Computation. New York, Taylor & Francis, 2014.
2. Brookshear, J.G. : Theory of Computation: Formal Languages, Automata, and Complexity, The Benjamin/Cummings Publishing Company, Inc, Redwood City, California, 1989.
Zařazení předmětu ve studijních programech:
Program Forma Obor Spec. Typ ukončení   Kredity     Povinnost     St.     Roč.     Semestr  
N-AIŘ-P prezenční studium --- bez specializace -- zá,zk 6 Povinný 2 1 Z