BEVEZETÉS AZ INFORMATIKÁBA 2. rész TARTALOMJEGYZÉK

BEVEZETÉS AZ INFORMATIKÁBA 2. rész TARTALOMJEGYZÉK BEVEZETÉS AZ INFORMATIKÁBA 2. RÉSZ.................................................................. 1 TARTALOMJEGYZÉK ......................................................................................................... 1 A SZÁMÍTÓGÉP..................................................................................................................... 2 A számítógép, mint információ-feldolgozó egység .......................................................................... 2 Út a számítógépig............................................................................................................................... 3 Az első generáció (1952-57) ......................................................................................................................... 10 Neumann János és a Neumann-elvek............................................................................................................ 11 Második generáció (1955-1964) ................................................................................................................... 13 Harmadik generáció (1965-1974) ................................................................................................................. 15 A negyedik generáció (1971-)....................................................................................................................... 16 Ötödik generáció ........................................................................................................................................... 17

A számítógép felépítése.................................................................................................................... 19 A központi feldolgozó egység....................................................................................................................... 19 Perifériák....................................................................................................................................................... 21 A számítógépek alapkonfigurációja .............................................................................................................. 25

A számítógépek programozása ....................................................................................................... 26 Programnyelvek kialakulása, fejlődése ......................................................................................................... 26 Gépi kódú programozás ................................................................................................................................ 26 Szimbolikus programnyelvek........................................................................................................................ 30 Automatikus kódolású programnyelvek........................................................................................................ 31 Algoritmikus programnyelvek ...................................................................................................................... 31

KÓDOLÁSI ELJÁRÁSOK................................................................................................... 35 Kódolás és dekódolás.................................................................................................................................... 35 Szeparálható kódok ....................................................................................................................................... 36 Prefix kódrendszer ........................................................................................................................................ 36 Az egyértelmű dekódolás elégséges feltétele ................................................................................................ 37 Szeparálható bináris kódrendszer.................................................................................................................. 37 Átlagos kódhossz .......................................................................................................................................... 39 Az entrópia és tulajdonságai ......................................................................................................................... 40 Hatásfok ........................................................................................................................................................ 42 Az egyértelmű dekódolás szükséges és elégséges feltétele........................................................................... 43 Huffman-kódolás .......................................................................................................................................... 43 Shannon-Fano kódolás .................................................................................................................................. 45 Shannon-féle bináris kódolás ........................................................................................................................ 46 Összefoglaló feladatok......................................................................................................................... 48

IRODALOMJEGYZÉK........................................................................................................ 49

1

A számítógép A számítógép, mint információ-feldolgozó egység „A számítógépek adatok és jelsorozatok feldolgozására szolgáló elektronikus műszaki berendezések.” [4] Ez a megfogalmazás az, amely leginkább megközelíti azt a berendezést, amelyre a szó hallatán gondolunk, és amely legjobban leírja a ma használatos gépeket. Elsősorban digitális számítógépekről van szó, napjainkban az analóg számítógépek száma csekély a digitális számítógépekhez viszonyítva. Érdekesség, olvasmány Az analóg és a digitális számítógép összehasonlítására szolgál a következő táblázat: [1, 4] analóg számítógép Az információknak mindig valamilyen fizikai állapot vagy változás felel meg. A mért mennyiségek tetszőleges közbenső értékeket vehetnek fel → folytonos jelek A számítások például kerekek elforgatásával, hosszúságmérésekkel, csigák, orsók, áttételek, ellenállások, kondenzátorok, erősítők használatával valósulnak meg. Egyedi feladatok megvalósítására készülnek. A megoldandó feladat változása a számítógép felépítésének, működésének változását is maga után vonhatja. Például különböző folyamatok modellezésére, vezérlésére használják.

digitális számítógép Az információ ábrázolására egyedi, jól elkülönült állapotokat – számokat – használnak fel. Az egymás után következő értékek között mindig van minimális eltérés, közbülső értékek nincsenek → diszkrét jelek A számítások a számértékektől függetlenül, az állapotokat leíró számokra vonatkozó műveleti szabályok alapján történik. Univerzális berendezés. A szoftver cseréjével ugyanaz a gép új feladat megoldására alkalmas. Elvileg bármilyen megoldható feladat megoldására alkalmasak.

A számítógépek megegyeznek abban, hogy valamilyen beérkező adatok alapján műveleteket végez, melynek eredményét megjeleníti. A gép a külvilágból érkező jeleket érzékeli, belső állapotait ezek hatására megváltoztatja, végül kimenő jelek segítségével pedig közli a külvilággal az eredményt. Általánosan tehát mindenféle feladatmegoldást adatfeldolgozásnak tekinthetünk. [2]

Bevitel

Feldolgozás

Eredmény

A feladatok közé tartozik az adatok befogadásától kezdve, az adatok tárolásán, visszakeresésén, műveletek végzésén keresztül, az eredmények közléséig minden tevékenység. 2

Út a számítógépig Manapság hétköznapjainkhoz tartozik a számítógép használata. Azoknak, akik „belenőnek” a számítógépek világába, teljesen természetes ez, azonban még most is sokan vannak, akik félve közelítenek a „csodamasinához”. Nem szabad azonban, hogy számítástechnika a megismeréséről való lemondáshoz vezessen! A bonyolult hardver és szoftver megértésében nagy segítséget jelenthet kialakulásuk folyamatának, történetének ismerete. Számolás, számírás, számolási segédeszközök A számolás, a számfogalom az ősember által ismert dolog volt. Az ember valószínűleg az ujjait használta a számoláshoz, ezért volt „kézenfekvő” a tízes számrendszer használata A latin digitus szó jelentése: ujj. Ebből a szóból ered az angol digit, számjegy elnevezés is. Érdekesség, olvasmány A számok leírása, illetve az erre szolgáló külön jelek, a számjegyek kialakulása az írással egy időben történt. Szükségessége gazdasági okokra is visszavezethető: az időszámításunk előtti ötödik évezredben kezdődött el olyan nagy birodalmak, államok kialakulása, mint például Egyiptom, Mezopotámia, Babilónia, a Római Birodalom, ahol már volt kincstár, adó. Sokat kellett számolni, valamint az adatokat rögzíteni is kellett. Több nép is használta a számok írására az ábécéjük betűit (pl. ókori görögök, zsidók, grúzok). A babiloniak két legnagyobb érdeme a 60-as számrendszer és a helyiérték bevezetése. A hindu matematika legfontosabb vívmányai a tízes számrendszer és a helyiérték alkalmazása, a műveleti jelek és a zárójel bevezetése, valamint a nullának, mint számjegynek a használata. A hindu matematika eredményei arab közvetítéssel kerültek Európába.

Az emberek mindig is törekedtek olyan eszközök készítésére, amely megkönnyíti a számolás hosszas és gyakorta bonyolult műveletét. A számoláshoz eleinte köveket, kavicsokat, csontokat használtak, a rögzítéshez pedig rovásokat készíttek fadarabba, csontba, alkalmaztak csomóba rakott köveket, fadarabokat, zsinegre kötött csomókat is. Mennyiségek rögzítésére sokáig használták Európa-szerte az úgynevezett rovásfákat. (Angliában egészen 1812-ig rováspálcán vezették az adózók által befizetett összeget.) A számolópálcák használatának az i.e. V. sz.-ból is van nyoma Kínában. Az abakusz ókori számolási segédeszköz. Rudakon vagy hornyokban mozgatható golyókat, kövecskéket tartalmaz. A kövecske latin neve calculus, innen származik a kalkulátor szó is. A rudak jelentették a helyiértékeket, a rudakon lévő golyók helyzete pedig a számjegyeket. Az összeadás és a kivonás igen egyszerűen és gyorsan elvégezhető vele, az eredményt könnyű volt leírni római számokkal. Az összeadás lépéseit mutatja a következő ábra:

3

Hasonló eszközt használnak még ma is a kínaiak és a japánok, az utóbbit szorobánnak nevezik. A szorzás elősegítésére a középkor kezdete táján széles körben elterjedt a gelosia-módszer (rácsos módszer), Európában a XIV. sz. elején vált ismertté. Az eszköz már az arab számok használatára épül. Érdekesség, olvasmány Az ábra egy szorzási feladat megoldását mutatja be. Az egyes négyzetekbe az adott oszlop tetején és az adott sor végén álló számjegy szorzatát írjuk, az átló fölé kerülnek a tízesek, az átló alá az egyesek. Ha a ferde sávok mentén összeadjuk a számjegyeket, megkapjuk a végeredményt. A jobb alsó sáv adja az eredmény legkisebb helyiértékű számjegyét, a bal felső sáv pedig a legnagyobbat. Ha egy sávban az összeg két számjegyű, akkor az első számjegyet a felette (és tőle balra lévő) sáv összegéhez adjuk. Ez a módszer megfelel annak, ahogy mi végezzük írásban a szorzást és a rész-szorzatokat egy-egy hellyel jobbra tolva írjuk le.

A

Napier-pálcák

egyszerűsítésére kitalálójáról,

a

készültek.

John

Napier

gelosia-módszer Az

eszköz

nevét

(1550-1617)

skót

tudósról kapta. A készlet tíz darab pálcából állt, egy pálcára egy számjegy többszörösei kerültek. Szorzás elvégzéséhez

az

egyik

tényezőnek

megfelelő

pálcákat rakták egymás mellé, majd a másik tényezőnek megfelelő sorokból a gelosiamódszernél megszokott módon leolvasták a szorzatot. Érdekesség, olvasmány Gaspard Schott jezsuita szerzetes alkotta meg az eszközt a következő módon: henger alakú számolópálcákat készített, felületükre a teljes Napier-féle pálcakészlet tartalmát felírta. Ezeket egy keretbe erősítette úgy, hogy forgatni lehessen őket, így úgy nézett ki, mintha a Napier-pálcákat tették volna egymás mellé.

A XVI. sz. vége felé Simon Stevin (1548-1620) használta először a logaritmust. A logaritmustáblák alkalmazásával a műveleteket egyszerűsíteni, gyorsítani lehetett. Az első logaritmus-táblákat egymástól függetlenül készítette 1588-ban Jost Bürgi és 1594-ben John Napier. A tízes alapú logaritmust 1615-ben vezette be Henry Briggs. A logarléc hosszú életű számolási segédeszköz, használatát még ma is tanítják.

4

Érdekesség, olvasmány Már régebben is alkalmaztak összeadásra és kivonásra két azonos beosztású, egymáshoz képest eltolható vonalzót: két hosszúságot egymás után mértek, vagy egyiket visszamérték a másikból. 1622-ben William Oughtred a vonalzókra logaritmusokat mért fel, de az eredeti számokat írta melléjük. Így a vonalzók elcsúsztatásával két szám logaritmusát tudta összeadni és kivonni, a vonalzóról viszont maga az eredmény, a két szám szorzata vagy hányadosa volt leolvasható. 1650-ben készítette Pattridge az első olyan logarlécet, amelyben egy nyelv csúszik a léctestben. A logarlécre egyéb skálabeosztásokat is készítettek, pl. a hatványozás, gyökvonás, reciprok értékek és szögfüggvények leolvasására. 1851-ben vezették be a csúsztatható ablakot, aminek segítségével több skálát is lehet egyszerre használni. Készültek speciális célokra alkalmas logarlécek is.

Mechanikus számológépek A számolóeszközök fejlődésének lendületet adott a hajózás, az egyre pontosabb szárazföldi és tengeri térképek iránti igény. Mindezek elkészítéséhez komoly csillagászati ismeretekre és rengeteg számítási műveletet elvégzésére volt szükség. 1623-ban egy csillagász, Wilhelm Schikard (1592-1635) tübingeni professzor a négy alapművelet elvégzésére alkalmas számológépet készített. A gépről Kepler iratai között maradt egy vázlat. A gépezet magját az aritmetikai egység alkotta, amely az összeadást és a kivonást végezte. Érdekesség, olvasmány A számológép felső része hat darab függőlegesen elrendezett hengeres Napier-pálcát tartalmaz, amely hat darab tízes számrendszerbeli helyiértéknek felelt meg, így a gép hatjegyű számokkal való műveletvégzésre volt alkalmas. Az egyes számjegyeket a kerekek elforgatásával lehet beállítani. A számlálómű fogaskerekekből készült. A számolást végzőnek a leolvasott részeredményeket kézzel kellett bevinni a számlálóműbe, és azzal összeadni. A számlálómű képes volt az átvitelt kezelni: a következő nagyobb helyiértékre: az egyik kerék egy teljes körülfordulása egy külön fog segítségével a következő helyiértéknek megfelelő fogaskereket egy számjeggyel elforgatta. Az eredmény a gép alján jelent meg. Schikard olyan kerekeket is felszerelt, amelyekkel a részeredményeket is lehetett tárolni. A gép jelezte csengőhanggal, ha a hetedik helyiértékre túlcsordulás történt. Az eredeti gép eltűnt, a Kepler számára készített másodpéldány elégett, így nem maradt fenn működő változat. A vázlat alapján 1960-ban készítettek egy jól működő másolatot.

Az első, „sorozatban gyártott” összeadógépet Blaise Pascal (1623-1662) francia filozófus tervezte 1642-ben. Összesen hét példányt készített el. Az automatikus átvitelt megvalósító gép „csak” összeadni és kivonni tudott, és hatjegyű számokkal dolgozott.

5

Érdekesség, olvasmány A számokat a gép elején lévő kerekeken kell beállítani, az eredmény pedig a gép tetején lévő kis ablakokban látszik. Az eszköz tízfogú fogaskerekeket tartalmaz, a fogaskerekek minden foga egy-egy számjegynek felel meg 0-tól 9-ig. A számokat összeadni vagy kivonni a fogaskerekek megfelelő számú foggal történő elforgatásával lehet. A gépet apja munkájának megkönnyítésére készítette az akkor 19 éves Pascal.

Gottfried Wilhelm Leibniz (1646-1716) német filozófus és matematikus Pascal gépét fejlesztette tovább. Gépével már szorozni, osztani, és gyököt vonni is lehetett. Két részből állt: az összeadómű megegyezett Pascal megoldásával. Az újdonságot a szorzómű jelentette, és a bordás tengely alkalmazása tette lehetővé. Érdekesség, olvasmány A henger felületén kilenc darab, eltérő hosszúságú borda van, ezek úgy működnek, mintha széles fogaskerékfogak lennének. A hengerhez illeszkedő fogaskerék saját tengelye mentén elmozdítható, és megfelelő beállításával elérhető, hogy a bordás henger egy teljes körülfordulása során fogaiba pontosan 1, 2, ... 9 számú borda akadjon be, és így ennyi foggal forduljon el a fogaskerék. A fogaskerék tengely menti eltolásával állítható be a szorzandó, a bordáshengert pedig annyiszor kell körbeforgatni, amennyi a szorzó, ekkor a fogaskerék a két szám szorzatának megfelelő számú foggal fordul el. A XIX. sz. végéig a bordás henger jelentette az egyetlen gyakorlatban is kivitelezhető mechanikus megoldást a szorzás gépesítésére, és alkotórésze maradt az összes mechanikus számológépnek még a XX. században is. Leibniz nevéhez még két olyan elméleti felfedezés is fűződik, aminek szerepe van az informatika fejlődésében. 1666-ban bebizonyította, hogy egy számolási művelet egymás után elvégezhető egyszerűbb lépések sorozatára bontható, 1679-ben pedig ismertette a számítástechnikában alapvető fontosságú kettes számrendszert.

