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 |