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 (typ souboru swf). Protože podpora přehrávače Adobe Flash Player před několika lety skončila, je problematické tyto animace přehrát. V seznamu níže jsou uvedeny, ale je možné se přepnout na stránku, kde nejsou.
| 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. Levá a pravá derivace | swf | Ukázky pravé a levé derivace slova, pojem nejednoznačnosti gramatiky. autor: Richard Ondra |
| 24. 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. | |
| 25. Redukce bezkontextové gramatiky | Vysvětlení postupu redukce bezkontextové gramatiky. | |
| 26. Redukce bezkontextové gramatiky | swf | Vysvětlení postupu redukce bezkontextové gramatiky na konkrétním příkladu. autor: Richard Ondra |
| 27. 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ě. | |
| 28. Převod BG na ZA | swf | Vysvětlení převodu bezkontextové gramatiky na zásobníkový automat.
Pozn. Na stránce 4 je správný popis, že do množiny vstupních symbolů ZA M se zařadí terminální symboly gramatiky G, ale v matematickém zápise je Σ={A,B,C}. Mělo by tam být Σ={a,+,*,(,)}. Na stránce 10 je další chyba - 3. argument přechodové funkce na řádku, který se na této stránce objeví, má být B. autor: Richard Ondra |
| 29. Turingův stroj | Definice Turingova stroje a ukázky výpočtů dvou Turingových strojů. | |
| 30. Turingův stroj | Popis Turingova stroje. Ukázka TS, který za slovo na vstupu přidá jeho zrcadlový obraz. autor: Michal Hrančík |
|
| 31. Turingův stroj | Popis Turingova stroje. Ukázka TS, který zdvojí slovo na vstupu. autor: Michal Hrančík |
|
| 32. 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 |
|
| 33. Simulace dvoupáskového TS jednopáskovým | swf | Ukázka simulace jednoho konkrétního dvoupáskového Turingova stroje jednopáskovým. autor: František Novák |
| 34. 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. autor: František Novák |
| 35. Simulace stroje RAM Turingovým strojem | swf | Obecný popis simulace stroje RAM vícepáskovým (konkrétně 7-páskovým) Turingovým strojem. Konkrétní kroky simulace pro jednotlivé instrukce stroje RAM. autor: František Novák |
| 36. NP-úplnost problému SAT | Důkaz tzv. Cookovy věty, tedy NP-úplnosti problému SAT. | |
| 37. 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. | |
| 38. 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. autor: František Novák |
| 39. 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. autor: František Novák |
| 40. 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í. | |
| 41. 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). | |
| 42. 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 |
|
| 43. Převod HC na HK | Algoritmus převodu problému Hamiltonovského cyklu na problém Hamiltonovské kružnice. | |
| 44. Převod HK na TSP | swf | Algoritmus převodu problému Hamiltonovské kružnice na problém obchodního cestujícího. autor: František Novák |
| 45. Postův korespondenční problém | swf | Popis Postova korespondenčního problému (PKP) a iniciálního Postova korespondenčního problému (IPKP). Převod IPKP na PKP. autor: František Novák |
| 46. Převod problému zastavení na IPKP | swf | Převod problému zastavení Turingova stroje na iniciální Postův korespondenční problém. autor: František Novák |
| 47. Nejdelší společná podposloupnost | swf | Algoritmus pro hledání nejdelší společné podposloupnosti dvou slov metodou dynamického programování. autor: František Novák |
| 48. 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í. | |
| 49. 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í. |
| 50. Třídící algoritmy | Ukázky běhu a pseudokódy tří třídicích algoritmů - bubblesort, heapsort a quicksort |