1820-ban Charles-Xavier Thomas de Colmar Franciaországban készítette Arithrométre nevű

gépét,

mely

egy

Leibniz-féle

bordás

hengerrel

működött.

A

számológép

tökéletesítéséhez tartozott később a billentyűzet és a tengelyek forgatására a villamos meghajtás alkalmazása is. 1885-ben készíti el az amerikai Stevens Borroughs (1857-1898) az első billentyűvel és nyomtatóval ellátott összeadógépet. 1887-ben készült el a svéd Theophil Witgold Odhner (1845-1905) nevéhez fűződő tekerős számológép, melynek lelke a bordáshenger helyett a bütyköstárcsa. Minden helyiértéket egyegy ilyen tárcsán állítottak be, a bütykök száma pedig egy karral volt változtatható. Működése gyakorlatilag megegyezett a korábbi megoldásokkal. 1905-ben készítették az első teljesen automatikus, gombnyomásra működő számológépet. A képen

egy

mechanikus

számológép látható. Folyamatok

vezérlésére

évszázadok

óta

már

alkalmaztak

6

különböző vezérlési módokat. Egy jellemző megoldás volt a tüskés henger, melynek kerülete szabta meg a program hosszát. A mintás szövés vezérlésére olyan módszer kellett, amivel hosszabb programot is meg lehet adni, és egyszerűen lehet a szövőszéket „átprogramozni” vagyis a mintát megváltoztatni. Joseph Marie Jacquard (1752-1834) francia mérnök 1810ben automatikus szövőszéket tervezett, amelynél fából készült vékony, megfelelően kilyuggatott lapok – kártyák – vezérelték a minták szövését. A képen a szövőszék tetején látható a lyukkártyás vezérlőszerkezet. A modern számítógépgyártás megalapozója Charles Babbage (1792-1871) brit matematikus és feltaláló. A XIX. században kidolgozta a modern digitális számítógép alapelveit. Több új típusú gépet is kigondolt, ezek egyike a logaritmustáblázatok készítésére tervezett differenciagép (Difference Engine) volt. Érdekesség, olvasmány A differenciagép a számolás eredményét a tervek szerint pontozóval közvetlenül a nyomda által használható fémlemezbe írta volna. Nevét a gép onnan kapta, hogy bizonyos függvényértékek (négyzetek, harmadik hatványok, logaritmusok, stb.) sorozatának kiszámítását különbségek, differenciák összeadására vezeti vissza. A gép 20 jegyű számokkal dolgozott volna. Újabb számítógépében, az Analytical-Enginben 1000 tengelyen 50 helyiértékű számoknak megfelelő számkereket akart elhelyezni. Babbage csak a gép egyes részeit tudta elkészíteni, a munkát azonban nem tudta befejezni: részben anyagi okok miatt, részben pedig a kor technikai lehetőségei nem voltak elegendőek. Babbage felismerte, hogy a számolási folyamat során szükség van a részeredmények tárolására. Az el nem készült gépre Ada Byron (Lord Byron költő lánya) írt programokat, kiemelkedő matematikai tehetségének köszönhetően ő nevezhető az első programozónak. Babbage univerzális gépet tervezett, amely adatbeviteli és eredmény-kiviteli egységből, számolóműből és részeredmény-tárolóból állt volna. A képen a malom rész látható, amely a számítási műveletek elvégzését szolgálta volna. A gép lyukkártyákról olvasta volna be az információkat, tudott volna utasításokat és adatokat tárolni, matematikai műveleteket végrehajtani, és adatokat kinyomtatni. Lyukkártyák vezérelték volna a számítási folyamatokat is. Megjelent a feltételes vezérlésátadás ötlete. A tárolómű 200 részeredmény tárolására lett volna alkalmas, 1000 db, egyenként 50 fogaskereket tartalmazó oszlop formájában. A gép működési elvei miatt sok történész Babbage-et tartja a modern digitális számítógép feltalálójának. 1991-ben megépítették az eredeti differenciagép egyszerűsített változatát Babbage részletes rajzai alapján. A gép négyezer alkatrészből áll, méretei 3,4 m × 0,5 m × 2,1 m. A berendezés tökéletesen működött: hibátlanul kiszámította a 7. hatványok táblázatának első száz értékét.

Az első működő differenciagépet 1853-ban készítette el Pehr Scheutz és fia, Edvard Scheutz. Babbage készülékét egyszerűsítették: a gép „csak” 15 jegyű számokat és harmadrendű differenciákat kezelt. Differenciagépeket egészen az 1940-es évekig használtak matematikai táblázatok készítésére. George Boole (1815-1864) és Augustus de Morgan (1806-1871) dolgozták ki a formális logikát. Ekkor már régóta használták a bináris kapcsolásokat órák, automaták vezérlésére. A Boole-algebra számítógép logikai tervezéséhez és programozásához nyújt elméleti alapot. 7

Megjelenik az elektromosság A lyukkártya alkalmazásának másik úttörője Herman Hollerith (1860-1929) német származású amerikai statisztikus volt. Az Egyesült Államok 1880-as népszámlálásán 55 millió ember adatait gyűjtötték össze. Az adatok feldolgozásához 500 ember munkájára volt szükség, 7 éven keresztül. Hollerith az 1890-es népszámlálás adatainak feldolgozásához szerkesztette meg rendezőgépét. Érdekesség, olvasmány Jacquard deszkalapjaihoz hasonló perforált kártyákat használt az adatfeldolgozásra. Egy kártyára egy ember adatait lyukasztotta. Az adatok feldolgozása során a lyukkártyák elektromos érintkezők között mentek át. Ahol a kártyán lyuk volt, az áramkör bezárult, így lehetett a lyukakat megszámolni. A népszámlálási adatatok feldolgozása ilyen módon mindössze négy hétig tartott! 1896-ban megalapította a Tabulating Machine Company nevű céget, amelyből aztán 1924-ben megalakult az IBM.

1914-ben Leonardo Torres y Quevedo (1852-1936) bevezette a lebegőpontos számábrázolást a számítástechnikában, és olyan programvezérlésű mechanikus számológépeket épített, amelyeknek kimeneti egysége írógép volt. Tőle származnak a programozási nyelvek első kezdeményezései is. 1932-ben építette Konrad Zuse (1910-1992) Németországban az első mechanikus tárolót tetszőleges adatok, elsősorban lebegőpontos számok tárolására. A tároló 24 bites adatokat tudott fogadni. Ő építette meg Z1 néven az első olyan szabadon programozható számítógépet, amely kettes számrendszerben működött és lebegőpontos számokkal dolgozott. Az első teljesen működőképes, szabadon programozható, programvezérlésű számítógépet, a Z3-at 1941-ben fejezte be. Érdekesség, olvasmány A Z1 esetében adatbevitelre billentyűzet szolgált, az adatkivitel pedig kettes számrendszerben egy világító tábla (fénymátrix) segítségével történt. A számolómű és a tároló telefonrelékből készült. A gép 24 bites szavakkal dolgozott, a memóriája 16 adat tárolását tette lehetővé. A gép tartalmazott decimális-bináris és bináris-decimális átalakítót is. Ilyen eszközt Zuse készített először. A Z2 már lyukfilmes adatbeviteli egységet tartalmazott. A Z3 22 bites szavakat használt és lebegőpontos számokkal dolgozott. A tárolóegység 1600 mechanikus reléből állt, 64 szám tárolására volt képes. A számolómű 400 relé felhasználásával készült. A műveletek jellemző végrehajtási ideje 3s. Zuse cége 1967-ig gyártott számítógépeket. Az 1956-ban bevezetett relés Z11-ből 50 db készült, a Z22 már elektroncsöves volt. A céget a Siemens vette át 1967-ben.

Alan Mathison Turing (1912-1954) 1936-ban írta le egy olyan számítógép matematikai modelljét, amely mint a lehető legegyszerűbb univerzális számítógép, bármilyen véges matematikai és logikai problémát meg tud oldani. Ez a ma Turing-gép néven ismert eszköz fontos lépcső volt a digitális számítógépek kifejlődésében. 8

Érdekesség, olvasmány A Turing-gép három részből áll: egy mindkét irányban végtelen tárolószalagból, egy vezérlőegységből és egy író-olvasó fejből. A szalag mezőkre oszlik, mindegyik mező egy adatot vagy utasítást tud tárolni. Csak a fej alatt elhelyezkedő egyetlen mező olvasható, illetve írható. A gép a következőképpen működik: Kezdetben a gép meghatározott állapotban van. Beolvassa a szalagról az éppen a fej alatt lévő jelet, ettől függően végrehajt valamilyen tevékenységet, és így új állapotba jut. Közben a szalagot is új mezőre pozícionálja. A fej beolvassa a szalagról a következő jelet, és így tovább. A folyamat akkor ér véget, amikor az olvasófej a STOP utasítást olvassa be.

George Stibitz (1903-) 1937-ben építette meg Complex Number Calculator nevű gépét. A gép bináris aritmetikát használt, a tárolóegység relékből készült. Az adatbevitel távírógéppel történt. A gép egy változatát 1943-ban ballisztikai számításokra használták. Claude Shannon (1916-) 1943-ban fedezi fel az elektromos kapcsolások és a logika kapcsolatát. Érdekesség, olvasmány Eszerint ha egy áramkörben egy kapcsoló zárt állása az igaz logikai értéket jelképezi, a nyitott állása pedig a hamis értéket, akkor két kapcsoló soros kapcsolása az ÉS műveletet valósítja meg, két kapcsoló párhuzamos kapcsolása pedig a VAGY műveletet. A digitális számítógépek áramköreinek tervezésében az elmélet lényeges segítséget jelent. Shannon a matematikai információelmélet egyik megalapítója is.

Howard Aiken (1900-1973) vezetésével fejlesztették ki az első teljesen automatikusan működő általános célú digitális számítógépet az Egyesült Államokban, a Harvard egyetemen. Építését 1939-ben kezdték meg. A gép a Mark I nevet kapta. Relékből épült fel és fixpontos számokkal

dolgozott.

A

memóriája

a

mechanikus

számológépekhez

hasonlóan

fogaskerekekkel, tízes számrendszerben tárolta az adatokat. Az adatbevitel lyukkártyákkal történt. A programot lyukszalag tartalmazta, ez vezérelte a gép működését. Továbbfejlesztése a Mark II, amely 1948-ban készült el, és már lebegőpontos számokkal is tudott dolgozni. Érdekesség, olvasmány A Mark I 3304 db kétállású kapcsolót tartalmazott, összesen kb. 760 000 alkatrészből állt és 500 mérföld (800 km) huzalt használtak fel hozzá. A gép kb. 15 m hosszú és 2,4 m magas volt, memóriájában 72 db 23 jegyű számnak volt hely. A gépnek egy összeadáshoz 0,33, egy szorzáshoz 4, egy osztáshoz 11 másodpercre volt szüksége és gyakran meghibásodott. A tengeri tüzérség részére készítettek vele lőtáblázatokat. Ezt a számítógépet 1959-ig használták.

9

Az első generáció (1952-57) Az elektronikus működésű számítógépek megjelenésével kezdték el generációkba sorolni a számítógépeket, azonban az egyes generációk között nem húzható meg éles választóvonal. Az első generációs elektronikus számítógépek jellemző építőeleme az elektroncső. Az elektroncsövet már 1904-ben feltalálták ugyan, de később jöttek rá arra, hogy nemcsak erősítőként, hanem kapcsolóként is alkalmazható. Mivel azonban a csövek drágák, megbízhatatlanok és rövid életűek voltak, csak az 1940-es évektől használták őket számítógépek készítésére. Kezdetben a programozás gépi kódban történt, utána jelent meg az assembly nyelv és az ebben készült programok lefordításához szükséges assembler. A gépek működtetéséhez állandó műszaki felügyelet kellett, mert a számítógép bármikor meghibásodhatott, a hiba megkereséséhez és kijavításához pedig hozzáértő szakemberek kellettek. A leggyakoribb hiba ok egy-egy cső kiégése volt. Üzemeltetésük ráadásul rengeteg energiát igényelt. 1939-ben az Egyesült Államokban építette meg John Atanasoff (1903-) és Clifford Berry (1918-1963) az első elektronikus gépet. (Atanasoff-Berry Computer, ABC) Ezt a számítógépet lineáris egyenletrendszerek megoldására használták. Érdekesség, olvasmány Vita folyt arról, hogy melyik az első általános célú elektronikus digitális számítógép. 1973-ban döntés született: ez a cím az Atanasoff-Berry Computert illeti meg.

Angliában, 1943-ban tudósok és matematikusok egy csoportja létrehozta az első teljesen elektronikus digitális számítógépet, a Colossust. Rejtjelezett német rádióüzenetek megfejtésére használták Alan Turing vezetésével, a németek ENIGMA nevű rejtjelét is ezzel fejtették meg. Mivel a háború után is katonai célokat szolgált, egészen 1975-ig titokban tartották a létezését. Az első általános célú elektronikus digitális számítógép, az ENIAC (Electronic Numerical Integrator And Computer). Ezt a számítógépet már szabadalmaztatták. Szintén katonai célokra kezdte tervezni John Presper Mauchly és John William Eckert a Pennsylvania egyetemen 1946-ban.

10

Érdekesség, olvasmány Az ENIAC 17468 elektroncsövet tartalmazott, több mint 100 kW elektromos energiát fogyasztott, 450 m2 helyet foglalt el, tömege 30 tonna volt. Megépítése tízmillió dollárba került. A relés számítógépeknél három nagyságrenddel gyorsabb volt: az összeadást 0,2 ms, a szorzást 3 ms alatt végezte el. A programja fixen be volt „drótozva” a processzorba így csak többnapos munkával, csatlakozások átkötésével lehetett megváltoztatni. Memóriája 20 db tízjegyű előjeles decimális számot tudott tárolni, egy-egy számjegy tárolására 10 db elektroncsövekből épített flipflop szolgát. Az elektroncsövek megbízhatatlansága miatt a gép csak rövid ideig tudott folyamatosan működni. Ballisztikai és szélcsatorna-számításokra használták. Az a számítás, ami a gépnek 15 másodpercig tartott, egy szakképzett embernek asztali kalkulátorral 10 órás munka volt. A gépet 1956-ban bontották le, mert elavult.

Az UNIVAC I. (UNIVersal Automatic Calculator) volt az első sorozatban gyártott univerzális számítógép, mely kereskedelmi forgalomban is kapható volt. Első volt abban is, hogy a számok mellett már szöveges információt is tudott kezelni, valamint háttértárként itt használtak először mágnesszalagot. Ezt a gépet is John Presper Eckert és John Mauchly tervezte, és ezt tekinthetjük az első generáció igazi kezdetének.

Neumann János és a Neumann-elvek 1951-ben

helyezték

üzembe

az

EDVAC-ot

(Electronic Discrete Variable Automatic Calculator), mely szintén Mauchly és Eckert vezetésével épült. Ez a gép már Neumann János (1903-1957) magyar matematikus elvei alapján készült. A Neumann-elvek A ma használt számítógépek felépítését, működését nagyban meghatározta Neumann János munkássága. 1946-ban a „First Draft of a Report on the EDVAC by John von Neumann című jelentésében fogalmazta meg azokat az elveket, amelyek alapján a mai számítógépek is felépülnek. Ezek az elvek röviden a következők [5]: 1. A számítógép legyen teljesen elektronikus, külön vezérlő és végrehajtó egységgel rendelkezzen. 2. Kettes számrendszert használjon. 3. Az adatok és a programok ugyanabban a belső tárban, a memóriában legyenek. 4. A számítógép legyen univerzális. 5. Folyamatos emberi beavatkozás nélkül hajtsa végre a műveletsort, logikai döntéseket hozva feldolgozás közben. 11

