Teoretická informatika

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Informatika
Obory informatiky
Programování
Matematická informatika
Teoretická informatika
Teorie složitosti
Umělá inteligence
Teorie grafů
Teorie informace
Informační technologie
Bioinformatika
Chemoinformatika
Geoinformatika
Lékařská informatika
Neuroinformatika
Sociální informatika
Informatici
Charles Babbage
Alan Turing
Donald Knuth
další...
Dějiny informatiky

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[editovat | editovat zdroj]

Automaty a gramatiky[editovat | editovat zdroj]

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

{anbn | 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

{anbncn | 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[pozn 1],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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Poznámky[editovat | editovat zdroj]

  1. Kontextová gramatika je označení pro gramatiku, která obsahuje jen pravidla tvaru např. ABCXDEF\toABCRSTDEF (kde ABC, RST, DEF jsou příklady řetězců, které ale mohou mít libovolnou délku a mohou obsahovat terminální i neterminální symboly). V tomto příkladu hrají řetězce ABC a DEF roli "kontextu", v němž je nahrazení povoleno, odtud název "kontextová".