A számítástechnika az információ és a számítás tudománya, ezek elméleti alapjaival, illetve számítógépes rendszereken belül ezek gyakorlati alkalmazásával foglalkozik. Habár a számítástechnika szó hallatán mindenki a modern számítógépekre gondol, maga a tudomány jóval régebbi múltra néz vissza. Edsger Dijkstra matematikus szavaival: "A számítástechnika csak annyira szól a számítógépekről, mint az asztronómia a teleszkópokról." A XX. századra a számítástechnika igen fontos tudománnyá fejlődött, amire egy hatalmas iparág épült fel. E hatalmas fejlődés következtében e tudománynak rendkívül sok területe alakult ki. Egy részük szorosan a matematikához tartozik (matematikai logika, számításelmélet, komplexitáselmélet), míg más részük szorosabban csatlakozik a számítógépekhez (programozási nyelvek, szoftver és algoritmus tervezés, adatbányászat, adatbázisok, mesterséges intelligencia).

Ókori kezdetek
Minden fejlett civilizáció kialakulásának elengedhetetlen feltétele a matematika és a számolás művészetének a megléte. Rovásos pálcák bizonyítják, hogy már a paleolit, történelem előtti emberek is számoltak. A csont, fa vagy kő pálcákra rovásokkal jegyeztek fel megörökítésre érdemes számokat. Nem tudjuk, hogy a számok e primitív ábrázolásától mikor jutott el az emberiség az absztrakt számokhoz. Az bizonyos, hogy minden általunk ismert nyelvnek van szava legalább az egy és kettő számokra.

Matematika agyagtáblán
A neolit korszak (Kr. e. 7000-3000) alatti letelepedéssel és városok kialakulásával rendkívüli fejlődés indult meg, megkezdődött az igazi civilizációk kialakulása fejlett munkamegosztással, bonyolult társadalmi, politikai és bürokratikus szervezetekkel. Az ókori civilizációk már fejlett matematikával rendelkeztek. A legrégebbi matematikával kapcsolatos leletek a mezopotámiai civilizáció atyjától, a sumerektől maradt ránk. A sumerek szorzótáblákat égettek anyagtáblába, illetve osztási és geometria problémákkal is foglalkoztak. A sumerek találmánya a 60-as számrendszer is, melyen alapszik a mi egy óránk hatvan percre, illetve a kör 360 fokra (60*6) való felosztása. Későbbi mezopotámiai agyagtáblák már másodfokú egyenletek megoldásával is foglalkoznak, illetve trigonometrikus táblázatokat tartalmaznak. Ezeket a kezdetleges számítási segédeszközöket minden bizonnyal felhasználták hatalmas építményeik tervezésénél. Emellett nagy valószínűséggel a babilóniaiak voltak akik Kr. e. 2400 körül feltalálták a legelső számológépet, az abakuszt, melyet összeadásra és kivonásra használtak. Az abakusz modern változatai a mai napig is használatosak.

Egy mordern abakusz

Görög filozófusok
Később a görögök önálló tudománnyá fejlesztették a matematikát. A nagy görög matematikus filozófusok nevei közismertek. Thálész a trigonometriában ért el nagy eredményeket (Thálész-kör). Püthagórasz, a “számok atyja” bizonyította be elsőként a róla elnevezett Püthagórasz-tételt. Püthagórasz emellett sok mással is foglalkozott, alapított például egy szigorú szabályok szerint működő titkos szektát. Ezoterikus és metafizikai világnézetüket nagy mértékben a matematikára alapozták. Érdeklődésük középpontjában az egész számok álltak, melyeket a végső valóságnak tartottak, amelyekre épül minden más a világban, hasonlatosan a Platóni ideákhoz. Püthagórasz állítólag kivégeztette egyik tanítványát, aki felfedezte az irracionális számokat, melyeket nem lehet leírni két egész szám hányadosaként.