A

számítógépnek

rendelkeznie

kell

egy

belső

címezhető írható-olvasható tárral. Ez egy közös tároló abban az értelemben, hogy egyaránt tárolja a végrehajtandó program utasításait, és a feldolgozandó adatokat is. A memóriában az utasítások és az adatok a)

C

ugyanolyan módon – binárisan – ábrázoltak. A gép vezérlése tehát tárolt program alapján történik:

megjelenik a belső programvezérlés elve. A számítógépnek soros működésű, az utasítások végrehajtása szekvenciálisan történik. A processzor tartalmaz egy önálló egységet az aritmetikai és logikai műveletek elvégzésére. Az adatok és a program be- és kivitelére önálló egységek szolgálnak. Érdekesség, olvasmány A First Draftban leírt Neumann-elvű számítógép logikai felépítését mutatja a következő ábra. A nyilak az adatáramlás irányát jelzik. A rövidítések jelentése: CA: központi aritmetikai egység, CC: általános vezérlést ellátó egység, M: memória, R: külső rögzítő egység, I: beviteli egység, O: kiviteli egység. [7] Az EDVAC-nak volt egy elsődleges 1024 szavas higany-késleltetővonalas operatív tára és egy másodlagos, lassabb, 20 kilószó kapacitású mágnesdrótos tára. A tár és az aritmetikai-logikai egység is soros volt, bitenként dolgozta fel az adatokat. Adatbevitelre egy írógépszerű eszközt használtak, adatkivitelre egy nyomtatót. Egy program végrehajtásához előbb az egész programot és az adatokat be kellett táplálni a memóriába. Ez volt az első tárolt programú számítógép: egy új probléma megoldásához nem kellett a gépet áthuzalozni.

Neumann János zsenialitását bizonyítja, hogy ő fogalmazta meg azokat az elveket, amelyek alapján a mai számítógépek is felépülnek. Érdekesség, olvasmány Neumann János életrajza 1903. december 28-án született Budapesten, jómódú családban. Apja Neumann Miksa bankár, anyja Kann Margit volt. Két öccse volt, egyikük orvos, másikuk jogász lett. Már egész kisgyermekként rendkívüli nyelvtehetségnek számított, és kivételesen jó emlékezőtehetsége volt. Hat éves korában már folyékonyan tudott ógörögül, apjával e nyelven viccelődött. Tudott latinul is, anyanyelvi szinten beszélt németül, és több ismerőse szerint németül is gondolkodott. Angolul úgy beszélt, hogy rendkívül gyorsan fordította a németül megfogalmazott gondolatait angolra. Mire leérettségizett, már matematikusnak számított. Fiatal korától érdeklődött a repülés és a technika más újdonságai iránt. Már ekkor gondolkodott kettes alapú elektromos számológép építésén. Mivel a matematika és a technika is érdekelte, párhuzamosan két egyetemet végzett. Göttingemben, a német matematika fellegvárában tartotta meg első előadását a társasjátékok elméletéről. 1930 és 1933 között Amerikában és Európában is tanított. Meleg, emberséges személyiség volt, ily módon kiváló tanáregyéniséggé vált. Amikor Németországban győzött a fasizmus, letelepedett az Egyesült Államokban, 1937-ben kapta meg az amerikai állampolgárságot. Bekapcsolódott a nácizmus elleni katonai előkészületekbe: részt vett az atomenergia felszabadításában és háborús célú felhasználásában, majd a békés energiatermelés szolgálatába állításának irányításában is. 1945-től 1957-ig a princetoni Elektronikus Számítógép projekt igazgatója. Ekkor már az emberi agy, valamint az idegrendszer működését utánzó gépek kötötték le figyelmét. 1945-ben a cambridge-i egyetemen (Anglia) elkészült

12

az első elektronikus, tárolt programú számítógép, az EDSAC (Electronic Delay Storage Automatic Computer), mely már a „Neumann-elvek” alapján működött. A számítógép működéséhez a biológiát hívta segítségül: az emberi agy feladat megoldásainak mintájára megalkotta az algoritmust, s az agyat vette alapul a számítógépben való számítások elvégzésének megvalósításához. Érdemeinek elismeréseképpen az Amerikai Egyesült Államok elnöke kinevezte az USA Atomenergetikai Bizottságának elnökévé. Neumann mondta: „a tudomány a jövőben inkább a szabályozás és vezérlés, programozás, adatfeldolgozás, kommunikáció, szervezés és rendszerek problémáival törődik majd”. Felismerte, hogy egy rendszer biztonságát illetve hatékonyságát nem annyira az határozza meg, hogy milyen elemekből épül föl, hanem hogy hogyan van rendszerré szervezve, az elemek között milyen minőségű és mennyiségű információ megy át. Neumann János jól látta a fejődés további irányát, de életművét már nem Eisenhower fejezhette be. Hátralevő éveiben súlyos rákbetegségben szenvedett. elnök Szabadság 1957. február 8-án halt meg Washingtonban, Amerikában. [23, 24, 25]

Éremmel tüntette ki.

Második generáció (1955-1964) A tranzisztorok megjelenése nem csak a híradástechnikában, de a számítógépek világában is jelentős változásokat hozott. A tranzisztort 1947-ben fedezte William Shockley, aki ezért aztán 1956-ban Nobel-díjat is kapott. A tranzisztorokkal kisebb, gyorsabb és megbízhatóbb logikai áramköröket lehetett készíteni, mint az elektroncsövekkel. Ezek a gépek sokkal kevesebb energiát fogyasztanak és sokkal hosszabb életűek. Másodpercenként egymillió műveletet is el tudtak végezni amellett, hogy megbízhatóságuk nagyságrendekkel nagyobb lett. Egyúttal sokkal olcsóbbá is váltak a számítógépek, emiatt nőtt az eladások száma, egyre több cég kezdett számítógépgyártással foglalkozni. Az 1950-es években több forradalmi újítás is született. Jay W. Forrester kidolgozza a ferritgyűrűs memóriát, a második és harmadik generációs gépek jellegzetes operatív tárát. Kidolgozzák az amerikai John Backus vezetésével a FORTRAN nyelvet, majd az évtized végén az ALGOL programozási nyelv definíciójának első változatát, és 1960-ban publikálják a COBOL első változatát. A szoftver értéke a hardverhez képest egyre nőtt. Ebben az időszakban építették az első szuperszámítógépeket, melyek különlegesen gyorsak voltak. A gyorsabb műveletvégzés elérésére fejlesztették ki az egy időben végrehajtható tevékenységek számának növelését. Az első teljesen tranzisztorizált számítógép, az RCA 501-es 1959-ben készül el. Input-output processzorokat vezettek be az adatbevitel és kivitel felügyeletére, így a CPU-t sok időigényes tevékenységtől és várakozástól szabadították meg. Jellemzővé vált a mágnesdobos és a ferritgyűrűs operatív tár használata, háttértárolóként mágnesszalagot és újdonságként mágneslemezt használtak.

13

Érdekesség, olvasmány Jelentős szerepet játszottak a számítástechnikai oktatás, kutatás és az alkalmazásfejlesztés fejlődésében Magyarországon a ’70-es években az ODRA számítógépek. Ezeken a gépeken már tanítani lehetett az ALGOL60 magas szintű algoritmikus programozási nyelvet is (pontosabban ennek az ODRA-1204 számítógépes változatát, az ALGOL-1204-et), amelyben sokkal egyszerűbben és elegánsabban lehetett programozni, mint gépi kódban. Az ODRA-1204 típusú, második generációs, közép-teljesítményű digitális számítógépet francia licence alapján a lengyel ELWRO cég fejlesztett ki 1967-ben. Az ODRA-1204 jellemzése: • vezérlő pult; • konzol írógép (ROBOTRON) a gép irányítására, de be/kimenethez is használni lehetett; • a központi egység 6 µs ciklusidejű, ferritgyűrűs operatív memóriája 16384 db. 24+1 bites ún. "gépi szó" kapacitású • 8 csatornás lyukszalagos be/kimeneti egység; • 80 karakter széles (DATA PRODUCT) sornyomtató; • 32 kiló-szavas (1 szó 24 bit) 96 Kbájt-os ferritgyűrűs operatív memória; • 4 db 64 kiló-szavas fix mágnesdob háttértár (kapacitás ~ 768 Kbájt) Programozása: Vezérlőrendszere nem volt, különböző kezelőprogramokat kellett használni, melyek bináris lyukszalagon voltak, ezek bevitele a memóriába a BINO elnevezésű fixen beépített bináris beolvasóval történt; • az utasítások végrehajtását mikroprogramok generálták, melyek 512 szavas tárban voltak; • assembler (JAS); • autókód ( MOST-2); • algoritmikus nyelvek (Algol-1204, FORTRAN); • a programok lyukszalagra rögzített szövegét különböző kezelő kétlépcsős fordító) programokkal közvetlenül a memóriába, vagy bináris szalagra fordítottuk, s a futtatáshoz is szükség volt úgynevezett segédprogramok (PP) bevitelére (I/O eljárások, függvények, eljárások). A működtetéséhez a vezérlőpult már nem játszott olyan nagy szerepet, hanem a segédprogramokkal – a konzol írógépet használva – az operátor kommunikálhatott, ezzel irányítva minden tevékenységet.

ODRA 1013

Az ODRA-1204 központi egysége

ODRA 1204

A korszak másik jellemző gépe: az R-30

[30, 31, 32, 33]

14

Harmadik generáció (1965-1974) A harmadik generációs számítógépek jellegzetes építőeleme az integrált áramkör, IC, melyet 1958-ban fedezett fel a texasi Jack S. Kilby. Az első integrált áramköröket tartalmazó számítógépek 1964-ben kerültek kereskedelmi forgalomba. Az integrált áramkörök tovább csökkentették a számítógépek árát, méretét és meghibásodási gyakoriságát. Mindezen tulajdonságok vonzóvá tették a számítógépet, a ’70-es években több mint 100.000 nagyszámítógépet és ugyancsak több mint 100.000 miniszámítógépet helyeztek üzembe. A könnyű kezelhetőséget segítette elő, hogy megjelent a monitor és a billentyűzet, valamint az első valódi operációs rendszerek. Ezekkel az olcsó gépekkel a számítástechnika kisebb cégek számára is elérhetővé vált. A Gene Amdahl tervei szerint készült IBM System/360-as megjelenése 1965-ben mérföldkőnek mondható: ez egy egész gépcsalád volt, amely hat különböző teljesítményű egymással kompatibilis modellből állt. Így lehetővé vált egy felhasználó számára, hogy bővíthesse a memóriát, nagyobb teljesítményűre cserélje a gépet, vagy más perifériát válasszon a gépéhez tetszés szerint úgy, hogy a már kész programjait használhatta az új gépen is. A

képen

számítógép

egy

IBM

látható.

360-as

A

terem

közepén a két nagy szekrényben van a számítógép. Az operátori konzolírógépen keresztül lehetett parancsokat

adni

az

operációs

rendszernek, és az üzeneteket is ide írta ki a gép. Elöl vannak a mágneslemezes egységek, a háttérben mágnesszalag-meghajtók, valamint egy sornyomtató látható.

15

A negyedik generáció (1971-) A hetvenes évektől kezdődően a számítógépek fejlődésében robbanásszerű változás történt. Ennek oka az igen nagy integráltságú (VLSI, Very Large Scale Integration) félvezető áramkörök megjelenése volt. Általánossá válik a félvezetős, integrált áramkörökből készült memória is. A mikroprocesszor megjelenése lehetőséget ad a személyi számítógép rohamosan terjedésének; elsősorban szövegszerkesztésre, táblázatkezelésre, grafikára, adatbáziskezelésre, játékra alkalmazzák. Az új technológiának köszönhetően tovább csökken a hardver ára, egyúttal megfigyelhető a szoftverek árának további növekedése a hardver árához képest. A számítógépek programozása szinte kizárólag magas szintű nyelveken történik. 1968-ban Nicklaus Wirth elkészíti a Pascal programozási nyelvet, amely a negyedik generációs számítógépeken arat sikert. Seymour Papert 1971-ben alkotja meg a teknőcgrafikával kiegészített LOGO nyelvet, amelynek pedagógiai érdemei elévülhetetlenek. E korszakra jellemző az is, hogy lehetővé válik a számítógépek összekapcsolódása hálózaton keresztül. Érdekesség, olvasmány Az első mikroprocesszor, 1971-ben készült, Ted Hoff tervezte, és az Intel készítette. Egy 7 mm oldalhosszúságú négyzet alakú szilíciumlapkán 2300 tranzisztort tartalmazott. A processzor 4 bites volt, azaz 4 bitet tudott párhuzamosan feldolgozni. Összesen 45 utasításból állt az utasításkészlete. Egyre több cég állította elő a saját mikroprocesszorait, megjelentek a 8, 16, 32, majd a 64 bites mikroprocesszorok. Az 1973-ban megjelent 8 bites Intel 8080-as mikroprocesszor meghatározó volt az újabb processzorok fejlesztésében és a személyi számítógépek gyártásában. 16 címvonala volt, így 64 kilobájt memóriát tudott megcímezni, a műveleteket azonban 8 bites adatokon tudta elvégezni. Az aritmetikai áramkörök fixpontos bináris és decimális számok összeadását és kivonását tudták elvégezni, a szorzást, osztást és a lebegőpontos műveleteket külön programozni kellett. 1973-ban az R2E nevű francia cég bemutatja az első mikroszámítógépet, a MICRAL-t. 1974-ben forgalomba kerül az első programozható zsebszámológép, a Hewlett-Packard által gyártott HP-65. Ugyanebben az évben megjelenik az első személyi számítógép, az Altair 8800, melyet összeszereletlen készlet formájában árusítottak, hihetetlen olcsón. Ez volt az első, kimondottan személyes felhasználásra tervezett asztali számítógép, és ez a gép indította el a számítógépes elektronika máig tartó forradalmát. A mikroszámítógépkészlet iránt hirtelen olyan nagy kereslet alakult ki, amire senki sem számított. Egyre több cég kezdett számítógépek gyártásával foglakozni, közük Tandy Corporation. Gépük billentyűzettel és katódsugárcsöves monitorral rendelkezett, az információ tárolására pedig mágneskazettás egység állt rendelkezésre. Stephen Wozniak és Steven Jobs Apple Computers néven alapított számítógépgyártó céget. Újítások közé tartozott a tárolására szolgáló olcsó lemezmeghajtó és a színes grafika, valamint az egér megjelenése. Áttörést jelentett az 1979-ben megjelenő VisiCalc, az első táblázatkezelő program, hiszen ezzel már a programozásban gyakorlatilag teljesen járatlan emberek is tudták a számítógépet használni 1981-ben lépett a színre IBM PC az IBM cég mikroszámítógépe. A PC bizonyította be, hogy a mikroszámítógép üzleti élet szükséges eszköze. Operációs rendszere a DOS. Ugyanebben az évben készült el az első hordozható mikroszámítógép, mely Adam Osborne műve volt. A gép 11 kg-ot nyomott. 1976-ban üzembe helyezik az első Cray-1 szuperszámítógépet, amely alkotójáról, Seymour Crayről kapja nevét. Kereskedelmi forgalomba is került, mivel azonban hétmillió dollárba került, csak igen nagy cégek tudták megvenni. Ez volt az első olyan számítógép, amely képes volt másodpercenként több mint százmillió lebegőpontos

