Detail předmětu
Matematické základy informatiky
FSI-VZI-KAk. rok: 2016/2017
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ů
4
Garant předmětu
Zajišťuje ústav
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
Předmět je vyučován formou přednášek, které mají charakter výkladu základních principů a teorie dané disciplíny. Cvičení je zaměřeno na praktické zvládnutí látky probrané na přednáškách.
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.
M.Chytil: Automaty a gramatiky.
Zařazení předmětu ve studijních plánech
Typ (způsob) výuky
Konzultace
17 hod., nepovinná
Vyučující / Lektor
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.
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.