A legfontosabb hatású talán mégis Euklidész (Kr. e. 300), a “geometria atyja” volt. Elemek című könyveiben a geometria tudományának teljes összegzését írta meg, mely két évezreden keresztül a véső szó volt a matematika ezen területén. Az Euklidész alkalmazta módszerek teremtették meg a modern matematikát is: 1. definiálja a geometria tárgyait (pl. pont, egyenes, sík), 2. axiómákat (magától értetődő alapállításokat) ad meg (pl. bármely két pont összeköthető egy egyenessel), 3. ezek alapján tételeket fogalmaz meg, 4. amely tételeket aztán bizonyít az axiómák segítségével.

Euklidész nevéhez kötődik az euklidészi algoritmus is, amely az egyik legrégibb ismert algoritmus, és mint ilyen, nagy fontosságú a számítástechnika történetében. Az euklidészi algoritmus segítségével bármely két szám legnagyobb közös osztóját kiszámíthatjuk. Az algoritmus egy lépésről lépésre leírt módszer, amit a leírt utasítások alapján bárki végre tud hajtani. Euklidész algoritmusát így lehet leírni:

1. Legyen A a nagyobbik szám, és B a kisebbik.
2. A-ból vond ki B-t egészen addig, amíg a maradék nem negatív. Ha a maradék 0, akkor B a legnagyobb közös osztó. Ha a maradék 1, akkor 1 a legnagyobb közös osztó.
3. Ha a maradék nem 0 vagy 1, akkor ismételd meg az 2. lépést, de A most legyen B, és B legyen a maradék.

Maga az algoritmus szó későbbi elnevezés, és egy félrefordítás eredménye. Kr. u. 825-ben jelent meg Al-Khwarizmi perzsa matematikus értekezése a hindu számokkal való számolásról. A latin fordító a szerző nevét Algoritmi-re torzította, és így ragadt meg az algoritmus elnevezés. (Al-Khwarizmitől származik egyébként az algebra kifejezés is.) Al-Khwarizmi értekezésének nagy szerepe volt a hindu számrendszer közel-keleti, majd európai bevezetésében. A hinduk már egészen korán kifejlesztették tízes alapú számrendszerüket. Arab tudósok aztán továbbfejlesztették ezt a rendszert, feltalálták például a tizedes pontot, amivel már tört számokat is le lehetett írni. Ez a rendszer végül Leonardo Fibonacci 13. századi könyve nyomán terjedt el Európában. Mindennek jelentősége abban áll, hogy Európában addig a római számokat használták, melyekkel nagyon körülményes a számolás. Mint azt mindnyájan megtanultuk az általános iskolában, a tízes alapú hindu-arab számrendszerben könnyen elvégezhető az összeadás és kivonás, ha a számokat egymás alá írjuk. A tízes számrendszer szinte forradalmasította a számolást, és lehetővé tette nagy függvénytáblázatok létrehozását, amik számok négyzetgyökeinek, logaritmusainak értékeit tartalmazta.

A különböző számrendszereknek nagy fontossága van a számítástechnikában. Minden mai számítógép a bináris (kettes) számrendszer alapján működik, lévén hogy két értékkel könnyebb számolni, és egyszerűbb azokat tárolni is (például merevlemezen ellentétes irányú mágneses mezővel). Maga a bináris számrendszer azonban jóval korábbi találmány: körülbelül a Kr. e. 3. században egy indiai matematikus fedezte fel, hogy 0-ások és 1-esek sorozatával bármely számot le lehet írni.  Az ipari forradalom volt az, amely legelőször  gyakorlati módon is felhasználta a bináris számrendszert: Joseph Marie Jacquard a 19. század elején megalkotta a lyukkártya vezérelte szövőgépet, amivel bonyolult mintázatú szöveteket lehetett készíteni.

A mechanikus gépek korszaka
Az 1620-as években feltalálták a logarlécet, amivel a szorzást, osztást, gyökvonást és logaritmus számítást minden eddiginél gyorsabban lehetett elvégezni. A logarléc a matematikusok és mérnökök alapeszköze lett egészen az elektronikus zsebszámológép feltalálásáig. A mérnökök állítólag az Apollo programban (mely 1969-ben feljuttatta az első embert a Holdra) sok számítás elvégzéséhez a logarlécet használták.

Logarléc

Már a logarléccel egyidőben, a 18. században megjelentek az első mechanikus digitális számológépek, amelyek hamarosan mind a négy alapművelet elvégzésére képesek lettek.

