Detail předmětu

Matematické základy informatiky

FSI-VZIAk. rok: 2009/2010

Kurz seznamuje studenty se základy matematické informatiky. Jsou diskutovány základní matematické struktury oboru, jejich vlastnosti a implementace. Jako vyjadřovacího jazyka je užito C#. Je demonstrováno praktické využití vět a důsledků při implementaci jednoduchých technický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 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ů.

Plánované vzdělávací činnosti a výukové metody

Metody vyučování závisejí na způsobu výuky a jsou popsány článkem 7 Studijního a zkušebního řádu VUT.

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.

Učební cíle

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

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.

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 M3I-P magisterský navazující

    obor M-AIŘ-3 , 1. ročník, letní semestr, povinný

  • Program M2I-P magisterský navazující

    obor M-AIŘ , 1. ročník, letní semestr, povinný
    obor M-AIŘ , 1. ročník, letní semestr, povinný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

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

Osnova

1. Úvod, základy C#.
2. Dynamické pole.
3. Seznam, fronta, zásobník, návrhy implementace.
4. Orientovaný graf, implementace orientovaného grafu.
5. Prohledávání grafu do šírky, do hloubky, smíšené prohledávání, intuitivní implementace, využití fronty a zásobníku pri implementaci prohledávání.
6. Způsoby implementace ohodnocení grafu.
7. Speciální grafové topologie (zejm. stromy, binární stromy), implementace, rámcově použití. AND-OR grafy.
8. Jazyky a gramatiky, Chomského klasifikace jazyků.
9. Automaty a gramatiky. Konečné automaty, deterministické, nedeterministické, bez zásobníku, se zásobníkem.
10. Implementace konečného automatu.
11. Turingův stroj, vyčíslitelnost, složitost algoritmu.
12. Základní pojmy teorie fuzzy množin.
13. Shrnutí probírané látky.

Cvičení s počítačovou podporou

26 hod., povinná

Vyučující / Lektor

Ing. Vít Ondroušek, Ph.D.

Osnova

1. Metodika zakládání tříd a využití polymorfizmu.
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 fronty a zásobníku. 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. Způsoby 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.