Efektívne algoritmy a zložitosť - 12 - Vypočítateľnosť

Zhrnutie prednášky

Prednáška uvádza teóriu vypočítateľnosti, ktorá skúma problémy, pre ktoré neexistuje žiaden algoritmus, a to ani pri neobmedzenom čase. Pojem algoritmus sa formalizuje Turingovým strojom a Churchovou-Turingovou tézou, podľa ktorej sa každá efektívna procedúra dá zapísať ako Turingov stroj. Ako praktickejší univerzálny model sa zavádza RAM s neobmedzene veľkými číslami v registroch a štyrmi inštrukciami (inkrement, dekrement, test na nulu, skok) s priamou a nepriamou adresáciou. Jeho sila sa ukazuje na programe pre výpočet 2^n a na tvrdení, že RAM je ekvivalentný Turingovým strojom. Napokon sa ukazuje, že zoznamy, reťazce aj samotné programy možno kódovať ako prirodzené čísla, napríklad pomocou prvočíselných exponentov a ASCII.

• - Teória vypočítateľnosti študuje problémy, ktoré nerieši žiaden algoritmus, ani s neobmedzeným časom.
• - Turingov stroj je univerzálny model výpočtov; Churchova-Turingova téza hovorí, že každá efektívna procedúra sa dá zapísať ako Turingov stroj.
• - Rôzne varianty Turingových strojov počítajú rovnakú triedu funkcií, líšia sa len rýchlosťou.
• - RAM model má registre s ľubovoľne veľkými číslami a inštrukcie inkrement, dekrement, test na nulu a go to.
• - Operandy môžu byť konštanta, register alebo nepriama adresácia; vstup je v R1, výstup v R2.
• - RAM je ekvivalentný Turingovým strojom, preto je tiež univerzálny; ukážkou je program pre 2^n.
• - Zoznamy (kódovanie cez prvočísla), reťazce (ASCII) aj RAM programy sa dajú zakódovať ako prirodzené čísla.

Zhrnutie pripravené s pomocou AI z prepisu videa.