Teoretická informatika

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

Přesně vymezit oblast teoretické informatiky není snadné; sdružení ACM SIGACT popisuje svůj obor takto:[1]

Obor teoretické informatiky se široce interpretuje jako obor zahrnující algoritmy, datové struktury, teorii složitosti, distribuované výpočty, paralelní výpočty, VLSI, strojové učení, počítačovou biologii, výpočetní geometrii, teorii informace, kryptografii, kvantové výpočty, počítačovou teorii čísel a algebru, sémantiku programovacích jazyků a verifikaci programů, teorii automatů a studium 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 teorii kódování, 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ítě.[2]

Historie

Logické inference a matematické důkazy existovaly již dlouhou dobu, ale až v roce 1931 dokázal Kurt Gödel svoje 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číslitelnosti 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ých sítí a 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-úplné, což je stěžejní výsledek pro teorii složitosti.

S vývojem 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ý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í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ů.

DFAexample.svgElliptic curve simple.png6n-graf.svgWang tiles.svgP = NP ?
Matematická logikaTeorie automatůTeorie číselTeorie grafůTeorie vyčíslitelnostiTeorie složitosti
GNITIRW-TERCESCommutative diagram for morphism.svgSimplexRangeSearching.pngTSP Deutschland 3.png
KryptografieTeorie typůTeorie kategoriíVýpočetní geometrieKombinatorická optimalizaceTeorie kvantových počítačů

Oblasti studia

Automaty a gramatiky

Umělecké ztvárnění Turingova stroje. Turingovy stroje slouží jako jeden z modelů obecného počítače.
Související informace naleznete také v článcích Teorie automatů a Formální jazyk.

Teorie automatů (anglicky automata theory) je studium 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í matematiky (předmět studia matematiky i matematické informatiky). Slovo automaty pochází z řeckého slova αὐτόματα, které znamená "samočinný".

Teorie automatů má těsnou souvislost s teorií 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

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 z oboru 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á vyjádřit náročnost řešení pouze asymptoticky, přinášejí její výsledky užitečné aplikace do reálných počítačů.

Reference

V tomto článku byl použit překlad textu z článku Theoretical computer science na anglické Wikipedii.

  1. SIGACT [online]. [cit. 2009-03-29]. Dostupné online. 
  2. ToCT [online]. [cit. 2010-06-09]. Dostupné v archivu pořízeném dne 2010-11-04. 

Související články

Externí odkazy

Média použitá na této stránce

DFAexample.svg
An example of a DFA state diagram
Elliptic curve simple.png
Autor: Created by Sean κ. + 23:33, 27 May 2005 (UTC), Licence: CC-BY-SA-3.0
A no-frills picture of a nonsingular elliptic curve.
SimplexRangeSearching.png
Simplex range searching.
TSP Deutschland 3.png

Kürzester Rundreiseweg durch die 15 größten Städte Deutschlands (14 sind genannt, Dortmund fehlt).

Insgesamt sind 14!/2 = 43.589.145.600 verschiedene Wege möglich.
Blochsphere.svg
(c) MuncherOfSpleens, CC-BY-SA-3.0
A vectorized version of this image. I'm assuming that it must be released under the GPL because of that.
Commutative diagram for morphism.svg
Commutative diagram for morphism.
Wang tiles.svg
A set of 13 Wang tiles that can tile the plane aperiodically, drawn from a description in a paper published by Karel Culik II in 1996.
6n-graf.svg
Graph, created in Neato
Maquina.png
This picture was uploaded by Schadel on en.wikipedia as a GIF. I (Alessio Damato) have converted it in PNG and optimized with optipng, saving 20% space, and then I uploaded it here in Commons (the license allowed that). Made Schadel on contribution to CEUAMI in Universidad Autónoma Metropolitana, Mexico, free for use to anyone interested in Computer Science