16

műveletet végrehajtani, az alapműveletek végrehajtási ideje 12,5 ns. Az áramköröket freonnal hűtött függőleges lapokra szerelték. Azóta építettek ugyan gyorsabb számítógépeket is, de a Cray-1-et azóta is használják!

A ’80-as évek sok újdonságot hoztak. Ezek egyike a nagyteljesítményű 32 bites mikroprocesszorok megjelenése volt, melyek alkalmasak voltak fejlett többfelhasználós és multitaszkos operációs rendszerek futtatására. Egy másik újítás felhasználóbarát grafikus felhasználói felület (graphical user interface, GUI) bevezetése. Ma már beszédvezérlésű gépek is léteznek. A ’90-es évekre a számítógépgyártás vált a világ leggyorsabban fejlődő iparágává, a világon eladott több százmillió (!) személyi számítógép jelentős hányadát pedig már magánemberek vásárolják.

Ötödik generáció Ennek az új generációnak egyik fontos alkotóeleme a mesterséges intelligencia lesz: olyan intelligens számítógép létrehozása a cél, amelyik lát, hall, beszél és gondolkodik, képes asszociálni, tanulni, következtetéseket levonni és dönteni. Érdekesség, olvasmány Egy elképzelhető fejlődési irány 1993-ban Leon O. Chua és Roska Tamás jelentették be egy forradalmian új számítógép feldolgozási egységének kifejlesztését. Folytonosan működő, kicsi analóg számítógépek ezreit működtetik összekapcsolva, szemben az eddig elterjedt néhány komplex, digitálisan működő processzorral. A celluláris neutrális hálózat egy chipen belül megközelítőleg tízezer piciny feldolgozó egység együttes munkájával oldja meg a feladatokat, szédületes sebességgel: másodpercenként egy trillió művelet elvégzésével. Hasznosítása a képfeldolgozás és alakfelismerés területén óriási változásokat idézett elő. [5] A Roska Tamás akadémikus vezette kutatócsoport több, mint tízévi, amerikaispanyol együttműködésben végzett munka eredményeként a jelenleg alkalmazott számítógépek működési elvétől gyökeresen eltérő konstrukcióval dolgozó analogikai számítógépet fejlesztett ki. Az elnevezés az analóg és a logikai működés egyesítésére utal. Roska Tamás szerint a digitális technika ismert fizikai alapjainak és működési módjainak átgondolása igencsak időszerű volt. Az optikai érzékelők - így például a kamerák - ontják az analóg jeleket, ezek digitálisra konvertálása pedig nem megy olyan könnyen, lassú és Roska Tamás energiaigényes folyamat. „Azokon a területeken - mondja Roska -, ahol változó jelek tömegével kell dolgozni, olyan számítógép válhat be, amelyben közel kerül egymáshoz az érzékelés és a feldolgozás.”

Az analóg módon működő és logikai műveletekre képes komputer, az analogikai számítógép lelkét, a CNN csipet Leon Chua, a Berkeleybeli University of California kínai származású amerikai professzora és tanítványa, L. Yang találta fel 1988-ban. A CNN egy Cellurális Neurális/Nemlineáris hálózat. Olyan processzorsereg, amelyben az egyes processzorok (cellák) egy négyzetrács csúcspontjaiban foglalnak helyet. Mindegyik cella a közvetlen környezetében lévővel van összeköttetésben, azoktól hatást kap, illetve azokra hat. Ezek a hatások alakítják ki a CNN működését. Erre építve 1992-ben Roska és Chua megalkotta az úgynevezett CNN Univerzális Gépet, amely egy kétdimenziós rácson több ezer CNN elemi processzort tartalmaz. A CNN csip maga egy vizuális mikroprocesszor, amelyben minden egyes tranzisztor fényérzékelő optikával rendelkezik.

17

Az analogikai számítógépben a jelek folytonosak, érzékszerveinkből mintegy hullámszerűen terjednek tovább az idegrendszerben. Ezért a tudósok ezt a modellt hullámszámítógépnek is hívják. Egy új számítógépfajta jelent meg: vizuális mikroprocesszorként (látócsipként) már működő példányokat is lehet vásárolni. A számítógép alapelvét agykutatók, Hámori József, Frank Werblin és mások munkái inspirációjára alkotta meg Roska Tamás és Leon Chua. Ma már megszületett az új retinamodellnek a vizuális mikroprocesszoron történő részleges megvalósítása is, Bálya Dávid fiatal magyar kutató jóvoltából. 2002. március 2-án a Bolyai-díjat RoskaTamás vehette át Mádl Ferenc köztársasági elnöktől. [26, 27] Feladat 1. 2.

Nézz utána, hogyan lehet abakusszal számolni! Készíthetsz számoló asztalt a lenti rajz alapján egy nagyobb kartonlapra. Gyűjts össze a számok ábrázolásához 50 darab közel egyforma kavicsot! Kellő gyakorlás után rendezhettek versenyt is! Milyen számokat ábrázolnak az abakuszok?

3.

Figyeld meg a következő ábrákon az összeadás lépéseit. Készítsetek hasonló feladatokat a számolóasztalon!

+

=

+

=

4.

Gyűjts képeket régebbi és mai számítógépekről! Ragaszd be a képeket füzetedbe! A képek forrásai számítástechnikai folyóiratok, újságok lehetnek. Internetről is tölthetsz le képeket! 5. Nézz utána, hogy a következő magyar vagy magyar származású személyek, milyen szerepet játszottak vagy játszanak ma is a számítástechnika fejlődésében! Neumann János, Kozma László, Kalmár László, Nemes Tihamér, Tarján Rezső, Roska Tamás, Halassy Béla, George Kemeny, Charles Simonyi.

18

A számítógép felépítése A számítógép eredményes működéséhez számos berendezés, egység összehangolt tevékenységére van szükség. Hardvernek nevezzük a számítógép „kézzel fogható részeit”, pontosabban mechanikus és elektronikus építőelemeinek, alkatrészeinek összességét. Szoftver nélkül azonban nem tudjuk a számítógépet használni. A szoftver a számítógép működtetéséhez, valamint a feladatok megoldásához használt programok összességét jelenti. Mindezen erőforrások együttes működése biztosítja a számítógépes feladatmegoldás lehetőségét. A számítógép logikai felépítését mutatja be a következő ábra: Központi feldolgozó egység

Input egység

Output egység

Háttértárak

A ma használt számítógépek felépítését, működését nagyban meghatározzák a Neumannelvek. A külvilágból az adatok, információk a számítógép input egységén keresztül jutnak a központi egységbe, ahol a feldolgozás történik. A háttértárakon adatok és programok tárolását végzi a gép, a feldolgozás eredményét pedig az output egységen keresztül közli a külvilággal.

A központi feldolgozó egység Központi feldolgozó egység Input egység

Processzor

Memóriák

CU ALU

ROM RAM

Háttértárak

19

Output egység

A központi feldolgozó egység (Central Processing Unit, CPU) két fő alkotóeleme a processzor és a memóriák, de valójában még tartalmaz ún. regisztereket is, melyek kis tárolókapacitású, de rendkívül gyors elérésű tárolók, gyakran használt adatok, illetve részeredmények tárolására szolgálnak. A CPU feladatai közé tartozik a gép irányítása, a feldolgozási folyamat vezérlése, az adatok feldolgozása, a külvilágból érkező illetve a külvilág felé küldött adatforgalom irányítása. Az egyes résztevékenységeket a CPU-n belül önálló részek végzik. Az egyik ilyen egység a processzor, amely a vezérlőegységből (Control Unit, CU) és az aritmetikai-logikai egységből (Arithmetical Logical Unit, ALU) áll, valamint tartalmaz gyors elérésű adattárolókat, regisztereket is. A processzor alkotóelemeit egyetlen áramköri lapon, chipen állítják elő. Az integráltsági fok egy ilyen lapkán óriási, több millió elektronikai alkotóelem zsúfolódik össze egyetlen cm2-en. A vezérlőegység feladata a parancsok (a parancs a legkisebb munkafolyamat a processzoron belül, melynek lépései az utasítások) feldolgozási sorrendjének meghatározása. Kapcsolatban áll az ALU-val és az operatív memóriával, feladata tehát az ezekkel való kapcsolattartás, valamint a parancsok értelmezése, és végső soron a számítógép egységeinek vezérlése mindezen információk alapján. Az ALU feladata a nevében van: aritmetikai és logikai műveletek végrehajtására szolgál. Egyszerű logikai áramkörökből épül fel, melyek összehasonlítani, léptetni, invertálni és összeadni tudnak. A processzoron belül az információ- és adatcsere ún. buszokon (vagy síneken) keresztül zajlik. A címbuszon keresztül történik a megfelelő tárolócella kijelölése, az adatbusz az adatok továbbítását látja el, a vezérlőbusz pedig vezérlőjeleket továbbít. A folyamatok időbeli ütemezését egy órajel-generátor végzi. Az órajel frekvencia a processzor, így a számítógép működési sebességének jellemző adata. A mai számítógépek esetén GHz nagyságrendű. A CPU másik fontos egysége az operatív tár vagy memória. Itt tárolódnak az adatok a processzor számára, ezek olyan adatok, amelyek a feldolgozáshoz éppen szükségesek, és gyorsan rendelkezésre is állnak. Alapvetően kétféle típusú memóriát különböztethetünk meg: ezek a ROM és a RAM. A RAM (Random Acces Memory, közvetlen hozzáférésű memória) olvasható, törölhető, újraírható tár. Csak áramellátás esetén őrzi meg tartalmát, mely a számítógép kikapcsolásakor, vagy akár áramszünet esetén elvész. A ROM (Read Only Memory, csak olvasható memória) adatai gyártáskor kerülnek fixen a tárba, így a felhasználó csak olvasni tudja (illetve a számítógép felhasználja 20

működéséhez) ezeket az adatokat, de törölni, írni nem. A ROM tartalma áramellátás nélkül is megmarad, így nem változó adatok, programok kerülnek ide. Az input és output egységeket, valamint a háttértárakat közös néven perifériáknak nevezzük. A központi egység a perifériákkal az adatcsatornákon keresztül tartja a kapcsolatot.

Perifériák A számítógép központi egysége és a külvilág közötti adatcserét megvalósító eszközöket be- és kiviteli (input-output, I/O) eszközöknek nevezzük. Az adatforgalom szempontjából a következő csoportokba sorolhatjuk ezeket: 1) Adatbeviteli vagy input egységek: az adatok, programok, vezérlőjelek ezeken keresztül jutnak a számítógépbe. Leggyakrabban a billentyűzetet és az egeret szoktuk használni. A billentyűzeten betűket, számokat, speciális jeleket, egyszóval karaktereket vihetünk be. Az egér mutatóeszköz, mellyel a parancsok begépelését válthatjuk ki rámutatással és kattintással. A sokféle egyéb eszköz közül néhány, a teljesség igénye nélkül: botkormány, scanner (lapbeolvasó), mikrofon, botkormány (joystick), trackball („hanyattegér”), vonalkód leolvasó, fényceruza, virtuális valóság kesztyű, stb. 2) Adatkiviteli vagy output egységek: Az információkat, a feldolgozás eredményeit ezeken az eszközökön keresztül jeleníti meg a számítógép. A leggyakrabban alkalmazott eszközök a képernyő (monitor) és a nyomtató (printer), de számos más berendezés is használatos, például hangszóró, rajzgép (plotter), mikrofilm, virtuális valóság sisak, stb. 3) Be- és kivitelre egyaránt alkalmas eszközök: Ide tartoznak a háttértárak, melyek adatok tárolására szolgáló eszközök. Tartalmukat áramellátás nélkül is megőrzik, így hosszú távú tárolásra alkalmasak. Adathordozóik szerint egyfajta csoportosításuk lehet a következő: A háttértárak lényeges jellemzői a tároló típusa, kapacitása, elérési ideje. a) Mágneses tárak Működési elvük: az adathordozó felületén lévő mágneses réteg alkalmas arra, hogy kétállapotú jeleket rögzítsen. Az elektromos áram mágneses mezőt hoz létre maga körül, mellyel az adatok rögzítésekor megváltoztathatjuk a felület mágnesezettségét. Olvasáskor a mágneses térben levő vezetőben áram keletkezik, így visszakaphatjuk azokat az elektromos jeleket (adatokat), amiket rögzítettünk.

21

Floppy A hajlékonylemezes meghajtó (floppy disk drive, FDD) adathordozója a hajlékony mágneslemez (floppy disk). A meghajtó a számítógépbe van építve, míg az adathordozó cserélhető. Ha írunk a lemezre vagy olvasunk róla, egy elektromotor megforgatja a lemezt. A lemezt két író-olvasó fej (pici elektromágnes) veszi közre, melyek sugárirányban mozoghatnak. A fej bitsorozatokat ír, amelyek a lemezen rendkívül kicsi (mikrométer nagyságrendű) mágnesezett tartományok. A lemez egy vékony, hajlékony műanyag korong, mindkét oldalán jól mágnesezhető anyaggal bevonva, műanyag burkolat védi a szennyeződésektől. A lemezeket óvni kell a magas hőmérséklettől és az erős mágneses hatásoktól! A lemez mérete többféle lehet. A normállemez 8” (8 coll vagy inch) a minilemez 5,25”, mikrolemez 3,5”, a kompaktlemez 3” átmérőjű. A leggyakrabban 3,5”-os lemezt használunk, melynek hétköznapi elnevezése „kislemez”. A lemezek burkolatán különböző nyílások vannak: nyílás az író-olvasó fej számára, indexlyuk a lemez helyzetének érzékelésére, írásvédő nyílás. A 3,5”-os lemezek esetén a fejnyílást fedőlap zárja el, amely a meghajtóban automatikusan kinyílik. Az 5,25”-os lemezek esetén, ha az írásvédő nyílást leragasztjuk, a lemezre nem lehet írni. Ez a megoldás védelmet nyújt a véletlen törlés és a vírusok ellen. A 3,5”-os lemez esetében ugyanezt a hatást érhetjük el, ha a sarkában lévő írásvédő ablakot kinyitjuk. A lemezt első használat előtt formázni kell. Ezzel a művelettel válik a lemez adattárolásra alkalmassá. A formázást az előre formázott lemezek esetén már a gyártás során elvégzik. Formázáskor a lemezen koncentrikus körök vagy sávok (trackek), majd a sávokon belül szektorok alakulnak ki. E kettő tartja nyilván az egyes állományok fizikai helyzetét a lemezen. A lemezeken található rövidítések jelentése: DS = Double Sided - kétoldalas lemez, DD = Double Density - dupla írássűrűség HD = High Density - magas felbontású. Lemezátmérő lemezjelzés kapacitás sávok száma szektorok száma

3,5” DS, DD DS, HD 720 KB 1,44 MB 80 80 9 18

5,25” DS, DD DS, HD 360 KB 1,2 MB 40 80 9 15

A floppy előnye, hogy cserélhető, olcsó, a számítógépek közötti adatcsere egyik eszköze, de hátránya, hogy kis kapacitású és lassú.

22

