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

{anbn|n\in N} = {e, ab, aabb, aaabbb atd.}. 

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

Regulární gramatika

• 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ů