Detail předmětu

Matematické základy informatiky

FSI-VZI-KAk. 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

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

Doporučená literatura

J.Plesník: Grafové algoritmy.
M.Chytil: Automaty a gramatiky.

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

  • Program M2I-K 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

 

Konzultace

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