1928-as svéd gyártmányú Odhner számológép

Itt fontos megállni és különbséget tenni az analóg és digitális eszközök között. Analóg eszközöknél a bemeneti és kimeneti értékek folyamatosan változnak, adott határértékek mellett tetszőleges értéket felvehetnek. Ilyen például a hagyományos higanyos lázmérő, amely 35 és 42 Celsius fok között bármely értéket mérhet. Analóg módon működik tovább a bakelit lemez vagy audio kazetta, melyeknél egy adott pillanatban a hangjel szintjét a barázda szélessége illetve a szalagon levő mágnese mező erőssége határozza meg, és amelyek tetszőlegesen kis értékkel változhatnak.

Ezekkel szemben áll a digitális kvarcóra, és a CD lejátszó. A digitális karórákban egy kvarc oszcillátor állít elő egy a kristályra jellemző frekvenciával (azaz periodikusan) egy elektromos jelet. Így a karóra csak diszkrét (nem folytonos) időértékeket tud mérni. A CD készítésekor a hangot 44.1 kHz-el mintavételezik, azaz kb. 0.02 ezredmásodpercenként megmérik. A mért értéket aztán 16 bitre kvantálják, azaz 65536 különböző hangszintet tudnak reprodukálni.

A digitális rendszerek előnye, hogy többszörös másolásnál sem romlik az információ, míg analóg rendszereknél a jel feldolgozása és másolása során a zajok, hibák halmozódnak. A digitális rendszerek hátránya ugyanakkor, hogy a valós világ értékeit csak közelíteni tudják a digitalizálásból adódóan.

A differenciálgépek
A következő nagy lépés a differenciálgépek feltalálása volt. Az első terveket Johann Müller készítette 1786-ban, de végül nem építette meg az eszközt. A differenciálgépek már jóval bonyolultabbak voltak mint az előbb említett mechanikus számológépek: polinomfüggvények kiszámítására lettek tervezve, és ezáltal képesek voltak trigonometrikus és logaritmus függvények közelítő számítására. Charles Babbages brit matematikus 1822-ben újra felfedezte az ötletet, és az angol kormány támogatásával neki is fogott a megépítésének. Hamarosan azonban áttért egy sokkal általánosabb, úgynevezett analítikus gép tervezésére.

Az analítikus gép forradalmi ötlet volt, az első általános célú programozható mechanikus számítógép. A gépet gőzgép hajtotta volna meg és körülbelül 30 méter hosszú lett volna. A bemeneti adatokat és lefuttatandó programot lyukkártyán kellett volna betáplálni, kimenetként egy nyomtató és csengő szolgált volna. Az eszköz rendelkezett volna belső tárolóegységgel, ami 1000 darab 50 számjegyű számot lett volna képes tárolni (ez körülbelül 21 kB-nak felel meg). A gép programozási nyelve olyasmi volt, amit ma gépi kódnak neveznénk. A gép logikai felépítése szinte teljesen azonos a mai modern számítógépekkel, Babbage jó 100 évvel előzte meg a korát. Különböző okok miatt az eszköz sajnos soha nem készült el, és maga az ötlet is jórészt feledésbe merült.

A tabulátor gépek és az IBM
Az 1880-as amerikai népszámlálás adatainak feldolgozása 7 évbe került. Az alkotmány 10 évenkénti népszámlálást írt elő, így nyilvánvalóvá vált, hogy a kézi számlálás nem járható út. A problémát Hermann Hollerith oldotta meg az elektromechanikus tabulátor gépével. A biztosok lyukkártyát használtak a számláláskor, minden egyes kártyán lyukak segítségével rögzítették (kódolták) a éppen számlált személy lakhelyét, életkorát és nemét. Ezeket a kártyákat aztán a tabulátor géppel összesítették és dolgozták fel. Az új módszerrel 18 hónap alatt sikerült végrehajtani a népszámlálást. Hollerith hamar ráérzett az új technikában rejlő lehetőségekre, és 1896-ban megalapította a Tabulating Machine Company-t. A tabulátor gépeket hatékonyan lehetett alkalmazni például könyvelési és leltári adatok feldolgozására. Egy fúzió után a céget átnevezték, és megszületett az International Business Machine, az IBM.

