Vysoká škola báňská - Technická univerzita Ostrava
ÚVOD DO TEORETICKÉ INFORMATIKY
Petr Jančar
Konečné automaty a regulární jazyky
| 1. Rozpoznávání jazyka | Motivace k zavedení konečných automatů. Na příkladu jazyka všech slov se sudým počtem symbolů 1 je ukázáno, jak by mohlo probíhat rozhodování o příslušnosti slova k jazyku. autor: Zdeněk Sawa |
|
| 2. Vyhledávání v textu | Jednoduchý algoritmus pro vyhledávání řezězce v textu. autor: Zdeněk Sawa |
|
| 3. Definice konečného automatu | Definice konečného automatu, konfigurací a přijímání slova konečným automatem. Ukázka přijímajícího i nepřijímajícího běhu včetně výpisu posloupnosti konfigurací. autor: Martin Kot |
|
| 4. Automat pro průnik jazyků | Ukázka, jak je možné k dvěma zadaným konečným automatům sestrojit konečný automat přijímající průnik jazyků dvou zadaných konečných automatů. autor: Martin Kot |
|
| 5. Automat pro sjednocení jazyků | Ukázka, jak je možné k dvěma zadaným konečným automatům sestrojit konečný automat přijímající sjednocení jazyků dvou zadaných konečných automatů. autor: Martin Kot |
|
| 6. Automat pro doplněk jazyka | Ukázka, jak je možné k zadanému konečnému automatu sestrojit konečný automat přijímající doplněk jazyka zadaného konečného automatu. Dále animace ukazuje, proč nemůžeme stejným způsobem obecně získat doplněk k jazyku přijímanému nedeterministickým konečným automatem. autor: Martin Kot |
|
| 7. Zřetězení regulárních jazyků | Motivační přiklad pro zavedení zobecněných nedeterministických automatů. V animaci se snažíme sestrojit automat pro zřetězení dvou regulárních jazyků. Nejprve je ukázáno, proč obecně nefunguje myšlenka, kdy se spojí přijímající stav automatu pro první jazyk s počátečním stavem automatu pro druhý jazyk. Potom je sestrojen ZNKA a je předvedeno jak příjme dva slova z požadovaného zřetězení jazyků. autor: Martin Kot |
|
| 8. Nedeterministický konečný automat | Ukázka různých výpočtů jednoho nedeterministického automatu nad jedním slovem. Příklad neúplného výpočtu, úplného nepřijímajícího i úplného přijímajícího výpočtu. autor: Martin Kot |
|
| 9. Zobecněný nedeterministický konečný automat | Ukázka různých výpočtů různých zobecněných nedeterministických automatů nad jedním slovem. autor: Martin Kot |
|
| 10. Převod NKA na DKA | Ukázka převodu nedeterministického konečného automatu na deterministický, realizováno nejprve pomocí grafu automatu, potom tabulkou. autor: Martin Kot |
|
| 11. Převod ZNKA na DKA | Příklad převodu zobecněného nedeterministického konečného automatu na deterministický konečný automat. autoři: Martin Kot, Zdeněk Sawa |
|
| 12. Normovaný tvar konečného automatu | Příklad převodu dvou konečných automatů do normovaného tvaru. autor: Martin Kot |
|
| 13. Minimalizace konečného automatu | Vysvětlení postupu minimalizace konečného automatu - odstranění nedosažitelných stavů a ekvivalentních stavů. autoři: Libor Bravenec, Petr Jančar |
|
| 14. Minimalizace konečného automatu | Příklad minimalizace konečného automatu. autoři: Libor Bravenec, Martin Kot, Petr Jančar |
|
| 15. Převod RV na ZNKA | Vysvětlení mechanické konstrukce zobecněného nedeterministického konečného automatu k zadanému regulárnímu výrazu. autoři: Martin Faltýnek, Martin Kot, Petr Jančar |
|
| 16. Převod RV na ZNKA | Ukázka základních kroků konstrukce zobecněného nedeterministického konečného automatu k zadanému regulárnímu výrazu a přiklad převodu jednoho výrazu. autor: Zdeněk Sawa |
|
| 17. Převod KA na RV | Vysvětlení mechanické konstrukce regulárního výrazu k danému konečnému automatu. Konstrukce využívá automat s hranami označenými regulárními výrazy a postupně se zjednodušuje automatu až do situace, kdy má jen jednu hranu označenou výsledným RV. autoři: Martin Faltýnek, Martin Kot, Petr Jančar |
|
| 18. Převod KA na RV | Příklad převodu konečného automatu na regulární výraz. autor: Zdeněk Sawa |
Bezkontextové gramatiky a zásobníkové automaty
| 19. Odvození slova v gramatice | Ukázka derivace (odvození) jednoho slova v bezkontextové gramatice. autor: Zdeněk Sawa |
|
| 20. Derivační strom | Ukázka tvorby derivačního stromu odpovídajícího jedné konkrétní derivaci. autor: Zdeněk Sawa |
|
| 21. Výpočet zásobníkového automatu | Ukázky výpočtů dvou různých zásobníkových automatů (jednoho deterministického a jednoho nedeterministického) nad různými slovy. autor: Martin Kot |
Výpočetní modely
| 22. Turingův stroj | Definice Turingova stroje a ukázky výpočtů dvou Turingových strojů. autor: Martin Kot |
|
| 23. Turingův stroj | Popis Turingova stroje. Ukázka TS, který za slovo na vstupu přidá jeho zrcadlový obraz. autoři: Michal Hrančík, Petr Jančar |
|
| 24. Turingův stroj | Popis Turingova stroje. Ukázka TS, který zdvojí slovo na vstupu. autoři: Michal Hrančík, Petr Jančar |
|
| 25. Stroj RAM | swf | Ukázka stroje RAM, který načte posloupnost čísel ze vstupu, spočítá jejich aritmetický průměr (zaokrouhlený dolů) a vypíše odchylky vstupních čísel od tohoto průměru. autoři: František Novák, Petr Jančar |
NP-úplné problémy
| 26. Převod SAT na 3-SAT | Algoritmus převodu problému splnitelnosti booleovských formulí na problém splnitelnosti booleovských formulí se třemi literály v každé klauzuli. autor: Zdeněk Sawa |
|
| 27. Převod 3-SAT na 3-CG | swf | Algoritmus převodu problému splnitelnosti booleovských formulí se třemi literály v každé klauzuli na problém barvení grafu třemi barvami. autoři: František Novák, Petr Jančar |
| 28. Převod 3-SAT na IS | swf | Algoritmus převodu problému splnitelnosti booleovských formulí se třemi literály v každé klauzuli na problém nezávislé množiny. autoři: František Novák, Petr Jančar |
| 29. Převod HC na HK | Algoritmus převodu problému Hamiltonovského cyklu na problém Hamiltonovské kružnice. autor: Martin Kot |
Aproximační algoritmy
| 30. Vrcholové pokrytí | Aproximační algoritmus pro hledání vrcholového pokrytí v grafu s maximálně dvojnásobným počtem vrcholů než má minimální pokrytí. autor: Zdeněk Sawa |
|
| 31. Problém obchodního cestujícího | Aproximační algoritmus pro hledání cesty obchodního cestujícího s maximálně dvojnásobnou délkou než má minimální. autor: Zdeněk Sawa |
Zpracováno za podpory projektu ESF OP RLZ:
CZ.O4.01.3/3.2.15.2/0326 E-learningové prvky pro podporu výuky odborných a technických předmětů