Vysoká škola báňská - Technická univerzita Ostrava
TEORETICKÁ INFORMATIKA
Petr Jančar
Konečné automaty a regulární jazyky
| 1. Výpočet NKA | Ukázka 2 výpočtů jednoho nedeterministického automatu nad jedním slovem. autor: Zdeněk Sawa |
|
| 2. Regulární operace | Konstrukce konečných automatů pro zřetězení, iteraci a sjednocení jazyků zadaných konečnými automaty. autor: Zdeněk Sawa |
Bezkontextové gramatiky a zásobníkové automaty
| 3. Redukce bezkontextové gramatiky | Vysvětlení postupu redukce bezkontextové gramatiky. autor: Martin Kot |
|
| 4. 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ě. autor: Martin Kot |
|
| 5. Převod BG na ZA | swf | Vysvětlení převodu bezkontextové gramatiky na zásobníkový automat. autoři: Richard Ondra, Petr Jančar |
Výpočetní modely
| 6. 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. autoři: Michal Hrančík, Petr Jančar |
|
| 7. Simulace dvoupáskového TS jednopáskovým | swf | Ukázka simulace jednoho konkrétního dvoupáskového Turingova stroje jednopáskovým. autoři: František Novák, Petr Jančar |
| 8. 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. autoři: František Novák, Petr Jančar |
NP-úplné problémy
| 9. NP-úplnost problému SAT | Důkaz tzv. Cookovy věty, tedy NP-úplnosti problému SAT. autor: Zdeněk Sawa |
|
| 10. 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í. autor: Zdeněk Sawa |
|
| 11. 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é vybran podmnožinu s daným součtem). autor: Zdeněk Sawa |
|
| 12. 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, Petr Jančar |
|
| 13. Převod HK na TSP | swf | Algoritmus převodu problému hamiltonovské kružnice na problém obchodního cestujícího. autoři: František Novák, Petr Jančar |
Nerozhodnutelné problémy
| 14. Postův korenspondenční problém | swf | Popis Postova korenspondečního problému. Převod PKP na iniciální Postův korenspondenční problém. autoři: František Novák, Petr Jančar |
| 15. Převod problému zastavení na IPKP | swf | Převod problému zastavení Turingova stroje na iniciální Postův korenspondenční problém. autoři: František Novák, Petr Jančar |
Metody návrhu algoritmů
| 16. Nejdelší společná podposloupnost | swf | Algoritmus pro hledání nejdelší společné podposloupnosti dvou slov metodou dynamického programování. autoři: František Novák, Petr Jančar |
Ostatní
| 17. Třídící algoritmy | Ukázky běhu a pseudokódy tří třídicích algoritmů - bubblesort, heapsort a quicksort autor: Petr Jančar |
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ů