Zobrazení zdroje stránky Teoretická informatika

{{Informatika}}
'''Teoretická informatika''' je oblast [[Matematická informatika|matematické informatiky]] a [[Matematika|matematiky]], která se zaměřuje na abstraktnější a [[Matematika|matematické]] aspekty zpracování informací, které mají využití v [[počítač]]ích a [[Informatika|zpracování informací]].

Přesně vymezit oblast teoretické informatiky není snadné; sdružení [[ACM SIGACT]] popisuje svůj obor takto:<ref>{{Citace elektronické monografie | titul = SIGACT | url = http://sigact.acm.org | datum přístupu = 2009-03-29}}</ref>

{{Citát v rámečku|Obor teoretické informatiky se široce interpretuje jako obor zahrnující [[Algoritmus|algoritmy]], [[Datová struktura|datové struktury]], [[Teorie složitosti|teorii složitosti]], [[Distribuovaný výpočet|distribuované výpočty]], [[paralelní výpočty]], [[Very-large-scale integration|VLSI]], [[strojové učení]], [[počítačová biologie|počítačovou biologii]], [[výpočetní geometrie|výpočetní geometrii]], [[teorie informace|teorii informace]], [[kryptografie|kryptografii]], [[kvantový výpočet|kvantové výpočty]], [[počítačová teorie čísel|počítačovou teorii čísel]] a [[Symbolický výpočet|algebru]], [[Sémantika programovacích jazyků|sémantiku programovacích jazyků]] a [[verifikace programů|verifikaci programů]], [[teorie automatů|teorii automatů]] a studium [[Náhoda|náhodnosti]]. Práce v tomto oboru se často vyznačuje důrazem na matematický přístup a přesnost.}}

Časopis [[Transactions on Computation Theory]] doplňuje [[teorie kódování|teorii kódování]], [[teorie učení|teorii učení]] a aspekty teoretické informatiky v takových oblastech jako jsou [[databáze]], [[získávání informací]], ekonomické modely a [[Počítačová síť|počítačové sítě]].<ref>{{Citace elektronické monografie| titul = ToCT| url = http://toct.acm.org/journal.html| datum přístupu = 2010-06-09| url archivu = https://web.archive.org/web/20101104004846/http://toct.acm.org/journal.html| datum archivace = 2010-11-04| nedostupné = ano}}</ref>

== Historie ==
Logické inference a matematické důkazy existovaly již dlouhou dobu, ale až v roce 1931 dokázal [[Kurt Gödel]] svoje [[Gödelovy věty o neúplnosti|věty o neúplnosti]], které stanovily principiální meze toho, jaké věty je možné dokázat nebo vyvrátit.

Tento vývoj vedl k modernímu studiu logiky a [[vyčíslitelnost]]i a ke vzniku teoretické informatiky jako oboru. V roce 1948 obor rozšířil [[Claude Shannon]] svoji matematickou teorií komunikace o [[teorie informace]]. V stejném desetiletí [[Donald Hebb]] představil matematický model [[teorie učení]] v mozku. S příchodem biologických dat, která s určitými úpravami jeho hypotézy podporovala, vznikla oblast [[neuronová síť|neuronových sítí]] a [[paralelní distribuované zpracování|paralelního distribuovaného zpracování]]. V roce 1971 nezávisle na sobě dokázali [[Stephen Cook]] a [[Leonid Levin]], že existují prakticky relevantní problémy, které jsou [[NP-úplnost|NP-úplné]], což je stěžejní výsledek pro [[teorie složitosti|teorii složitosti]].

S vývojem [[kvantová mechanika|kvantové mechaniky]] na začátku 20. století se objevil koncept, že pro provádění matematických operací by bylo možné použít vlnovou funkci částic. Jinými slovy mělo by být možné počítat funkce na více stavech současně. To vedlo ke konceptu [[kvantový počítač|kvantových počítačů]] v druhé polovině 20. století, které začaly být prakticky zajímavé v 90. letech 20. století, když [[Peter Shor]] ukázal, že takové metody by mohly být použity pro rozklad velkých čísel v [[polynomiální čas|polynomiálním čase]], což by v případě úspěchu vedlo k překonání většiny moderních systémů [[kryptografie s veřejným klíčem]].

Výzkum v oboru moderní teoretické informatiky je založen na těchto významných objevech, ale zahrnuje množství dalších matematických a interdisciplinárních problémů.
{| style="border:1px solid #ddd; text-align:center;  margin: 0 auto;" cellspacing="15"
| <math> P \rightarrow Q \,</math>
| [[Soubor:DFAexample.svg|96px]]
| [[Soubor:Elliptic curve simple.png|96px]]
| [[Soubor:6n-graf.svg|96px]]
| [[Soubor:Wang tiles.svg|96px]]
| '''P = NP''' ?
|-
| [[Matematická logika]]
| [[Teorie automatů]]
| [[Teorie čísel]]
| [[Teorie grafů]]
| [[Teorie vyčíslitelnosti]]
| [[Teorie složitosti]]
|-
| '''GNITIRW-TERCES'''
| <math>\Gamma\vdash x : Int</math>
| [[Soubor:Commutative diagram for morphism.svg|96px]]
| [[Soubor:SimplexRangeSearching.png|96px]]
| [[Soubor:TSP Deutschland 3.png|96px]]
| [[Soubor:Blochsphere.svg|96px]]
|-
| [[Kryptografie]]
| [[Teorie typů]]
| [[Teorie kategorií]]
| [[Výpočetní geometrie]]
| [[Kombinatorická optimalizace]]
| [[Kvantový počítač|Teorie kvantových počítačů]]
|}

== Oblasti studia ==

=== Automaty a gramatiky ===
[[Soubor:Maquina.png|náhled|Umělecké ztvárnění [[Turingův stroj|Turingova stroje]]. Turingovy stroje slouží jako jeden z modelů obecného počítače.]]
{{Viz též|Teorie automatů|Formální jazyk}}

'''Teorie automatů''' ({{Vjazyce2|en|''automata theory''}}) je studium [[abstraktní stroj|abstraktních strojů]] a [[automat]]ů, včetně výpočetních problémů, které mohou být pomocích nich řešené. Jedná se o obor teoretické informatiky, která sama patří do [[diskrétní matematika|diskrétní matematiky]] (předmět studia [[matematika|matematiky]] i [[matematická informatika|matematické informatiky]]). Slovo ''automaty'' pochází z řeckého slova αὐτόματα, které znamená "samočinný".

Teorie automatů má těsnou souvislost s teorií [[formální jazyk|formálních jazyků]]. Automat je konečnou reprezentací formálního jazyka, který může obsahovat nekonečný počet slov. Automaty jsou často klasifikovány třídou formálních jazyků, kterou mohou rozpoznat.

=== Teorie vyčíslitelnosti ===
{{Viz též|Teorie vyčíslitelnosti}}

Tato teorie studuje [[částečně rekurzivní funkce]] a [[Rekurzivní množina|rekurzivní množiny]], tedy takové funkce a množiny z oboru [[Přirozená čísla|přirozených číslech]], jejichž hodnotu (případně členství prvku v nich) lze zjistit [[Algoritmus|algoritmem]].

Mnoho pojmů a výsledků (například neexistence [[Turingův stroj|Turingova stroje]], který řeší [[halting problem]]) má přímou analogii v částečně rekurzívních funkcích.

=== Teorie složitosti ===
{{Viz též|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á vyjádřit náročnost řešení pouze [[Asymptotická složitost|asymptoticky]], přinášejí její výsledky užitečné aplikace do reálných počítačů.

== Reference ==
{{Překlad|en|Theoretical computer science|699378328}}
<references />

== Související články ==
* [[Formální gramatika|Gramatiky]] a [[Formální jazyk|jazyky]]
* [[Optimalizace (informatika)]]
* [[Algoritmická teorie informace]]
* [[Kryptografie]]
* [[Formální sémantika]]
* [[Neuronové sítě]]
* [[Neuronové počítače]]
* Analýza [[Algoritmus|algoritmů]] a [[složitost algoritmů|složitosti]]
* [[Matematická logika]] a [[formální jazyk]]y
* [[Teorie typů]]

== Externí odkazy ==
* {{Commonscat}}

{{Pahýl}}
{{Autoritní data}}

[[Kategorie:Teoretická informatika| ]]