Winchester Merevlemezes tároló (hard disk drive, HDD). Adathordozója merev, mágnesezhető felületű (fém) lemezkorong. A lemezek itt nem cserélhetők, ugyanis a meghajtóval egybeépítettek, és több is lehet egymás felett egy tengelyen. A lemezek és a meghajtó légmentesen záródó tokban helyezkednek el, mert az oldalakhoz tartozó író-olvasó fejek olyan közel vannak a lemezfelülethez (0,3 µm), hogy egy porszem is komoly károkat okozhat. A jelrögzítés módja hasonló a floppy-nál megismertekkel: az adatok tárolása koncentrikus körökben elhelyezkedő sávokban és szektorokban történik. Újdonság azonban, hogy a lemezek egymás feletti sávjait cilindereknek nevezik, a tárolás pedig klaszterekben, a szektorok logikailag összetartozó csoportjában történik. A winchester lemezei együtt forognak, jóval gyorsabban, mint a floppy. További, jelentős különbség van a tárolható adatok mennyiségében is: a winchesterek tárolókapacitása Gigabyte nagyságrendű, tehát nagy kapacitású, gyors háttértár. Legtöbbször a számítógép házában található, nem cserélhető, de léteznek kivehető merevlemez-meghajtók is (mobil rack-ek) és hordozható, külső winchesterek is. A floppyn és a winchesteren kívül számos más, kevésbé ismert illetve használt mágneslemezes tár is létezik, mint például a Zip Drive, az „A” Drive, a Jaz Drive. Érdekesség, olvasmány Zip Drive A legtöbb ZIP-meghajtó hordozható, s így minden gépre gyorsan csatlakoztatható. A hozzá tartozó lemezekre 100 MB illetve 250 MB fér. Hátránya, a meghajtó nem kompatíbilis a hagyományos floppy lemezekkel. „A” Drive A rendszeregységbe beépíthető, vagy a párhuzamos portra csatlakoztatható mágneslemezes háttértár. 120 MB-os cserélhető lemezekkel működik, de a 3,5-es floppy lemezeket is kezelni tudja. Tízszer gyorsabb és 83-szor nagyobb kapacitású a 3,5”-os floppy-meghajtónál. Mivel drága, nem terjedt igazán el. Jaz Drive A Jaz Drive cserélhető mágneslemezei lehetnek 1 vagy 2 GB-osak is. Gyorsasága majdnem eléri a merevlemezek gyorsaságát. A meghajtó nagyon drága.

Mágnesszalagos tárak A háttértáraknak ez a típusa már a ‘60-as években megjelent. Működése leginkább a közönséges magnetofonok működésére hasonlít. A mágnesszalagos adattárolókat streamernek, „adatáramoltatónak” is nevezik. Ma leginkább archiválásra, azaz nagy mennyiségű adat hosszú ideig való tárolására használják, illetve gyakran (pl. winchester-tartalom) biztonsági másolat elkészítéséhez alkalmazzák. Az áruk a winchesteréhez hasonló, de a kazettáik olcsók. Előnye, hogy nagy mennyiségű, akár

23

több gigabájtnyi adat olcsó tárolása lehetséges. Hátránya viszont, hogy lassú, ugyanis a szalagot oda kell „pörgetni”, ahol a keresett információ található. b) Optikai tárak E tárak esetén az adatokat lézersugár írja egy forgó optikai lemezre. Ez a lemez műanyagból készült, melyre fémfólia kerül. A lemezen az információt hordozó jelek spirálisan rögzítettek. Az információkat különböző fényvisszaverő képességű „gödröcskék” (pitek) formájában tárolják a lemezen. Olvasáskor a lemezkorongot egy gyenge lézernyalábbal világítják meg, és a visszaverődő fény erőssége alapján határozza meg a meghajtó a tárolt jelet. Mivel az információt lézersugár olvassa ki, ezért a lemez nincs kitéve komoly fizikai igénybevételnek. Az adathordozó réteget védő műanyag réteg óvja a portól, és a lemez a röntgensugarakra sem érzékeny. A CD (Compact Disk, CD-ROM = CD Read Only Memory) kapacitása 650 MB – 4 GB. Csak olvasható lemez, a tartalma nem változtatható meg. Előnye, hogy olcsón lehet

rajta

nagy

mennyiségű

adatot

tárolni

(adathalmazokat,

lexikonokat,

telefonkönyveket, telepítő programokat). A CD-meghajtó zenei CD-ket is képes lejátszani. A meghajtók ára fokozatosan csökken, tárolókapacitásuk és átviteli sebességük egyre nő. Kezdetben adatkiolvasási sebességük lényegesen kisebb volt, mint a winchestereké, kb. 150 Kbyte/s. A meghajtókat ma egy gyorsasági viszonyszámmal szokták jellemezni: egy tízszeres sebességű meghajtó adatkiolvasási sebessége 1500 Kbyte/s. Ma már többszörösére nőtt ez a sebesség is. Léteznek olyan CD-k is, amelyek nem csupán olvashatóak, hanem írhatóak is. Az egyszer írható (CD-R) lemezek esetén erős lézernyalábbal égethető információ a lemez felületére. Vannak újraírható (CD-RW) lemezek is. A DVD az optikai lemezes tároló-technológia új generációja. Tulajdonképpen ez egy nagyobb kapacítású, gyorsabb CD, amely képes mozi minõségû videót, CD-nél jobb minõségû hangot, fényképeket, és számítógépes adatokat tárolni. A DVD célja, hogy a házi szórakoztató eszközöket, a számítógépeket, és az üzleti információkat egyetlen digitális formátumban egyesítse. Mit jelent a DVD rövidítés? Sok féle eredete van a mozaik szónak, de hivatalosan nincs szabványosítva a szó. Néhány változat jelentéséről: Digital Video Disc (digitális videó lemez) - az eredeti jelentés, melyet néhány DVD fejlesztõ javasolt Digital Versatile Disc (sokoldalú digitális lemez) - egy késõbbi jelentés, melyet néhány DVD fejlesztõ javasolt 24

A DVD adatsűrűsége igen nagy, így tárolókapacitása több gigabájtnyi. A DVD-re ráfér egy kétórás videofilm is, sztereó hanggal, jó képernyőfelbontással. c) Egyéb A tárgyaltakon kívül igen sok olyan háttértár létezik – vagy létezett –, melyek alkalmazása kevésbé elterjedt. A teljesség igénye nélkül néhány: lyukkártya, lyukszalag, mágnesdob, mágneskártya, magnetooptikai tárolók. A számítógép belsejében, a gépházban található a számítógép egységeit fizikailag összekötő áramköri lap az alaplap, mely helyet ad a processzor, a memóriák, az illesztőkártyák számára. A perifériák ugyanis illesztő-áramkörökön keresztül kapcsolódnak az alaphoz. A billentyűzet illesztője az alaplapba van építve, más perifériákhoz azonban az illesztők külön kártyákon,

ún.

illesztőkártyákon

vagy

vezérlőkártyákon

helyezkednek

el

(pl.

monitorvezérlő). A részegységeket buszrendszer köti össze, ehhez csatlakoznak az illesztőkártyák és a beépített illesztők is. A buszrendszer bővíthető.

A számítógépek alapkonfigurációja Alapkonfiguráción értjük a számítógép központi egységét, a vele egybeépített belső memóriával együtt, egy merev és egy hajlékony mágneslemez egységet, mint háttértárolót, egy billentyűzetet és egy monitort. A multimédia számítógép CD-ROM-meghajtót, hangkártyát, hangszórókat és mikrofont tartalmaz. Egy „egyszerű” számítógép dobozában az egyes hardverelemek – igen vázlatosan – a következőképpen helyezkednek el: [36]

25

A számítógépek programozása A számítógép az adatok, információk befogadására, tárolására, visszakeresésére, feldolgozására, az eredmények közlésére alkalmas elektronikus gép. A számítógép működéséhez azonban nem elég maga a berendezés, a hardver: szükség van szoftverekre, programokra. Egy adott feladat megoldásának lépéseit, valamint azok sorrendjét az algoritmus írja le. Az algoritmusban leírt lépéseket a számítógép számára „érthető” formában kell megadnunk: ez a program, létrehozásának folyamata pedig a programozás. A program legkisebb funkcionális egysége az utasítás. A program az utasítások sorozatából áll. Az utasításokat tárolni kell, majd egyenként, a meghatározott (nem feltétlenül lineáris) sorrendben végre kell hajtani. A leírás nyelvét programozási nyelvnek nevezzük.

Programnyelvek kialakulása, fejlődése A világon több száz programozási nyelvet használnak. E nyelvek jelentőségét akkor értjük meg, ha megvizsgáljuk, hogyan működtethető a számítógép ilyen nyelvek használata nélkül. [2] A számítógép alapvetően csak a saját „nyelvét” képes megérteni Ez egy olyan utasításnyelv, amely a számítógép számára közvetlenül érthető módon, azaz bináris formában adja meg az elvégzendő feladat végrehajtásához szükséges információkat. Ezt a nyelvet nevezzük gépi kódnak.[2] A számítógép működésének alapjául a már tárgyalt Neumann-elvek szolgálnak!

Gépi kódú programozás Az utasítások végrehajtása a vezérlőegység feladata. A gépi kódú utasítás végrehajtásához információkra van szüksége: „mit” kell elvégezni, „mikkel”, azaz meg kell adni az operációt és az operandusokat. Ezek az információk a központi tárban, bináris szám formájában helyezkednek el, így ezek címére szükségünk lesz. Tudnunk kell azt is, hogy a majdani eredmény hova kerüljön, valamint azt is, hogy keressük a következő utasítást.

26

Az utasítás formája tehát: op.

c1

ahol op.: az elvégzendő művelet kódja.

c2

c3

c4

(a műveletek sorszámozottak)

c1: az első operandus címe c2: a második operandus címe c3: az eredmény címe c4: a soron következő utasítás címe Például a program végrehajtása során eljutunk a következő értékadási művelethez: Z := X +Y. Ekkor itt az első operandus az X címen (c1), a második operandus az Y címen (c2) van, az eredménynek pedig a Z címre (c3) kell kerülnie, a végrehajtandó művelet pedig összeadás (op.).

Valószínűleg

a

programunknak

további

folytatása

is

van,

az

utasítások

egymásutániságának biztosítására ismernünk kell a következő utasítás memóriacímét: c4. Ezek a címek tárbeli címek, bináris számokkal jelöltek. [2] Az ilyen – elvileg elkészíthető – gépet 4 címes gépnek nevezzük. Ha egy utasítás 24 bit (3 byte) címezhető memóriaterületen helyezkedik el, és 4 bit „jut” az operációra, akkor 24 = 16 féle műveletet tud elvégezni ez a gép. A további címerekre marad 55 bit, így 25 = 32 féle címet lehet megszólítani. Gondoljunk csak bele: ha minden utasításnak ennyi információval kellene rendelkeznie, akkor egy-egy utasítás is rengeteg helyet foglalna el, nemhogy egy egész program! Ilyen gépet nemigen érdemes építeni. Milyen módon lehetne az utasítás hosszát – az információk számát – csökkenteni? Fenntarthatunk egy külön memóriaterületet, rekeszt az eredmény számára, így az eredmény címe kikerül az utasításból: op.

c1

c2

c4

Ekkor egy 3 címes utasítás-formához jutunk, az ilyen utasításokkal dolgozó gép 3 címes gép. Az eredményt tároló rekesz elnevezése: akkumulátor, mely tehát egy kitüntetett memóriaterület, regiszter. Az operációra és a memóriaterületek címzésére egyaránt 6-6 bit állhat rendelkezésre, így 26 = 64 féle művelet végezhető el, ugyanennyi rekesz címezhető meg. Nem kell minden utasításnak tárolnia azt sem, hogy mi a második operandus címe (nincs is minden utasításnak két operandusa!). A második operandus legyen mindig az, amit az akkumulátor tárol. Így már 2 címes géphez jutottunk: op.

c1 27

c4

Ha ekkor 4 bitet szánunk az operátorra, 24 = 16 féle műveletet képes a gép elvégezni. Marad 10-10 bit a tárolóterület címzésére, így 210 = 1024 rekesz áll rendelkezésre. (Ilyen számítógép már létezett.) Valójában megtakarítható a következő utasítás címének tárolására szolgáló utasítás-rész is akkor, ha elgondolkodunk a Neumann-elvek közül azon, amely azt határozza meg, hogy a gép soros működésű legyen. Ezek szerint a soron következő utasítás lesz a következő – az utasításban felesleges letárolni a címét! Tüntessünk ki egy újabb rekeszt, regisztert, melynek nem lesz más feladata, mint hogy vezesse, adminisztrálja, tárolja a következő utasítás címét. Ezzel eljutottunk az 1 címes géphez! A bevezetett regiszter neve: utasítás-számláló regiszter. Az utasítás felépítése tehát a következő: Op

c1

Címrész MIVEL Kell csinálni (operandus)

műveleti rész MIT kell csinálni (operáció)

Mivel bináris számok formájában tároltak az utasítások is és az adatok is (Neumann-elv!), „ránézésre” nem is látszik, hogy mi van egy memóriarekeszben, vagy utasításrészben. A számítógép azonban más memóriaterületen tárolja az adatokat és az utasításokat. Az, hogy melyik részre hány bit jut, már gyártótól függ, tőle függ a gép utasításkészlete is. Az ilyen módon leírható programozási nyelvek a gépi kódú programozási nyelvek. A gépi kódban való programozás igen nehéz, hálátlan munka, hiszen számok tömkelegével kell dolgozni. „Cserébe” a gép az ilyen utasításokat tudja a leggyorsabban végrehajtani, hiszen egy olyan nyelven „szólunk hozzá”, amit közvetlenül megért: a beírt jelsort a gép azonnal végre tudja hajtani, minden további átalakítás nélkül. Eleinte ez volt az egyedüli lehetőség a gép programozására. Gyakorlatilag csak az képes ezen a nyelven helyesen működő programokat írni, aki jól ismeri a gép belső felépítését. Minden processzor külön nyelvvel rendelkezik, a programok tehát processzorfüggők.

28

Érdekesség, olvasmány A gépi kódú programozás megértése érdekében tekintsük a következő példát [1]: Képzeljük el, hogy van egy számítógép, melynek néhány utasítása gépi kódban a következő: MIT? 01 02 03 04

MIVEL? xxxx xxxx xxxx xxxx

11 12 21

xxxx xxxx xxxx

22

xxxx

23

xxxx

31 32 33

0000 0000 0000

JELENTÉSE a := a + (xxxx) a := a - (xxxx) a := a ⋅ (xxxx) a := a / (xxxx) (xxxx) := a a := (xxxx) e := xxxx xxxx,ha a < 0 e := e + 1,ha a ≥ 0 xxxx,ha a = 0 e := e + 1,ha a ≠ 0 beolvasás az „a”-ba kiírás az „a”-ból STOP

Az xxxx jelölés rekeszcímre utal, melynek értéke 1000 ≤ xxxx ≤ 2000 lehet a 0 és 1 utasításcsoportnál, és 0 ≤ xxxx ≤ 1000 a 2 utasításcsoportnál. (1000 a program utolsó utasításának sorszáma. Ezért azért fontos tudnunk, mert ebből látszik, hogy egy adott számsor adatot vagy műveletet jelöl.) Az „a” jelölje az akkumulátort. Feladat: Készítsünk programot, amely négy tetszőleges szám összegét határozza meg! A feladat megoldásához készítettük a következő két folyamatábrát: az elsőben leírtuk a feladat megoldásához szükséges algoritmust, a másodikat a megfelelő gépi kódú utasításokkal építettük fel. Mellettük található maga a program. A számokat képviselő változók és rekeszcímeik legyenek a következők: A: 1000, B: 1001, C: 1002, D: 1003. E feladat megértése után az adott utasításkészlet felhasználásával már összetettebb feladatok megoldására is vállal–kozhatunk.