Egy lyukkártya

Analóg számítógépek
Mindezek mellet az analóg számítógépeknek is nagy szerepe volt.

Valójában egészen a II. világháborúig az analóg számítógépek képviselték a csúcstechnológiát. Az analóg számítógépek valós fizikai rendszereket modelleznek le, és az ezeket leíró egyenletekre tudnak megoldást adni. A valós világ dinamikus rendszereinek többségét differenciálegyenletek írják le: sebesség változása erő hatására (Newton második törvénye), az elektromágneses tér (Maxwell-egyenletek), rádióaktív bomlás, mindenfajta hullámmozgás, hőáramlás stb. Elektronikai eszközök, mint például az ellenállás, kapacitás és tekercs segítségével lehetővé vált ezen rendszerek modellezése. Ezekkel az eszközökkel képesek vagyunk elektromos jelek (hullámformák) összeadására, integrálására és más egyéb műveletekre. Persze nem minden analóg számítógép működött elektronikus elven. A legfejlettebb mechanikus analóg számítógépeket a hadsereg használta, tipikus felhasználási területük a tüzérségi fegyverek, hajóágyúk vezérlése: a számítógépnek ki kellett számolnia a lövedék megfelelő röppályáját figyelembe véve egyebek mellett a célpont mozgását, gravitációt, légellenállást, a szél irányát és sebességét.

A mechanikus analóg számítógépekre egy különleges példa a szovjet vízintegrátor, amelyet 1936-ban építettek. Ez a szerkezet csövekkel és pumpákkal összekötött tárolók halmazából állt. A tárolókban levő vízszint jelképezte a számokat, és az áramló víz sebessége a matematikai műveleteket. A vízintegrátort is differenciálegyenletek megoldására használták.

A számítógépek matematikai elmélete

Turing-gépek
Alan Turing angol matematikust tartják a modern számítástechnika atyjának. Legnagyobb jelentőségű alkotása egy elméleti tanulmány volt, amit 1936-ban publikált “A kiszámítható számokról, az Entscheidungs-problémára alkalmazva” címmel. Turing e tanulmányában leírja egy szimbólum feldolgozó gép matematikai modelljét, melyet Turing-gépnek hívunk. A Turing-gép egy nagyon egyszerű szerkezet: egy olvasófejből áll, amely egy végtelen hosszúságú szalagról szimbólumokat olvas be. Mikor a gép beolvas egy szimbólumot, azt felülírhatja, és a szalagot balra vagy jobbra mozgathatja a következő szimbólum olvasásához. Hogy éppen mit kell tennie, az egy parancstáblától függ, illetve attól, hogy milyen állapotban van a gép. A gép véges számú belső állapottal rendelkezik, melyeket számokkal szoktak jelölni. A gép az 1-es állapotból indul, és a parancstábla minden egyes állapothoz megadja, hogy egy adott beolvasott szimbólum esetén mit kell tennie: mit írjon a szalagra, elmozgassa-e a szalagot és milyen irányba, illetve melyik legyen a gép következő állapota. A gép egészen addig dolgozik míg el nem ér egy olyan állapotba és szimbólumhoz, melynél a táblázat parancsa azt mondja, hogy ÁLLJ.

A gép tehát kap egy bemeneti adathalmazt a szalagon, azt a parancstábla alapján feldolgozza, és a kimeneti adatok máris ott vannak a szalagon. Mielőtt azonban az eszközt használhatnák, meg kell oldani pár gyakorlati problémát, például ki kell találni hogy jelképezzük a számokat a szalagon. Erre a legegyszerűbb módszer a bináris számrendszer használata. Ekkor, mint már volt róla szó, két szimbólummal (0 és 1) bármely számot leírhatunk. Ha több bemeneti számra van szükség, akkor egy harmadik szimbólum is kell, ami elválasztja egymástól a számokat. Most már csak az a kérdés mire használhatjuk ezt a gépet.
Nos, egy kis leleményességgel és nem kevés idővel az ember írhat egy parancstáblát, ami mondjuk a bemeneti számot megduplázza. Esetleg egy olyat is, ami tetszés szerinti két bemeneti számot összeszoroz. Turing zsenialitása abban áll, hogy bebizonyította, bármi ami kiszámítható, azt egy megfelelő Turing-gép ki tudja számítani.

