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

Související informace naleznete také v článku Teorie automatů.

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 lze vytvořit z množiny symbolů pomocí operací zřetězení, sjednocení a iterace. Tyto jazyky lze popsat konečnými automaty, regulárními gramatikami nebo regulárními výrazy. Všechny jazyky, které lze zadat výčtem (tedy konečné) jsou regulární.

Bezkontextové jazyky dostaneme, pokud mimo výše uvedených operací povolíme rekurzi. Tyto jazyky jsou rozpoznávané bezkontextovými gramatikami nebo zásobníkovými automaty. Bezkontextové jazyky jsou schopné párovat závorky. Příkladem bezkontextového jazyka je jazyk

{(ⁿ)ⁿ | n$\in \,\!$N} = {ε, (), (()), ((())) atd.}

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

Kontextové jazyky dostaneme při použití podmíněné rekurze. Tyto jazyky jsou rozpoznávané kontextovými gramatikami nebo lineárně ohraničeným Turingovým strojem. Příkladem kontextového jazyka, který není bezkontextový, je

{(ⁿaⁿ)ⁿ | n$\in \,\!$N} = {ε, (a), ((aa)), (((aaa))) atd.}

Pro důkaz lze použít Pumping lemma.

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ý.

Pokud povolíme libovolné přepisování, dostaneme 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.

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

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ů