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í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 jazyku, který není bezkontextový, je

L = { aⁿ : n je prvočíslo }

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

Hlavní článek: 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

Hlavní článek: 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ů