Turing ezen túlmenően bevezeti az univerzális Turing-gép fogalmát. Bebizonyítja, hogy létezik egy olyan Turing-gép, mely egyedül képes kiszámítani bármit, ami kiszámítható. Ha ennek a gépnek betápláljuk a szalagon egy másik Turing-gép parancstábláját (megfelelő módon kódolva), akkor az univerzális Turing-gép pont úgy fog viselkedni mint az eredeti. Turing ezzel megalkotta az univerzális számítógép fogalmát. Ma, a mindenütt jelenlevő PC-k világában mindez természetesnek tűnik, de Turing felfedezése akkoriban egészen megdöbbentő volt. A mai modern számítógépek Turing-teljesek, azaz egyenértékűek Turing univerzális gépével abban a tekintetben, hogy elméletben mit tudnak kiszámítani.

A kérdés ezek után már csak az, mi az ami kiszámítható?

A kiszámíthatóság határai
Turing az Entscheidungs-probléma kapcsán írta tanulmányát. Az Entscheidungs-problémát David Hilbert német matematikus fogalmazta meg 1928-ban. Hilbert a 20. század elején átfogó programot hirdetett meg a matematika rendbetételére, miután a meglévő matematikai rendszerekben zavaró paradoxonokat találtak, amik kétségessé tette az addig elért eredményeket. Hilberték az egész matematikát egy egységes, formalizált, ellentmondásmentes axióma-rendszerből próbálták levezetni. Ebben a formális rendszerben a matematikai szimbólumok hasonlatosak egy nyelv betűihez, melyekből a rendszer nyelvtana alapján lehet mondatokat, azaz igaz állításokat megfogalmazni. Az Entscheidungs-problémában Hilbert azt kérdezte, hogy létezik-e egy olyan algoritmus, amely egy adott formális matematika rendszer minden lehetséges állításáról (mondatáról) el tudja dönteni, hogy az igaz (megfelel-e a nyelvtani szabályoknak) vagy sem. Hilbert hitt abban, hogy létezik ilyen algoritmus, és így nem lesz megoldhatatlan matematikai probléma.

Kurt Gödel osztrák matematikus azonban megmutatta, hogy ez sajnos nem így van. Híres, 1931-es Nemteljességi-tételében bebizonyította, hogy bármely formális matematika rendszerben, amely magába foglalja az egészeket, az összeadást és az szorzást, megfogalmazhatók olyan igaz állítások, melyek nem bizonyíthatók a rendszer szabályaival. Gödel azt is bebizonyította, hogy ha egy ilyen rendszer axiómái ellentmondásmentesek, akkor ez a rendszer szabályaival nem bizonyítható. Ez váratlan és óriási csapás volt a matematikusok számára: akárhogy is igyekeznek, mindig lesznek olyan problémák, amelyek kicsúsznak a kezükből. Ráadásul még az sem bizonyítható be, hogy az általuk felépített matematikai rendszer ellentmondásmentes. (A matematikusok számára életbevágó, hogy az axióma-rendszerük ellentmondásmentes legyen, ellenkező esetben bármely állítás és annak ellentettje is bizonyítható.)

Gödel tételét felhasználva Turing bebizonyította, hogy nem létezik olyan Turing-gép, ami minden számelméleti problémát meg tudna oldani.

Enigma és a kódtörők

Háborúban a megfelelő kommunikációs csatornák biztosítása létfontosságú. A 20. századra a legfontosabb katonai kommunikációs eszköz a rádió, telefon és telegráf lett, melyekkel hatalmas távolságokra lehetett információt küldeni azonnal. A probléma az üzenetek titkosítása volt, lévén hogy a levegőben terjedő rádiós jeleket bárki könnyen lehallgathatja. A hadviselő feleknek égetően szükséges lett megfelelő titkosítási módszerek kidolgozása.

