Uvítáme odezvu od návštěvníků této stránky. Pokud v animacích objevíte nějaké chyby nebo nejasnosti nebo budete mít návrhy na vylepšení animací a vytvoření dalších, kontaktujte, prosím, e-mailem .
Některé animace byly v minulosti studenty v rámci diplomových prací vytvořeny pomocí Adobe Flash. Protože podpora přehrávače Adobe Flash Player před několika lety skončila, tyto animace se v seznamu níže nezobrazují. Je možné se ale přepnout na stránku, kde jsou uvedeny i ony.
| 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. | |
| 2. Vyhledávání v textu | Jednoduchý algoritmus pro vyhledávání řetězce v textu. | |
| 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í. | |
| 4. Automat pro průnik jazyků | Ukázka, jak je možné pro dva zadané konečné automaty sestrojit konečný automat přijímající průnik jazyků přijímaných těmi zadanými. | |
| 5. Automat pro sjednocení jazyků | Ukázka, jak je možné pro dva zadané konečné automaty sestrojit konečný automat přijímající sjednocení jazyků přijímaných těmi zadanými. | |
| 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. | |
| 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ů. | |
| 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. | |
| 9. Výpočet NKA | Ukázka 2 výpočtů jednoho nedeterministického konečného automatu nad jedním slovem. | |
| 10. 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. | |
| 11. 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. | |
| 12. Převod ZNKA na DKA | Příklad převodu zobecněného nedeterministického konečného automatu na deterministický konečný automat. | |
| 13. Normovaný tvar konečného automatu | Příklad převodu dvou konečných automatů do normovaného tvaru. | |
| 14. Minimalizace konečného automatu | Vysvětlení postupu minimalizace konečného automatu - odstranění nedosažitelných stavů a nahrazení množin ekvivalentních stavů jejich reprezentanty. autor: Libor Bravenec |
|
| 15. Minimalizace konečného automatu | Příklad minimalizace konečného automatu. autor: Libor Bravenec |
|
| 16. 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 |
|
| 17. 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. | |
| 18. 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, který se postupně transformuje až do situace, kdy má jen jednu hranu označenou výsledným RV. autoři: Martin Faltýnek, Martin Kot |
|
| 19. Převod KA na RV | Příklad převodu konečného automatu na regulární výraz. | |
| 20. Regulární operace | Konstrukce konečných automatů pro zřetězení, iteraci a sjednocení jazyků zadaných konečnými automaty. |
| 21. Odvození slova v gramatice | Ukázka derivace (odvození) jednoho slova v bezkontextové gramatice. | |
| 22. Derivační strom | Ukázka tvorby derivačního stromu odpovídajícího jedné konkrétní derivaci. | |
| 23. 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. | |
| 24. Redukce bezkontextové gramatiky | Vysvětlení postupu redukce bezkontextové gramatiky. | |
| 25. Nevypouštějící bezkontextová gramatika | Vysvětlení postupu převodu bezkontextové gramatiky na tzv. nevypouštějící, tedy neobsahující pravidla s epsilon na pravé straně. |
| 26. Turingův stroj | Definice Turingova stroje a ukázky výpočtů dvou Turingových strojů. | |
| 27. Turingův stroj | Popis Turingova stroje. Ukázka TS, který za slovo na vstupu přidá jeho zrcadlový obraz. autor: Michal Hrančík |
|
| 28. Turingův stroj | Popis Turingova stroje. Ukázka TS, který zdvojí slovo na vstupu. autor: Michal Hrančík |
|
| 29. Vícepáskový Turingův stroj | Popis vícepáskového Turingova stroje. Ukázka dvoupáskového TS, který na výstupní pásku umístí zdvojené vstupní slovo. autor: Michal Hrančík |
| 30. NP-úplnost problému SAT | Důkaz tzv. Cookovy věty, tedy NP-úplnosti problému SAT. | |
| 31. 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. | |
| 32. Převod 3-SAT na ILP | Algoritmus převodu problému splnitelnosti booleovských formulí se třemi literály v každé klauzuli na problém celočíselného lineárního programování. | |
| 33. Převod 3-SAT na Subset-Sum | Algoritmus převodu problému splnitelnosti booleovských formulí se třemi literály v každé klauzuli na problém Subset-sum (rozhodování, zda z dané množiny celých čísel je možné vybrat podmnožinu s daným součtem). | |
| 34. Převod IS na HC | Algoritmus převodu problému nezávislé množiny na problém Hamiltonovského cyklu. autoři: Michal Hrančík, Martin Kot |
|
| 35. Převod HC na HK | Algoritmus převodu problému Hamiltonovského cyklu na problém Hamiltonovské kružnice. |
| 36. 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í. | |
| 37. 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í. |
| 38. Třídící algoritmy | Ukázky běhu a pseudokódy tří třídicích algoritmů - bubblesort, heapsort a quicksort |