|
Program cvičení:
- Procvičení základních jazykových operací; speciálně pak operace kvocientu. Návrh konečných automatů pro jednoduché jazyky a konstrukce
složitějších automatů z jednodušších.
- Procvičení algoritmů pro převod do normovaného tvaru a zjišťování izomorfismu automatů. Procvičení algoritmu minimalizace. Důkazy neregularity
konkrétních jazyků.
- Návrh nedeterministických konečných automatů, převod na deterministické. Procvičení regulárních výrazů jako prostředku popisu regulárních jazyků.
- Převody mezi konečnými automaty, regulárními výrazy a regulárními gramatikami. Procvičení uzávěrových vlastností třídy regulárních jazyků.
- Návrh konkrétních bezkontextových gramatik. Převod konkrétních (nejednoznačných) gramatik na jednoznačné. Procvičení algoritmů redukce a odstranění epsilon-pravidel.
- Konstrukce zásobníkových automatů. Převody mezi bezkontextovými gramatikami a zásobníkovými automaty. Návrhy deterministických zásobníkových automatů.
Procvičení uzávěrových vlastností třídy bezkontextových jazyků.
- Převod gramatik do Chomského normální formy. Důkazy nebezkontextovosti jazyků pomocí pumping lemmatu. Konstrukce Turingových strojů.
- Procvičení porovnání asymptotického růstu konkrétních funkcí. Návrh a analýza složitosti konkrétních (polynomiálních) algoritmů.
- Procvičení několika obecných metod návrhu polynomiálních algoritmů. Návrh vzájemné simulace mezi konkrétními výpočetními modely.
- Návrh nedeterministických polynomiálních algoritmů. Prokázání polynomiální převeditelnosti mezi konkrétními problémy.
- Prokazování příslušnosti jednotlivých problémů k PTIME, NPTIME, PSPACE, NPSPACE a prokazování NP- a PSPACE-obtížnosti.
- Konstrukce částí univerzálního Turingova stroje. Důkazy nerozhodnutelnosti problémů. Aplikace Riceovy věty.
- Procvičení vybraných témat z aproximačních a pravděpodobnostních algoritmů.
- Rezerva.
Odkazy:
|
|
