|
|
Hlavní nabídka Prohlížení IS/STAG
Nalezené předměty, počet: 1
Stránkování výsledků vyhledávání
Nalezeno 1 záznamů
Export do Xls
Informace o předmětu
KMF / NNTEI
:
Popis předmětu
Pracoviště / Zkratka
|
KMF
/
NNTEI
|
Akademický rok
|
2023/2024
|
Akademický rok
|
2023/2024
|
Název
|
Teoretická informatika
|
Způsob zakončení
|
Zkouška
|
Způsob zakončení
|
Zkouška
|
Akreditováno / Kredity
|
Ano,
5
Kred.
|
Forma zakončení
|
Kombinovaná
|
Forma zakončení
|
Kombinovaná
|
Rozsah hodin
|
Přednáška
2
[HOD/TYD]
Cvičení
2
[HOD/TYD]
|
Zápočet před zkouškou
|
Ano
|
Zápočet před zkouškou
|
Ano
|
Automatické uznávání zápočtu před zkouškou
|
Ne
|
Počítán do průměru
|
ANO
|
Vyučovací jazyk
|
Čeština
|
Obs/max
|
|
|
|
Automatické uznávání zápočtu před zkouškou
|
Ne
|
Letní semestr
|
16 / -
|
0 / 0
|
0 / 0
|
Počítán do průměru
|
ANO
|
Zimní semestr
|
0 / -
|
0 / -
|
0 / -
|
Opakovaný zápis
|
NE
|
Opakovaný zápis
|
NE
|
Rozvrh
|
Ano
|
Vyučovaný semestr
|
Letní semestr
|
Vyučovaný semestr
|
Letní semestr
|
Minimum (B + C) studentů
|
nestanoveno
|
Volně zapisovatelný předmět |
Ano
|
Volně zapisovatelný předmět
|
Ano
|
Vyučovací jazyk
|
Čeština
|
Počet dnů praxe
|
0
|
Počet hodin kontaktní výuky |
0
|
Hodnotící stupnice |
A|B|C|D|E|F |
Periodicita |
každý rok
|
Hodnotící stupnice pro zp. před zk. |
S|N |
Periodicita upřesnění |
|
Základní teoretický předmět |
Ano
|
Profilující předmět |
Ne
|
Základní teoretický předmět |
Ano
|
Hodnotící stupnice |
A|B|C|D|E|F |
Hodnotící stupnice pro zp. před zk. |
S|N |
Nahrazovaný předmět
|
KMF/INTEI
|
Vyloučené předměty
|
Nejsou definovány
|
Podmiňující předměty
|
Nejsou definovány
|
Předměty informativně doporučené
|
Nejsou definovány
|
Předměty,které předmět podmiňuje
|
Nejsou definovány
|
Graf četnosti udělených hodnocení studentům napříč roky:
Obrázek PNG
,
XLS
|
Cíle předmětu (anotace):
|
Cílem předmětu je seznámit studenty s některými nosnými oblastmi teoretické informatiky. Získané znalosti jsou orientované na: analýzu textů programu zapsaného ve zvoleném programovacím jazyce, kompilátory, využití Turingových strojů, problém rozhodnutelnosti a problematiku složitosti algoritmů.
|
Požadavky na studenta
|
Podmínkou k udělení zápočtu je aktivní účast na cvičení a úspěšné zpracování semestrálních prací. Předmět je zakončen zkouškou. Aktivní účast na cvičení lze nahradit vypracováním úkolů.
|
Obsah
|
1. Úvod do teorie jazyků a gramatik, historie, základní pojmy.
2. Regulární výrazy a regulární množiny.
3. Využití regulárních výrazů, praktická práce s regulárními výrazy.
4. Regulární jazyk (podle Chomského klasifikace - jazyk typu 3), využití regulárních výrazů při definici pravidel regulárního jazyka.
5. Konečný automat jako nástroj pro vytvoření lexikálního analyzátoru - scanneru.
6. Bezkontextový jazyk (podle Chomského klasifikace - jazyk typu 2). Vlastnosti bezkontextových jazyků.
7. Derivační strom jako prostředek pro grafické vyjádření struktury věty. Chomského a Greibachové normální forma.
8. Zásobníkový automat a jeho vztah k bezkontextové gramatice. Využití zásobníkového automatu při tvorbě syntaktického analyzátoru parseru.
9. Turingovy stroje (TS).
10. Grafická reprezentace TS, modulární konstrukce, základní stavební bloky TS.
11. Použití TS jako akceptoru jazyků. Jazyk přijímaný TS. Modifikace TS. Turingovy stroje a jazyky typu 0.
12. Různé problémy a meze rozhodnutelnosti související s TS.
13. Složitost algoritmu, polynomiální převoditelnost a nezvládnutelné problémy.
|
Aktivity
|
|
Studijní opory
|
|
Garanti a vyučující
|
-
Garanti:
doc. Ing. Tomáš Brandejský, Dr. ,
RNDr. Josef Rak, Ph.D. ,
-
Přednášející:
doc. Ing. Tomáš Brandejský, Dr. (100%),
RNDr. Josef Rak, Ph.D. (100%),
-
Cvičící:
Ing. Roman Diviš, Ph.D. (100%),
Ing. Marie Nedvědová (100%),
RNDr. Josef Rak, Ph.D. (100%),
|
Literatura
|
-
Základní:
MAREŠ, Jan. Jazyky, gramatiky a automaty. 2. vyd.. Praha, 2011. ISBN 978-8001-04904-4.
-
Doporučená:
LINZ, Peter. An introduction to formal languages and automata. Sixth edition.. Burlington, 2017. ISBN 9781284077247.
-
Doporučená:
JOHN E. HOPCROFT, Rajeev MOTWANI a JEFFREY D. ULLMAN. Introduction to automata theory, languages, and computation. 3. ed.. Pearson Addison-Wesley, 2014. ISBN 9781292039053.
|
Časová náročnost
|
Prezenční forma studia
|
Aktivity
|
Časová náročnost aktivity [h]
|
Domácí příprava na výuku
|
20
|
Příprava na zkoušku
|
33
|
Semestrální práce
|
45
|
Kontaktní výuka
|
52
|
Celkem
|
150
|
|
Předpoklady - další informace k podmíněnosti studia předmětu |
Předpokládají se základní znalosti matematiky, algoritmizace, programování a datových struktur. |
Získané způsobilosti |
Absolvování předmětu jsou získány základní informace z teorie jazyků, Turingových strojů, složitosti algoritmů a problému rozhodnutelnosti. |
Vyučovací metody |
- Monologická (výklad, přednáška, instruktáž)
- Dialogická (diskuze, rozhovor, brainstorming)
- Nácvik dovedností
|
Hodnotící metody |
- Ústní zkouška
- Posouzení zadané práce
|
|
|
|