Detail předmětu

Matematické základy informatiky

FSI-VZI-KAk. rok: 2011/2012

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, rekapitulace pokročilejších konstrukcí C#.
2. Seznam, fronta, zásobník, návrhy reprezentace a implementace.
3. Zobecnění seznamu; orientovaný graf, reprezentace a implementace.
4. Prohledávání grafu do šířky, do hloubky, smíšené prohledávání; využití fronty a zásobníku.
5. Způsoby implementace ohodnocení grafu, prohledávání ohodnoceného grafu.
6. Speciální grafové topologie (zejm. stromy, binární stromy), reprezentace a implementace, rámcově použití. AND-OR grafy.
7. Jazyky a gramatiky, Chomského klasifikace jazyků.
8. Automaty a gramatiky, reprezentace.
9. Konečný automat bez zásobníku, reprezentace.
10. Konečný automat se zásobníkem, reprezentace.
11. Turingův stroj, vyčíslitelnost, složitost algoritmu.
12. Základní pojmy teorie fuzzy množin.
13. Shrnutí probírané látky.