START

START

INPUT A

INPUT a (1000) := a

1 2

31 0000 11 1000

INPUT B

INPUT a (1001) := a

3 4

31 0000 11 1001

INPUT C

INPUT a (1002) := a

5 6

31 0000 11 1002

INPUT D

INPUT a (1003) := a

7 8

31 0000 11 1003

A := A + B + C + D

a := a + (1000) a := a + (1000) a := a + (1000)

9 10 11

01 1000 01 1001 01 1002

PRINT A

PRINT a

12

32 0000

STOP

STOP

13

33 0000

29

PROGRAM

Feladat Készítsünk programot, amely két tetszőleges szám a) különbségét b) szorzatát c) hányadosát d) átlagát számítja ki!

Tapasztalhattuk, hogy a gépi kódú programozás az ember számára igen kényelmetlen: a hosszú bináris számokkal való műveletvégzés nehéz, könnyen téveszteni lehet. A hiba megkeresése sem egyszerű. Minden műveletet olyan szinten le kell bontani, hogy egy-egy utasításban csak egyetlen hardverutasítás szerepeljen. [2] Mindezen okok arra sarkallták a programozókat, matematikusokat, hogy olyan programozási nyelvet készítsenek, amely az ember számára könnyebben kezelhető.

Szimbolikus programnyelvek A szimbolikus programnyelvekben az utasításkódok és a rekeszek címei helyén az ezekre utaló szavak, betűk állnak. [1] Mivel a szimbólumok betűkombinációkból álló mnemonikus (megjegyezhető) kódok, könnyebb megtanulni, használni őket, hiszen beszédesebbek, mint a számsorozatok.[5] Az utasításkódok helyett használt szimbólumokat azonban választhatjuk meg szabadon: ezeket a gyártók adják meg. Ezeket, a géphez még közel álló, és gyakran géphez kötött nyelveket nevezzük assembly szintű nyelveknek [2] vagy alacsony szintű nyelveknek [5]. Az így készített programokat viszont a számítógépek nem értik meg közvetlenül, ezért a gépnek először le kell fordítania a saját nyelvére, gépi kódjára a szimbólumokat (azaz a műveleti kódot, az utasítások, és az operandusok címét át kell alakítani a megfelelő bináris számokká). Erre szolgál az assemblernek nevezett fordítóprogram, melyet egy adott géptípushoz készítenek el. Ez tulajdonképpen egy „szótár”, egy táblázat, amelynek egyik oszlopában a mnemonikus kódok, a másik oszlopában az ezekhez tartozó numerikus kódok vannak. [2] A feldolgozás emiatt a közbeékelődő lépés miatt ugyan lassul, cserébe viszont az emberhez közelebb álló nyelvet kaptunk. (Az embernek kevesebbet, a számítógépnek többet kell dolgoznia.) Ez a nyelv tehát az emberi nyelv és a gépi kód között van, de még inkább közelebb a gép nyelvéhez. Abban az időben, amikor az erőforrások szűkössége miatt fontos volt, hogy a hardverhez közelebb álló nyelvet használjanak, sok program készült ilyen nyelven. A számítógépek tömeges terjedése azonban megkívánta az emberközelibb nyelvek kialakítását. [2] 30

Automatikus kódolású programnyelvek Az ún. mikro-utasítások mellet feltűntek a makro-utasítások, melyek összetettebb műveletek elvégzését tették lehetővé. Ekkor jelent meg a változó is, amely olyan, aminek az értéke valamilyen adat, illetve a címke is, amely olyan memóriacímet szimbolizál, amelyen egy utasítás van. Függvényeket hoztak létre, és „visszajöttek” a matematikai jelek. Az ilyen tulajdonsággal bíró nyelveket nevezzük automatikus kódolású programnyelveknek. (Vannak irodalmak, melyek középszintű nyelveknek nevezik. [5]) Géptípustól függetlenebb, nagy hatékonyságú programozási nyelvek tartoznak ide. Fordítója az ún. compiler, amely a gépi kódot állítja elő. A compiler az egész forrásnyelvű programot végig, utasításonként (soronként) vizsgálja szintaktikailag, értelmezi, lefordítja a programot, készít egy lefordított állományt is, mely az eredetivel egyenértékű, de sokkal gyorsabban működő gépi kódú program. Hiba esetén jelzést ad. A programozónak ismernie kell továbbra is a gép legtöbb hardver paraméterét. Az ötvenes években jelent meg a FORTRAN (FORmula TRANslation) és ilyen nyelv például a C, a FORTH. [5]

Algoritmikus programnyelvek Egyre erősödött az igény a géptől független nyelvek iránt: a programozó t ne befolyásolja az, hogy programja milyen gépen fog futni, ne kelljen a gép hardveréhez igazítania a programját. Tegye ezt meg a fordító, a forrásprogramot mindegyik gép a saját gépi kódjára fordítsa le. [2] Ehhez még bonyolultabb fordítóprogramokra van szükség, és a hangsúly a gépről az algoritmusra kerül. Szokás ezeket a nyelveket magas szintű programozási nyelveknek is nevezni. A programozó segítségükkel gépfüggetlen programokat készíthet, amelyek ugyan kevésbé hatékonyak, de szabadon hordozhatók. Ismét meg kell említenünk a FORTRAN-t, mely műszaki-tudományos problémák megoldására készült elsősorban: kevés bemenő adat, bonyolult műveletek jellemzik az ilyen feladatokat. Ebben az időszakban jelent meg a COBOL (COmmon Business Oriented Language) is, de merőben más céllal: adatfeldolgozásra orientált nyelv ez, így sok bemenő adat feldolgozására tervezték, a sok kimenő adatot viszonylag kevés és egyszerűbb matematikai művelettel állítva elő. [2] Az üzleti életben, de akár népszámlálási, szavazási adatok feldolgozására alkalmas.

31

A hatvanas években jelent meg az ALGOL (ALGOrithmic Language) melyet matematikai feladatokhoz, műszaki-tudományos feladatok megoldására terveztek. A FORTRAN-nal ellentétben ezt a nyelvet nem a gyakorlat alakította, hanem szigorúan, matematikailag definiálták. Számos változata alakult ki a fejlesztések nyomán. A PL/1 (Programming Language One) programozási nyelvet az az igény hozta létre, hogy egyesíteni szerették volna a fenti nyelvek kedvező tulajdonságait: sok adattal legyen képes dolgozni, és egyúttal ismerjen sokféle, bonyolult matematikai műveletet is. (Sajnos a munka előkészítése így sok energiát igényelt, hiszen a programot mindenre fel kellett készíteni…) Az 1960-as évek közepén John Kemeny és Thomas Kurtz egy rendkívül egyszerű programnyelvet fejlesztettek ki, amelyet BASIC-nek (Beginner’s All Purpose Symbolic Instruction Code) neveztek el. A kezdő számítógép-használóknak kitűnő segítséget nyújt a programozással való ismerkedéshez. Interaktív nyelv, közvetlen kapcsolat van az ember és a gép között. Előnyei közé tartozik, hogy könnyen megtanulható, és a kisebb feladatok gyorsan és sikeresen megoldhatók (ez fontos a kezdők – például a gyerekek! – tanulása-tanítása során!), így oktatási célokra igen jól használható. Hátránya azonban, hogy nem eléggé strukturált, így nem szorít a tervezésre, nincsenek eljárások, terjedelmes programok írására a nyelv nem alkalmas. A gépi nyelvre való lefordításhoz interpretert (értelmező) használ. Az interpreterek soronként fordítják a programot, és ellenőrzik szintaktikailag, majd le is futtatják a sort, ezek után térnek a következő sorra. Előfordulhat azonban, hogy 1-2 adattal lefuttatva a programot, rejtve marad még szintaktikai hiba, hiszen lehet, hogy nem minden programsorra adódott a vezérlés a futás során. (Ilyen hiba a compiler típusú programoknál nem fordulhat elő.) Érdekesség, olvasmány Kemény János György matematikus, a BASIC programozási nyelv kifejlesztője 1926. május 13-án született Budapesten. Családja 1940-ben az Egyesült Államokba vándorolt, középiskoláit New Yorkban végezte, majd a Princetoni Egyetem hallgatója lett. A Manhattan-terv keretében a későbbi Nobel-díjas Richard Feynman munkatársa volt. A legnagyobbaktól, köztük Neumann Jánostól tanult, s 22 évesen Albert Einstein csoportjában dolgozott. 27 évesen elvállalta a Dartmouth-i Főiskola egyik matematika tanszékének megszervezését. Munkatársával, Tom Kurtz-cal 1962-ben javasolta az egyetemi számítóközpont létesítését, és kidolgozták a világ egyik első időosztásos rendszerét. Kemény felismerte, hogy a számítógép csak akkor válik mindenki számára hozzáférhetővé, ha a programozás, a programozási nyelv egészen egyszerű. Ezért 1964-ben Tom Kurtz-cal kidolgozta a BASIC (Beginner’s All-purpose Symbolic Instruction Code = a kezdők bármely célra használható szimbolikus utasítás kódja) nevű programozási nyelvet. Mindmáig szélesebb körben elterjedt programozási nyelv, amellyel lehetővé vált, hogy az addig csak kutatóknak hozzáférhető misztikus számítógépen diákok is dolgozhassanak. Tudományos munkásságát folytatva J. L. Snell-lel a Markov-láncok témakörében kutatott. A Three Mile Islandi atomerőmű-baleset után őt kérték fel a kormányzati vizsgálat vezetésére. A Keményjelentés országos visszhangot váltott ki, és szerzőjét az Egyesült Államok egyik legismertebb és legbecsültebb polgárává tette.

32

Az Egyesült Államokban hunyt el 1992. december 26-án. Keménytől származik a mondás: "A társadalom fő reménysége a számítógép lehet, az emberek és számítógépek harmonikus együttélése". [34, 35]

A PASCAL programnyelv alapjait Niklaus Wirth definiálta 1968-ban (Standard Pascal), azóta több változata is megjelent. A nyelvet Blaise Pascal matematikusról nevezték el. Általános célú programnyelv, mely jól olvasható és könnyen érthető megfogalmazást tesz lehetővé. Korszerű adatstruktúra, vezérlési szerkezet jellemzi, sok adattípus használható, sőt a programozó is értelmezhet típusokat. Az amerikai Borland Intézet terméke a TURBO PASCAL, mely kibővített változat, felhasználóbarát kialakítás jellemzi. Szigorú, deklaratív nyelv,

határozottan

típusorientált.

Strukturált

programozást

tesz

lehetővé.

[14]

Fordítóprogrammal, compiler segítségével dolgozik. Magas szintű programnyelvek még: ADA, C bizonyos változatai, LOGO. Érdekesség, olvasmány A Logo programozási nyelv és a hozzá kapcsolódó pedagógiai elvek kidolgozása és elterjesztése elsősorban Seymour Papert amerikai professzor nevéhez fűződik. A Logo lényegesen többet jelent egy számítógépes programnyelvnél: tulajdonképpen egy olyan pedagógiai környezetet, „mikrovilágot” jelent, amelyben a gyermekek maguk tehetnek felfedezéseket, miközben minden kényszer és „magolás” nélkül számos új ismeret birtokába jutnak. A teknőc a számítógép billentyűzetén keresztül utasítható a számára „érthető” feladatok végrehajtására: tud adott távolsággal előre vagy hátra menni, adott szöggel jobbra vagy balra elfordulni, tollát (ami a „hasára van erősítve”) felemelni, leereszteni, más színűre és vastagságúra cserélni, ezáltal mozgásával képes nyomot hagyni a képernyőn. A diák rögtön ellenőrizheti gondolkodásának és cselekedeteinek következményét. Megfigyeli utasításának hatását, majd módosíthatja azokat céljának megfelelően. A Logo filozófiája a modulszerűen felépített programozás: az egyes elemekből épül fel a program. A programírás- és építés tehát logikai egységekre bontható. A képernyőn megjelenő alkotás varázslat, amelynek elképzelője, kitalálója és létrehozója a gyermek. [29]

A magas szintű programozási nyelvekről összességében elmondható, hogy gépfüggetlenek, áttekinthetők, aránylag egyszerűen megérthetők, közelebb állnak az emberi gondolkodáshoz. A programot mindig le kell fordítani gépi kódra, és egy utasítás általában több gépi kódúnak felel meg. Segíti a hatékony programírást. A magas szintű nyelvek újabb generációja Szakít a hagyományos programozási móddal: nem a feladat megoldását elvégző utasítássort kell megadnia a programozónak, hanem a feladat kitűzésénél adott alapismereteket: tényeket és következtetési szabályokat kell megfogalmazni, majd közölni a célt: a meghatározandó adatokat. A mennyiben az alapismeretekből levezethető a cél, azt a gép közli. Ilyen nyelvkísérlet például a PROLOG. [5] Az objektum-orientált programozás, illetve a grafikus fejlesztő felületek (Delphi) újfajta szemlélet kialakulását hozták. A mesterséges intelligencia kutatások kapcsán fejlesztettek ki egy ismeretleíró nyelvet, a LISP-et, amelyet a műszaki programokban is előszeretettel alkalmaznak. [5] 33

Az adatbázisok kezelésére az SQL, a hálózati kommunikáció támogatására a JAVA, honlapok készítéséhez a HTML nyelvek szolgálnak. Érdekesség, olvasmány A programnyelvek szigorú szabályok szerinti formalizált nyelvek, ellentétben a köznyelvvel. A következő ábra bemutatja a programnyelvek kapcsolódását az általános nyelvfához: Nyelvek Természetes nyelvek

Köznyelvek

Formális nyelvek

Hangjegyírás, képletírás

Szaknyelvek

általános nyelvek Programozási nyelvek

Sokféle csoportosítás lehetséges még, például az alkalmazások szerinti csoportosítás. A különböző alkalmazási területekre speciális programnyelveket fejlesztettek ki. Általában két csoportot különböztetünk meg: géporientált és problémaorientált programnyelveket. Géporientált programnyelvek A géporientált programnyelvek a számítógép speciális műszaki tulajdonságait különösen jól használják ki. Az ilyen nyelven megfogalmazott programok azonban nagymértékben kötődnek ahhoz a számítógéptípushoz, amelyre készültek, azaz más típusú számítógépen rendszerint nem futtathatók. E nyelvek utasításainak azonos vagy hasonló struktúrájuk van, mint az adott számítógép gépi utasításainak, fordításkor a géporientált programnyelv minden utasításából egy gépi utasítás keletkezik. Előnyösen alkalmazhatók speciális feladatokra, például rendszerszoftver előállítására. Ezeknek a nyelveknek a megtanulása és kezelése általában nehezebb, mint a problémaorientáltaké. A géporientált nyelveket assembly nyelveknek is nevezik (to assemble: összeállítani). Problémaorientált programnyelvek Míg a géporientált nyelvek utasításai az alkalmazott számítógép gépi utasításainak felelnek meg, addig valamely problémaorientált nyelv utasításai nem veszik figyelembe a számítógép-struktúrát. Ezek rendszerint összetettebbek is, mint a gépi utasítások, ezért a problémaorientált nyelv egy utasításának lefordításából többnyire több gépi utasítás keletkezik. A problémaorientált nyelvek előnye egyrészt abban nyilvánul meg, hogy a programok jól áttekinthetők, másrészt abban, hogy a programozás aránylag egyszerű, és hogy a problémaorientált nyelven írt programok különböző számítógéptípusokon lefuttathatók, amennyiben a megfelelő fordítóprogram rendelkezésre áll. A problémaorientált nyelvet nevezik magas szintű programnyelvnek is. Ezek általában bizonyos szakterületek igényeinek megfelelően vannak kidolgozva. Törekvés van arra, hogy egy univerzális programnyelvet fejlesszenek ki, amely a legjobban illeszkedik az emberi nyelvhez.

