XP01TGR | Teorie grafů | Rozsah výuky: | 2+1 | ||
---|---|---|---|---|---|
Přednášející (garant): | Demlová M. | Typ předmětu: | S | Zakončení: | ZK |
Zodpovědná katedra: | 301 | Kreditů: | 3 | Semestr: | Z |
Anotace:
Konečné automaty. Nerodova věta a její aplikace, redukce automatu. Nedeterministické automaty též s e-přechody. Regulární výrazy a Kleeneova věta. Gramatiky a jejich klasifikace. Bezkontextové gramatiky, jejich redukce. Zásobníkové automaty. Vztah mezi zásob. automaty a bezkontextovými gramatikami. Chomského normální tvar, lemma ovkládání. Algoritmus CYK pro bezkontextové gramatiky. Turingovy stroje jako akceptory a jako počítače funkcí. Nerozhodnutelnost problému zastavení Turingova stroje. Další algoritmicky neřešitelné úlohy.
Literatura Č:
Literatura A:
|
Stránka vytvořena 14. 2. 2002, semestry: Z/2001-2, Z/2002-3, L/2001-2, L/2002-3, připomínky k informační náplni zasílejte správci studijních plánů | Návrh a realizace: I. Halaška (K336), J. Novák (K336) |