Matematické základy informatiky (FSI-VZI-A)

Akademický rok 2022/2023
Garant: prof. RNDr. Ing. Miloš Šeda, Ph.D.  
Garantující pracoviště: ÚAI všechny předměty garantované tímto pracovištěm
Jazyk výuky: angličtina
Cíle předmětu:
Cílem předmětu je seznámit studenty se základními matematickými strukturami oboru a metodikou jejich možných implementací. To je úvodem do vhodností a přiměřeností jejich použití.
Výstupy studia a kompetence:
Kvalifikovaná tvorba a používání netriviálních objektově orientovaných implementací základních matematických struktur oboru.
Prerekvizity:
Předpokládá se znalost algoritmizace, strukturovaného přístupu k řešení problémů a znalost metodiky tvorby neobjektových programů.
Obsah předmětu (anotace):
Kurz seznamuje studenty se základy matematické informatiky. Jsou diskutovány formální jazyky a gramatiky a nástroje pro zpracování slov v těchto jazycích.
Dalším tématem je predikátový počet, metody dokazování pravdivosti logických formulí a klasifikace složitosti problémů s vymezením tříd P a NP.
Jako vyjadřovacího jazyka je užito C/Python. Je demonstrováno praktické využití vět a důsledků při implementaci jednoduchých technických aplikací.
Kurz završují základy teorie grafů, zahrnují algoritmy prohledávání grafů, eulerovských tah a hamiltonovských cest, hledání nejkratší cesty, minimální kostry, toků v sítích, barvení grafů a aplikace struktur počítačové geometrie.
Metody vyučování:
Předmět je vyučován formou přednášek, které mají charakter výkladu základních principů a teorie dané disciplíny. Cvičení je zaměřeno na praktické zvládnutí látky probrané na přednáškách.
Způsob a kritéria hodnocení:
Požadavky k zápočtu: je vyžadován samostatně vypracovaný softwarový projekt, který důsledně používá přednášených metodik. Zpracování projektu je kontrolováno a konzultováno průběžně. Zkouška probíhá obvyklým způsobem.
Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky:
Účast na přednáškách je žádoucí, na cvičeních povinná. Výuka běží podle týdenních plánů. Způsob nahrazení zameškaných cvičení je plně v kompetenci vyučujícího.
Typ (způsob) výuky:
    Přednáška  13 × 4 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. Greenshaw, R. and Hoover, H.J.: Fundamentals of the Theory of Computation Principle and Practice. Morgan Kaufmann, 1998.
2. Jungnickel, D: Graphs, networks and algorithms, 4th edition. Springer Berlin, Heidelberg, 2013.
3. Meduna, A., Švec, M.: Grammars with context conditions and their applications. Wiley, 2005.
Zařazení předmětu ve studijních programech:
Program Forma Obor Spec. Typ ukončení   Kredity     Povinnost     St.     Roč.     Semestr  
N-ENG-Z příjezd na krátkodobý studijní pobyt --- bez specializace -- zá,zk 6 Volitelný 2 1 Z