34

Kódolási eljárások Az információ továbbításánál, a kommunikációnál láthattuk, hogy célunk az, hogy az információ az adótól eljusson a vevőhöz

Kódolás és dekódolás is történik a cél érdekében. A csatorna előtt kódolás szükséges, mert: -

az adó jeleit a csatorna rendszerint nem tudja értelmezni,

-

a kódolással az átvitel hatásfokát javíthatjuk,

-

a csatorna az adó kódolt jeleit kevésbé torzítja.

Ha az adó az A1, A2, A3,…An jeleket bocsátja ki, p1, p2, p3,…pn valószínűségekkel, ahol

n

∑

i =1

pi

= 1

,

de a csatorna csak az X1, X2,…Xm alapjelekből ( betűkből ) képes alapjel-sorozatait ( szavait ) felépíteni és továbbítani, akkor kódolásról van szó. Az n rendszerint sokkal nagyobb, mint az m. (n>>m). A számítástechnikában a bináris alapjeleket használjuk. Ekkor az m=2 ( 0 vagy 1 alaplelek)

Kódolás: Amikor az A1, A2, A3,…An jelek és az SX1, SX2,…SXn alapjel-sorozatok (szavak) halmaza között kölcsönösen egyértelmű hozzárendelést létesítünk, kódolást valósítunk meg. A számítástechnikában többféle kódrendszert is használnak. Ezek hatásfoka különböző lehet. Ennek eldöntéséhez részletesebb elemzésre van szükségünk. Ezután tekintse át az alábbi táblázatot, ahol különböző kódolási rendszereket láthat!

35

A K1 kódrendszernél az {A1, A2, A3, A4} jelek halmazához a {00, 01, 10, 11} szavak

halmazát rendeltük kölcsönösen egyértelműen. A K2 kódrendszernél {A1, A2, A3, A4}

{1, 10, 100, 1000}

A dekódolás akkor felel meg a célnak, ha a kódolt üzenetből ismét az eredeti üzenetet kapja a vevő.

Szeparálható kódoknak azokat a kódokat nevezzük, amelyeknél a közlemény az elemek közötti határolójel nélkül egyértelműen dekódolható, azaz megfejthető. A magyar nyelv nem szeparálható kódrendszer. Ezért használ határoló jelet, a szóközt. Vajon mi volt az üzenet a következő szavaknál: kalapács, törölköző, szerszám… A morse abc sem szeparálható kódrendszer. A két alapjel ( rövid, hosszú ) mellett elválasztó jelet is használ.

Prefix kódrendszer. Az olyan kódokat, ahol egyik kód sem eleje egy másik kódnak prefix vagy irreducibilis kódnak nevezzük. Vizsgálja meg, hogy az fenti táblázat K1, K2, K3, K4 kódrendszerei közül 1. melyik kódrendszer szeparálható és melyik nem! 2. Vizsgálja meg azt is, hogy melyik prefix és melyik nem! Egy létező, kódolt üzenet legyen a következő: 10010001101110 Mi volt az eredeti üzenet, ha a K1 kódrendszert használja? A dekódolásnál meg kell keresni, sorban, azokat a szavakat, amelyek a kódrendszerben megtalálhatók. A jelzésekből egyértelmű a dekódolás. Az üzenet:

A3 A2 A1 A2

A3 A4 A3

A kódrendszer tehát szeparálható. Mivel egyetlen szó sem eleje egy másik szónak, ezért prefix is. Mit üzentek, ha K2 kódolást használták?

Az üzenet:

A3

A4

A1 A2 A1 A1 A2

36

Másképpen nem csoportosíthatunk, mert akkor olyan szavakat kapnánk, amelyek nem szerepelnek a K2 kódrendszerben, vagyis nem lehet hogy a kódolás eredményei. Nézze meg a kérdést a K3 és a K4 kódrendszer esetén is! A K4 kódrendszernél nem dekódolható egyértelműen a mondat, mert mindkét esetben olyan szavakat kaptunk, amelyek szerepelnek a K4 kódtáblázatában. Az üzenet vagy A3 A1 A3 A1 A1 A4 A2 A4 A1 vagy

A3 A2 A1 A1 A2 A3

A4

A3

Ezért a K4 kódrendszer nem szeparálható kódrendszer. Könnyen megállapítható az is, hogy nem is prefix.

Az egyértelmű dekódolás elégséges feltétele Egy kódolt üzenet egyértelmű megfejtésének, azaz szeparálhatóságának elégséges feltétele az, hogy egyik kód sem legyen egy másik kódnak eleje, azaz, hogy prefix legyen. Tehát: ha egy kódrendszer prefix akkor egyértelműen dekódolható. Ha nem prefix akkor lehet, hogy egyértelmű a dekódolás ( pl.: K2 ), de lehet, hogy nem ( pl.: K4 ). A feltétel csak elégséges és nem szükséges.

Szeparálható bináris kódrendszer 1. Adott egy J = {A1, A2, … An} jelrendszer. Osszuk fel a halmazt két tetszőleges (de nem üres) részhalmazra úgy, hogy a két halmaz uniója J legyen. 2. Rendeljük az egyik halmaz (J0) elemeihez a 0, a másik halmaz (J1) elemeihez az 1 kódot. 3. A J0 halmazt osszuk két részre – ha lehetséges –, az egyik részhez rendeljünk 0-t, a másik részhez 1-et, és ezeket az értékeket írjuk az előző kódok után. 4. Alkalmazzunk a J1 halmazra is ugyanezt az eljárást. 5. Folytassuk ezt a folyamatot addig, amíg lehet, amíg kettéoszthatók a halmazok elemei. Legyen: J = { A1, A2, A3, A4 } Első lépés:

J0 = { A1 }¥

0

J1 = { A2, A3, A4 }¥ 1 Második lépés: A J0 tovább nem bontható, ezért a J1 felosztásával folytatjuk. J1,0 = {A2} ¥

0

J1,1 = {A3, A4}¥

1

37

Harmadik lépés:

J1,1,0 = {A3} ¥

0

J1,1,1={A4} ¥

0

Jelek

1. lépés

2. lépés

A1

0

A2

1

10

A3

1

11

A4

1

11

3. lépés

Az eredmény Ö

0

Ö

10

110

Ö

110

111

Ö

111

Láthatjuk, hogy a K3 kódrendszert kaptuk, amiről korábban is megállapítottuk, hogy szeparálható kódrendszerről van szó. Az algoritmus nem rögzíti, hogy a halmazokat hogy osszuk fel, csak azt mondja, hogy a részhalmazok uniója a felosztott halmaz legyen. Nézzünk egy más módon való felosztást! Jelek

1. lépés

2. lépés

Az eredmény

A1

0

00

Ö

00

A2

0

01

Ö

01

A3

1

10

Ö

10

A4

1

11

Ö

11

Most a K1 kódrendszert kaptuk. Ráadásul most csak 2 lépésből állt az algoritmus. Nem ugyanazt a kódrendszert kaptuk a két esetben, de a dekódolás egyértelmű, ezért egy üzenet is egyértelműen megfejthető. Végezze el egy konkrét üzenet kódolását és dekódolását mindkét kódrendszerrel! Legyen az üzenet:

SZÉK

K3 kódrendszerrel: Jelek

1. lépés

A1=S

0

A2=Z

1

10

A3=É

1

11

A4=K

1

11

Kódolva:

2. lépés

3. lépés

Ö

0

Ö

10

110

Ö

110

111

Ö

111

010110111

Mivel prefix a kódrendszer, ezért egyértelműen dekódolható. Dekódolva:

S

Z

É

K

A K1 lódrendszerrel: A1 A2 A3 A4 SZÉK

00011011

38

Az eredmény

SZÉK

A szeparálható bináris kódolás nagyon egyszerű eljárás. Akkor célszerű alkalmazni, ha csak az egyértelmű kódolás és megfestés a feladat. Feladat

- Kódolja, majd dekódolja szeparálható bináris kódolással a következő üzeneteket: ALMA ALMA A FA ALATT. Alma a fa alatt

Átlagos kódhossz Eddigi

elemzéseinknél

csak

az

üzenet

szeparálhatóságával,

egyértelmű

megfejthetőségével foglalkoztunk. Viszont nem elhanyagolható kérdés az sem, hogy milyen hatékonysággal folyik a kommunikáció. Egy távirat küldésénél igyekszünk röviden, tömören megfogalmazni az információt, mert a fizetendő összeg az üzenet hosszától is függ nem csak az információ mennyiségétől. Ha valaki sokat beszél, és keveset mond, akkor azt szoktuk mondani, hogy nem elég hatékonyan kommunikál. A telefon szolgáltatások rövid üzeneteinél is lényeges szempont, hogy a küldendő üzenetet meg tudjuk-e tömören fogalmazni. A megfogalmazás tömörsége függ attól, hogy az egyes kódok milyen hosszúak és mennyi az átlagos kódhossz. Ha az adó az A1, A2, A3,…An jeleket adja, p1, p2, p3,…pn valószínűségekkel, ahol

n

∑

i =1

pi

= 1

, és ha

h1, h2, h3,…hn a kódolt szavak hossza, akkor az átlagos kódhossz a szavak súlyozott átlaga.

h=

n

∑

i =1

p ih i

Feladat:

-

Számítsa ki az átlagos kódhosszt a K1, K2, K3, K4 kódrendszereknél!

39

K1 esetén minden esetben hi=2, ezért h=2 K2 kódrendszernél h1=1, h2=2, h3=3, h4=4. h=

4

∑

i =1

p i h i = 1/2*1+1/4*2+1/8*3+1/8*4=

4 + 4 + 3 + 4 15 = 8 8

14 12 K4-nél: h= 8 8 Érdekes, hogy az átlagos kódhossz a K4 kódrendszernél a legkisebb. Mivel a K4 kódrendszer K3-nál:h=

nem prefix, ezért hatékonyság szempontjából nem jöhet szóba. A többi közül a K3 esetén a legkisebb az átlagos kódhossz.

Az entrópia és tulajdonságai Egy rendszer információtartalmát – eddig – csak olyan esetekben értelmeztük, amikor a jelek kibocsátásának valószínűségei meggyeztek. Azt mondtuk, hogy ha az adó az A1, A2, A3,…An 1 jeleket azonos valószínűségekkel adja ( minden pi = p = ), akkor az információtartalom: n 1 log 2 n = log 2 = − log 2 p p Ha nem tételezzük fel a valószínűségek egyenlőségét, akkor átlagos információtartalmat számolhatunk. Ez az entrópia. Ha az adó az A1, A2, A3,…An jeleket adja, p1, p2, p3,…pn valószínűségekkel, ahol

n

∑ pi

= 1

, és 0 < pi ≤ 1, akkor a

i =1

n valószínűségekkel súlyozott információtartalom: − ∑ p i log 2 p i i =1 n A H(A)=H(p1, p2, p3,…pn) = − ∑ p i log 2 p i függvényt entrópiának, a rendszer i =1 határozatlanságának, bizonytalanságának nevezzük. Ez a megközelítés azt jelenti, hogy egy jel kibocsátásakor annyi információt nyerünk, amennyi bizonytalanság megszűnik. - Az átlagos kódhossz és az entrópia között is van összefüggés. Bizonyítható, hogy: h≥

H(A) log 2 m

H(A) log 2 m értékétől. Ezt másként úgy is mondhatjuk, hogy az átlagos szóhossz vagyis, hogy az átlagos kódhossz nem lehet nagyobb a

H(A) log 2 m Bináris kódolásnál az átlagos szóhossz minimuma éppen az entrópia, mivel ekkor m=2, ezért minimuma

h min = H(A)

40

A K1, K2, K3, K4 kódrendszereknél kiszámítottuk az átlagos kódhossz értékeit. K1: h= 2 15 8 14 K3: h= 8 12 K4: h= 8 Számítsuk most ki az entrópiát! H(A)=H(p1, p2, p3,…pn) = H( 1 2 , 1 4 , 18 , 18 ) = ? K2: h=

1 1 1 1 1 1 1 1 14 H( 1 2 , 1 4 , 18 , 18 ) = − ( ⋅ log 2 + ⋅ log 2 + ⋅ log 2 + ⋅ log 2 ) = 2 2 4 4 8 8 8 8 8 Láthatjuk, hogy valóban a K3 kódrendszernél veszi fel az átlagos kódhossz a minimumát. h min = H(A) - Az entrópia további tulajdonságai: n A H(A)=H(p1, p2, p3,…pn)= − ∑ p i log 2 p i i =1

n

függvény, ahol ∑ p i = 1 , és 0 < pi ≤ 1

-

a (0; 1] intervallumban folytonos,

-

minden változójában szimmetrikus,

-

maximumát akkor veszi fel, ha minden pi =

i =1

1 n

Az első két tulajdonság könnyen bizonyítható. Mivel a logaritmus függvények folytonosak a lehetséges pi értékek esetén, és folytonos függvények összege is folytonos, ezért az első tulajdonság már bizonyított is. A függvény szimmetrikus voltának bizonyítását azzal támaszthatjuk alá, hogy az összeadásnál a tagok felcserélhetők, vagyis az összeadás kommutatív. A harmadik tulajdonság bizonyítása nehezebb. Két változó (p1=p és p2=1-p) esetén azt kell igazolni, hogy a H(p, 1-p)= − [p ⋅ log 2 p + (1 − p) ⋅ log 2 (1 − p)] függvénynek p=1/2 –nél van maximuma.

41

Feladat:

- Mutassa meg, hogy ha minden pi= definícióját adja!

1 , akkor az entrópia az információ mennyiség korábbi n

- Határozza meg a következő entrópiákat! H(1/4, 1/4, 1/4 1/4)=? H(1/4, 1/4, 1/2)=? H(1/4, 1/4, 1/4, 1/4)=? H(1/2, 1/4, 1/16, 1/16, 1/16, 1/16)=?

Hatásfok H(A) ahol H(A) az entrópia, h az átlagos kódhossz az m h ⋅ log 2 m az alapjelek száma. A hatásfok nem lehet nagyobb, mint 1. f ≤ 1 Bináris kódolásnál f = H(A) ≤ 1 h A hatásfok viszonyszám, ezért százalékban is megadhatjuk. Pl.: f=0.9 esetén 90 % is írható. Egy kódolás hatásfoka f =

Számítsuk ki a táblázattal adott K1, K2, K3, K4 kódrendszereknél a hatásfok értékeit! H(A) Mivel mind a négy kódrendszer bináris ezért számolhatunk az f = képlettel. h Az etrópia mindegyik kódrendszernél H( 1 2 , 1 4 , 18 , 18 ) = 14 8 14 14 7 8 8 = 14 ≈ 0.933 = 93.3% = = 0.875 = 85% f1 = = f 2 2 8 15 15 8 14 14 8 8 = 7 >1 = 1 = 100% f3= f4= 14 12 6 8 8 Mivel K4 nem dekódolható egyértelműen, ezért kizárható a hatásfok vizsgálatából. Így a

