Számítógép-tudomány

A Wikipédiából, a szabad lexikonból.

A számítógép-tudomány (computer science) a matematika egyik igen fiatal tudományága, amely az információfeldolgozó gépek (pl. számítógépek) tervezésének és működtetésének elméleti, matematikai alapjaival foglalkozik. Némileg elnagyoltan az algoritmusok általános elméletének is nevezhető.

A számítógép-tudomány tehát nem azonos sem az informatikával, sem a számítástechnikával, főleg ha a szilíciumchipek gyártásának technikáját is ideértjük, sem pedig az információelmélettel, bár vannak kisebb-nagyobb átfedések. A számítástudománynak nem feladata konkrét szoftverek fejlesztése; bár foglalkozik azzal, hogy hogyan lehet a szoftverek hatékony tervezését segíteni; ennek milyen elméleti alapjai vannak; nem feladata konkrét információfeldolgozó gépek tervezése, bár szintén foglalkozik azzal, hogyan lehet ezek hatékonyságát elméletileg növelni; végképp nem feladata pedig ezek megépítése.

Talán helyesebb lenne számítástudományról beszélni és ezt mint a jelfeldolgozó gépek absztrakt matematikai elméleteként meghatározni, ahogyan ezt néhány szerző és előadó teszi.

A számítógép-tudomány a matematika egyik legkésőbb, mintegy fél évszázada ö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, Kleene, Markov, Mealy, Moore, 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.

A számítógép-tudomány alágakra bontása még elég vitatható véglegességű, mivel hiába oly gyors e tudomány fejlődése, még mindig nagyon frissek az eredmények. Alágak helyett inkább csak elméletekről, részterületekről beszélhetünk. Néhány alág, pl. a számításelmélet azért többé-kevésbé már jól differenciálódott.

Néhány kialakulóban lévő alága, elméletcsoportja:

  • kiszámíthatóságelmé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 (érdekesség, hogy tekinthető a matematikai logika részének is). (ld. angolul) volt.
  • formális nyelvek, formális nyelvtanok és automaták elmélete: ide sorolhatóak a generatív nyelvtanok, á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;
  • számításelmélet: ez elsősorban a Turing-gépek és hasonló automaták elmélete, mégpedig az ezek által futtatott algorimtusok idő-és memóriaigényének vizsgálata, központi problémája az hatékonysági vagy bonyolultsági osztályok (P, NP stb.) közti kapcsolatok megállapítása, vagy az indeterminisztikus algoritmusok vizsgálata és alkalmazása;
  • algoritmusok és absztrakt adatszerkezetek elmélete: ide tartozik a gráfelméleti algoritmusok vizsgálata (keresési problémák; s pl. a matroidok alkalmazása az ilyesfajta problémákra), az informatika bizonyos alapfogalmainak (adatszerkezetek) matematikai leírása;
  • formális szemantika: ez a fordítóprogramok különböző formális nyelvtanokkal való leírásának matematikai elméletéből nőtte ki magát, fontos szerepet játszanak benne az attribútumnyelvtanok és rekurzív nyelvtanok elmélete (például), vagy például a logikai programozás elméleti leírása;
  • mesterségesintelligencia-kutatás (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;

Lásd még: algoritmus.

Más nyelveken