Matematické základy informatiky (FSI-VZI)

Akademický rok 1999/2000
Garant: prof. RNDr. Ing. Tomáš Březina, CSc.  
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:
Důkladné seznámení se základními matematickými objekty oboru a metodikou
jejich možných implementací. Součástí kurzu je i seznámení s vhodností a
přiměřeností jejich použití v konkrétních aplikacích.
Výstupy studia a kompetence:
Kvalifikovaná tvorba a používání netriviálních objektově orientovaných
implementací základních matematických objektů oboru.
Prerekvizity:
 
Obsah předmětu (anotace):
Kurz seznamuje se základy matematické informatiky. Jsou diskutovány
základní matematické objekty oboru, jejich vlastnosti a implementace.
Jako vyjadřovacího nástroje je užito prostředí Delphi. Je demonstrováno
praktické vyuzití vět a důsledků při implementaci jednoduchých
inženýrských aplikací.
Metody vyučování:
 
Způsob a kritéria hodnocení:
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íha obvyklým způsobem.
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  14 × 3 hod. nepovinná                  
    Cvičení na počítači  14 × 2 hod. povinná                  
Osnova:
    Přednáška 1. Úvod, opakování základů Delphi.
2. Koncept výjimek a chránených bloků. Sekvencní a náhodný prístup k datům,
vlastník a uzivatel dat.
3. Seznam, návrh implementace seznamu, struktury FIFO, LIFO.
4. Kolekce, návrh implementace kolekce.
5. Orientovaný graf, implementace orientovaného grafu.
6. Prohledávání grafu do šírky, do hloubky, smíšené prohledávání,
intuitivní implementace, vyuzití struktur FIFO, LIFO pri implementaci.
7. Způsoby implementace ohodnocení grafu.
8. Speciální grafové topologie (zejm. stromy, binární stromy),
implementace, rámcově použití. AND-OR grafy.
9. Výraz (formule) jako strom, manipulace s výrazy jako manipulace
se stromy.
10. Jazyky a gramatiky, Chomského klasifikace jazyků.
11. Konečné automaty, deterministické, nedeterministické, bez zásobníku,
se zásobníkem.
12. Implementace konecného automatu.
13. Automaty a gramatiky.
14. Turingův stroj, vyčíslitelnost, složitost algoritmu.
    Cvičení na počítači 1. Metodika zakládání tříd a používání virtuálních metod.
2. Zásady zvýšení bezpečnosti kódu, oddělení režijních a datových tříd.
3. Objektová implementace seznamu (lineární sekvenční struktury).
Metodika použití.
4. Objektová implementace kolekce (lineární struktury s náhodným přístupem).
Metodika použití.
5. Objektová implementace stromu jako zobecnění implementace seznamu.
6. Objektová implementace obecného orientovaného grafu,
prohledávání grafu I.
7. Objektová implementace obecného orientovaného grafu, prohledávání
grafu II.
8. Zpusoby implementace ohodnocení grafu.
9. Prohledávání speciálních grafových topologií. Příklady využití.
10. Návrh řešení jednoduchých problémů realizovaných prohledáváním
orientovaného ohodnoceného grafu.
11. Návrh objektové implementace gramatiky, generování slov jazyka.
12. Objektová implementace konečného automatu bez zásobníku.
13. Objektová implementace konečného automatu se zásobníkem.
14. Příklady využití konečného automatu.
Literatura - základní:
4. Greenshaw, R. and Hoover, H.J.: Fundamentals of the Theory of Computation Principle and Practice. Morgan Kaufmann, 1998.
Zařazení předmětu ve studijních programech:
Program Forma Obor Spec. Typ ukončení   Kredity     Povinnost     St.     Roč.     Semestr  
M2301-5 prezenční studium Inženýrská informatika a automatizace 01 Inženýrská informatika a automatizace informatika zá,zk 6 Povinný 2 1 Z