Az amerikaiak egy elég egyedi megoldást találtak: a II. világháborúban mind az európai mind a csendes-óceáni hadszíntéren indiánokat használtak az üzeneteik titkosítására. Amerikában tucatnyi indián törzs él, mindegyik saját
nyelvvel és dialektussal, melyeket szinte senki nem ért a törzsön kívül. Ezek a nyelvek ráadásul soha nem is léteztek írott formában. Ezen nyelvek használata ideális megoldás volt a problémára, főleg hogy sok indián belépett a hadseregbe. Az indiánokat persze megfelelően ki kellett képezni, sok katonai kifejezés például nem is létezett a nyelvükön. Így lett az őrnagyból “ezüst sas”, vagy a harci repülőből “zúgó madár”. A németeknek soha nem
sikerült feltörniük ezt az indián kódot.

Az általánosabb megoldás persze inkább elektromechanikus kódoló eszközök használata volt, melyek egy szöveg betűit más betűkké alakították át. A leghíresebb ilyen eszköz a németek által használt Enigma volt. Az Enigma leginkább egy írógéphez hasonlított. Mikor az operátor lenyomta egy betű billentyűjét, a gép egy felvillanó izzóval jelezte, hogy milyen betűt kell írnia helyette. Az aktuális betűhelyettesítést
három forgó tárcsa (rotor) vezérelte, mindegyiknek 26 lehetséges állása volt. A kódolás bonyolultságát az adta, hogy minden egyes betű leütésekor a tárcsák elfordultak, és így megváltozott a helyettesítési szabály. A gép szimmetrikusan működött: ugyanazon kezdő rotor beállítás mellett a titkosított üzenet begépelésekor a gép dekódolta az eredeti üzenetet. Az Enigmát különböző módosításokkal mindegyik fegyvernemnél bevezették a németek bízva annak feltörhetetlenségében. Emellett kódkönyveket is rendszeresítettek, amelyek megadták, hogy egy adott napon milyen tárcsabeállításokat kell használni.

A lengyelek már 1932-ben megkezdték az Enigma feltörését, és hozzájutottak néhány kódkönyvhöz is egy német ügynökön keresztül. Sikerült is feltörniük a kódolást, és építetek egy Bomba nevezetű elektromechanikus
számítógépet az üzenetek megfejtésének gyorsítására. Azonban a németek időközben továbbfejlesztették az Enigmát. Az ország lerohanásakor a lengyelek továbbadták az általuk összegyűjtött tudást és néhány Enigma replikát az angoloknak és franciáknak.

Az Ultra kódnevű szupertitkos angol kódfeltörő program az azóta híressé vált Bletchley Parkban kezdődött meg, ahová összegyűjtötték az ország legnagyobb koponyáit. Alan Turing terve alapján 1940-ben megépítették saját Bomba gépüket, amely már sikeres tudta feltörni az Enigma üzeneteket. Az Ultra felbecsülhetetlen segítséget nyújtott a szövetségeseknek, főleg az Atlanti csatában, melyben Anglia kis híján elvérzett. A német tengeralattjárók farkasfalka taktikája rendkívül sikeresen működött. A tengeralattjárók magányosan vadásztak az óceánon, és mikor rábukkantak egy angol konvojra követték azt, és értesítették a többi tengeralattjárót.

Miután elegendő tengeralattjáró gyűlt egybe, összehangolt támadással elsüllyesztették a konvojt. A háború elején Anglia hihetetlen mennyiségű hajóterhet veszített, és ezzel gyakorlatilag el lett vágva a gyarmatbirodalma és Amerika élelmiszer és nyersanyag utánpótlásától. A német üzenetek elfogásával az angolok biztonságos vizekre tudták irányítani a konvojokat. Az angolokat zsákmányolt kódkönyvek is segítették, és egy idő után már folyamatosan fel tudták törni a német üzeneteket.

1943-ban aztán megépítették a Colossust, az első programozható elektronikus számítógépet, ahol a mechanikus kapcsolókat elektronikus vákumcsövek váltották fel.
Szemben a német Z3-mal, ez nem volt általános célú, kifejezetten kódtörésre tervezték.
Mindent összevetve a történészek szerint az Ultra program mintegy két évvel rövidítette meg a háborút. (Folytatjuk)

  Végh Norbert, Stockholm