Teoretická informatika

Teoretická informatika je oblast matematické informatiky, která zkoumá matematické zákonitosti, které mají využití v počítačích a zpracování informací.

Oblasti studia

Automaty a gramatiky

Teoretická informatika studuje třídy automatů a formálních gramatik, u nichž každý rozpoznává nějakou množinu formálních jazyků. Čtyři nejvýznamnější z nich jsou (počínaje nejslabší třídou, která rozpoznává nejmenší množinu jazyků):

Regulární jazyky, které je možno popsat konečnými automaty, regulárními gramatikami nebo regulárními výrazy. Příkladem regulárního jazyka je jazyk, který obsahuje předem dané slovo (například abba).

Bezkontextové jazyky, které jsou rozpoznávané bezkontextovými gramatikami nebo zásobníkovými automaty. Příkladem bezkontextového jazyka je jazyk

{aⁿbⁿ | n$\in \,\!$N} = {e, ab, aabb, aaabbb atd.}

Každý regulární jazyk je bezkontextový; zde uvedený bezkontextový jazyk však není regulární. Dokázat to lze mj. Pumping lemmatem.

Kontextové jazyky rozpoznávané kontextovými gramatikami nebo lineárně ohraničeným Turingovým strojem. Příkladem kontextového jazyka, který není bezkontextový, je

{aⁿbⁿcⁿ | n$\in \,\!$N} = {e, abc, aabbcc, aaabbbccc atd.}

Každý bezkontextový jazyk je kontextový. Toto zdánlivě paradoxní tvrzení lze vysvětlit tak, že kontextová gramatika je gramatika, v níž každé pravidlo zaměňuje jeden symbol řetězcem v nějakém kontextu,zatímco "bezkontextová gramatika" je označení pro kontextovou gramatiku, v jejímž každém pravidlu je kontext prázdný.

Gramatiky uvedené v předchozích odrážkách tvoří tzv. Chomského hierarchii.

Rekurzivně spočetné jazyky rozpoznávané všemi gramatikami nebo Turingovými stroji. Příkladem takového jazyka, který není kontextový, jsou výpočty, které vyžadují paměť diametrálně větší, než je délka vstupního slova (například na vstupu bude číslo n a program vrátí (n!)-tou (viz faktoriál) cifru z desetinné části Ludolfova čísla.

Teorie vyčíslitelnosti

Související informace naleznete také v článku Teorie vyčíslitelnosti.

Tato teorie studuje částečně rekurzivní funkce a rekurzivní množiny, tedy takové funkce a množiny na přirozených číslech, jejichž hodnotu (případně členství prvku v nich) lze zjistit algoritmem.

Mnoho pojmů a výsledků (například neexistence Turingova stroje, který řeší halting problem) má přímou analogii v částečně rekurzívních funkcích.

Teorie složitosti

Související informace naleznete také v článku Teorie složitosti.

Teorie složitosti se zabývá zkoumáním, jak rychle dokáží některé matematické modely reálných počítačů (například Turingův stroj) vyřešit různé druhy problémů. Ačkoli se tím dá náročnost řešení pouze asymptoticky, přinášejí její výsleky užitečné aplikace do reálných počítačů

Další oblasti

• Gramatiky a jazyky
• Optimalizace (informatika)
• Algoritmická teorie informace
• Kryptografie
• Formální sémantika
• Teorie počítačů (neboli teoretická informatika)
• Neuronové sítě
• Neuronové počítače
  • Analýza algoritmů a složitosti
  • Matematická logika a formální jazyky
• Teorie typů