Teoretická informatika

Teoretická informatika je oblast 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í gramatika, u nichž každý rozpoznává nějakou množinu 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 jazyku 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 jazyku, 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 Ludolfova čísla.

Teorie vyčíslitelnosti

• Teorie vyčíslitelnosti
• Teorie složitosti

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ů