|
|
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
KVD / 9KAF
:
Popis předmětu
Pracoviště / Zkratka
|
KVD
/
9KAF
|
Akademický rok
|
2023/2024
|
Akademický rok
|
2023/2024
|
Název
|
Konečné automaty a formální jazyky
|
Způsob zakončení
|
Zkouška
|
Způsob zakončení
|
Zkouška
|
Akreditováno / Kredity
|
Ano,
1
Kred.
|
Forma zakončení
|
Kombinovaná
|
Forma zakončení
|
Kombinovaná
|
Rozsah hodin
|
Přednáška
14
[HOD/SEM]
|
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
|
Ano v případě předchozího hodnocení 4 nebo nic.
|
Počítán do průměru
|
ANO
|
Vyučovací jazyk
|
-
|
Obs/max
|
|
|
|
Automatické uznávání zápočtu před zkouškou
|
Ano v případě předchozího hodnocení 4 nebo nic.
|
Letní semestr
|
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ů
|
10
|
Volně zapisovatelný předmět |
Ano
|
Volně zapisovatelný předmět
|
Ano
|
Vyučovací jazyk
|
-
|
Počet dnů praxe
|
0
|
Počet hodin kontaktní výuky |
|
Hodnotící stupnice |
1|2|3|4 |
Periodicita |
každý rok
|
Hodnotící stupnice pro zp. před zk. |
S|N |
Periodicita upřesnění |
|
Základní teoretický předmět |
Ne
|
Profilující předmět |
Ne
|
Základní teoretický předmět |
Ne
|
Hodnotící stupnice |
1|2|3|4 |
Hodnotící stupnice pro zp. před zk. |
S|N |
Nahrazovaný předmět
|
KVD/CKAF
|
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):
|
Konečné automaty: Způsoby reprezentace, činnost. Deterministické a nedeterministické automaty. Automaty bez výstupu a s výstupem. Ekvivalence automatů. Formální jazyky: Definice jazyka. Jazyky rozpoznatelné konečnými automaty. Gramatiky. Klasifikace gramatik a formálních jazyků. Regulární výrazy, gramatiky a jazyky. Převod regulárního výrazu na automat. Základy teorie bezkontextových jazyků. Zásobníkové automaty a bezkontextové jazyky.
|
Požadavky na studenta
|
Úspěšné vypracování zadaného projektu
|
Obsah
|
1. Deterministický konečný automat bez výstupu. Řetězec, délka řetězce, zřetězení slov. 2. Klasifikační automat. Činnost automatu 3. Způsoby reprezentace konečných automatů. Nedeterministický konečný automat 4. Rozpoznávání řetězců nedeterministickým konečným automatem 5. Konfigurace automatu. Převod nedeterministického konečného automatu na deterministický. 6. Deterministický konečný automat s výstupem. Iniciální automat s výstupem 7. Redukce konečného automatu. Ekvivalence automatů 8. Formální jazyky. Jazyky rozpoznatelné konečnými automaty 9. Gramatiky. Klasifikace gramatik. Nerodova věta 10. Regulární jazyky a gramatiky. Regulární množiny. Regulární výrazy 11. Převod regulárního výrazu na konečný automat. Převod nedeterministického konečného automatu na regulární výraz. 12. Přechodové grafy. Kleenova věta. Vztah regulárních gramatik, regulárních jazyků a konečných automatů. 13. Bezkontextové jazyky a gramatiky. Zásobníkový automat. Normální tvary bezkontextových gramatik
|
Aktivity
|
|
Studijní opory
|
|
Garanti a vyučující
|
|
Literatura
|
-
Doporučená:
Demlová, Marie; Koubek, Václav. Algebraická teorie automatů. Praha : SNTL, 1990. ISBN 80-03-00348-2.
-
Doporučená:
Chytil, Michal. Automaty a gramatiky. Praha : SNTL, 1984.
-
Doporučená:
Molnár, Ludovít; Melichar, Bořivoj; Češka, Milan. Gramatiky a jazyky. Bratislava : Alfa, 1987.
-
Doporučená:
Manna, Zohar. Matematická teorie programů. Praha : SNTL, 1981.
-
Doporučená:
Kocur, Pavel. Úvod do teorie konečných automatů a formálních jazyků. Plzeň : Západočeská univerzita, 2001. ISBN 80-7082-813-7.
-
On-line katalogy knihoven
|
Předpoklady
|
Odborné znalosti - pro úspěšné zvládnutí předmětu se předpokládá, že je student před zahájením výuky schopen: |
nejsou předepsány žádné specifické předpoklady |
|
Výsledky učení
|
|
Hodnoticí metody
|
|
Vyučovací metody
|
|
|
|
|