IB102 Automaty, gramatiky a složitost
prof. RNDr. Jan Strejček, Ph.D.
IB102 Automaty, gramatiky a složitost
prof. RNDr. Jan Strejček, Ph.D.
IB102 Automaty, gramatiky a složitost
Info
Course
Term
Autumn 2014
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 15/9/2014 to 21/9/2014.
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 22/9/2014 to 28/9/2014.
3. týden: Minimalizace konečných automatů. Nedeterministické konečné automaty. Automaty s epsilon-kroky. Uzávěrové vlastnosti regulárních jazyků.
Open
Chapter contains:
1
Homework Vault
1
ROPOT
3
PDF
1
Study Materials
1
Study text
Teacher recommends to study from 29/9/2014 to 5/10/2014.
4. týden: Regulární výrazy. Vztah konečných automatů, regulárních výrazů a gramatik. Rozhodnutelné problémy pro regulární jazyky. Aplikace.
Open
Chapter contains:
1
Homework Vault
3
ROPOT
3
PDF
1
Study Materials
1
Study text
Teacher recommends to study from 6/10/2014 to 12/10/2014.
5. týden: Bezkontextové gramatiky. Derivační stromy. Redukované gramatiky. Jednoduchá pravidla a epsilon-pravidla.
Open
Chapter contains:
1
Homework Vault
3
ROPOT
3
PDF
1
Study Materials
1
Study text
Teacher recommends to study from 13/10/2014 to 19/10/2014.
6. týden: Chomského normální forma. Věta o vkládání pro bezkontextové jazyky. Přímá a nepřímá levá rekurze. Greibachové normální forma. Zásobníkové automaty.
Open
Chapter contains:
2
Homework Vault
11
ROPOT
5
PDF
2
Study Materials
1
Study text
Teacher recommends to study from 20/10/2014 to 26/10/2014.
7. týden: Rozšířené zásobníkové automaty. Zásobníkové automaty a bezkontextové gramatiky. Nedeterministická syntaktická analýza shora dolů.
Open
Chapter contains:
1
PDF
1
Study text
Teacher recommends to study from 27/10/2014 to 2/11/2014.
8. týden: Nedeterministická syntaktická analýza zdola nahoru. Uzávěrové vlastnosti a (ne)rozhodnutelné problémy pro bezkontextové jazyky. Deterministické bezkontextové jazyky a jejich vlastnosti. Aplikace bezkontextových jazyků.
Open
Chapter contains:
2
Homework Vault
5
PDF
2
Study Materials
1
Study text
Teacher recommends to study from 3/11/2014 to 9/11/2014.
9. a 10. týden: Turingovy stroje. Rekursivní a rekursivně spočetné jazyky. Rozhodnutelnost problémů. Problém zastavení.
Open
Chapter contains:
4
Homework Vault
9
PDF
4
Study Materials
1
Study text
Teacher recommends to study from 10/11/2014 to 23/11/2014.
11. týden: Redukce
Open
Chapter contains:
2
Homework Vault
5
PDF
2
Study Materials
1
Study text
Teacher recommends to study from 24/11/2014 to 30/11/2014.
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 1/12/2014 to 7/12/2014.
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 8/12/2014 to 14/12/2014.
14. týden: Myhill-Nerodova věta
Open
Chapter contains:
1
Image
3
ROPOT
1
PDF
1
Study text
Teacher recommends to study from 15/12/2014 to 21/12/2014.
Previous
Next
Operations
View all