IB102 Automaty a gramatiky
prof. RNDr. Jan Strejček, Ph.D.
IB102 Automaty a gramatiky
prof. RNDr. Jan Strejček, Ph.D.
IB102 Automaty a gramatiky
Info
Course
Term
Autumn 2013
Informace o předmětu (sylabus, systém hodnocení,...)
Open
Chapter contains:
1
Study text
Literatura a jiné informační zdroje
Open
Chapter contains:
1
Folder
1
Study text
1. týden: Formální jazyky. Gramatiky. Chomského hierarchie.
Open
Chapter contains:
2
Homework Vault
5
PDF
3
Study Materials
1
Study text
Teacher recommends to study from 16/9/2013 to 22/9/2013.
2. týden: Konečné automaty. Paralelní kompozice automatů. Věta o vkládání.
Open
Chapter contains:
2
Homework Vault
5
PDF
2
Study Materials
1
Study text
Teacher recommends to study from 23/9/2013 to 29/9/2013.
3. týden: Myhill-Nerodova věta. Aplikace. Minimalizace konečných automatů.
Open
Chapter contains:
2
Homework Vault
5
PDF
2
Study Materials
1
Study text
Teacher recommends to study from 30/9/2013 to 6/10/2013.
4. týden: Nedeterministické konečné automaty. Automaty s epsilon-kroky. Uzávěrové vlastnosti regulárních jazyků. Regulární výrazy.
Open
Chapter contains:
4
ROPOT
1
PDF
1
Study text
Teacher recommends to study from 7/10/2013 to 13/10/2013.
5. týden: Vztah konečných automatů, regulárních výrazů a gramatik. Rozhodnutelné problémy pro regulární jazyky. Aplikace. Bezkontextové gramatiky. Derivační stromy.
Open
Chapter contains:
2
Homework Vault
5
PDF
2
Study Materials
1
Study text
Teacher recommends to study from 14/10/2013 to 20/10/2013.
6. a 7. týden: Redukované gramatiky. Jednoduchá pravidla a epsilon-pravidla. Chomského normální forma. Věta o vkládání pro bezkontextové jazyky.
Open
Chapter contains:
2
Homework Vault
3
ROPOT
5
PDF
2
Study Materials
1
Study text
Teacher recommends to study from 21/10/2013 to 3/11/2013.
8. týden: Přímá a nepřímá levá rekurze. Greibachové normální forma. Zásobníkové automaty, metody akceptování.
Open
Chapter contains:
4
ROPOT
1
PDF
1
Study text
Teacher recommends to study from 4/11/2013 to 10/11/2013.
9. týden: Rozšířené zásobníkové automaty. Zásobníkové automaty a bezkontextové gramatiky. Nedeterministická syntaktická analýza.
Open
Chapter contains:
2
Homework Vault
5
PDF
2
Study Materials
1
Study text
Teacher recommends to study from 11/11/2013 to 17/11/2013.
10. týden: Uzávěrové vlastnosti a (ne)rozhodnutelné problémy pro bezkontextové jazyky. Deterministické bezkontextové jazyky a jejich vlastnosti. Turingovy stroje.
Open
Chapter contains:
3
Homework Vault
7
PDF
3
Study Materials
1
Study text
Teacher recommends to study from 18/11/2013 to 24/11/2013.
11. týden: Rozhodnutelnost problémů. Problém zastavení. Redukce.
Open
Chapter contains:
2
Homework Vault
5
PDF
2
Study Materials
1
Study text
Teacher recommends to study from 25/11/2013 to 1/12/2013.
12. týden: Časová složitost algoritmů a problémů. Třídy P a NP.
Open
Chapter contains:
2
Homework Vault
5
PDF
2
Study Materials
1
Study text
Teacher recommends to study from 2/12/2013 to 8/12/2013.
13. týden: NP-úplné problémy. Prostorová složitost algoritmů a problémů. Třída PSPACE. Vztahy složitostních tříd.
Open
Chapter contains:
2
Homework Vault
5
PDF
2
Study Materials
1
Study text
Teacher recommends to study from 9/12/2013 to 15/12/2013.
14. týden: Závěrečné informace.
Open
Chapter contains:
1
Image
3
ROPOT
1
Study text
Teacher recommends to study from 16/12/2013 to 22/12/2013.
Previous
Next
Operations
View all