leghatékonyabb kódrendszer a K3 kódrendszer. Az esetek közül a K3 kódolási módszer elérte a 100 % hatásfokot. Tehát, ha egy bináris kódrendszer átlagos kódhossza felveszi minimumát, akkor hatásfoka maximális. A hatásfokkal kapcsolatos fogalom a redundancia vagy másként mondva a terjengősség. redundancia= 1-hatékonyság.

r = 1− f 42

Az egyértelmű dekódolás szükséges és elégséges feltétele Ha az adó az A1, A2, A3,…An jeleket adja, p1, p2, p3,…pn valószínűségekkel, ahol

n

∑

i =1

pi

= 1

, és ha

h1, h2, h3,…hn a kódolt szavak hossza, akkor a kódolt üzenet egyértelmű

dekódolhatóságának szükséges és elégséges feltétele az, hogy teljesüljön: Bináris kódolásnál m=2 , a feltétel így módosul:

n ∑ m- hi ≤ 1 i =1

n ∑ 2- h i ≤ 1 i =1 Ellenőrizzük a feltétel teljesülését a már jól ismert bináris kódrendszerek esetén!

K1 kódrendszernél:

4 1 ⋅4 =1 ∑ 2- h i = 22 i =1

K2-nél:

4 1 15 1 1 1 + + = <1 ∑ 2- h i = + 3 1 2 24 16 2 2 2 i =1

K3 esetén:

4 1 1 1 1 + + =1 ∑ 2- h i = + 3 1 2 23 2 2 2 i =1

K4-nél:

4 1 1 1 1 + + >1 ∑ 2- h i = + 2 1 2 22 2 2 2 i =1

Látható, hogy az egyértelmű dekódolhatóság szükséges és elégséges feltétele az első három esetben teljesül. A K4 esetében már korábban is láttuk, hogy a dekódolás nem egyértelmű. Mostani megállapításunk korábbi meglátásunkkal szinkronban van. Ezek után nézzünk további kódolási algoritmusokat! A korábban vázolt szeparáló bináris kódolásnál csak a kódolt üzenet dekódolhatósága volt a követelmény. A most következő eljárásoknál a kódolás hatásfokára is tekintettel leszünk.

Huffman-kódolás „A méz mindig kevés.” – mondja Micimackó. A számítástechnikában ezt úgy fordíthatnánk le: „A hely mindig kevés.” A tárolás során mindig gondot okozott az adatok mérete, ezért megpróbáltak olyan kódolási eljárást kifejleszteni, amellyel az adatok hatékonyan 43

tömöríthetőek, ezáltal kisebb helyet foglalnak. A Huffman-kódolás segítségével hatékonyan (helytakarékosan) tudjuk adatainkat kódolni (és ezáltal tárolni). A kódolási rendszer maximális hatásfokú. A Huffman kódolás optimális hosszúságú kódrendszer előállítására szolgál, ezzel az eljárással prefix kódot készíthetünk, úgy, hogy a gyakrabban előforduló elemeket rövidebb kóddal helyettesítjük, mint a ritkábban előfordulókat. Nézzük a kódolás algoritmusát! 1. Adott egy J = {A1, A2, … An } jelrendszer p1, p2, p3,…pn valószínűségekkel, ahol

n

∑

i =1

pi

= 1

A kódolandó jeleket rendezzük előfordulási valószínűségük szerint csökkenő sorrendbe! p1 ≥ p2 ≥ … ≥ pn 2. A két legkisebb valószínűségű jelet kódoljuk –sorrendben- 0, 1 kódelemekkel. Majd valószínűségeiket adjuk össze! 3. Újra keressük meg a két legkisebb valószínűségű jeleket! Ismét kódoljuk –sorrendben- 0val, 1-gyel, és a most kapott megfelelő alapjelet írjuk az eddig kapott jelek elé! 4. Ezt az eljárást addig folytassuk, amíg csak 2 jelet kapunk. Ezeket is lássuk el a megfelelő sorrendben alapjelekkel! Kész vagyunk a kódolással. Példa A kódolandó elemek: A1 pi értékeik:

½

A2 ¼

A3

A4

1

1

/8

0

/8

A1 ½

A2 ¼

A3 /8

A4 /8

1

1

rendezettek 1

0

1

¼

¼ 10

0

11

0

½

10 110 111

1 Ø 0

1

0

½

Ø Ø

1

0

Ø

1

10 110 111

A Huffman-kód hatékony kódolási eljárás és veszteségmentes kódolást eredményez, de akadnak természetesen hátrányai is. Ilyen például a rendezés problémája, ugyanis ez nagy elemszám esetén hosszú időt vehet igénybe. Ráadásul a rendezéshez a valószínűségeket közös nevezőre kell hozni, ez is további időveszteséget jelent. [7]

44

Feladat

- Kódolja, majd dekódolja Huffman kódolással a következő üzeneteket: ALMA ALMA A FA ALATT. Alma a fa alatt - Végezze el a kódolást és dekódolást, ha: A1,

A2,

A3,

A4,

A5,

A6,

A7,

A8

1/2, 1/8, 1/8, 1/16, 1/16, 1/16, 1/32, 1/32 - Végezze el a kódolást és dekódolást, ha: A1,

A2,

A3,

A4,

A5,

A6,

A7,

1/2, 1/8, 1/8, 1/8, 1/16, 1/32, 1/32

Shannon-Fano kódolás 1. A kódolandó jeleket valószínűségeik szerint csökkenő sorrendben írjuk fel. 2. A jelek halmazát két –lehetőleg egyenlő valószínűségű– részhalmazra osztjuk. Az egyik részhalmazba tartozó minden jelhez 0-t, a másik részhalmaz minden eleméhez 1-et rendelünk, ezeket az eddigi kód után írjuk. 3. A 2. lépést addig ismételjük, amíg minden részhalmaz már csak 1 elemet tartalmaz. Példa A kódolandó elemek: A1 pi értékeik:

½ 1. lépés

A2 ¼

A3

A4

1

1

/8

/8

rendezettek

2. lépés

3. lépés

A kódok Ö0

A1

p1

0

A2

p2

1

0

A3

p3

1

1

0

Ö 110

A4

p4

1

1

1

Ö 111

Ö10

A Shannon-Fano kódolás egyszerűbb, mint a Huffman kódolás. Ha minden lépésnél biztosítható az egyenlő valószínűségű részhalmazokra bontás, akkor az eljárás maximális hatásfokú. Ez a feltétel általában nehezen biztosítható.

45

Feladat

- Kódolja, majd dekódolja Shannon-Fano kódolással a következő üzeneteket: ALMA ALMA A FA ALATT. Alma a fa alatt - Végezze el a kódolást és dekódolást, ha: A1,

A2,

A3,

A4,

A5,

A6,

A7,

A8

1/2, 1/8, 1/8, 1/16, 1/16, 1/16, 1/32, 1/32 - Végezze el a kódolást és dekódolást, ha: A1,

A2,

A3,

A4,

A5,

A6,

A7,

1/2, 1/8, 1/8, 1/8, 1/16, 1/32, 1/32

Shannon-féle bináris kódolás Az előző kódolási eljárás gyenge pontját javítja ki a Shannon-féle kódolás Nem szukséges a két halmaz egyenlő valószínűségekre bontása. Másként oldja meg a hatásfok növelését. A kódolás menete a következő: 1. Az A1, A2, … An jeleket írjuk fel előfordulási valószínűségeik csökkenő sorrendjében. (p1 ≥ p2 ≥ … ≥ pn) 2. Számítsuk ki a következő sorozat elemeit: a1

=0

a2

= p1 + a1= p1

a3

= p2 + a2 = p1 + p2

. . . an

= pn-1+ an-1= p1 + … + pn-1

an+1 = pn + an = p1 + n… + pn = Σ pi = 1 i 3. Határozzuk meg azt a legkisebb hi számot, melyre még teljesül: 2hi * pi ≥1 4. Írjuk át az an sorozat elemeit bináris alakra és ai elemek tört részét vegyük hi hosszúságúnak. Ha kell levágjuk, ha kell kiegészítjük.

46

Példa A kódolandó elemek: A1

A2

pi értékeik:

¼

1.

½

½ ¼

1

/8

1

A3

A4

1

1

/8

/8

/8 csökkenő sorrendben rendezett

2. a1 = 0 Ö 0.02 a2 = 0 + ½ = 0,5 Ö 0.12 a3 = 0,5 + ¼ = 0,75 Ö 0.112 a4 = 0,75 + 1/8 = 0,875 Ö 0.1112 a5 = 0,875 + 1/8 = 1 3. h1 = ? h1 = 1 -nél 21 * ½ = 1 ≥ 1 teljesül, tehát meg van a legkisebb h. h1=1 h2 = ? h2 = 1-nél 21 * ¼ < 1, tehát 21 * ¼ ≥ 1 nem teljesül. h2 = 2 –nél 22 * ¼ = 1 ≥ 1 teljesül, ezért h2=2 h3 = ? h3 = 3-nál 23 * 1/8 = 1 ≥ 1, ezért h3 = 3 h4=?

h4 = 3

4. mivel: a1 =

0.02

a2 =

0.5= 0.102

a3 =

0.75= 0.1102

a4= 0.875= 0.1112 Feladat

- Kódolja, majd dekódolja Shannon-féle bináris kódolással a következő üzeneteket: ALMA ALMA A FA ALATT. Alma a fa alatt - Végezze el a kódolást és dekódolást, ha: A1,

A2,

A3,

A4,

A5,

A6,

A7,

A8

1/2, 1/8, 1/8, 1/16, 1/16, 1/16, 1/32, 1/32 - Végezze el a kódolást és dekódolást, ha: A1,

A2,

A3,

A4,

A5,

A6,

A7,

1/2, 1/8, 1/8, 1/8, 1/16, 1/32, 1/32 47

Összefoglaló feladatok 1. Kódolja a Huffman-kódrendszer segítségével! Indul a görög aludni. 2. Kódolja a Huffman-kódrendszer segítségével! Egy meggy sem megy. 3. Kódolja a Huffman-kódrendszer segítségével! Szép kék még az ég. 4. Kódolja a Shannon-Fano módszerrel! Gyere, nézz szét! 5. Kódolja a Shannon-Fano módszerrel! Indul a görög aludni. 6. Kódolja a Shannon-Fano módszerrel! Alma a fa alatt. 7. Állítsa elő szeparálható kódrendszert a pohár szóra! 8. Állítsa elő szeparálható kódrendszert az informatika szóra! 9. Kódolja Shannon-féle bináris eljárással! Kék az ég. 10. Kódolja Shannon-féle bináris eljárással! Számítógép

48

Irodalomjegyzék [1] Dr Koncz József: TECHNIKA – INFORMATIKA

Agria Kiadó Kft. 1990 És Dr. Perge Imre: Bevezetés az informatikába Főiskolai jegyzet, Eger, 1993 valamint Dr. Koncz József előadásai [2] Csépai János: A számítástechnika alapjai

Műszaki Könyvkiadó, Budapest, 1985. [3] G. Cullmann, M. Denis-Papin, A, Kaufmann: A hír tudománya – Az információelmélet alapjai

Gondolat, Budapest, 1973. [4] Hans Breuer SH atlasz – Informatika

Springer Hungarica Kiadó Kft., 1995 [5] Rozgonyi-Borus Ferenc RAM-ba zárt világ (Számítástechnikai segédkönyv)

Mozaik Oktatási Stúdió, Szeged, 1997. [6] Rozgonyi-Borus Ferenc Számítástechnika 5-6

Mozaik Oktatási Stúdió, Szeged, 1998. [7] Rozgonyi-Borus Ferenc Számítástechnika 7

Mozaik Kiadó, Szeged, 2000. [8] Rozgonyi-Borus Ferenc Számítástechnika – Összefoglaló feladatgyűjtemény

Mozaik Kiadó, Szeged, 1997. [9]

Dr. Kovács Tivadar, Dr. Kovácsné Cohner Judit, Ozsváth Miklós, G. Nagy János: Mit kell tudni a PC-ről?

49

ComputerBooks, Budapest, 1998. [10] Dancsó Tünde – Végh András: Számítástechnika 10-11 éveseknek

Műszaki Könyvkiadó, Budapest, 1997. [11] Dancsó Tünde – Végh András: Számítástechnika 11-12 éveseknek

Műszaki Könyvkiadó, Budapest, 1998. [12] Végh András: Számítástechnika 12-13 éveseknek

Műszaki Könyvkiadó, Budapest, 1997. [13] Végh András: Számítástechnika 13-14 éveseknek

Műszaki Könyvkiadó, Budapest, 2001. [14] Dr. Koncz József: A PASCAL programozási nyelv elmélete és gyakorlata

EKTF Líceum Kiadó, Eger, 1999. [15] Schulcz Róbert Számítástechnika – Munkatankönyv 6. osztályosoknak

Comenius Kiadó Kft., Nágocs, 2003. [16] Schulcz Róbert Számítástechnika – Munkatankönyv 7. osztályosoknak

Comenius Kiadó Kft., Nágocs, 2003. [17] Schulcz Róbert Számítástechnika – Munkatankönyv 8. osztályosoknak

Comenius Kiadó Kft., Nágocs, 2003. [18] Pitrik József: Tanári

kézikönyv

az

Informatika,

Könyvtárhasználat,

Számítástechnika

tankönyvsorozathoz

Apáczai Kiadó, Celldömölk, 1999. [19] Pitrik József: INFORMATIKA 5-6. – Könyvtárhasználat, számítástechnika (Tankönyv kezdők részére)

Apáczai Kiadó, Celldömölk, 1999. [20] Pitrik József: 50

INFORMATIKA 7-8. – Könyvtárhasználat, számítástechnika (Tankönyv haladók részére)

Apáczai Kiadó, Celldömölk, 1999. [21] http://www.szabilinux.hu/konya/konyv/2fejezet/2fdigi2.htm [22] Bodnár István Olivér, Kiss Csaba, Krnács András: Számítástechnikai alapismeretek A

Műszaki Könyvkiadó, Budapest, 2000. [23] http://www.neumann-centenarium.hu [24] http://www.zsido.hu/kozosseg/Neumann.htm [25] http://www.ffg.sulinet.hu/oktinfo98/oppe/index.htm [26] http://www.scitech.mtesz.hu/10kiraly/kiraly_5.htm [27] http://www.mta.hu/aktualis/kivonat/hirek_2003_02.html [28] Bonifert Zsolt: Informatika

Műszaki Könyvkiadó, 2001. [29] Turcsányiné Szabó Márta, Zsakó László: Comenius Logo gyakorlatok

Kossuth Kiadó, 1997. [30] http://www.cic.klte.hu/iszk30/oktatas.htm [31] http://www.cic.klte.hu/ttk50/inf.htm [32] http://www.inflab.bme.hu/hist/oldies.html [33] http://ttk.unideb.hu/ttk25/mtcs/szk.html [34] http://www.sulinet.hu/eletestudomany/archiv/2001/0121/kronika/kronika.html [35] http://www.hpo.hu/ipsz/200104/ evnaptar.htm [36] http://www.mek.iif.hu/porta/szint/muszaki/szamtech/pc [37] http://www.mek.iif.hu/porta/szint/tarsad/konyvtar/informat/jegyzet/html/index.html [38] http://www.inlap.jate.u-szeged.hu/modtan/nyito.htm

51