Detail předmětu

Matematické základy informatiky

FSI-VZIAk. rok: 1999/2000

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

Jazyk výuky

čeština

Počet kreditů

6

Garant předmětu

prof. RNDr. Ing. Tomáš Březina, CSc.

Zajišťuje ústav

Ústav automatizace a informatiky (ÚAI)

Výsledky učení předmětu

Kvalifikovaná tvorba a používání netriviálních objektově orientovaných
implementací základních matematických objektů oboru.

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.

Učební cíle

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.

Základní literatura

Greenshaw, R. and Hoover, H.J.: Fundamentals of the Theory of Computation Principle and Practice. 1998 (EN)

Zařazení předmětu ve studijních plánech

  • Program M2301-5 magisterský

    obor , 1. ročník, zimní semestr, povinný

Typ (způsob) výuky

 

Přednáška

42 hod., nepovinná

Vyučující / Lektor

prof. RNDr. Ing. Tomáš Březina, CSc.

Osnova

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

28 hod., povinná

Vyučující / Lektor

prof. RNDr. Ing. Tomáš Březina, CSc.

Osnova

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.