Számítástudomány

Lásd még: Informatika

Mindkét tudományág lényege, hogy az információkezelést és -feldolgozást állítja vizsgálata fókuszába elméleti és gyakorlati megközelítésben. Kialakulása az 1940-es években kezdődött, nemcsak időben egybeesve, de szoros kapcsolatban is az első elektronikus számítógépek tervezésével.

A számítástudomány nem azonos sem az informatikával, sem a számítástechnikával (főleg ha a szilíciumcsipek 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, miképp lehet a szoftverek hatékony tervezését segíteni, és 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életi szinten növelni; végképp nem feladata pedig ezek megépítése, bár a tudományág úttörői, mint Alan Turing vagy Neumann János, munkatársként részt vettek a számítógépek korai modelljeinek építésében, kialakításában is (elméleti munkásságukkal szoros kapcsolatban).

Számítástudomány

A számítástudomány a matematika egyik, igen fiatal tudományága, amely az információfeldolgozó gépek (például 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épek megjelenése, a mechanikus számítási eljárások megindították az algoritmus definíciójának és a programok írásmódjának formalizálását, az algoritmusok és programok szintaktikai (utasítások, vezérlési struktúra), szemantikai (helyesség, ekvivalencia), valamint kiszámíthatósági (a bemeneti értékekhez tartozó kiszámítási idő és memóriaszükséglet) tulajdonságainak mélyreható vizsgálatát. E kutatási területeket összefoglalóan matematikai számítástudománynak nevezzük.”

Az információkezelés és -feldolgozás matematikai alapjai köré csoportosul, és a számítások alapvető természetének megértésére irányul, mely számos alkalmazáshoz vezet a hatékony algoritmusok elemzésében és tervezésében, valamint a megbízható hardver- és szoftverrendszerek tervezésére és ellenőrzésére szolgáló formális módszerek fejlesztésében.

Elméleti alapjai:

• az automataelmélet,
• a fordítóprogramok,
• az adatbázis-elmélet.

Gyakorlati területei:

• a számítógépes irányítás és szabályozás,
• a nagy rendszerek analízise és szintézise,
• a mérnöki tervezés.

Ezek alapjait a halmazok, ítéletek, relációk, függvények, a számelmélet, a különböző algebrai struktúrák, azon belül főként a Boole-algebra adja. Fontos része a kódelmélet, azon belül a zajmentes és zajos csatornák, az optimális és hibajavító kódolás alapelemei, az automaták és formális nyelvek elmélete, a párhuzamos és elosztott számítási rendszerek elmélete, valamint az algebra, a logika és a kategóriák a számítástudományban. Komplex vizsgálati területe a kiszámíthatóságelmélet, valamint annak kiterjesztése, a bonyolultságelmélet, mely azt vizsgálja, miképp lehet osztályozni az algoritmikusan megoldható problémákat, feladatokat a megoldásukhoz szükséges erőforrások mennyisége szerint.

A számítógép-tudománnyal átfedésben levő átmeneti elemei:

• az adatstruktúrák,
• az algoritmusok,
• a programozási nyelvek,
• a szoftvertechnológia,
• a mesterséges intelligencia,
• az adatbázis-kezelés.

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

A számítógép-tudomány tárgya maga a számítógép mint eszköz; az információfeldolgozó gépek tervezésének és használatának elméleti kérdéseit kutatja. A matematika egyik igen fiatal tudományága, amely az információfeldolgozó gépek (például 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ő. Eredményei és tárgya közé tartoznak a számításokat végző rendszerek és módszerek megértésével, tervezési módszerekkel, algoritmusokkal és eszközökkel, a fogalmak tesztelésének, valamint az analízisnek és verifikációnak módszereivel, a tudásreprezentációval és ennek implementációjával foglalkozó elméletek. Komplex vizsgálati területei a véges automaták, valamint a veremautomaták, mint a Turing-gép speciális esetei.

Fő elemei: az algoritmusok és adatszerkezetek, a programozási módszertan és nyelvek, valamint a számítógépes elemek és architektúrák.

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 János, Stephen Cole Kleene, Andrej Markov, George H. Mealy, Edward Forrest Moore, Emil Post, Kurt Gödel, John McCarthy é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 fejlődése rendkívül gyors, a legtöbb alágnak azonban már van kialakult és közmegegyezéses jellegű elnevezése és feladatköre. Néhány alága, elméletcsoportja:

• kiszámíthatóságelmélet, rekurzióelmélet: az algoritmusok futásának befejeződését, eredményes lefutásának lehetőségét és viszonyait vizsgálja, más szavakkal: 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 a matematikai logika részének is tekinthető).
• A bonyolultságelmélet a kiszámíthatóságelmélet kiterjesztése. Azt vizsgálja, hogyan lehet osztályozni az algoritmikusan megoldható problémákat, feladatokat a megoldásukhoz szükséges erőforrások mennyisége szerint.
• automataelmélet, számításelmélet, bonyolultságelmélet vagy komplexitáselmélet: 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 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, ill. Oroszországban. Fontos terület a Turing-gépek és hasonló automaták elmélete, mégpedig az ezek által futtatott algoritmusok 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;
• absztrakt adatszerkezetek elmélete: ide tartozik a gráfelméleti algoritmusok vizsgálata (keresési problémák és például 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;
• logikai tervezés és optimalizálás: ez a hagyományosan mérnöki tudomány a számítógép-tudomány absztrakt modelljeinek tanulmányozásával egy idő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 kapukbó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őállítani. Optimális egy áramkör (általában), ha a kapuk számát sikerül minimalizálni.
• 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;

Számos terület (pl. a párhuzamos algoritmusok elmélete, az axiomatikus bonyolultságelmélet stb.) azonban még mindig inkább csak születőfélben lévő elmélet, mintsem önálló névvel rendelkező tudományág formájában létezik, és nehezebben sorolható a fenti alágak közé.

• algoritmus
• Informatika

• Alice és Bob – 6. rész: Alice és Bob a kiszámíthatóság határán
• Alice és Bob – 7. rész: Alice és Bob egymillió dolláros kérdése
• Alice és Bob – 8. rész: Alice és Bob biztonsága
• Ralston, Anthony: Programozás és számítógép-tudomány. Műszaki Könyvkiadó, Bp., 1974. ISBN 963-10-0616-6. (er. mű: Introduction to Programming and Computer Science, McGraw-Hill Inc.; ford. Dr. Szabados József).