„Számítástudomány” változatai közötti eltérés

önállósult ága. Keletkezését 1936-tól, [[Alan Turing]] angol matematikus automata- és algoritmuselméleti cikkeinek megjelenésétől, illetve [[Neumann János]], [[Stephen cole Kleene|S. C. Kleene]], [[Andrej Markov|A. Markov]], [[George H. Mealy|G. H. Mealy]], [[Edward Forrest Moore|E. F. Moore]], [[Emil Post|E. Post]], [[Kurt Gödel]], [[John MacCarthy]], és más kutatók hasonló jellegű munkáinak napvilágra kerülésétől kezdve számíthatjuk.

 

* [[kiszámíthatóságelmélet]], rekurzióelmélet: ez egyes függvényeknek, műveleteknek más függvényekkel való kiszámíthatóságával foglalkozik, tekinthető a számításelmélet egy olyan ágának vagy testvérterületének is; mely Turing-gépek és automaták helyett hagyományos matematikai fogalmakra (függvény, generált struktúra stb.) alapoz. E terület úttörője [[Stephen Cole Kleene]] volt (érdekesség, hogy tekinthető a [[matematikai logika]] részének is) <ref>[http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Kleene.html (ld. angolul)]</ref>.

* automataelmélet <ref name="ralston" />, számításelmélet, vagy bonyolultságelmélet: [[formális nyelv]]ek, formális nyelvtanok és [[absztrakt automata|automaták]] elmélete: ide sorolhatóak a [[generatív nyelvtan]]ok, általánosabban a [[produkciós rendszerek]], az automatatípusok által generált és/vagy elfogadott nyelvek vizsgálata, az egyes automatatípusok összehasonlítása; ennek az alágnak rengeteg fontos kutatója volt mind nyugaton, mind a [[Szovjetunió]]ban; fontos terület a [[Turing-gép]]ek és hasonló automaták elmélete, mégpedig az ezek által futtatott [[algoritmus]]ok idő-és memóriaigényének vizsgálata, központi problémája a hatékonysági vagy bonyolultsági osztályok (P, NP stb.) közti kapcsolatok megállapítása, illetve az indeterminisztikus algoritmusok vizsgálata és alkalmazása;

* logikai tervezés és optimalizálás <ref name="ralston" />: ez a hagyományosan mérnöki tudomány a számítógép-tudomány absztrakt modelljeinek tanulmányozásával egyidőben alakult ki, nagyrészt tőlük függetlenül, logikai áramköröket ugyanis nemcsak számítógépekben, hanem egyszerűbb automatákban is használnak. Az áramkörök tervezésével és optimalizálásával foglalkozik, logikainak azért nevezik, mert az áramkörmodelleket ún. [[logikai kapu]]kból építi fel: egy logikai kapu olyan elektronikus szerkezet, amely a bemenő digitális (a gyakorlatban szinte mindig elektronikus) jelek valamilyen [[logikai függvény]]ét képes előálítani, optimális egy áramkör (általában), ha a kapuk számát sikerül minimalizálni.

* mesterségesintelligencia-kutatás <ref name="ralston" /> (pontosabban ennek matematikai alapjai): az az algoritmusok hatékonyságát azok önállóságának, önműködésének szempontjából vizsgálja; ez az elmélet a számítógép-tudomány, az informatika és a kognitív tudomány érdekes határterületeiből nőtt össze és ki;

 

== Hivatkozások ==