Animace k předmětům teoretické informatiky

Animace, u kterých není explicitně uveden autor, vypracovali Petr Jančar, Martin Kot a Zdeněk Sawa. Některé animace vypracovali studenti v rámci svých diplomových a bakalářskářských prací pod vedením Petra Jančara. U těch je jméno autora explicitně uvedeno. Pokud byla animace od studenta upravena, je u ní i jméno autora úprav.

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 .

Konečné automaty a regulární jazyky

1. Rozpoznávání jazyka pdf 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 pdf Jednoduchý algoritmus pro vyhledávání řetězce v textu.
3. Definice konečného automatu pdf 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ů pdf 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ů pdf 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 pdf 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ů pdf 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 pdf 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 pdf Ukázka 2 výpočtů jednoho nedeterministického konečného automatu nad jedním slovem.
10. Zobecněný nedeterministický konečný automat pdf 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 pdf 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 pdf 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 pdf Příklad převodu dvou konečných automatů do normovaného tvaru.
14. Minimalizace konečného automatu pdf 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 pdf Příklad minimalizace konečného automatu.
autoři: Libor Bravenec, Martin Kot
16. Převod RV na ZNKA pdf 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 pdf 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 pdf 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 pdf Příklad převodu konečného automatu na regulární výraz.
20. Regulární operace pdf Konstrukce konečných automatů pro zřetězení, iteraci a sjednocení jazyků zadaných konečnými automaty.

Bezkontextové gramatiky a zásobníkové automaty

21. Odvození slova v gramatice pdf Ukázka derivace (odvození) jednoho slova v bezkontextové gramatice.
22. Derivační strom pdf 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 pdf 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 pdf 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 pdf 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

Výpočetní modely

29. Turingův stroj pdf Definice Turingova stroje a ukázky výpočtů dvou Turingových strojů.
30. Turingův stroj pdf Popis Turingova stroje. Ukázka TS, který za slovo na vstupu přidá jeho zrcadlový obraz.
autor: Michal Hrančík
31. Turingův stroj pdf Popis Turingova stroje. Ukázka TS, který zdvojí slovo na vstupu.
autor: Michal Hrančík
32. Vícepáskový Turingův stroj pdf 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

NP-úplné problémy

36. NP-úplnost problému SAT pdf Důkaz tzv. Cookovy věty, tedy NP-úplnosti problému SAT.
37. Převod SAT na 3-SAT pdf 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 pdf 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 pdf 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 pdf 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 pdf 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

Nerozhodnutelné problémy

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

Metody návrhu algoritmů

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

Aproximační algoritmy

48. Vrcholové pokrytí pdf 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 pdf Aproximační algoritmus pro hledání cesty obchodního cestujícího s maximálně dvojnásobnou délkou než má minimální.

Ostatní

50. Třídící algoritmy pdf Ukázky běhu a pseudokódy tří třídicích algoritmů - bubblesort, heapsort a quicksort