Építészet | Felsőoktatás » Építőmérnöki informatika jegyzet

É P Í T Ő M É R N Ö K I EURÓPAI UNIÓ STRUKTURÁLIS ALAPOK I N F O R M A T I K A BMEEOFTAT07 segédlet a BME Építőmérnöki Kar hallgatói részére „Az építész- és az építőmérnök képzés szerkezeti és tartalmi fejlesztése” HEFOP/2004/3.31/000101 MŰSZAKI PROBLÉMÁK MEGOLDÁSA SZÁMÍTÓGÉPEN 1. előadás: Műszaki problémák megoldása számítógépen Tartalom:1. Mérnöki feladatok típusai; 11 Tervezés; 12 Analízis; 13 Szabályozás; 2 Szimuláció; 2.1 Hasonlósági törvények; 22 Folyamatok izomorfizmusa; 23 Matematikai analógia; 3 Modellek; 3.1 Fizikai modell; 32 Matematikai modell; 33 Algoritmizálás; 34 Számítástechnikai modell; 3.5 Számítógépi program; 36 Modell validáció 1. Mérnöki feladatok típusai Informatikai illetve rendszerelméleti szempontból a mérnöki feladatokat három csoportba sorolhatjuk: tervezés, analízis és szabályozás. Ez a felosztás természetesen önkényes és nem diszjunkt, a valóságban

gyakran átfedés van közöttük. Nagyon fontos figyelembe venni, hogy egy mérnöki feladatnak nem csupán több megoldása lehetséges, mint egy matematikai problémának, hanem a megoldása matematikai értelemben nem egyértelmű, szigorúan tekintve nem algoritmizálható. A feladat egyértelművé tételével a szaktárgyak foglalkoznak. 1.1 Tervezés A tervezés egy olyan tevékenység, amely egy új, még meg nem lévő objektum, berendezés, rendszerjellemzőinek (szerkezeti, geometriai, energetikai, szilárdsági, esztétikai stb), megadott körülmények melletti, előírt feltételeket kielégítő meghatározására irányul. Fontos szerepet kap a megvalósíthatóság (technikai és technológiai lehetőségek) illetve valamilyen (műszaki illetve gazdasági) szempontból való optimalizálás kérdése. 1.2 Analízis Vagyis annak elemzése, vizsgálata, hogy egy már meglévő illetve megtervezett berendezés esetén, miként változnak a tervezés során

meghatározott, a tervezési körülményeket kielégítő rendszerjellemzők, ha a tervezésitől eltérő körülmények lépnek fel. 1.3 Szabályozás Annak a beavatkozásnak a megtervezését jelenti, amely biztosítja, hogy a külső körülmények változása esetén a rendszerjellemzők csak olyan mértékben változzanak, amely változás még nem veszélyezteti a rendszer zavartalan működését. Ezt a feladat típus építőmérnökökről lévén szó nem vizsgáljuk a továbbiakban. 2. Szimuláció A szimulációt az analízis egy bonyolultabb formájának tekinthetjük, alkalmazása mindhárom típusú mérnöki feladat megoldásánál alapvető szerepet játszik. Ebben az esetben maga a rendszer igen bonyolult és vizsgálata általában csak számítógéppel lehetséges (digitális szimuláció). Fontos és gyakori jellemzője a szimulációnak az időtényező, valamint a Paláncz Béla, 2007 1 MŰSZAKI PROBLÉMÁK MEGOLDÁSA SZÁMÍTÓGÉPEN véletlenszerűség.

A szimulációval drága, hosszú időtartamot igénylő és esetenként megvalósíthatatlan vizsgálatok válthatók ki. Pl egy űrutazás szimulációja, egy atomerőműben kialakuló vészhelyzet elemzése stb. A szimuláció alatt egy olyan kísérleti eljárást értünk, amelynek során az eredeti, valóságos vagy elképzelt műszaki, gazdasági, biológiai stb. rendszert, egy neki megfelelő modellel helyettesítjük és a rendszer vizsgálatát ezzel a modellel végezzük. Magát a modellt szokás szimulátornak is nevezni. A szimuláció célja általában tervezés, analízis vagy optimalizáció Lényeges, hogy a szimuláció nemcsak számítógéppel történhet, bár ez a leggyakoribb. Minél mélyebb elméleti ismeretekkel rendelkezünk, annál sikeresebb lehet a számítógéppel történő modellezés. Az alábbi ábra egy fizikai - műszaki rendszer szimulációjával kapcsolatos elvi sémát szemléltet. valóságos vagy elképzelt rendszer Fizikai hasonlóság

Fizikai analógia Eredeti Matematikai analógia Szimulátor Elvek Modell 1.1 ábra Egy fizikai - műszaki rendszer szimulációjának elve 2.1 Hasonlósági törvények A fizikai hasonlósági törvény (elv) alkalmazására példa lehet egy az eredetinél jelentősen kisebb méretű repülőgép modell szélcsatornában való vizsgálata, amely alapján azután az eredeti gép repülési tulajdonságaira következtethetünk. De ez a fizikai hasonlósági törvényen alapuló szimulációs módszer nemcsak a repülőiparban megszokott, hanem alkalmazható a gépkocsi és hajótervezés esetén is, sőt az új típusú elektromos hajtások az ún. lineáris motorok tervezésénél is, továbbá a vegyiparban, ahol az eredeti méretű üzem tervezéséhez hozzátartozik az ún. pilot-plant (kísérleti üzem) vizsgálat, azaz a laboratóriumi méreteknél nagyobb, de az eredetinél kisebb méretű berendezéseken végzett kísérlet. Természetesen, ezekben az esetekben jól kell

ismerni azokat a hasonlósági kritériumokat amelyek azonossága esetén a valódi és a szimulátorként alkalmazott rendszerben a folyamatok ugyanúgy zajlanak (pl. az áramlástani folyamatok hasonlósági száma, a Reynolds szám = v d/ν, vagy a kémia reakciók hasonlóságának egyik hasonlósági száma a Damköhler szám = k , stb). Paláncz Béla, 2007 2 MŰSZAKI PROBLÉMÁK MEGOLDÁSA SZÁMÍTÓGÉPEN 2.2 Folyamatok izomorfizmusa Egy másik szimulációs elv a fizikai folyamatok analógiájának elve, azaz egy izomorfizmus (kölcsönös megfeleltetés) a különböző fizikai folyamatok között. Például egy ilyen megfeleltetés adható egy mechanikai rendszer (rúgóállandó + csillapítás + külső erőhatás) ahol az erő támadáspontja elmozdulásának időbeli alakulását vizsgáljuk és egy strukturálisan ennek megfelelő elektromos hálózat (induktivitás + vezetőképesség+ áramerősség) között, amely utóbbiban a feszültség időbeli

változását tekintjük. Így lehetségessé válik például a mechanikai rendszer dinamikájának vizsgálata az elektromos hálózat dinamikájának a vizsgálata alapján. Hasonló izomorfizmus adható például egy hőtechnikai folyamat és egy elektromos hálózat között. A számítástechnika egy korábbi korszakában ezen az elven működtek az ún. analóg számítógépek illetve ezeknek és a digitális gépeknek az együtteseként működő hibrid számítógépek. 2.3 Matematikai analógia A harmadik szimulációs elv a matematikai analógia, amely azt jelenti, hogy különböző folyamatok leírásának matematikai modellje, a matematikai alakja, egyenletei egyezők. Ezen az elven alkalmazhatunk digitális számítógépet, amellyel az eredeti folyamat matematikai modelljének megfelelő folyamatokat produkálunk a számítógép hardware-jében. 3. Modellek A számítógéppel történő vizsgálathoz tehát, a rendszert leíró matematikai összefüggések

előállítása szükséges. Ennek meghatározása több lépésben történik Ezek közül az első a rendszeranalízis. Ennek során az eredeti rendszert, fizikai, technológiai vagy egyéb meggondolások, megkötések figyelembevételével, annak környezetétől elhatároljuk és funkcionálisan kapcsolódó részekre, objektumokra bontjuk 3.1 Fizikai modell Ezután definiáljuk ezen objektumok fizikai modelljét, azokat a változókat, amelyek egyértelműen leírják ezeknek a részrendszereknek a működését, továbbá a szaktárgyakban megismert fogalmak segítségével és a fizikai törvényszerűségek alapján meghatározzuk a rendszer rendszerváltozónak kapcsolatát, egymásra hatásukat. Ebben a fázisban fontos szerepe van a műszaki meggondolásokon nyugvó elhanyagolásoknak. A mérnöki tevékenység az elhanyagolások művészete. 3.2 Matematikai modell Az így kapott fizikai modellnek megadjuk a matematikai leírását, amelyet matematikai rendszermodellnek,

vagy egyszerűen csak matematikai modellnek neveznek. Ennek a matematikai struktúrának elég kifinomultnak kell lennie ahhoz, hogy helyesen tükrözze a fizikai folyamatokat, ugyanakkor elég egyszerűnek ahhoz, hogy kezelhető, megoldható legyen. Itt a matematikai ismeretek alkalmazása az elsődleges fontosságú. Paláncz Béla, 2007 3 MŰSZAKI PROBLÉMÁK MEGOLDÁSA SZÁMÍTÓGÉPEN 3.3 Algoritmizálás A matematikai modell általában implicit formában tartalmazza a keresett rendszerváltózókat, pl. egy egyenletrendszer ismeretlenjeinek vagy egy differenciál egyenletrendszer ismeretlen függvényeinek formájában. A matematikai modell megoldása ezeknek az ismeretleneknek explicit formában való megadása. Ez történhet ritkán, egyszerű modell esetén analitikus vagy általánosan, numerikus formában. A megoldás lépéseit a matematika és a numerikus módszerek ismeretében kell meghatározni, amelyek összességét nevezzük a megoldási algoritmusnak. 3.4

Számítástechnikai modell A megoldás algoritmusának számítógépen történő végrehajtása érdekében, az algoritmust úgy kell átalakítanunk, hogy az a számítógép működésének megfelelő legyen, azaz szekvenciákra, elágazásokra és ismétlésekre (ciklusokra) kell bontanunk az eredeti algoritmus lépéseit. Ebben a fázisban az informatikai, számítástechnikai ismereteinket kell felhasználnunk. 3.5 Számítógépi program Ahhoz, hogy a számítástechnikai modellnek megfelelő algoritmust a számítógéppel végrehajtassuk, szükség van egy olyan reprezentációra, amelyet a számítógép „megért”. Ez valamilyen programnyelv, amelynek szigorú szintaktikája van. A számítástechnikai modellnek illetve a megoldás algoritmusának ezen reprezentációját, amelyet a gép feldolgozni képes nevezzük számítógépi programnak. A programírásnak, a programozásnak és ellenőrzésnek külön technológiája van lásd software engineering.

Modellvalidáció Eredeti rendszer Programverifikáció Számítógépi modell =Szimulátor Rendszerelemzés Modellalkotás Programozás Matematikai modell 1.2 ábra A szimuláció végrehajtásához szükséges feladatok 3.6 Modell validáció A modellezési folyamat záróköve, a modell alkalmazása által kapott eredmények mérnöki kiértékelése és ellenőrzése és ha szükséges a kiinduló fizikai modell módosítása, más elhanyagolások figyelembevétele. Irodalom Paláncz B. (1992) : Műszaki problémák megoldása formulaorientált nyelven, BME, Budapest Paláncz Béla, 2007 4 ALGORITMUS ÉS JELLEMZŐI 2. előadás: Algoritmus és jellemzői Tartalom:1.Algoritmus fogalma 2 Numerikus és nem-numerikus algoritmusok 21 Numerikus algoritmusok. 22 Nem-numerikus algoritmusok 3 Algoritmusok jellemzői 31 Hatásosság 32 Hatékonyság. 33 Komplexitás Az informatika két legfontosabb az adat és az algoritmus. Láttuk, hogy a probléma megoldása megfelel az

információ átalakításának és új információ előállításának. Ennek során, a kiinduló információból, amelyeket az egyenletek és a mért, számszerűen ismert értékek reprezentálnak, egy eljárással, műveletek véges sorozatával el állítjuk a megoldást, az új információt. Az információ megjelenési formáját adatnak, az átalakításhoz szükséges lépések sorozatát algoritmusnak nevezzük. Ez a szemléletmód arra szolgál, hogy a megoldást automatizálhassuk, azaz, számítógéppel elvégeztethessük. Ezzel kapcsolatban a következő kérdések megválaszolása alapvető : - hogyan lehet egy algoritmust megadni és számítógéppel végrehajtatni? - hogyan lehet egy algoritmust elemezni, minősíteni? A következőkben az algoritmus fogalmát vizsgáljuk részletesebben. 1. Algoritmus fogalma A legegyszerűbb algoritmusok, azok a szabályok, amelyek szerint a tízes számrendszerben a négy alapműveletet elvégezzük. Ilyen szabályokat

először a IX században élt arab matematikus al-Kvarizmi javasolt, akinek a nevéből származtatják az algoritmus szót. Algoritmusnak olyan egyértelmű előírást nevezünk, amely meghatározza, hogy egy adott feladatosztályhoz tartozó feladatok megoldásakor, milyen műveleteket, milyen sorrendben kell végrehajtanunk. Az algoritmusnak véges számú lépésben kell el állítania a megoldást Példaként tekintsük két természetes szám legnagyobb közös osztójának el állítását. Nyilván annyi ilyen feladat van ahány szám pár képezhet . Elsőként nézzük a megoldást, amely a definíciót követi. Tekintsünk két számot, mondjuk, 18 és 12 1. Megoldás: A definíció alapján: LKO (18,12) = max( metszet (osztói (18), osztói(12))) = max (metszet({2,3,6,9},{2,3,4,6})) = max ({2,3,6}) = 6 2. Megoldás: Euclides algoritmus: LKO(18,12) = LKO(18-12,12) =LKO(6, 12)= LKO(6, 12 - 6) = LKO(6, 6) =6 Input : a,b igen a <>b nem igen a<b b=b-a nem Output :

a a=a-b stop 1.ábra Az Euklideszi algoritmus Paláncz Béla, 2007 5 ALGORITMUS ÉS JELLEMZŐI 2. Numerikus és nem-numerikus algoritmusok Az algoritmusok két nagy csoportját szokás megkülönböztetni. Az ún numerikus algoritmusokat, amelyek általában számokkal végeznek műveleteket, pl. egy nem-lineáris egyenlet numerikus megoldása, és a nem-numerikus algoritmusokat, ahol az aritmetikai műveletek jelentősége elenyésző, pl. egy vektor maximális elemének kiválasztása 2.1 Numerikus algoritmusok A numerikus algoritmusok széleskörű elterjedésének egyik oka, hogy nagyon sok más műveletet vissza lehet vezetni a négy alapműveletre. Igaz, hogy ez a visszavezetés nem mindig abszolút pontos, de tetszőleges, előre megadott pontossággal ( helyesebben hibával) elvégezhető. Ezt jól mutatja a Heron által javasolt négyzetgyökvonás algoritmusának példája, amellyel egy szám a, négyzetgyökét csak közelítőleg, de tetszőleges pontossággal lehet

kiszámítani osztások, szorzások és összeadások sorozatával. Az egymást követő lépések számítása a következő formulával történik: ahol a kezdőérték pl. xi+1 = (xi + a/xi)/2 az eljárást addig folytatjuk, amíg x0 = a abs(xi+1 - xi ) > ε ahol ε egy alkalmasan választott hibakorlát. Konvergencia esetén ez biztosítja a algoritmus véges lépésszámát. Pl legyen a = 31, ekkor ε = 000001 választás esetén a sorozat: 31, 16, 8.96875, 62126, 560123, 5560123, 556776 A modern matematika egy speciális ága a numerikus analízis, eljárásokat dolgozott ki arra, hogy olyan bonyolultabb műveleteket, mint például az integrálás, differenciálás stb. az alapműveletekre vezessünk vissza. 2.2 Nem-numerikus algoritmusok Az algoritmusok egy másik csoportja a numerikus feladatok (mennyi ?) megoldásától eltérően ún. logikai feladatok megoldására szolgál. Ezeket szokás nem-numerikus algoritmusoknak nevezni Ilyen problémák esetén a kérdés

általában hogyan ?, melyik ?, milyen esetben ? stb. Keressük meg egy halmaz legkisebb elemét (melyik ?). Legyen a halmaz H és elemei hi , sorszámozottak, i =1,2,.,n Az algoritmus a következő lehet: Paláncz Béla, 2007 6 ALGORITMUS ÉS JELLEMZŐI Input: H s = h1 i=2 igen hi < s s=hi nem i=i+1 igen i>n Output :s nem Stop 2. ábra Halmaz legkisebb elemének keresése 3. Algoritmusok jellemzői Miután ugyanannak a feladatnak a megoldására több algoritmus is adható, célszerű az algoritmusokat minősíteni. Az ehhez szükséges szempontokat az algoritmus jellemzőinek nevezzük Itt most csak a fogalmak ismertetésére szorítkozunk. Hatásosság Ezzel a jellemzővel azt mérjük, hogy az algoritmus milyen mértékben alkalmas arra, hogy vele, az adott feladatosztályhoz tartozó problémák minél szélesebb, teljesebb körét megoldjuk. Egy algoritmus akkor hatásosabb egy másiknál, ha az általa megoldható feladatosztály bővebb mint a másikkal

megoldható feladatosztály. Példaként tekintsük a következő algoritmust (közvetlen behelyettesítés módszere) az x = g(x) típusú nemlineáris egyenletek megoldására, xi+1 = g ( xi ) Legyen g(x) = (20 + 3 sqrt(x) – 8 x)P. Válasszuk P értékét P = 03 –ra Ekkor konvergens eljárást kapunk. Ha azonban P = 05 akkor már a módszer divergens, azaz az algoritmus már nem alkalmas a P = 0.5 esetre Az eredeti algoritmust módosítva azonban egy hatásosabb algoritmust kaphatunk, amely ebben az esetben is konvergens, azaz működik: xi+1 = λ g ( xi ) + (1 - λ ) xi Paláncz Béla, 2007 7 ALGORITMUS ÉS JELLEMZŐI ahol 0 < λ < = 1. Α λ = 1 választás esetén az eredeti algoritmust kapjuk, azaz az új algoritmus minden olyan feladatot megold amit a korábbi és mint láttuk olyat is amelyet az eredeti nem volt képes. 3.2 Hatékonyság Egy algoritmus hatékonyságát a végrehajtásához szükséges idővel és tároló kapacitással mérhetjük. Ezek közül

általában az idő a fontosabb, a nagyobb súllyal figyelembeveendő tényező. Egy algoritmus nyilván annál hatékonyabb minél gyorsabban és minél kisebb tárolóterület felhasználásával oldja meg a problémát. Gyakran azonos feladatosztály problémáinak megoldására szolgáló algoritmusok egyike gyorsabb, de több helyet igényel és megfordítva. Nézzünk egy példát, egy polinom helyettesítési értékének kiszámítását Ezt elvégezhetjük közvetlen hatványozással, de a Horner elrendezés alkalmazásával is. Legyen adott egy negyedfokú polinom, y(x) = c4 x4 + c3 x3 + c2 x2 + c1 x +c0 Ennek a polinomnak a helyettesítési értékét az x = xh helyen, azaz az y(xh) értékét meghatározhatjuk ún. közvetlen hatványozással, yh = c0 + c1 xh + c2 xh xh + c3 xh xh xh + c4 xh xh xh xh A műveletek száma : 4 összeadás és 10 szorzás. A Horner elrendezést alkalmazva yh = c0 + xh (c1 + xh (c2 + xh (c3 + c4 xh ))) Most csupán 4 összeadásra és 4

szorzásra van szükség, tehát a Horner elrendezésen alapuló algoritmus a hatékonyabb. Komplexitás Ezzel a jellemzővel azt mérjük, hogy miként változik az algoritmus végrehajtásához szükséges műveletek száma a probléma méretének növelésével. (műveleti komplexitás) Pl. Természetes számok összeadása a) Naiv módszer, amikor a műveletek száma egyenes arányban növekszik az összeadandók számával: 1 + 2 + 3 + .+ n b) Gauss módszere, függetlenül az összeadandók számától mindig csak egy osztást , egy szorzást és egy összeadást kell elvégezni: n/2(1+n) Polinomiális komplexitás még megoldható számítógépen nagy n esetén is: (nC – ahol C állandó és n a feladat mérete). Vannak exponenciális komplexitású algoritmusok is pl Hanoi tornyai 2n-1, vagy az utazó ügynök probléma. Ezeknél nagy n esetén közelítő algoritmusokat szokás alkalmazni. Irodalom Trahtenbrot B.A (1978) : Algoritmusok és absztrakt automaták, Műszaki

Könyvkiadó, Budapest Paláncz Béla, 2007 8 SZÁMÍTÓGÉP ÉS PROGRAM 3. előadás: Számítógép és program Tartalom:1 Kézi és gépi számítás. 2Elemi programszerkezetek 21 Szekvencia 22 Elágazás 23 Ismétlések .3 Programnyelvek 1. Kézi és gépi számítás Egy algoritmus előírásai szerint dolgozó ember a számítási folyamat során bizonyos tájékoztatást (információt) vesz fel, tárol, dolgoz fel és bocsát ki. Ezt az információt rendszerint papíron írja le (ábrázolja) számjegyek, betűk vagy más jelek felhasználásával. Ezeknek a jeleknek a halmazát célszerű ABC-nek nevezni. Például az algebrában használt ABC a szokásos betűkön és számjegyeken kívül tartalmaz még műveleti jeleket, zárójeleket stb. Az ember által végzett "kiszámítási" eljárásra a következők jellemzők: Papirlap Utasitások Számok irása Ember Számoló eszköz 1.ábra Kézi számítás Az információk tárolására a gépnek is

szüksége van egy ABC-re, azonban a grafikus jelek helyett a gépben az ABC jeleit különböző fizikai állapotokkal jellemzik, általában a fizikai állapotokat 0-nak vagy 1-nek feleltetik meg. A gépbe belépő és a gép működése közben átalakuló összes információt számok formájában, kettes számrendszerben kódolják. Így többek között magát az algoritmust is, amely a gép munkáját vezérli, szintén számsorozat formájában írják fel. Tár Vezérlö egység 1 11 12 15 1. 2 0 00 00 25 Aritmetikai egység 3 10 0 00 01 02 2. ábra Gépi számítás Paláncz Béla, 2007 9 SZÁMÍTÓGÉP ÉS PROGRAM 2. Elemi programszerkezetek A számítógépen végrehajtandó feladatok, utasítások sorozatát programnak nevezzük. A leggyakrabban alkalmazott elemi utasítások a következők: Aritmetikai utasítások: összeadás, kivonás, szorzás, osztás. Vezérlésátadó utasítások: feltétel nélküli és feltétellel vezérelt vezérlés átadás. Az

elemi programszerkezetek, a szekvencia, elágazás és az iteráció felhasználásával minden algoritmus felépíthető. Szekvencia A legegyszerűbb esetben az adott feladatot megoldó algoritmusszerkezet az, amikor az egyes utasításokat a leírásuk sorrendjében kell végrehajtani. Elágazás Az előbbi utasításokat kibővíthetjük feltétellel vezérelt utasításokkal. Ez azt jelenti, hogy az algoritmus végrehajtása egy feltételtől függően eltérő utasításokkal folytatjuk. Az elágazás sémái eltérö ábrázolási módokban Input: x Input: x igen y=2x x>10 nem x>10 igen y=2x y=-x nem y=-x Output: y Output: y Struktogram Folyamatábra 3. ábra Elágazás megvalósítása 2.3 Iteráció Az algoritmusok többségénél előfordul, hogy bizonyos műveleteket többször meg kell ismételni. Az ilyen jellegű algoritmus, illetve programszerkezeteket iterációnak nevezzük. Különbséget szokás tenni, az ún. számlálással és feltétellel

vezérelt ismétléses szerkezetek között A számlálással vezérelt esetben tudjuk, hogy hányszor kell az ismétlést végrehajtanunk. A feltétellel vezérelt ismétlésnél az ismétlések száma ismeretlen. Ezzel szemben ismert valamilyen feltétel, amely igaz volta esetén a kérdéses műveletek megismétlendők. Ha a feltétel hamissá válik akkor az ismétlés (ciklus) befejeződik. A számlálással és a feltétellel vezérelt ismétlések programnyelvi megvalósítása alapján szokás for illetve while ciklusokról beszélni. Paláncz Béla, 2007 10 SZÁMÍTÓGÉP ÉS PROGRAM In pu t : N i=0 In pu t : N s= 0 s=0 i = 1 .N i =i +1 s=s+i Ou tp ut : s s=s+i ig en g oto i <N n em Ou tp ut: s 4.ábra Számlálással vezérelt ismétlés 3. Programnyelvek A nyelvek együtt fejlődtek a számítógéppel (hardware). - Első generációs nyelv az ún. gépi nyelv, az utasítások közvetlen bináris kódban való leírása Így a programírás időigényes és

a program nehezen áttekinthető. Pl két szám összeadása gépi nyelven: 010000110011101000111101010000010001011101000010. - A második generációs nyelvek az ún. assembly nyelvek, amelyek szimbólumokat és szavakat használnak a program leírására. Pl. a C = A + B művelet elvégzése Assembly nyelven: LOAD A hozd be az A rekesz tartalmát az akkumulátorba (aritmetikai egység), ADD B add hozzá a B rekesz tartalmát az akkumulátor tartalmához, STORE C az eredményt tárold a C memóriarekeszben. - A harmadik generációs nyelvek sorába tartoznak pl. a BASIC, COBOL, FORTRAN és C nyelvek Ezeket a nyelveket magas szintű nyelveknek hívják. -A negyedik generációs nyelvek egyik fejlődési irányának jellemzője az adatszerkezet és a rajtuk végzett műveletek összerendelése, az ún. objektum orientált nyelvek, pl Visual Basic, C++ A másik fejlődési irány a számítógép-algebra alkalmazása, az ún. formula orientált és szimbolikus nyelvek kialakulása, pl.

MathCAD, Maple, Mathematica, MATLAB stb Ezen utóbbiak nagyszámú beépített függvénnyel rendelkeznek, amelyek a szimbolikus számítások mellett a numerikus feladatok megoldását is nagymértékben támogatják, és lehetővé teszik az ún. funkcionális programozást és a vizualizációt. Körülbelül 1000-re becsülhető a használatos programnyelvek száma, és ebből kb. 20 nyelv tartozik a leginkább elterjedt nyelvek csoportjába. Vannak kihaló és születő nyelvek, amelyeket az új igények és követelmények hoztak létre. Ilyen pl a Java, amelyet a multimédia és az Internet hálózat elterjedése hívott életre. Irodalom Csöke - Garamhegyi (1997) : A számítógép-programozás logikai alapjai, Nemzeti Tankönyvkiadó, Budapest. Paláncz Béla, 2007 11 PROGRAM ÉS ALGORITMUS TERVEZÉS 4. előadás: Program és algoritmus tervezés Tartalom:1. Fokozatos finomítás módszere; 2 Modularitás; 3 Rekurzió; 4 Megosztás módszere; 5. Párhuzamosítás; Mint

láttuk, a program az algoritmus (szemantika) leírása (reprezentációja) egy definiált jelrendszerrel (ABC), megadott szabályok (szintaktika) szerint, amelyet a számítógép értelmez (interpretál) és végrehajt. A program változókat használ a megfelelő memória rekeszek azonosítására. A memória rekeszek tartalmát a változóhoz rendelt adatnak nevezzük. Láttuk azt is, hogy a számítógép ún. bemenő információkat alakít át kimenő információvá Ezeket bemenő illetve kimenő adatoknak nevezzük. Az adatok és azok átalakítását leíró algoritmus, a program reprezentációja a számítógépben számokkal, pontosabban bináris kódok sorozatával történik. A változóhoz hozzárendelt adatot a változó értékének nevezzük, amely a program végrehajtása során, futása közben általában változik. Az algoritmus és annak számítógépi reprezentációja, a program között szoros kapcsolat van, ezért a program szerkezetében, felépítésében

tükröződik az algoritmus jellege. Ennek megfelelően, olyan módszerek, eljárások alakultak ki, amelyeket az algoritmus és programtervezésnél egyaránt célszerű követni az eredményesség (hatásos, hatékony és alacsony komplexitású algoritmus ill. program) érdekében 1. Fokozatos finomítás módszere A top - down technika lényege, hogy először a megoldandó problémának egy átfogó, nem részletes megoldását keressük, majd a részfeladatok ismeretében, azok megoldásának lépéseit fokról fokra haladva egyre jobban mélyítjük, finomítjuk. Példaként tekintsük a legnagyobb közös osztó meghatározásának problémáját. Próbáljuk megoldani a feladatot a definíció alapján, azaz 1. Tekintsük a két szám osztóit, mint két sorozatot 2. Határozzuk meg ennek a két sorozatnak a közös részét 3. Keressük meg a közös rész maximális elemét 2. Modularitás A modularitás módszere logikailag a top - down technika következménye, amennyiben

az egyes részfeladatok megoldásai, a program felépítése szempontjából külön egységként jelentkeznek. Az előző példában egy szám osztóinak meghatározása egy önálló feladatként tekinthető, amelynek megoldását két különböző bemenő adatra kell elvégezni. Célszerűnek látszik ezt az algoritmusrészt úgy megadni, hogy csak egyszer legyen szükség a leírására. Erre ad lehetőséget a modul, amely egy önálló algoritmusrész programjának általános, azaz tetszőleges bemenő adatokra érvényes, leírását adja. Paláncz Béla, 2007 12 PROGRAM ÉS ALGORITMUS TERVEZÉS A moduláris programszerkezet alkalmazásának több előnye van : 1) egyszerre, egymástól függetlenül többen dolgozhatnak ugyanazon feladat részfeladatain. 2) a modul önmagában is tesztelhető, ellenőrizhető, így könnyebb a hibákat megtalálni. 3) a modul más feladat részfeladatának megoldásánál is felhasználható, modulkönyvtárak hozhatók létre. A

moduláris technika alkalmazásával kapcsolatosan három fontos fogalompárt kell megismerni. Ezek közül az első, a modulok input illetve output változóival (használatos a paraméter elnevezés is) kapcsolatos. A modulokat éppen az önálló, többszöri felhasználásuk érdekében, valamilyen adott input és output változókkal írnak meg. Ezeket nevezzük a modul formális változóinak, gyakran formális paramétereinek. A modul aktuális felhasználásakor (a modul hívásakor) azonban alkalmazhatunk más változókat vagy éppen számértékeket is, amelyeket aktuális változóknak illetve aktuális paramétereknek nevezünk. Amíg az aktuális változók mindig értékkel rendelkeznek (kivéve a szimbolikus számításoknál) addig a formális változók csak arra valók, hogy definiálják a modul bemenő és kimenő változóit és ezeken keresztül magát a modul által megvalósítandó algoritmust. A másik fogalom pár a modulok között történő

adatátadással kapcsolatos. A modulok közötti adatátadás lehet ún. érték és címszerinti adatátadás Az érték szerinti átadásnál az aktuális változó értéke belekerül a formális változó számára a modul hívásakor kijelölt memóriarekeszbe. A címszerinti átadásnál pedig, a híváskor nem az aktuális változó értéke, hanem a neki megfelelő memóriarekesz címe adódik át a hívott modulnak, amely a hívás alatt - ha a program futásának vezérlése ebben a modulban van - az aktuális változót, mint a megfelelő formális változót kezeli, majd a vezérlésnek a hívó modulba visszaadása után az aktuális változó visszanyeri eredeti szerepét (maszkolás). Hivó program a 12.1 Modul érték szerint 12.1 Aktuális paraméter x Formális paraméter 12.1 cim szerint 1. ábra A modulparaméterek adatátadási formái A harmadik fontos fogalom pár az ún. változói hatáskör kérdésével kapcsolatos A moduláris programozás során

megkülönböztetünk lokális és globális változókat. Itt röviden csak annyit jegyzünk meg, hogy egy adott modul szempontjából csak a modulon belül érvényes változót lokális változónak, azt amely az adott modulon kívül is érvényes, globális változónak nevezzük. Ilyenkor a globális változó a modulon belül is felhasználható, attól függetlenül, hogy Paláncz Béla, 2007 13 PROGRAM ÉS ALGORITMUS TERVEZÉS nem szerepel a modul formális változói között. Ezzel lényegében az adatátadás egy másik formáját valósíthatjuk meg a különböző modulok között. A lokális és globális elnevezések relatív viszonyokat tükröznek. Egy modul számára, amely egy másik modulba van ágyazva (onnan kerül meghívásra), az öt hívó modul lokális változói, az ö szempontjából globális változók. 3. Rekurzió A rekurziót abban az esetben alkalmazzuk, amikor a részfeladatok megegyeznek magával a feladattal. A rekurzív technika jellemzője,

hogy a modul saját magát hívja csak más aktuális változóval. Hogy az algoritmus a rekurzív hívás során ne kerüljön végtelen ciklusba, két fontos jellemzővel kell rendelkeznie 1) Léteznie kell egy ún. bázis kritériumnak, vagy más szóval leállási feltételnek, amelynek teljesülésekor a modul már nem hívja meg önmagát 2) A rekurzív hívások során az algoritmus egyre közelebb kell, hogy vigyen a bázis kritériumhoz Számoljuk ki például 3 faktoriálisát, azaz határozzuk meg a 3! = 1*23 értékét. Ehhez az alábbi lépésekre van szükség 3! = 3*2! 2! = 2*1! 1! = 1 (bázisérték) 2! = 2*1=2 3! = 3*2 = 6 1. lépés : definiáljuk 3!-t a 2!- sal kifejezve, így tehát a 3! kiszámítását el kell halasztani a 2! kiszámításáig 2. lépés : definiáljuk 2!-t az 1!- sal, ami explicit módon adott Ez a bázisérték. 3. lépés : az 1! értékével kiszámítjuk a 2! értékét 4. lépés : a 2! értékével kiszámítjuk a 3! értékét Vannak olyan

esetek, amikor egy algoritmus nem rekurzív formában való megírása a feladat megoldását nagyon bonyolulttá tenné, szemben a rekurzív megközelítéssel. Erre jó példa a Hanoi tornyai-nak nevezett probléma. Legyen adott három függőleges rúd, amelyeket A, B és C-vel jelölünk, és legyen az A rúdon alulról felfelé csökkenő méretben n darab korong. Az A-ról a C rúdra kell eljuttatni a korongokat az alábbi szabályok szerint: 1) Egyszerre csak egy korongot mozgathatunk 2) Nagyobb korongot nem helyezhetünk kisebb korongra Paláncz Béla, 2007 14 PROGRAM ÉS ALGORITMUS TERVEZÉS Az n korong áthelyezését A-ról C-re az alábbi részfeladatokra bonthatjuk : 1) Az A rúd legfelső n-1 korongjának áthelyezése a B rúdra 2) Az A rúd legnagyobb korongjának áthelyezése a C-re 3) A B rúd n-1 korongjának áthelyezése a C-re A B C Azaz, ha az eljárás neve Hanoi (n, A,B,C) vagyis n korongot helyezzünk A-ról C-re a B-n keresztül, akkor ez a

következő lépésekkel valósítható meg : 1) Hanoi (n-1,A,C,B) 2) Hanoi(1,A,B,C) 3) Hanoi(n-1,B,A,C) Az algoritmus: Hanoi (n, A,B,C) = Ha n = 1 then A Æ C különben Hanoi (n-1,A,C,B); A Æ C; Hanoi(n-1,B,A,C) ; 4. Megosztás módszere A módszer lényege, hogy a feladatot nem az eredeti halmazon, hanem annak kiválasztott részhalmazán oldjuk meg, azaz az eredeti halmazt lépésről lépésre szűkítve kapjuk meg a keresett megoldást. Példaként nézzük a keresés feladatát egy már rendezett sorozatban. Idézzük fel a szótárak használatát, amikor nem az első vagy utolsó oldaltól indulva lapozzuk végig a szótárat amíg megtaláljuk a keresett szót, hanem felütjük a szótárat valahol középen és a keresett szót összehasonlítjuk az ott talált szóval. Ha a keresett szó előbb van az ABC - ben akkor a keresett szó a szótár első felében van, ellenkező esetben a második felében. Ezután a megfelelő részben folytatjuk tovább a keresést az előző

felezési módszerrel. Ezt a keresési módszert bináris vagy logaritmikus keresésnek nevezik. Vajon miért? 5. Párhuzamosítás Az algoritmusok egyes lépéseinek végrehajtása során előfordul, hogy két vagy több lépés egymástól függetlenül akár párhuzamosan, egyidejűleg is végrehajtható, mivel a lépések eredményei nem befolyásolják egymást. Ennek a lehetőségnek a kihasználása érdekében, a párhuzamosítás megvalósításához, bizonyos hardware és szoftware feltételeknek kell eleget tenni. Irodalom Naps - Nance (1992) : Introduction to Computer Science, West Publishing Company, New York Paláncz Béla, 2007 15 ADATTÍPUSOK ÉS ELEMI ADATSZERKEZETEK 5. előadás: Adattípusok és elemi adatszerkezetek Tartalom: 1. Elemi adattípusok; 2 Elemi adatszerkezetek; 3 Adatok tárolása a memóriában 4. Adatállomány; 5 Text típusú adatállomány Az algoritmus fogalmának bemutatása során láttuk, hogy minden algoritmus adatokból és

műveletekből, vagy másként tevékenység szerkezetekből épül fel. A tevékenység- szerkezetek után fordítsuk figyelmünket az adatokra! Egy programban szereplő adatokra az azonosítók, más néven programváltozók (röviden változók) segítségével hivatkozhatunk. Mint láttuk, a számítógépben minden információt, adatot és programutasítást egy bitsorozat ír le. Egy bitsorozat önmagában azonban még nem egyértelmű Például a 01000001 bitsorozat jelentheti az A betűt, de a 65 értékű számot is. A bitsorozathoz tartozó jelentés akkor tehető egyértelművé, ha az adatokat osztályokba soroljuk, vagyis ha megadjuk típusukat. Ha az előbbi bitsorozat egy egész számnak megfelelő adattípus, akkor a 65-ös számot, ha egy karakter típusú adat, akkor az A betűt jelenti. Az adat típusa meghatározza annak értékhalmazát és a vele végezhető műveleteket. A változó típusát a hozzárendelt adat típusa definiálja. 1. Elemi adattípusok

Amelyek tovább már nem bonthatók egyszerűbb elemekre. 1.1 Egész: osztás kivezet (pl 1, -23) 1.2 Racionális: csak szimbolikus nyelvek esetén (pl 2/13) 1.3 Valós adattípus: véges tizedes tört (pl 00139), kerekítési hiba 1.4 Komplex típus: valójában összetett, 2 elemű vektor (pl 22 – 34i) 1.5 Logikai: igaz (1) vagy hamis (0) Műveletek igazság táblái: a 0 0 1 1 b 0 1 0 1 a AND b 0 0 0 1 a OR b 0 1 1 1 NOT a 1 1 0 0 Reláció, mint logikai változó. 1.6 Karakter típus: a változó név de a karakter típusú adat - ASCII kód Elemeit az ún. ASCII (American National Standard Code for Information Interchange) kódtábla definiálja. Összesen 0255 különböző karakter közül választhatunk Minden karakterhez egy numerikus (0.255) azonosító szám tartozik Modernebb változata Unicode Paláncz Béla, 2007 16 ADATTÍPUSOK ÉS ELEMI ADATSZERKEZETEK 2. Elemei adatszerkezetek Az adatokat sokféle módon szervezhetjük. Az adatszerkezet, vagy más néven

összetett adattípus egy bizonyos adatszervezés matematikai vagy logikai modellje. Az adatszerkezeteket az egymással logikailag összetartozó egyszerű adatok alkotják. Ezek az adatszerkezetek a fájl kivételével a memóriában történő adatszervezés különböző módjait testesítik meg. A legfontosabb elemi adatszerkezeteket ismertetjük az alábbiakban 2.1 Karakterlánc: karakterek sorozata, amely olyan egydimenziós tömbnek tekinthet ő (lásd tömb) ahol az elemek karakterek. 2.2 Tömbök Tudjuk, hogy minden adatszerkezet, mint összetett adattípus, elemi típusokból épül fel, ezért annak megadásánál meg kell mondanunk, hogy milyen típusú elemekből és hogyan képezzük őket. Az összetett struktúra képzése abból a problémából fakad, hogy sokszor van szükségünk olyan azonos tulajdonságú és szerkezetű változókra, amelyeket valamilyen szempontból együtt kell kezelnünk. Magától adódik az ötlet, hogy közös névvel hivatkozzunk rájuk,

de úgy, hogy elemeik megkülönböztethetők maradjanak. A tömb azonos típusú, meghatározott számú, sorrendbe helyezett elemekből álló sorozat, ahol az elemeket index (általában pozitív, de mindig egész számok) azonosítják. A szimbolikus nyelvekben ezekből a megkötésekből csak a sorrendiség marad. Az egydimenziós tömböt vektornak, a kétdimenziós tömböt mátrixnak (vagy táblázatnak) nevezzük és a közöttük elvégezhető műveletekre speciális szabályok érvényesek. Bizonyos rendszereknél a tömb akárhány dimenziós is lehet. 1 D Tömbök - vektor: egy név de több adat. Jellemzők: azonos típusú adatok, vektor elemindex: egészszám sor és oszlop vektor, transzponált 3 művelet a vektorok között: eredmény: skalár, vektor és mátrix 2 D Tömbök - mátrix- sor és oszlop index: mátrix szorzása vektorral, mátrix - mátrix szorzása, egységmátrix és inverz mátrix. Record: mezői vannak, amelyek eltérő típusú elemeket

tartalmazhatnak - MATLAB megvalósítása a cella tömb (cell- array) 3. Adatok tárolása a memóriában A memóriát úgy képzeljük el, mint egy sokfiókos szekrényt, amelynek minden fiókjához, de egyszerre csakis egyhez férhetünk hozzá. Egy fiókban lényegében egyetlen számot helyezhetünk el, de nem akármekkorát. Ennek maximális értéke 255 lehet Ezt a képzeletbeli fiókot nevezzük bájtnak. Pl. 5 kettes számrendszerben 1 bájton: 0*27 + 026 + 025 + 024 + 023 + 122 + 021 + 1 20 = 5 Azaz 00000101 Paláncz Béla, 2007 17 ADATTÍPUSOK ÉS ELEMI ADATSZERKEZETEK A bájt valóságban tovább bontható 8 kisebb egységre, ezek a bitek. Egy bit két értéket vehet fel: 0-t vagy 1-et. Ha a tárolandó számot bináris, azaz kettes számrendszerben adjuk meg, akkor világos, hogy miért lehet az egy fiókban elhelyezhető szám maximális értéke 255. Ha a 8 egymást követő bitet a kettes számrendszer helyértékeinek feleltetjük meg, akkor a legnagyobb szám

alakja: 11111111. Ez pedig a tízes számrendszerben: Egész Ennél nagyobb egész szám esetén több fiókot fogunk össze. Az egész számokat általában 2 bájton ábrázoljuk. Az első bit az előjel számára szolgál, amely pozitív esetben 0, negatív számnál pedig 1. Valós típus A valós számokat normál alak segítségével ábrázoljuk: x = m Re alakban, ahol m a mantissza, e az exponens és R az alapszám. Ezzel a módszerrel a valós szám ábrázolását visszavezettük két egész szám (m és e) ábrázolására. A megvalósításnál az exponenst egy K eltolási állandóval eltolják, hogy a kitevő pozitív maradjon. c=e +K A c-t nevezzük karakterisztikának. Ebben az esetben a számábrázolás szerkezete : előjel|karakterisztika|mantissza A tárolás általában 6 illetve 8 bájton történik. A 32 illetve 64 bites ábrázolás esetén: Single precision : előjel : 1 bit, exponent : 8 bit, mantissza : 23 bit Double precision : előjel : 1 bit, exponent : 11

bit, mantissza : 52 bit, 16 jegy pontosságnak felel meg. Karakter : 1 byte Logikai: 1 byte Tömb típus Mint említettük, a tömb lényegében lineáris adatszerkezet, azaz az elemek az egymást követ ő memóriahelyeket foglalják el. A számítógép a tömb neve alapján meghatározza a tömb kezd ő elemének memória címét (báziscím), majd az index, valamint az elemtípusának megfelelő tárolási hossz ismeretében az indexnek megfelelő elem helyét a memóriában. Az i -edik elem címe (memória rekesz azonosító): báziscím + (i -1) * elemtípus hossza Paláncz Béla, 2007 18 ADATTÍPUSOK ÉS ELEMI ADATSZERKEZETEK 4. Adatállomány Az adatállomány, vagy más néven file ( állomány), a másodlagos tárolón elhelyezett adatok önálló névvel azonosított halmaza. A file-t bármely adattípus sorozata alkothatja Ennek a sorozatnak az egymástól megkülönböztetett részeit a file komponenseinek nevezzük. A file alkalmazásának előnye, hogy például a

tömbbel szemben, komponensenként lehet behozni vagy kivinni az elsődleges memóriából, amíg pl. a tömb minden eleme egyidejűleg bent kell, hogy legyen. Tehát pl a file-ban való keresésnél mindig csak egy komponenst hozunk be a memóriába és azt vizsgáljuk. A másik előny, hogy nem kell előre megadni a méretét a memóriában való helyfoglalás miatt, mint pl. a tömb esetén és méretének csak a másodlagos memória szab határt 5. Text típusú adatállomány Speciális file-típus az ún. text file, ahol a komponensek változó hosszúságú stringek, amelyeket egy kocsivissza (Carrige Return) és egy soremelés (Line Feed) zár le. Ezeket (CR+LF) együttesen nevezzük sorvégjelnek. A MATLAB, amelyet tudományos műszaki számítások céljára terveztek, elsősorban numerikus adatokat tartalmazó adatállományok kezelésére alkalmas, amelyeknél a numerikus értékek karakter illetve karakterlánc formájában szerepelnek a file-ban és csak az aktuális

MATLAB változóba való beíráskor, illetve a file-ba való kiíráskor konvertálódnak automatikusan pl. valós számból karakterlánccá vagy karakterláncból valós számmá. Irodalom Lipschutz (1993) : Adatszerkezetek, McGraw-Hill Inc. - Panem Kft Budapest Kaufmannn, A (1972) : Pontok,élek, ívek.gráfok, Műszaki Könyvkiadó, Budapest Paláncz Béla, 2007 19 PROGRAMOZÁSI TÉTELEK 6. előadás Programozási tételek Tartalom: 1. Egyszerű programozási tételek; 11 Eldöntés; 12 Kiválasztás; 13 Keresés; 14 Megszámlálás; 2. Összetett programozási tételek; 21 Rendezés; 22 Kigyűjtés; 23 Szétválogatás; 2.4 Sorozatok egyesítése; 25 Sorozatok közös része; A tömb, mint adattípus fontos szerepet játszik a számítástechnikában, ezért ezek kezelésére alapalgoritmusokat dolgoztak ki. Ezeket nevezzük programozási tételeknek A programozási tételek típusai, az algoritmusok bemenete és kimenete alapján a következő csoportokba sorolhatók:

Bemenet Kimenet sorozat skalár sorozat sorozat sorozat sorozatok sorozatok sorozat 1. Egyszerű programozási tételek Az elemi programozási tételek, olyan feladatok megoldására szolgálnak segítségül, amelyek visszavezethetők az egy értéknek egy sorozathoz rendelésének problémájára. Eldöntés Ebben az esetben a sorozathoz egy logikai értéket rendelünk. Ha a sorozatban található adott tulajdonságú elem, akkor 1, különben 0. function y=eldont(s,T) n=length(s); i=1; while and(i<n,not(T(s(i)))) i=i+1; end if or(T(s(n)),i<n) y=1; else y=0; end ahol T(x) egy tulajdonság függvény, amely 1 ha x kielégíti a tulajdonságot, különben 0. Kiválasztás Az algoritmus gondolatmenete nagyon hasonlít az eldöntés szabályára, azzal a különbséggel, hogy most a keresett elem helyét, illetve magát az elemet kell megadni. A kiválasztás esetén feltételezzük, hogy van mit kiválasztani, azaz a keresett adatnak benne kell lennie a sorozatban. function

y=kivalaszt(s,T) i=1; while not(T(s(i))) i=i+1; end y=i; Paláncz Béla, 2007 20 PROGRAMOZÁSI TÉTELEK Keresés A lineáris keresés szabályát akkor alkalmazzuk, ha nincs biztosíték arra, hogy a kiválasztandó elem benne van a halmazban. Ennek megfelelően ez a szabály az eldöntés és kiválasztás szabályát ötvözi egybe. A függvény 0 ad vissza, ha nincs a vektorban keresett tulajdonságú elem. function y=keres(s,T) n=length(s); i=1; while and(i<n,not(T(s(i)))) i=i+1; end if i<n y=i; elseif T(s(n)) y=n; else y=0; end Megszámlálás A megszámlálás szabálya azokban az esetekben alkalmazható, ha rendelkezésünkre áll egy sorozat és egy,a sorozat elemein értelmezhető T tulajdonság és az a feladatunk, hogy számoljuk meg a T tulajdonsággal rendelkező elemeket. function y=szamlal(s,T) n=length(s); z=0; for i=1:n if T(s(i)) z=z+1; end end y=z; 2. Összetett programozási tételek A feladatok többsége esetén nem elegendő a megoldáshoz egyetlen

elemi programozási tétel alkalmazása, hanem azok kombinálására van szükség. Az összetett programozási tételek körébe tartozó feladatok esetén a megoldás eredményeként mindig egy vagy több sorozatot kapunk. 2.1 Rendezés A rendezésre nagyon sokféle módszer kínálkozik. Ezek közül nézzük a maximum kiválasztáson alapuló rendezést. Ennek a módszernek a lényege, hogy kiválasztjuk a legnagyobb értékű elemet, amit a sorozat végére helyezünk, úgy, hogy a legnagyobb elemet felcseréljük a sorozat utolsó elemével, majd a vizsgált sorozat hosszát eggyel csökkentjük. Paláncz Béla, 2007 21 PROGRAMOZÁSI TÉTELEK function y=rendez(x) n=length(x); nc=n; for i=1:n-1 imax=1; for j=1:nc if x(imax)<x(j) imax=j; end end maxi=x(imax); x(imax)=x(nc); x(nc)=maxi; nc=nc-1; end y=x; 2.2 Kigyűjtés Ebben a esetben egy sorozatból egy adott tulajdonsággal rendelkező összes elemet ki kell gyűjteni, eltérően a kiválasztástól, amikor csak egy ilyen

elem kiválasztása volt a cél. function y=kigyujt(x,T) n=length(x); y=[]; for i=1:n if T(x(i)) y=[y,x(i)]; end end 2.3 Szétválogatás Ebben az esetben egy sorozatból két sorozatot állítunk elő. A bemenő sorozat elemeit valamilyen feltétel alapján két diszjunkt sorozatra bontjuk. function y=szetvalogat(x,T) n=length(x); i=1; j=n; for k=1:n if T(x(k)) y(i)=x(k); i=i+1; else y(j)=x(k); j=j-1; end end Paláncz Béla, 2007 22 PROGRAMOZÁSI TÉTELEK 2.4 Sorozatok egyesítés Adott két sorozat, határozzuk meg azt a sorozatot, amely azokat az elemeket tartalmazza, amelyek az egyik és másik sorozatban is benne vannak. De ezek csak egyszer szerepelnek az egyesítésben. Az s1 sorozatot átmásoljuk s3 vektorba, majd minden s2 sorozatbeli elemről eldöntjük, hogy benne van-e s1 sorozatban. Ha nincs, akkor beletesszük az s3 egyesítést tartalmazó vektorba. function s3=egyesit(s1,s2) n1=length(s1);n2=length(s2); for i=1:n1 s3(i)=s1(i); end for i=1:n2 j=1; while

and(j<n2,not(s2(i)==s1(j))) j=j+1; end if and(not(s2(i)==s2(j)),not(j<n2)) s3=[s3,s2(i)]; end end Több sorozat unióját úgy állítjuk elő, hogy az első kettő unióját tekintjük, majd ennek és a harmadik sorozatnak állítjuk elő az unióját, és így tovább. 2.5 Sorozatok közös része Két sorozat metszetének meghatározásánál azokat az elemeket keressük, amelyek az egyik és másik sorozatban is szerepelnek. Az s1 sorozat minden elemét összehasonlítjuk az s2 sorozat minden elemével. Ha s1(i) = s2(j), j = 1,,n2 valamelyik j-re igaz akkor s3(k) = s1(i), azaz s1(i) beletesszük a közös részt képviselő sorozatba. function s3=kozos(s1,s2) n1=length(s1); n2=length(s2); k=1; for i=1:n1 j=1; while and(j<n2,not(s1(i)==s2(j))) j=j+1; end if or(s1(i)==s2(n2),j<n2) s3(k)=s1(i); k=k+1; end end Irodalom Ledgard H.F (1996) : Az objektum orientált programozás alapjai, Műszaki Könyvkiadó, Budapest. Paláncz Béla, 2007 23 LINEÁRIS EGYENLETRENDSZEREK

NUMERIKUS MEGOLDÁSA 7. előadás: Lineáris egyenletrendszerek numerikus megoldása Tartalom: 1. Az egyenletrendszerek típusai 2 Megoldási módszerek MATLAB felhasználásával 1. Az egyenletrendszerek típusai Legyen az egyenletek száma : n és az ismeretlenek száma : m. 1.1 Inhomogén egyenletrendszer (n = m) Abban az esetben ha az n = m és az egyenletrendszer inhomogén, azaz Ax=b Két eset lehetséges: 1.11 normál eset: det (A) ) ≠ 0 Két egyenlet esetén grafikusan szemléltetve az ismeretlenek (x1, x2) síkján két egymást metsző egyenest kapunk, ahol a metszéspont reprezentálja az egyértelmű megoldást: 1. ábra Létezik egyértelmű megoldás Azaz ilyenkor van megoldás és egyértelmű! 1.12 szinguláris eset: det(A) = 0 Ha az egyenletrendszer mátrixának determinánsa zérus, akkor két lehetőség van 1.121 rang(A) = rang (A:b) Vagyis az egyenletrendszer mátrixának rangja (pl. a mátrixban lévő lineárisan független oszlopvektorok száma) egyenlő

a jobboldal vektorával, mint oszlop vektorral bővített A mátrix (A:b) rangjával. Ebben az esetben végtelen sok megoldás létezik, mivel a két egyenletet reprezentáló egyenes egybeesik: Paláncz Béla, 2007 24 LINEÁRIS EGYENLETRENDSZEREK NUMERIKUS MEGOLDÁSA 2. ábra Végtelen sok megoldás Ekkor a végtelen sok megoldás közül megoldásként a legkisebb normájú megoldást tekinthetjük. Az alábbi ábrán az u =5 + v megoldású egyenletrendszer hibáinak négyzetösszege négyzetgyökét (hibavektor normáját) látjuk v függvényét, sqrt((5+v)2+v2) 11 10 9 8 7 6 5 4 3 -5 -4 -3 -2 -1 0 v 1 2 3 4 5 3.ábra A megoldások normájának minimuma A legkisebb négyzetek értelmében kapott megoldás, a minimumot adó v = -2.5 lesz, tehát az u=2.5 és v = -25 értékeket tekintjük megoldásnak. 1.122 rang(A) <> rang (A:b) Amennyiben a két mátrix rangja nem egyenlő, akkor a hagyományos értelemben nincs megoldás, hiszen a két egyenletet

reprezentáló egyenesnek nincs közös pontja. Az alábbi ábrán ez az eset látható: Paláncz Béla, 2007 25 LINEÁRIS EGYENLETRENDSZEREK NUMERIKUS MEGOLDÁSA 4.ábra Ha nincs megoldás akkor hibavektorok normájának minimumához tartozó vektort tekintjük megoldásnak Ekkor is definiálhatunk egy legkisebb hibájú „megoldást”, amely ugyan egyik egyenletet sem elégíti általában ki, azonban az egyes egyenletek hibáinak négyzetösszege minimális lesz. Tehát most a minimális normájú hibavektorhoz tartozó vektort tekintjük megoldásnak. 1.2 Abban az esetben ha az n > m és az egyenletrendszer inhomogén, (rank(A) =m) azaz az egyenletek száma több, mint az ismeretlenek száma (túlhatározott egyenletrendszer). A hagyományos értelemben nincs egyértelmű megoldás hiszen n egyenletből m kiválasztva más- más megoldás adódik. Itt megint a legkisebb négyzetek elvét alkalmazva az egyenletek hibáira, kaphatjuk meg a megoldást. 1.3 Abban az

esetben ha az m > n és az egyenletrendszer inhomogén, Azaz a változók száma több, mint az egyenletek száma (alulhatározott egyenletrendszer). Most végtelen sok megoldás adódik, hiszen az egyik fölös változót paraméternek tekintve, annak minden értékéhez kapunk egy megoldást. 1.4 Homogén egyenlet, A x = 0 Ekkor a megoldás feltétele, hogy det(A) = 0. A megoldást az A mátrix nullterének bázisát alkotó vektorok lineáris kombinációja adja. Azaz végtelen sok megoldás adódik Ezek közül a legkisebb normájú választható, mint megoldás. 2. Megoldási módszerek MATLAB felhasználásával 2.1 kvadratikus mátrix (n = m) és det(A) ≠ 0 A= 52 -60 39 -25 b = 260 325 det(A) = 1040 x = linsolve(A,b’) x = 12.5 6.5 Paláncz Béla, 2007 26 LINEÁRIS EGYENLETRENDSZEREK NUMERIKUS MEGOLDÁSA Továbbá alkalmazható még : x = inv(A) *b’, x = A b’, x = pinv(A) b’ 2.2 det(A) = 0 és rank(A) = rank(A:b) – végtelen sok megoldás A = 52 -52 39

-39 b = 260 195 det(A) = 0 Ab = 52 -52 260 39 -39 195 rank(A) = 1 rank(Ab) = 1 x = pinv(A)*b’ adja a legkisebb normájú megoldást. x = 2.5 - 2.5 2.3 det(A) = 0 és rank(A) ≠ rank(A:b) – a hagyományos értelemben nincs megoldás A = 52 -52 39 -39 b = 260 325 det(A) = 0 Ab = 52 -52 260 39 -39 325 rank(A) = 1 rank(Ab) = 2 x = pinv(A)*b’ adja a legkisebb négyzetek értelmében a megoldást, azaz, azt az x vektort amelyre norm ( A* x – b) minimum. x = 3.1 - 3.1 2.4 Inhomogén, túlhatározott egyenletrendszer (n > m) A = 2.0000 10000 2.5000 20000 1.0000 30000 4.0000 60000 7.0000 20000 x = pinv(A)* b’ x = 4.0132 -1.2710 b = 5 10 9 3 27 rank(A) = 2 vagy x = linsolve(A, b’) x = 4.0132 -1.2710 2.5 Inhomogén, alulhatározott egyenletrendszer (m > n) A = 6. 165 14 b = 54 100 x1 = pinv(A)*b’ vagy x2 = linsolve(A,b’) 14. 48 54 x1 = 3.665 x2 = 0 4.780 6.922 -3.347 -4.301 A pinv által adott megoldás normája kisebb, norm(x1) = 6.891 és norm(x2) = 8145 2.6

Homogén egyenletrendszer, A x = 0 A = 2 2 -19/33 12 9 -2 78 9 11 det(A) = 0 az A nulltere: x1 = null(A) x1 = 1 -32/13 -66/13 megoldás: x2 = C x1. ahol C = áll. Irodalom Stoyan G. (2005) MATLAB Typotex kiadó, Budapest Paláncz Béla, 2007 27 LINEÁRIS EGYENLETRENDSZEREK NUMERIKUS MEGOLDÁSA Paláncz Béla, 2007 28 NEMLINEÁRIS EGYENLETEK, INTERPOLÁCIÓ ÉS REGRESSZIÓ 8. előadás: Nemlineáris egyenletek, interpoláció és regresszió Tartalom: 1. Nemlineáris egyenlet megoldása; 11 Intervallumfelezés módszere; 12 Newton módszer; 1.3 MATLAB függvények 2 Interpoláció; 21 Lokális interpoláció; 22 Globális interpoláció; 2.3 Spline interpoláció; 3 Regresszió; 31 Regressziós egyenes; 32 Polinomiális regresszió; 3.3 MATLAB függvények 1. Nemlineáris egyenlet megoldása A feladat az f(x) = 0 egyenlet gyökeinek meghatározása. Ehhez általában valamilyen információval kell rendelkeznünk ezen gyökök közelítő értékéről. Szerencsére a

mérnöki gyakorlatban ez az információ általában adott. Gyakran tudjuk, hogy a gyök pl valós, pozitív és közelítően mekkora az értéke illetve milyen intervallumba esik. Intervallumfelezés módszere Ebben az esetben tudjuk, hogy a keresett gyök milyen intervallumba esik. Itt mindig egy gyökre gondolunk, azaz f(x1) f(x2) < 0 ahol x1≠ x2. A módszer algoritmusa a következő: 1) Válasszuk meg x1 és x2 értékeit úgy, hogy az f(x1) f(x2) < 0 feltétel igaz legyen. 2) Számítsuk ki az intervallum felezőpontját: xc = (x1 + x2)/2 3) Ha abs( f(xc)) < ε hibakorlát akkor befejezzük a számítást. Egyébként megvizsgáljuk, hogy f(x1) f(xc) > 0 igaz -e! 4) Ha igaz, akkor x1 = xc és visszalépünk a 2) pontra 5) Ellenkező esetben x2 = xc és visszalépünk a 2) pontra. Newton módszer Egy gyökhöz közeli pontból kiindulva a következő iterációs formulát alkalmazzuk: amelyet az alábbi ábra alapján x i+1 = xi + f (xi)/f (xi) f(x1) x2 x1 f(x)

1.ábra A Newton módszer elve tg (α) = f (x1)/(x1 - x2) = f (x1) Paláncz Béla, 2007 29 NEMLINEÁRIS EGYENLETEK, INTERPOLÁCIÓ ÉS REGRESSZIÓ Jellemzők: - a konvergencia négyzetes - ha f(x) ~ 0 oszcilláció lép fel! - ha f(0) ~ 0, inflexiós pont közelében lévő gyök esetén, lassú konvergencia (divergencia). MATLAB függvények Nemlineáris egyenlet megoldására a MATLAB az fzero() függvényt alkalmazza. Nézzünk egy polinomot: f(x) = x3 - 2x – 5 Határozzuk meg a valós gyökét! Rajzoljuk fel! >>ezplot(x^3 - 2*x - 5,[-2, 3]) 0 10 5 0 -5 -10 -2 -1.5 -1 -0.5 0 0.5 x 1 1.5 2 2.5 3 2.ábra A polinom görbéje Definiáljuk a függvényt:A valós gyök meghatározása: >>f=@(x)x^3-2*x-5; Egy pontból kiindulva: >>fzero(f, 2) ans=2.09455148154233 Két közrezáró pontot alkalmazva: >> fzero(f,[1,3]) ans = 2.09455148154233 Polinom összes gyökének numerikus meghatározására a roots() függvény használható. Az előbbi

polinom esetén az együtthatók vektora: >>p = [1 0 -2 -5]; A gyökök pedig, >> roots(p) ans = 2.09455148154233 -1.04727574077116 + 113593988908893i -1.04727574077116 - 113593988908893i Paláncz Béla, 2007 30 NEMLINEÁRIS EGYENLETEK, INTERPOLÁCIÓ ÉS REGRESSZIÓ 2. Interpoláció Ha ismerjük az yi = f(xi) összetartozó (xi, yi) értékeit, i = 1,n pontokban, kérdés mi lesz az yt = f(xt) értéke, ahol xi < xt < xi+1? 2.1 Lokális interpoláció A legegyszerűbb interpoláció a lineáris interpoláció. Ekkor az xt értéke csak a szomszédos értékektől függ: y =yi + (yi+1-yi)/(xi+1-xi) (x-xi) ahol xi < x < xi+1. 12 10 8 6 4 2 0 -2 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 3.ábra Interpolációs pontok A MATLAB-ban a lineáris interpolációra az interp1() függvényt alkalmazhatjuk, y = @(x)interp1(X,Y,x) formában, ahol X és Y az interpolációs pontok xi és yi koordinátáit tartalmazó vektorok. interp1(X,Y,x) 12 10 8

6 4 2 0 0 0.1 0.2 0.3 0.4 0.5 x 0.6 0.7 0.8 0.9 1 4.ábra Lineáris interpoláció 2.2 Globális interpoláció Ekkor f(x) -t valamilyen bázisfüggvények lineáris kombinációjaként közelítjük! Ezek lehetnek például algebrai vagy trigonometrikus polinomok de más függvények is. Az együtthatókat úgy kell meghatározni, hogy yi = y(xi) teljesüljön minden i-re! Azaz algebrai polinomok esetén Paláncz Béla, 2007 31 NEMLINEÁRIS EGYENLETEK, INTERPOLÁCIÓ ÉS REGRESSZIÓ y1 = a2 x12 + a1 x1 + a0 y2 = a2 x22 + a1 x2 + a0 y3 = a2 x32 + a1 x3 + a0 azaz n-ed fokú polinommal való közelítés esetén n+1 adat párra (xi,yi) van szükség! Az a0, a1 és a2 ismeretlenekre adódó lineáris egyenletrendszer mátrixa az ún,. Vandermonde mátrix. A gond, hogy a Vandermonde mátrix rosszul kondicionált! Ezért azután az együtthatókat célszerűbb más módon számolni. Pl a Lagrange-féle alakban A MATLAB-ban a polinomiális interpoláció függvényét a

polifit() és a polival() függvények segítségével állíthatjuk elő: >> n=length(X) % az interpolációs pontok száma >> p=polyfit(X,Y,n-1); % az interpolációs polinom együtthatóinak vektora >> yp=@(x)polyval(p,x) % maga az interpolációs függvény polyval(p,x) 16 14 12 10 8 6 4 2 0 0 0.1 0.2 0.3 0.4 0.5 x 0.6 0.7 0.8 0.9 1 5.ábra A lineáris és a polinomiális interpoláció Látható, hogy a végeken irreális lengések lépnek fel. Oka túl sok pont, túl magasfokú interpolációs polinom. Ezért 7-8 pontnál több esetén nem alkalmazandó! 2.3 Spline interpoláció Sok pont esetén az átmenetet a kettő között! Szakaszonként polinomiális.Pl harmadfokú polinom. Az együtthatókat a pont párokból illetve a sima átmenet feltételéből határozhatjuk meg. A MATLAB-ban a spline() függvényt alkalmazhatjuk: >> ys=@(x)spline(X,Y,x) spline(X,Y,x) 12 10 8 6 4 2 0 0 0.1 0.2 0.3 0.4 0.5 x 0.6 0.7 0.8 0.9 1

6.ábra Spline interpoláció Paláncz Béla, 2007 32 NEMLINEÁRIS EGYENLETEK, INTERPOLÁCIÓ ÉS REGRESSZIÓ 3. Regresszió Az adatok hibával terheltek és ezekre akarunk egy modellt illeszteni, amelynek paramétereit keressük. Az interpolációhoz képest tehát itt a görbe nem megy át a mérési pontokon! 3.1 Regressziós egyenes Legyen a közelítő modell y(x) = b1*x + b0 A rendelkezésre álló adatok: (xi, yi) i=1,.,n > 2 Több egyenlet mint ismeretlen (b0, b1) y1 = b1*x1 + b0 . yn = b1*xn + b0 A végtelen sok megoldás közül a megfelelőt a legkisebb négyzetek módszere adja, azaz amely minimalizálja az F(b0, b1) = Σ (yi - (b1*xi + b0))2 függvényt. Erre használhatjuk a már megismert polyfit() függvényt! Ha az adat párok száma n akkor m< n-1 esetére polyfit(X,Y,m) függvény az m-ed fokú regressziós görbét adja! Tehát regressziós egyenes esetén: p= polyfit(X,Y,1) % az egyenes paraméterei u=@(v)polyval(p,v) % pedig a regressziós egyenes

függvénye polyval(p,v) 1050 1000 950 900 850 800 750 20 30 40 50 60 v 70 80 90 100 7.ábra Regressziós egyenes 3.2 Regressziós polinom Ebben az esetben a közelítő polinom nem elsőfokú, hanem magasabb fokú polinom. Ennek fokszáma n adat esetén maximum m = n – 2, hiszen m = n-1 már interpolációt jelent. polyval(p,v) 1050 1000 950 900 850 800 750 20 Irodalom 30 40 50 60 v 70 80 90 100 8.ábra Harmadfokú regressziós polinom Zsakó L. (1997) : Programozási feladatok, Kossuth Kiadó, Budapest Paláncz Béla, 2007 33 A SZÁMÍTÓGÉPES GRAFIKA ALAPELEMEI 9. előadás: A számítógépes grafika alapelemei Tartalom: 1.Felhasználási terület; 2Megjelenítési alapfogalmak; 21A megjelenítés módja; 2.2 Színezés; 3Grafikus hardver eszközök; 31Input eszközök; 32Output eszközök; 3.21Nyomtatók; 322Monitorok 1. Felhasználási terület A mikroszámítógépek elterjedése, illetve ezek robbanásszerű fejlődése alapvetően

megváltoztatta a programozók, felhasználók viszonyát a számítógéphez. Ennek a változásnak a legszembetűnőbb jele a számítógép és az ember közötti kommunikáció átalakulása Az új kommunikációs forma a kép, illetve a képeken keresztül történő információcsere A számítógépes grafika magába foglalja a grafikai célú eszközök egyre bővülő körének a készítéséhez és működtetéséhez szükséges ismereteket éppúgy, mint a korszerű grafikai programcsomagok és grafikára orientált programnyelvek ismeretét. Az ember és számítógép gyors visszacsatoláson alapuló (un. interaktív) együttműködésében is elsőrendű szerepet játszanak a számítógépes grafikai módszerek A számítógépes grafika az informatikának azon területe mely képek, ábrák előállításával, szerkesztésével, feldolgozásával, felismerésével, rögzítésével foglalkozik. Jellemző ipari, műszaki és egyéb alkalmazások: - műszaki,

•számítógépes tervezés (Computer Aided Design) – CAD, •számítógépes gyártás (Computer Aided Manifacturing) – CAM, •egységes számítógépes tervezés és gyártás – CAD / CAM, •számítógépes építészeti tervezés (Computer Aided Architecture Design) – CAAD, - folyamatirányítás, - számítógépes oktatás (Computer Aided Education) – CAE, - térinformatika, térképészet, - orvostechnika, - szemléltető grafika (mérések, számítási eredmények, üzleti grafika), - szimuláció (környezeti folyamatok, tevékenységek tanulási folyamata), - játékok, animációk, - reklám, művészeti grafika. A felsorolt példák korántsem merítik ki az alkalmazási kört. A grafikai megjelenítés a számítástechnika minden szintjére behatolt. Jelenleg szoftverek, operációsrendszerek megjelenési formája, felhasználói felülete is többnyire grafikus. Koczka György, 2007 34 A SZÁMÍTÓGÉPES GRAFIKA ALAPELEMEI 2. Megjelenítési

alapfogalmak 2.1 A megjelenítés módja A számítógépes grafika elsődleges célja képek megjelenítése. A kép elemi részekből tevődik össze akár hardveres, akár szoftveres oldalról vizsgáljuk. Pont: Egyetlen pötty a megjelenítő eszközön. A képernyőn pixelnek nevezik Vonal: Egyenes szakasz, illetve elemi görbedarab (általában ív). Folt: Mintával kitöltött tartomány. A homogén mintázatot tömör kitöltésnek nevezik Karakter: Egy jelkészlet egyetlen eleme, általában betű vagy számjegy. A megjelenítés két elvében és megvalósítási technikájában különböző módon történhet. • Vektoros módszer esetén az objektumok kulcspontjait definiáljuk, tulajdonságai szabják meg az alakját. A kép jellemzője a folytonos vonalvezetés és a minőségromlás nélküli nagyíthatóság. • Pixeles módszer esetén az alakzat geometriáját pontokkal közelítjük. Az objektumot csak a képi benyomás után tudjuk azonosítani az

alakját leíró pontjai alapján. A látvány az emberi szem véges felbontóképességén alapul A pixeles eszközök jóval nagyobb memóriát igényelnek, szoftveres szempontból azonban sokkal egyszerűbbek. Az alábbi ábra szemlélteti a két megjelenítési módszer közötti különbséget Mindkét elv használatos szoftver és hardver eszközöknél egyaránt. 2.2 Színezés A színek a szembe jutó különböző hullámhosszú fénysugarak érzékelése. A látható tartomány összes színét tartalmazó fényt fehérnek, teljes hiányát feketének érzékeljük. Az informatikában többféle elvet használnak arra, hogy szubjektív érzetünket analitikus formában leírhassuk. A színek leírására használt modellek: - Az RGB modell alapja három szín, a vörös a zöld és a kék. E színek különböző arányú keverésével lehet a színtartomány más részét leírni. A színeket az alapszínek össze- Koczka György, 2007 35 A SZÁMÍTÓGÉPES GRAFIKA

ALAPELEMEI adásával állítjuk elő (additív színkeverés). Sugárzó testek színleírásának jellemző modellje (pl monitor) - A CMYK modell az elnyelt fény tulajdonságain alapul. Alapja négy szín, a cián a bíbor a sárga és a fekete E színek papírra festett különböző arányú keverése a fény egy részét elnyeli és a maradék szín kelt színérzetet. A fekete komponens a festékek tökéletlensége miatt szükséges, elvileg az első három komponens elegendő a keveréshez. A színeket az alapszínek kivonásával állítjuk elő (szubtraktív színkeverés) A nyomtatók használt színmodellje. - A HSB modell az ember színérzékelését veszi alapul. Három összetevője az árnyalat, a telítettség és a fényerő. Az árnyalat az érzékelt fény hullámhosszával arányos mennyiség. A telítettség a szín tisztasága, azaz mennyi fehér komponens van belekeverve A fényerő, pedig a világossága vagy sötétsége - Az LAB eszközfüggetlen elméleti

színmodell. Három érték, a világosság (L), egy zöldmagenta színátmenetben (A) és egy kék-sárga színátmenetben (B) elfoglalt hely definiálja a színt Találkozhatunk olyan színezési módokkal (pl. nyomdatechnikában), ahol nem matematikai úton definiálják, hanem egyedi szempont szerint válogatják össze a színeket, amik közül választhatunk (pl. Pantone Process színskála) A megjelenítő eszközök különböző színmodelleket használhatnak. Természetesen a pixelekhez rendelt színinformációt bitekkel reprezentáljuk Ennek megfelelően az elérhető színt a színkomponensek bitszámából adódó variációs lehetőségek határozzák meg. 3. Grafikus hardver eszközök A hardvereket több szempont szerint lehet csoportosítani: - az információ iránya szerint input és output eszközök, - a megjelenítés illetve az információ gyűjtése szempontjából vektoros és pixeles, - a kép anyagi megjelenési formája szerint papír, film, vagy

virtuális kép egy monitoron. Vizsgáljuk meg, illetve a fontosabbakat jellemezzük az első szempont szerint. 3.1 Input eszközök Diszkrét pontok bevitelére alkalmas eszközök: - Egér – mutatóeszköz, használata a vizuális visszacsatoláson alapul. Főbb típusai mechanikus görgős és az optikai 2D-s pontok bevitelére alkalmas - Digitalizáló – táblával és precíziós mechanikával ellátott eszköz, mely saját billentyűzettel rendelkezik, így 3D-s pontok és jelek bevitelére is alkalmas. - Fényceruza – a képernyőre mutatva vihetjük be a kívánt pontot. - Billentyűzet – általában kurzormozgató billentyűkkel és a képen mozgó szálkereszttel pozícionálhatunk. Képek, ponthalmazok bevitelére alkalmas eszközök: Koczka György, 2007 36 A SZÁMÍTÓGÉPES GRAFIKA ALAPELEMEI - szkenner – papírképek digitalizálása, - digitális fényképezőgép – digitális fényképek készítéséhez, - CCD kamera – digitális videofilm

készítéséhez. A fenti eszközök tartalmaznak egy félvezető fényérzékelő elemet (CCD chip), mely a beérkező fényt megfelelő módon elektromos jelekké alakítja. 3.2 Output eszközök Vektoros megjelenítő: - Rajzgép – kis kocsin mozgó tollakkal, speciális papíron történik a rajzolás. Főbb típusok a sík, a tekercses és a dobos plotter A 70-es, 80-as évek klasszikus megjelenítő eszköze. A korlátozott színszám és a vonalorientált rajzolási mód elavulttá tette Pixeles megjelenítők: - nyomtató, - monitor, - mikrofilm – a 70-es, 80-as évek nagy szín és pixelfelbontású outputja. 3.21 Nyomtatók Gyakrabban használt típusok: - Karakternyomtató – hasonlóak az elektromos írógépekhez. Elemi egysége a karakter Egyes technikai megoldások (sornyomtatók) igen nagy sebességgel nyomtatnak, azonban a formázási kötöttségek és a nehézkes mechanika miatt elavultak. - Mátrixnyomtató – egy vagy több tűsor festékszalagon

keresztül hagy nyomot a papíron. Egy karakter képe pontmátrixból áll össze E nyomtatótípus grafikus üzemmódban is használható Megfelelő festékszalaggal színes nyomtatás is lehetséges - Lézernyomtató – speciális anyagból készült hengerre lézer írja fel pontokkal a képet. Ahol a lézer a hengerhez ér, a felülete elektrosztatikusan feltöltődik és itt a festék megtapad. A papíron végiggördítve a festék a papírra tapad, amit ráégetnek - Tintasugaras nyomtató – tintacseppeket lövell a papírra. A nyomtatási minőség erősen függ a cseppek méretétől, a festék és a papír minőségétől A nyomtatótípus fő erőssége a viszonylag olcsó és jó minőségű színes nyomtatási lehetőség. - Hőnyomtató – speciális, hőérzékeny papíron a kívánt pontok helye elszíneződik. A kép minőségét az inch-enként nyomtatott pontszámmal jellemezzük (dot/inch). Tipikus értéksorozatok: 150, 300, 600, 1200 dpi illetve 180, 360, 720,

1440 dpi. 3.22 Monitorok A manapság használt videomegjelenítők a pixelgrafikus elvet használják. Jellemző technikai megvalósítások: - Katódsugárcsöves – elektronsugár pásztázza a fényérzékeny foszforréteggel bevont ernyőt. Az elektron energiájával arányos intenzitású fénykibocsátásra készteti a képernyőt A színes monitorokban három színágyú van, melyekből kibocsátott sugarak együtt mozognak. A foszforréteg is három különböző típusból épül fel, és egy színháló található a képcsövön Koczka György, 2007 37 A SZÁMÍTÓGÉPES GRAFIKA ALAPELEMEI - Folyadékkristályos – két átlátszó lap között vékony folyadékkristály réteg található. A kristály molekulái elektromos tér hatására elfordulnak, és nem minden irányban egyformán engedik át a fényt. - Gázplazmás – két üveglapból áll, melynek felületére egymáshoz közel elektródákat helyeznek. A közöttük lévő teret megfelelő gázzal

töltik fel Feszültség hatására a gáz fény kibocsájtására késztethető, mely lényegében a két elektróda vonalán kis kiterjedésben történik. A videórendszer két részre bontható. A megjelenítő monitorra (képernyő, vezérlő rendszer) és egy direkt elérésű memóriára (grafikus kártya) A videorendszer üzemmódja karakteres vagy grafikus, egy időben csak az egyik - Karakteres üzemmódban a kép egy kiválasztott karakterkészlet elemeiből áll. Minden karakternek van egy leíró pontmátrixa a memóriában (egy pont egy bit) Közvetlenül csak a karakter pontmátrixa érhető el, az egyes képpontok nem - Grafikus üzemmódban a képhez pixelenként férhetünk hozzá, azaz a grafikus kártyán közvetlenül címezhető. Egy pixel színét a leíró bitszám határozza meg Karakteres üzemmódot már csak igen kevés helyen használnak. A korszerű szövegszerkesztők is grafikus módban dolgoznak, de sok elvet átemeltek pl karaktertábla A karaktert nem

mindig egy pontmátrix ír le, hanem egy vektortáblázat (TrueType, Type 1 karakterkészletek). A grafikus üzemmódok áttekintő jellemzése: A grafikus módok két csoportra bonthatók, a palettás és a direkt színmódra. - Direkt színmód: a színleíró bitek közvetlen tartalmazzák az RGB színt. - Palettás színmód: a használni kívánt szín sorszámához tartozó palettaregiszterek tartalmazzák az RGB színt. Egy pixel színszámát a leíró bitszáma szabja meg: Színszám=2bit/pixel . A TrueColor 32 bites üzemmódja egy nem használt bájtot tartalmaz. A kép memóriaigénye az alábbi képlettel számítható: méret = X irányú pixelszám * Y irányú pixelszám (bit/pixel) / 8 [bájt] A grafikus kártya lineáris memória. A monitoron a kép egy pontmátrix A kettő között egy-egy értelmű a hozzárendelés. A videomemória kezdete (0 bájtján kezdődő bitek) felel meg a képernyő bal felső pixelének. Az üzemmódra jellemző címfüggvény adja

meg, hogy melyik pixelnek mely bitcsoport felel meg a memóriában. A képernyő koordinátarendszere is a bal felső sarokból indul, jobbra és lefelé pozitív irányú (természetes kiosztás) Irodalom Koczka György: Bevezetés a számítógépes grafikába, Műegyetemi kiadó, 2002 Szirmay-Kalos László: Számítógépes grafika, ComputerBooks, 1999 Koczka György, 2007 38 A SZÁMÍTÓGÉPES GRAFIKA ALGORITMUSAI 10. előadás: A számítógépes grafika algoritmusai Tartalom: 1.Grafikai szoftverek; 11 Gépközeli szint; 12 Fejlesztői szint; 1.3Alkalmazói szint; 2Grafikus algoritmusok; 21Vonal rajzolása; 211Egyszerű vonalrajzoló (DDA); 2.2Vágás és ablakozás; 221 Pont láthatósága; 222Egyenes vágása; 2.3Poligonfestés; 24Foltkitöltés; 25Képfeldolgozás; 26Mozgásérzékeltetés 1. Grafikai szoftverek Hardverek, szoftverek grafikus igénye igen sokrétű. Az igények különböző szintű megvalósítást igényelnek Egy digitalizáló eszközből érkező

jelek feldolgozása vagy egy interaktív vonalrajzoló nyilván más jellegű program készítését követeli meg Három fő szint jellemzi a grafikus igényű programokat. 1.1 Gépközeli szint Többnyire eszközök vezérlését, alapfunkciókat ellátó eljárásokat készítenek e szinten. Jellemző programozási eszközök: - közvetlen memóriacímzés (pl. videokártya programozása), - portkezelés (pl. hardver eszköz üzemmód beállítása), - vezérlő szekvenciák (pl. nyomtató, rajzgép vezérlése), - alacsony szintű függvényhívás (grafikus eszközök tartalmazhatnak, vagy külön mellékelnek ezekhez alapfunkciókat ellátó eljárásokat). A különféle hardver eszközök vezérlésére, programozására más-más módot részesítenek előnyben. Példa: PC-s környezetben a szabványos alapszintű funkciókat a BIOS látja el. Néhány fontos video BIOS függvény funkciója: •üzemmód beállítás, •videolap állítás, •pixel kigyújtás,

•karakter kiírás, •karaktertábla kiválasztás. E funkciók szoftver megszakításhívással használhatók a programokban. Koczka György, 2007 39 A SZÁMÍTÓGÉPES GRAFIKA ALGORITMUSAI 1.2 Fejlesztői szint A magas szintű programozási nyelvek jelentős része tartalmaz grafikus eljáráscsomagot. A grafikus feladatok szubrutinok hívásával oldhatók meg. Manapság a funkciók köre szabványosnak tekinthető, azonban használatukban eltérés lehet. Példa: A Pascal grafikus unit néhány fontos szubrutinja nevével és funkciójával: 1.3 InitGraph grafikus üzemmód beállítása Putpixel adott színű pont kigyújtás SetColor tinta színének megadása SetRGBPalette adott sorszámú palettaregiszterek állítása Line vonal rajzolása Circle kör rajzolása OutTextXY szöveg írás megadott pozícióra GetImage kép elmentése PutImage kép beillesztése FillPoly kitöltött sokszög rajzolása FloodFill adott színű vonallal határolt

tartomány kitöltése CloseGraph grafikus üzemmód zárás Alkalmazói szint Az informatika fejlődésével, a felhasználói kör bővülésével indultak igazán fejlődésnek ezek a szoftverek. Jellemző képviselői e szintnek az integrált programcsomagok és a mérnöki tervezőrendszerek. A grafikus felhasználói felület, a menüvezérelt interaktív kapcsolat szinte kötelező A rajzolás művelete általában grafikus funkció kiválasztásával, pozícionáló eszközzel történik. A felhasználói interfész négy összetevőre bontható. - Felhasználói modell: ez a felhasználó által alkotott fogalom a munkája végzéséhez szükséges program kezelési tevékenységről. Átfogó képet kell alkotnia a program működéséről. - Parancsnyelv: a felhasználó parancsok segítségével tudja kezelni a rendszert. Ezeket ikonok, menük vagy parancssor segítségével lehet kiadni. - Visszajelzés: a visszajelzés révén győződhet meg a felhasználó arról,

hogy parancsait a program pontosan megértette. - Információ megjelenítése: tevékenységünk érdemi részének folyamatos megjelenítése alapvetően fontos. Ettől interaktív a tevékenység Koczka György, 2007 40 A SZÁMÍTÓGÉPES GRAFIKA ALGORITMUSAI Példa: Az AutoCAD rendszer fontosabb funkciói: - rajzi környezet beállítása (papírméret, pozícionáló háló, rajzi segédeszközök, etc.), - rajzelemek létrehozása, •egyszerű rajzi entitások: pont, vonal, kör, ív, szöveg, •összetett rajzi entitások: vonallánc, blokk, mintázat, méretvonal, - rajzelemek módosítása, transzformálása, - a rajz szervezése, •blokkok: fizikailag összekapcsolt rajzelemek, melyek azonosítóval rendelkeznek, •fóliák: logikailag összekapcsolt rajzelemek, melyek bizonyos helyzetekben közösen kezelhetők, - a rajz nézetváltása, - rajzelemek lekérdezése, - a rajz megjelenítése hardver eszközökön, - kapcsolat az operációs rendszerrel. A rajzot

felépítő grafikus elemeket a rendszer terminológiájával élve rajzelemeknek (entity) nevezzük. Jól érzékelhető a váltás, melyet a szoftverek szintjei adnak. Az előző két szinten számítástechnikai–programozási megoldást kellett adni, és azt megfogalmazni Az alkalmazói szint biztosítja, hogy a megszokott szerkesztési fogásokkal dolgozhassunk. Természetesen a szoftver használatát megfelelő mélységben ismerni kell 2. Grafikus algoritmusok Ebben a fejezetben azokról az algoritmusokról lesz szó, melyek alapjául szolgálnak mind a megjelenítésnek, mind pedig a grafikus modellezésnek. 2.1 Vonal rajzolása A számítógéppel előállított képeken gyakran van szükség egyenes szakaszokra. Részben, mert rajzainkat is egyenesek alkotják, részben a görbék is jól közelíthetők kis egyenes szakaszokkal. Több grafikus algoritmus is a hatékony vonalrajzoló algoritmusra épül. 2.11 Egyszerű vonalrajzoló (DDA) A vonalat egységnyi

lépésekből teszi össze. (A pixelek távolsága egy egység.) Először kiszámítjuk a lépésszámot dl = max(dx, dy) Az x és y irányú elemi növekmények: Koczka György, 2007 41 A SZÁMÍTÓGÉPES GRAFIKA ALGORITMUSAI εx = dx/dl és εy = dy/dl x0 = x1, y0 = y1 i = 0, 1, , dl-re a kirajzolt pont helye: round(xi, yi), az elméleti egyenes lépései: xi+1 = xi + εx és yi+1 = yi + εy . A pixelek helye az elméleti egyenesből kerekítéssel adódik (nyomvonal). Igen egyszerű és rövid algoritmus. Lebegőpontos műveleteket igényel, ezért csak a kis vonaligényű szoftverekhez alkalmas. 2.2 Vágás és ablakozás Az alkalmazások jelentős része azt a benyomást kelti a felhasználóban, mintha ablakon keresztül nézne egy igen nagyméretű képet. Az operációs rendszerek felhasználói felülete is ablakozási technikán alapul Az alábbi algoritmusok téglalap alakú ablakon működnek 2.21 Pont láthatósága A vágási műveletek alapja egy egyszerű

egyenlőtlenségpár, mely eldönti, hogy a pont belül van-e. Legyen xbal, xjobb, ybal, yjobb az ablak szélének, x,y a pont képernyőkoordinátái A Láthatóság feltétele: xbal < x < xjobb ybal < y < yjobb Vonalas alakzatoknál ez a módszer nem alkalmazható. A pontokra bontás, majd a feltételvizsgálat igen lassúvá tenné az eljárást 2.22 Egyenes vágása Figyeljük meg az egyenesek és az ablak kölcsönös helyzetét. A konvex határ mindig csak egy látható szakaszt állíthat elő. A vázolni kívánt algoritmus Cohen és Sutherlandtől származik. Az alapelv, hogy minél gyorsabban elhagyja azokat az egyeneseket, melyek nem láthatók. Koczka György, 2007 1001 1000 1010 0001 Ablak 0000 0010 0101 0100 0110 42 A SZÁMÍTÓGÉPES GRAFIKA ALGORITMUSAI A képernyő határait meghosszabbítjuk úgy, hogy a teljes képet kilenc részre osszák fel. E tartományok egy 4-bites kódot kapnak az ábra szerint. Az egyenes végpontjai pedig

megkapják azt a kódot, melyikben fekszenek. A vágási algoritmus lépései: - Nyilvánvaló, ha mindkét végponthoz zérus tartozik az egyenes teljes terjedelmében belül van. - Amennyiben a két kód logikai szorzata (logikai és) nem nulla, az egyenes kívül esik. - Egyébként darabolni kell. A darabolás módja, hogy megkeressük az egyenes és a képernyő egyik élének metszéspontját. Az ábrán pl a C pontot Ekkor az AC szakasz elhagyható A CB szakasz vizsgálatával megkapjuk a D pontot, így a megjeleníthető BD szakaszt. 2.3 Poligonfestés Az algoritmus célja, hogy tetszőleges síkidomot be tudjunk festeni egy megadott színűre. Egy általános síkidomot tetszőleges mértékben közelíthetünk poligonnal. Legyen a poligon oldalszáma n. Egy kiszemelt pontjából n-2 darab háromszögre vághatjuk Ezzel a feladatot visszavezettük háromszög festésére. A háromszöget vízszintes csíkokra vágjuk a képernyő sorai szerint, majd adott színű

vízszintes vonalakkal kitöltjük. A szakaszok végpontjai a számított metszéspontokból adódnak A gyakran használt színátmenetes poligonkitöltésnek is a fenti algoritmus szolgálhat alapot. Ekkor a vízszintes vonalat valamilyen interpolációval számolva pixelenként más színnel kell rajzolni. 2.4 Foltkitöltés Sok esetben olyan alakzatot kell kifesteni, mely poligonokra vágása komoly nehézségbe esik vagy nem is igen kivitelezhető. Nevezzük az ilyen többszörösen összefüggő tartományt foltnak Rendelkezzen meghatározott színű határvonallal Indulásnak meg kell adni egy olyan [x,y] pontot, amely a folt belsejébe esik. Az algoritmus vízszintes vonalakkal próbálja betölteni a zárt területet. A tárból kiolvas egy [x,y] koordinátát. Az [x,y] ponttól jobbra, majd az [x-1,y] ponttól balra haladva addig rajzolja be a vízszintes vonal pontjait, amíg már berajzolt ponthoz, vagy határponthoz nem ér. Eközben figyeli az egyel följebb és egyel

lejjebb lévő vonal pontjait, és amikor ezeken a vonalakon berajzolt pontot üres pont követ, az üres pont koordinátáit a tárba helyezi. Ilyen módon egy üres pont minden szomszédos üres pontja a következő menetben be lesz rajzolva, Koczka György, 2007 43 A SZÁMÍTÓGÉPES GRAFIKA ALGORITMUSAI hiszen vagy maga is bekerül a tárba, vagy egy ilyen pontból üres pontokon keresztül, vízszintes irányból elérhető. 2.5 Képfeldolgozás Az alapelvet ismertetve, csupán érintőlegesen foglalkozunk a témával. Remek szoftverek és kiterjedt irodalom áll a felhasználók rendelkezésére. A feldolgozás alapja az a bitmátrix amely a feldolgozandó képet leírja. Tekintsük az alábbi ábrát. A bal oldal a képernyő egy részlete, az a képrészlet, melyet vizsgálni fogunk. Vegyük azt az alapesetet, mikor a kép monokrom Jelölje 0 ahol a pixelek fehérek és 1 ahol feketék (bal felső ábra) Ez megfelel egyébként a tárolt kép bitjeinek Az ábra egy 16 x

16 pixeles dobozban fér el. Ennek megfelelően mérete 2 x 16 bájt Végezzünk egy egyszerű módosítást a teljes képen A 0-kat cseréljük fel az 1-esekkel (bal alsó ábra). A képernyőn az ábra inverze, azaz a negatívja jelenik meg 000000000000000000 011100000000000000 011111000000000000 011111110000000000 011111111100000000 011111111111000000 011111111111110000 000000111100000000 000000011110000000 000000001111000000 000000000111100000 000000000011110000 000000000001111000 000000000000111100 000000000000011110 000000000000001110 000000000000000110 000000000000000000 111111111111111111 100011111111111111 100000111111111111 100000001111111111 100000000011111111 100000000000111111 100000000000001111 111111000011111111 111111100001111111 111111110000111111 111111111000011111 111111111100001111 111111111110000111 111111111111000011 111111111111100001 111111111111110001 111111111111111001 111111111111111111 Színes kép esetén bonyolódik a helyzet. A grafikus üzemmódnak

megfelelően a bitmátrix nagyobb lesz 256 színű üzemmódnál egy pixelnek egy bájt felel meg A kép mérete így 16 x 16 bájtosnak adódik. Természetesen nem csak globális manipulációkat végezhetünk. Retusálhatjuk, módosíthatjuk a kép tetszőleges részét Koczka György, 2007 44 A SZÁMÍTÓGÉPES GRAFIKA ALGORITMUSAI 2.6 Mozgásérzékeltetés A mozgás érzékeltetése a számítógépes grafika alapvető igényévé vált. Három csoportba sorolhatók a különböző megvalósítások Képek egymás utáni sorozata Az általában előre elkészített képeket folyamatosan, egymás után másoljuk a videomemóriába. Egyszerű módszer, de csak igen gyors hardverrel lesz folyamatos a mozgás. Valós idejű mozgásérzékeltetésre csupán korlátozottan alkalmas Képrészletek egymás utáni sorozata Általában fix háttérre helyezzük el a már korábban elkészített alakzatokat. Folyamatosan mentjük az eltakart részleteket, majd visszarajzoljuk, és az

alakzatokat új helyre rakjuk. Az animációk kedvelt módszere Lépésekre bontva: 1. Alakzat, háttér elkészítése 2. Az alakzat pozíciójának számítása 3. Az alakzat hátterének mentése 4. Az alakzat megjelenítése 5. Várakozás (legyen időnk látni) 6. Háttér visszatöltése 7. Feltétételes ugrás 2-re Képpixelek folyamatos frissítése Képünk megváltozott pontjait rajzoljuk át, a többihez nem nyúlunk. A módszerrel folyamatosan pásztázzuk a meglévő és az új kép pontjait Ahol eltérés van, frissítjük a videomemóriát. A módszer csak akkor hatékony, ha az elkészített új kép tárolt szerkezete megegyezik a képernyő szerkezetével Lépésekre bontva: 1. A látható kép elkészítése 2. Az új kép elkészítése a tárolóra 3. Frissítés, szükség szerint várakozás 4. Feltételes ugrás 2-re A 2., 3 pont összevonható, ha a kép készítési folyamata nem zavarja a látványt és ez programozástechnikailag megoldható. Az animáció

a mozgás érzékeltetésének speciális fajtája. Amennyiben egy grafikus objektum mozgását, vagy mozgáskomponensét ismétlődő képsorral le tudjuk írni, akkor e fázisok előre elkészíthetők. Az objektumot új helyén ekkor a képsorozat egy megfelelő tagja jeleníti meg. Irodalom Koczka György, 2007 45 A SZÁMÍTÓGÉPES GRAFIKA ALGORITMUSAI Koczka György: Bevezetés a számítógépes grafikába, Műegyetemi kiadó, 2002 W. M Newman – R F Sproull: Interaktív számítógépes grafika, Műszaki Könyvkiadó, 1987 Koczka György, 2007 46 SZÁMÍTÓGÉPES GRAFIKAI MODELLEZÉS I. 11. előadás: Számítógépes grafikai modellezés I Tartalom: 1.Grafikai modellezés; 11Geometriai modell; 12Geometriai tervezés; 1.3Alakleírás; 131A leírással szemben támasztott követelmények; 132Az alakleírásra használt matematikai eszközök; 1.4A valószerűség elérésére használt módszerek 1. Grafikai modellezés A számítógépes grafika szorosan

kapcsolódik a modellezéshez. Ennek egyik oka az, hogy a számítógépes grafika igen kényelmes lehetőséget nyújt a számítógépes modellek viselkedésének megfigyeléséhez. A képi megjelenítés könnyebben átlátható és értelmezhető, mint a táblázatos forma Másrészt az interaktív grafikát felhasználhatjuk a tervezési alkalmazásokban is, ahol a grafikai modell a tervezési folyamat jelentős részét teszi ki. 1.1 Geometriai modell Ahhoz, hogy megjeleníthessük a valóság egy kiszemelt részét – nevezzük színtérnek ezt a gondolatban elhatárolt térrészt – grafikus output eszközön, a következő lépéseket kell megtennünk: Koczka György, 2007 47 SZÁMÍTÓGÉPES GRAFIKAI MODELLEZÉS I. színtér (a valóság elkülönített része) ⏐ ⏐ ⏐← geometriai modellalkotás ⏐ ↓ modelltér ⏐ ⏐← transzformációk ⏐← vetítés ⏐ ↓ képtér (az alakzatok látványa) ⏐ ⏐← transzformáció a hardver eszköz

koordinátarendszerébe ⏐ ↓ megjelenítő eszköz a megjelenítendő alakzatok kiválasztása a fontos tulajdonságok megtartása a tárgymodellek elhelyezése a tárgytér elkészítése (a nézőpont irányú modelltér) a nézőpont irányú látvány előkészítése alakzatok a képsíkban a hozzájuk tartozó mélységi adatokkal a látvány rögzítése A szoftverek, grafikus tervezők egy–két fázist átvesznek a felhasználótól. Az AutoCAD menü szinten biztosítja a modelltér képtér transzformációkat. Természetesen biztosítottak a képtér monitor, nyomtató transzformációk is Az alakzatokat adatszerkezetben tárolt koordinátái, azok kapcsolati összefüggései teljes mértékben meghatározzák. Az ilyen tulajdonsággal rendelkező modelleket geometriai modellnek nevezzük. Példa: Test felszínének közelítése és képi megjelenítésének előkészítése. A felszínt diszjunkt p1, p2,., pn poligonokkal közelítjük, területük rendre f1, f2,,

fn n n i =1 i =1 Ezzel a közelítő poliéder p = U p i és felszíne F = ∑ f i . Megfelelő felosztás esetén a test alakjának képe jól közelíti a valóságot és a számított felszín is megfelelő pontosságú. Ábrázolásához meg kell határozni a poligonok modelltérbeli csúcsponti koordinátáit. A megfelelő nézőpont szerinti transzformációt elvégezve, a csúcsokat vonalakkal összekötve előáll a test drótvázas képe. Legyen egy relációs adatbázis két táblája a poliédert leíró adatszerkezet. Az egyik tábla a csúcsokat, a másik a csúcsokat tartalmazó éleket, azaz a kapcsolatokat tartalmazza. Koczka György, 2007 48 SZÁMÍTÓGÉPES GRAFIKAI MODELLEZÉS I. Csúcsok és koordinátáik: azonosító x y z csúcsp xp yp zp Élek és a hozzá tartozó végpontok: azonosító kezdőpont végpont élk csúcsp csúcsq A poligonok éleivel összerendelt csúcsponti koordináták a test drótvázas geometriai modelljét alkotják.

Tömör megjelenítéshez meg kell adni a lapokat. A lapokat csúcsaik megfelelő sorrendű felsorolásával definiáljuk. A körbejárást a jobbkéz-szabály konvenció betartásával úgy végezzük, hogy a normális a poliéderből kifelé mutasson. Vegyük az előző csúcsok-koordináták táblához a lapok táblát: azonosító darab 1. csúcs . K. csúcs lapk K csúcsp . csúcsq . A darab oszlop megadja, hogy az adott lapnak hány csúcsa van. (Ebben a táblában előfordulhatnak üres cellák.) A lapok takarásvizsgálat után megjeleníthetők kontúrjukkal, festhetők vagy világítást használva árnyalhatók. A poliéder lapjaival összerendelt csúcsponti koordináták a test geometriai modelljét alkotják. 1.2 Geometriai tervezés A geometriai tervezés a konstruktív geometria elvén alapszik. Ennek alapgondolata, hogy minden véges háromdimenziós geometriai alakzat véges számú diszjunkt geometriai testtel és véges számú kombináló művelettel

(logikai operátorok) leírható. Az elvnek megfelelően a tervező rendszerek saját alaptest készlettel rendelkeznek. Példa: Az AutoCAD szilárdtest modellezőjében három, testeken végrehajtható boole-művelettel dolgozhatunk, az egyesítéssel a közösrész-képzéssel és a kivonással. 1.3 Alakleírás Egy grafikus programnak több, néha egymásnak ellentmondó szempontnak kell megfelelnie. Teljesítenie kell a felhasználó követelményeit, matematikailag jól kezelhető modellt kell alkotnia, számítási munka és tárigény szerint hatékonynak kell lennie Vizsgáljuk meg e szempontokat. 1.31 A leírással szemben támasztott követelmények Többnyire a felhasználó igényei szabják meg, hogy alakleírásunknak mely tulajdonságokkal kell rendelkeznie. A görbetervezés legfontosabb szempontjai a következők Koczka György, 2007 49 SZÁMÍTÓGÉPES GRAFIKAI MODELLEZÉS I. - Tengelyfüggetlenség: egy alakzat képe nem változhat meg, ha egy más

koordinátarendszerben fogalmazzuk meg jellemző pontjait. - Többértékűség: a leírandó alak általában nem tekinthető valamely koordináta egyértékű függvényének. - Támpontok, csomópontok: görbe alakjának interaktív kijelölésére szolgálnak. Olyan pontok, melyeken a görbének keresztül kell haladnia, illetve amelyek előre látható módon irányítják a görbe alakját. - Globális, lokális változtathatóság: a tervező által végzett módosítás hatása a változtatott környezetre, illetve a teljes görbére. - Hullámzás kiegyenlítés: igény lehet a lokális hullámzás csökkentésére, a zaj szűrésére. - Sokoldalúság: akadályozhatja a felhasználót, ha a görbeleírás csak meghatározott alakváltoztatásokat tesz lehetővé. Például körívek rajzolásával nehézkes bonyolult alakot megrajzolni. - Folytonossági követelmények: a bonyolult alakzatokat rendszerint különféle, végüknél összeillesztett görbével modellezik. Az

illeszkedés rendje meghatározza az eredő alakzat formáját. A felülettervezés követelményei a fentiekhez nagyon hasonlóak. Az esetek jelentős részében a görbékre alkalmazott módszerek kiterjesztésével oldhatók meg a problémák 1.32 Az alakleírásra használt matematikai eszközök 1.321 Görbék megadása Egyszerű grafikus problémák esetén a koordináták függvénykapcsolatba hozása elegendő. Mérések kiértékelésére, gazdasági diagrammok ábrázolására többnyire kielégítő Görbék modellezéséhez azonban a paraméteres (vektor–skalár) görbéket használják a leggyakrabban. A görbe pontjainak egy vektor felel meg r(t) = [x(t) y(t) z(t)] . Itt a koordináták a t paraméter függvényei A paraméter egy meghatározott intervallumban – rendszerint 0 és 1 között – mozoghat. A többértékűség követelménye természetesen kielégül 1.322 Felületek megadása A kétváltozós függvények korlátozott felhasználási területtel

bírnak. Jól használhatók egy terep bemutatására, szintvonalai ábrázolására. Általános esetben kétparaméteres (vektor–skalár) függvényekkel tudjuk a felületeket kezelni r(u,v)=[x(u,v) y(u,v) z(u,v)] . Mindhárom koordináta kétváltozós függvény, u és v egy meghatározott tartományon mozoghat. 1.323 Vektor-vektor függvény ábrázolása Ezek a függvények olyan mennyiségek kezelésére alkalmasak, melyek a tér egy pontjához vektort rendelnek. Megjelenítésükre szemléletes a vektoros módszer alkalmazása, mert így a nagyság és az irány is bemutatható. Koczka György, 2007 50 SZÁMÍTÓGÉPES GRAFIKAI MODELLEZÉS I. 1.324 Az alaktervezés interpolációs eszközei Az alakleírás módja az alkalmazástól függ. Analitikus és szintetikus alkalmazásokról beszélhetünk. Az analitikus alkalmazásokban a tárgyak mért adataiból indulunk ki Görbét vagy felületet illesztünk egy tárgy jellemző pontjaihoz. Célunk a valószerű illesztés,

a mérések számának minimalizálása stb Szintetikus alkalmazásokkal a tervezésben találkozhatunk. A felhasználó interaktív módon létrehozza az alakzatot, és addig módosítja, amíg az elfogadható nem lesz - Az analitikus módszerek jellemző matematikai eszköze az alakzatot leíró függvénykapcsolatok ismerete. - A szintetikus módszerekre jellemző, hogy a modellezendő alak támpontjainak megadásával alakítjuk ki a kívánt objektumot. E támpontokon nem feltétlen halad át az alakzat, csupán jellemzi azt. Amennyiben pontok defíniálják az alakzatot, megjelenítéséhez megfelelő interpolációs eljárást kell választanunk. Vizsgáljuk meg a gyakrabban használt 2D-s módszereket Interpoláció polinommal A módszer korlátai: •Magasabb fokszám esetén az egyenletrendszer rosszul kondícionálttá válhat. •A tapasztalat azt mutatja, hogy ötödfokúnál magasabb fokszámoknál nem várt szélsőértékek jelennek meg a függvény menetében. •A

függvény csak globálisan változtatható. A fentiek miatt görbetervezésre csak korlátozottan alkalmas. Regresszió Gyakran előforduló probléma, hogy ismerjük a függvény típusát, de több a pont, mint a hipotézisgörbe variálható együtthatóinak száma. Ebben az esetben valamilyen függvénykiegyenlítést kell alkalmaznunk Természetesen a keresett függvény nem halad át az alappontokon, csupán megfelelően közelíti azt. Az általánosan használt legkisebb négyzetek módszere az együtthatókat az xi helyen vett yi − Φ( xi ) eltérések négyzetösszegének minimalizálásával határozza meg. Spline interpoláció A lokális változtathatóság és a nem várt görbelefutás indokolja az alacsonyabb fokszámú polinomokkal és intervallumok illesztésével történő közelítést. A spline az [xi-1, xi] szakaszokon olyan harmadfokú polinomokból áll, melyek a végpontokon folytonosan, törésmentesen és simán csatlakoznak a szomszédos polinomokhoz.

Egy alappont kis elmozdítása csupán kis mértékű globális változást okoz. Bézier- és a B-spline módszer Az előző eljárások mindegyike egyenletrendszer megoldására vezethető vissza. A súlyozásos módszerek alapgondolata, hogy az alappontok közelében domináljon maga a pont, távolodva legyen csökkenő a hatása. Több, erre az elvre épülő interpoláció használatos. Előnyük a viszonylag egyszerű, általában explicit vagy iterációs megoldó algoritmus, és a szépen alakítható forma A hát- Koczka György, 2007 51 SZÁMÍTÓGÉPES GRAFIKAI MODELLEZÉS I. rány, hogy az alappontokon általában nem megy keresztül a megkonstruált függvény. Ilyenkor szokás az alappontokat támpontoknak is nevezni. Egy támpont elmozdítása adott pontnyi széles intervallumon okoz lokális változást. 1.4 A valószerűség elérésére használt módszerek A grafikus megjelenítőkön nem tudunk és nem is mindig célszerű olyan képet előállítani, amely a

valódi látvány tökéletes ábrázolása lenne. Olyan módszerekre van szükség, amelyek figyelembe veszik az adott alkalmazás igényeit, a kép előállításához szükséges munka mennyiségét és a megjelenítő hardver jellemzőit, képességét. A megjelenítési módszerek alapproblémája a mélység, azaz a harmadik dimenzió érzékeltetése. A megjelenítés fontosabb eszközei: Alak, forma érzékeltetése - a kontúrvonal rajzával (drótvázas megjelenítés), - a terület festésével (sraffozás, árnyalás). A háromdimenziós látvány kétdimenziós képének előállításához alapvető a vetítés. Gyakran használt vetítési módok: - párhuzamosan síkra, - perspektíven síkra – a távlatot azzal érzékelteti, hogy a közelebbi tárgyakat nagyobbnak ábrázolja a távolabbiaknál, - nem sík felületre. A térbeliség érzékeltetésének főbb módszerei: - Merőleges vetítés - Perspektív vetítés - Takart felületek elhagyása - Árnyalás -

Kinetikus mélységi hatás Irodalom Bajcsai Pál: Numerikus analízis, Akadémia Kiadó, 1985 Koczka György: Bevezetés a számítógépes grafikába, Műegyetemi kiadó, 2002 W. M Newman – R F Sproull: Interaktív számítógépes grafika, Műszaki Könyvkiadó, 1987 Koczka György, 2007 52 SZÁMÍTÓGÉPES GRAFIKAI MODELLEZÉS II. 12. előadás: Számítógépes grafikai modellezés II Tartalom: 1.Grafikai modellezés; 11Transzformációk; 111Homogén koordináták; 1.12Transzformációs mátrix; 113Transzformációk konkatenációja; 12Takart felületek elhagyása; 1.21Tárgytér algoritmusok; 122Képtér algoritmusok; 1.3Árnyalás; 131Árnyalási poliéder 1. Grafikai modellezés 1.1 Transzformációk Egy grafikus rendszernek lehetővé kell tennie, hogy a felhasználó az alakzatok elkészítése során különböző transzformációkat alkalmazzon. Fel kell tudnia nagyítani, mozgatnia kell, alkalmanként tükrözésre és forgatásra is szükség lehet A

számítógépes grafika matematikai apparátusa a lineáris algebra eszköztárán alapul. Az alakleírást vektoros, a koordináta transzformációkat mátrixos írásmóddal tárgyaljuk. 1.11 Homogén koordináták A homogén tárgyalásmód eredetileg a projektív geometria eszköztárába tartozott. Egy n-dimenziós problémának megfelel egy n + 1-dimenziós térbeli probléma. Az így definiált alakzatok leírásánál nem szerepel explicit állandó tag Ebből adódik a homogén kifejezés is. A háromdimenziós transzformációkat négy dimenzióban kényelmesebb tárgyalni. Az r = [x y z] vektornak megfelel az r = [wx wy wz w] w ≠ 0 homogén vektor. Kényelmes az r = [x y z 1] alak használata (w = 1). 1.12 Transzformációs mátrix Az r pontot mozgassuk el r pontba. Vektorosan jelölve r = r ⋅ T Az általános háromdimenziós transzformáció mátrixos alakja: [x y z 1] = [x y ⎡a ⎢b z 1] ⋅ ⎢ ⎢c ⎢ ⎣d e f g h i j k l 0⎤ 0⎥⎥ 0⎥ ⎥ 1⎦

Koczka György, 2007 53 SZÁMÍTÓGÉPES GRAFIKAI MODELLEZÉS II. Három elemi háromdimenziós transzformációt részletezünk. A többi transzformációt is általában ezekre vezetjük vissza. Eltolás: D vektor irányú eltolás transzformációs mátrixa: ⎡1 ⎢0 ⎢ ⎢0 ⎢ ⎢⎣ D x 0 0 1 0 0 1 Dy Dz 0⎤ 0⎥⎥ 0⎥ ⎥ 1⎥⎦ Léptékezés: A léptékezési transzformációval mindhárom koordinátatengely irányában független mértékű nagyítást végezhetünk. Mátrixa: ⎡S x ⎢0 ⎢ ⎢0 ⎢ ⎣0 0 Sy 0 0 0 0 Sz 0 0⎤ 0⎥⎥ 0⎥ ⎥ 1⎦ Sx, Sy, Sz ≠ 0 Forgatás: A meghatározott tengely körüli ϕ szögű elforgatás mátrixa: ⎡ cos ϕ ⎢− sin ϕ ⎢ ⎢ 0 ⎢ ⎣ 0 sin ϕ cos ϕ 0 0 0 0 1 0 z tengely körül 0⎤ 0⎥⎥ 0⎥ ⎥ 1⎦ ⎡cos ϕ ⎢ 0 ⎢ ⎢ sin ϕ ⎢ ⎣ 0 0 − sin ϕ 1 0 0 cos ϕ 0 0 0⎤ 0⎥⎥ 0⎥ ⎥ 1⎦ 0 ⎡1 ⎢0 cos ϕ ⎢ ⎢0 − sin ϕ ⎢ 0 ⎣0 y tengely körül 0 sin ϕ cos ϕ 0 0⎤

0⎥⎥ 0⎥ ⎥ 1⎦ x tengely körül A forgatás pozitív iránya konvencionálisan a jobbkéz-szabály által megszabott. (Formálisan ezért különbözik az y tengely körüli az x és z tengely körüli forgatástól) Mindhárom transzformációnak van inverz párja, mely a fordított transzformációt hajtja végre. 1.13 Transzformációk konkatenációja Több transzformáció egymás utáni alkalmazását helyettesíthetjük egyetlen mátrix alkalmazásával. Amennyiben T1, T2, , Tn transzformációt egymás után kell végrehajtani, akkor ugyanazt a hatást érhetjük el egyetlen Te transzformációval, ahol Te = T1 · T2 · . · Tn A mátrixok összeszorzásakor a transzformációk sorrendjét be kell tartani. Példa: Középpontos tükrözés transzformációs mátrixának elkészítése. Legyen [k1 k2 k3] a tükrözés középpontja. Teendőnk a következő: eltolás [-k1 -k2 -k3] vektorral, tükrözés az origón keresztül, majd eltolás [k1 k2 k3] vektorral. Az

origón ke- Koczka György, 2007 54 SZÁMÍTÓGÉPES GRAFIKAI MODELLEZÉS II. resztül történő tükrözés mátrixát abból az egyszerű meggondolásból írjuk fel, hogy minden koordináta előjele vált a műveletnél! ⎡ 1 ⎢ 0 ⎢ ⎢ 0 ⎢ ⎣− k1 1.2 0 1 0 − k2 0 0 1 − k3 0⎤ ⎡ − 1 0 0 0⎥⎥ ⎢⎢ 0 − 1 0 ⋅ 0⎥ ⎢ 0 0 − 1 ⎥ ⎢ 1⎦ ⎣ 0 0 0 0⎤ ⎡ 1 0⎥⎥ ⎢⎢ 0 ⋅ 0⎥ ⎢ 0 ⎥ ⎢ 1⎦ ⎣k1 0 1 0 k2 0 0 1 k3 0⎤ ⎡ − 1 0 −1 0⎥⎥ ⎢⎢ 0 = 0 0⎥ ⎢ 0 ⎥ ⎢ 1⎦ ⎣2k1 2k 2 0 0 −1 2k 3 0⎤ 0⎥⎥ 0⎥ ⎥ 1⎦ Takart felületek elhagyása A számítógépes grafika egyik legizgalmasabb és egyben legnehezebb problémája a tömör tárgyak takart részeinek elhagyása. A színtérben a tömör tárgyak átlátszatlan anyaga elzárja a fénysugarak útját, így azok nem jutnak a szemünkbe, azaz nem látszanak. Annak érdekében, hogy valószerűbb képet kapjunk, valamilyen takarási algoritmust kell

alkalmazni A módszerek két csoportra bonthatók. Tárgytér vagy képtér algoritmusok annak megfelelően, hogy a takarásvizsgálatot hol végzik A tárgytér algoritmus a tárgyak közötti geometriai összefüggések alapján határozza meg, mely részletek láthatók. A számításokat a lehető legnagyobb pontossággal, rendszerint a lebegőpontos processzor pontosságával végzik Ez sokkal nagyobb a megjelenítő eszköz pontosságánál, így a kép tetszőlegesen nagyítható minőségromlás nélkül A képtér algoritmus a végső képnél vizsgálja, hogy a pontokban mi látszik Egyenként meghatározza a képet alkotó pixelek színét, fényerősségét. Pontossága megegyezik a megjelenítő eszköz felbontásával A két elv eltérő hatékonyságú. Bonyolult színtér esetén a tárgytér algoritmusok számítási igénye erősen nő. A képtér algoritmusok csak a kép látható részének bonyolultságától függnek, így lényegesen lassabban nő a számítások

mennyisége. Az algoritmusok bonyolultsága is a képtér módszerek javára billenti a mérleget 1.21 Tárgytér algoritmusok Triviális vizsgálat A módszer arra szolgál, hogy egy lapról eldönthessük, hogy látható-e (szükséges feltétel). Amennyiben a poligon normálisa a szemlélő felé néz, azt jelenti, ha nem takarja egy másik poligon, akkor látszik. Másképpen, ha a normális vektora és a szemlélő irányába mutató vektor skaláris szorzata pozitív, a lap kielégíti a láthatóság szükséges feltételét. Statisztikusan a lapok felét kiszűrhetjük az eljárással Amennyiben a tárgytérben egy test van, a test konvex és diszjunkt poligonokból áll, ez a feltétel elégséges is! 1.22 Képtér algoritmusok Mélységpuffer algoritmus Ez az algoritmus a legegyszerűbb a képtéralgoritmusok között, de az elv mindegyiknél megtalálható. A képernyő nézetablakának minden pixeléhez feljegyezzük annak a tárgynak a képtérbeli mélységét és

színét, mely a szemlélőhöz a legközelebb fekszik. Koczka György, 2007 55 SZÁMÍTÓGÉPES GRAFIKAI MODELLEZÉS II. A gyakorlatban két tömböt használunk, egyet a mélység, egyet a szín számára. Mindkettőt a nézetablak pixelkoordinátáival címezzük 1.3 Árnyalás A háromdimenziós színtér raszterképének valószerűsége az árnyalást előidéző fizikai jelenségek sikeres szimulációjától függ. Árnyalási modellt használunk a felület megjelenítésekor a fényerősség és a szín kiszámításához A két fő alkotórész a felületi és a megvilágítási tulajdonságok Felületi jellemzők: - Geometria: a ráeső fény milyen irányba verődik vissza. - Visszaverő képesség: meghatározza, hogy a ráeső fényből mennyi verődik vissza. - Áttetszőség: meghatározza, hogy mennyit enged át a ráeső fényből. Megvilágítás: - Szórt megvilágítás: a színtér megvilágítása minden irányból egyenletes. - Irányfény: a színtérben

pontszerű fényforrások vannak. Ezek okozzák a tárgyak egyenetlen árnyaltságát, a tükröződési és a csillogási jelenséget. A végtelenbe helyezett forrásról párhuzamos sugarak érkeznek Amennyiben távolságfüggővé kívánjuk tenni a megvilágítást, véges távolságot kell adni a fényforrásnak, a világítás irányát és az intenzitását helyfüggővé kell tenni - Árnyék: irányfényben az egyes tárgyakra mások, illetve önmaga részei is árnyékot vethetnek. 1.31 Árnyalási poliéder Az előző képletekkel kiszámítható egy tetszőleges felületi pont színe. Bár a számítás nem túl bonyolult, mégis sokszor kell végrehajtani. Csökkenthetjük a számítási munkát, ha kihasználjuk, hogy a szomszédos pixelek fényessége egymáshoz közeli (élektől megfelelő távolságban). Ha egy felületet nem egyenletével írunk le, hanem geometriai modellel közelítjük, szintén nem ismerjük minden pixelhez a normális értékét. Egy folytonos

felület poliéderárnyalása zavaróan hathat a nézőre. A folytonos árnyalás igen valószerű látványt nyújt. Vizsgáljuk meg a különböző módszereket egy gömbön, viszonylag durva felosztású geometriai modell esetén. Koczka György, 2007 56 SZÁMÍTÓGÉPES GRAFIKAI MODELLEZÉS II. Drótváz modell A geometriai modell három és négyszögekből áll. Az árnyalási poliéder Megjelenítés a lapok független árnyalásával. Gouraud módszere a folytonos árnyalásra Mindegyik lap csúcspontjaiban meghatározza a normálisokat, majd ezekből a csúcsok színét. A lapon belüli árnyalást a csúcsponti értékekből interpolálja Phong módszere a folytonos árnyalásra Alapelve, hogy nem a színeket, hanem a normálvektorokat interpolálja és ebből számítja minden pixelnél a színt az árnyalási modellel. Phong módszere több számítást igényel, de sok esetben valószerűbb eredményt ad. Pontok független árnyalása Az árnyalás pontos

számításához minden pontban egyenként meghatározzuk a normálvektort és ebből a pixel színét. A gömbön bemutatott példán is látszik, hogy a folytonos árnyalási modellek intenzitásviszonyainak látványa csak kevéssé megkülönböztethető. A poliéder sziluettje zavaró lehet, de ezt csak a felosztás finomításával javíthatjuk. Irodalom Koczka György: Bevezetés a számítógépes grafikába, Műegyetemi kiadó, 2002 W. M Newman – R F Sproull: Interaktív számítógépes grafika, Műszaki Könyvkiadó, 1987 Pirkó József: 3D Perspektivikus grafika, ComputerBooks, 1988 Koczka György, 2007 57 INFORMÁCIÓS RENDSZEREK 13. előadás: Információs rendszerek Tartalom: 1.Információs rendszerek; 11Az információs infrastruktúra összetevői; 12Az információs rendszerek részei; 1.21 Adatok; 122 Hardver; 123Szoftver; 1.24Felhasználók; 2 Adatbázisok; 21Adatbázis; 22Adatmodell; 23Adattárolási eszközök; 2.4 Adatbázis-kezelés jellemző

műveletei; 25Adatbázis védelem 1. Információs rendszerek Alapfogalmak egyszerűen megfogalmazva: Az információ valamely dologról, jelenségről, kapcsolatról nyert hasznos ismeret. Az adat az információ megjelenési formája. Az információs rendszereknek nem csak tárolni kell az adatokat, hanem biztosítani kell azt is, hogy azok kellő időben, a megfelelő formában eljussanak az őket igénylő személyekhez, illetve az újonnan keletkező adatok is tárolódjanak a rendszerben. Az információs rendszerek célja az információ tárolása és feldolgozása. Társadalmi szervezettségünk, de mindennapi életünk is aligha képzelhető el korszerű információs rendszerek létrehozása és használata nélkül. Az elektronika és számítógépek elterjedésével a hatvanas években kialakult az információs rendszerek infrastruktúrája. 1.1 • Az információs infrastruktúra összetevői Adatfeldolgozás: A feladatot általában számítógép látja el.

Irányulhat tranzakciók végzésére, vagy akár vezetői döntés előkészítésre is. • Telekommunikáció: Az információ távolabbi helyekre való eljuttatására szolgál. A telefon, telex, telefax és természetesen a számítógépes hálózatok (LAN-ok, WAN-ok tartoznak ide). • Automatizált irodai szolgáltatások: Írógépek, másolók, képfeldolgozók, terminálok, személyi számítógépek alkotják. Természetesen a számítástechnika mai fokán a fenti kategóriák összemosódnak. Azonban látszik, hogy egy információs rendszer nem jelentheti egyetlen szoftver megalkotását és használatát Koczka György, 2007 58 INFORMÁCIÓS RENDSZEREK 1.2 Az információs rendszerek részei Minden információs rendszer négy részből tevődik össze: 1.21 Adatok Adatszerkezetekben tárolt információk. 1.22 Hardver Minden rendszer valamilyen konkrét hardveren valósul meg. Ennek része a számítógép (illetve számítógépek elosztott

rendszereknél), a terminálok, a tárolók és a hozzájuk tartozó telekommunikáció. 1.23 Szoftver Az információs rendszerek szoftver részei: • Operációs rendszer felügyeli az adatbázis-kezelő működését. • Adatbázis-kezelő rendszer fő feladata a file-műveletek és jogosultságok kezelése. • Alkalmazói programok a tényleges tevékenység megfogalmazása egy programnyelv segítségével. A három szint kialakítása a rugalmasságot biztosítja. Példa: UNIX, Oracle (kernel és felület) Sybase (op.-rendszerek, adatbázis-kezelő, parancsértelmező, gazdanyelvek) Windows, Jet, Access Windows, Microsoft SQL server (Sybase alapú), Powerbuilder 1.24 Felhasználók A felhasználás módjától függő csoportok: • Alkalmazási programozók: A megadott igények alapján készítik el az alkalmazás programjait. • Nem programozó alkalmazók: A megírt programok alapján léphetnek kapcsolatba a rendszerrel. A jogkörben, illetve a

hozzáférésben viszonylag bővek a lehetőségeik • Menü alapján dolgozó felhasználók: A rendszeres tevékenység végzői. Előre programozott kérdésekkel és igényekkel fordulhatnak a rendszerhez Koczka György, 2007 59 INFORMÁCIÓS RENDSZEREK 2. Adatbázisok 2.1 Adatbázis Egy adatfeldolgozói környezetben lévő hasznos adatok és kapcsolatok összessége. Tágabb értelemben két típust különböztetünk meg. • Tény-adatbázis: Objektumok tulajdonságait tartalmazza. • Dokumentum típusú adatbázis: Szövegszerű leírások alkotják. A gyakorlatban a tény-adatbázist szokás adatbázisnak tekinteni. A tény-adatbázisnak biztosítania kell: • igények hatékony kielégítését • adatok közötti kapcsolatok ábrázolását • redundancia-mentességet és konzisztenciát • adatvédelmet • helyreállíthatóságot • többfelhasználós rendszereknél az adatok egyidejű elérhetőségét 2.2 Adatmodell Az

adatbázis-kezelő rendszerek adatmodellekre épülnek. Az adatmodell egyedek, tulajdonságok, kapcsolatok halmaza. Absztrakt módon tükrözi az objektumok információegyedeit és kapcsolatait. Típusai: • Hierarchikus – fa Fa szerkezetű gráffal szemléltethető, ahol a csomópontok az egyedek, az ágak a kapcsolatok. Az alá- és fölérendeltségű adatstruktúrák kezelésére a legalkalmasabb A kapcsolatok 1:1 illetve 1:N jellegűek • Hálós – gráf Koczka György, 2007 60 INFORMÁCIÓS RENDSZEREK Általánosított hierarchikus szerkezet, egy elemnek több szülője lehet. A kapcsolatok M:N jellegűek. • Relációs - az adatokat logikailag relációkban, szemléletesen tekintve táblázatokban ábrázoljuk. A kapcsolatok az egyedek tulajdonságain keresztül épülnek fel 2.3 Adattárolási eszközök Összetett adattípusok és adatszerkezetek összevetése adattárolási szempontból: Típus Tárolási hely Tárolási mód Adatelérés Elemek

típusa tömb memória folytonos direkt egyforma rekord memória folytonos direkt különböző file adattároló operációs rend- direkt, szek- egyforma, szer definiált venciális lönböző kapcsolt lista memória, adat- elosztott tároló 2.4 szekvenciális egyforma, lönböző kükü- Adatbázis-kezelés jellemző műveletei Karbantartás: rögzítés, módosítás, törlés. Informális igények: keresés, kigyűjtés. Rendezés: fizikai, logikai módon. 2.5 Adatbázis védelem Az információs rendszer legértékesebb és legsérülékenyebb része általában az adat. Ezért kiemelten fontos szempont a védelem és a helyreállíthatóság. Adatvesztési okok: Koczka György, 2007 61 INFORMÁCIÓS RENDSZEREK • Adatvesztés fizikai okból - hardver hiba esetén. Tükrözések, mentések, tranzakciós szemlélet. • Adatvesztés logikai okból - szoftver, felhasználói hiba okán. Mentések. • Külső okból – illetéktelen felhasználók

betörésénél. Jelszó beállítása. Felhasználói szintű védelem. Irodalom Quittner Pál: Adatbázis-kezelés a gyakorlatban, Akadémia Kiadó, 1993 Koczka György, 2007 62 RELÁCIÓS ADATBÁZISOK 14. előadás: Relációs adatbázisok Tartalom: 1.Relációs adatbázisok; 11Tábla; 12Kulcs; 13Normalizálás; 1311NF; 1.32 2NF; 1333NF; 134 Magasabb NF; 14Relációs műveletek; 2SQL nyelv; 2.1Az SQL szabvány; 22Adattípusok; 23 Az utasítások csoportosítása; 2.31Adatleíró utasítások; 232Adatkezelő utasítások; 233Vezérlő utasítások; 2.34Egyéb utasítások 1. Relációs adatbázisok A reláció azt fejezi ki, hogy halmazok, vagy bizonyos elemeik között valamilyen összefüggés áll fenn. Reláció az aritmetikai relációk szűkebb csoportja is: például a<b. A relációs adatbázisoknál az egyedek tulajdonságai kapják a hangsúlyt. Szemléletesen táblákba foglalt adataik és azok kapcsolatai adják ki az adatbázist. A relációk az az adatok

logikai reprezentációi. Az adatstruktúrát a tárolási és elérési módtól függetlenül írják le. 1.1 Tábla A táblának sorai és oszlopai vannak. Egy sor, egy egyednek felel meg Az oszlopok nevei alkotják a reláció fejlécét. Az oszlopokban lévő adatok az egyed tulajdonságai Ahhoz, hogy egy táblázat valóban egy relációs adatbázis táblája lehessen a következő feltételeknek kell eleget tennie: • A sorokban lévő oszlopok száma azonos. • Minden oszlopnak egyedi neve van. • A sorok cellái csak egy értéket vehetnek fel. • A sorok egyértelműen azonosíthatók • A sorok és oszlopok sorrendje nincs megkötve. Koczka György, 2007 63 RELÁCIÓS ADATBÁZISOK 1.2 Kulcs Egy tábla bármely sorához létezik legalább egy oszlopkombináció, mely azt azonosítja és meghatározza a többi értéket. Ezeket azonosító, a többit leíró tulajdonságnak nevezzük Elsődleges kulcsnak nevezik ezt a kombinációt. Egyszerű a kulcs, ha

az egy tulajdonság. Összetett kulcs, amennyiben több tulajdonságból tevődik össze. Alternatív kulcs, ha egyéb tulajdonságcsoportból is kialakítható sorazonosító. Idegen kulcs a reláció azon tulajdonságcsoportja, mely egy másik reláció egyedére hivatkozik. 1.3 Normalizálás Tervezésnél a cél, hogy relációink redundancia-mentesek legyenek. Ehhez bizonyos feltételeket kell teljesíteni A feltételek folyamatos kielégítését normalizációs folyamatnak nevezzük. Az állapotokat növekvő számmal jelölik, és normál formának hívják (NF) A funkcionális függőség formálisan reprezentálja az egyértékű tényeket. Azt mutatja, hogy egy tulajdonság egy vagy több másikat egyértelműen meghatároz. 1.31 1NF Egy táblázat adatai 1NF-ban vannak, ha: - kielégíti az előző tábla definíciót - minden sorhoz tartozik egyedi kulcs, melytől a többi tulajdonság funkcionálisan függ - kulcs tulajdonság nem hiányozhat 1.32 2NF - 2NF-ban van, ha

1NF és a nem kulcs tulajdonságok teljesen függnek az elsődleges kulcstól. 1.33 3NF - 2NF-ban van és a funkcionális függés csak az elsődleges kulcsokból indulhat ki. 1.34 Magasabb NF Gyakorlatban elegendő az adatokat a 3NF-ban esetleg a hatékonyság érdekében alacsonyabb formában elhelyezni. Bonyolult helyzetben, vagy elméleti szinten további finomításokra is szükség lehet. Ezeket 4NF és 5NF-nak nevezi az elmélet Megjegyzés: a magasabb NF-ra törekvés többségében elméleti jellegű és általában a hatékonyság rovására megy. Koczka György, 2007 64 RELÁCIÓS ADATBÁZISOK Példa: Adatbázis tervezése, normalizációs folyamat. Egy cég dolgozóinak, fizetésének nyilvántartásához szükséges adatok: Név Cím Beosztás Osztály Főnök Pénz Dátum Azonosító: Név, Dátum A táblázat 1NF-ban van. Problémák: adatredundancia, törlésnél egyéb információk elvesztése. Név Cím Beosztás Osztály Főnök Azonosító: Név

Név Pénz Dátum Azonosító: Név, Dátum, Idegen kulcs: Név A táblázat 2NF-ban van. Problémák: kisebb adatredundancia, új osztály csak új dolgozóval lehetséges (tranzitív függőség megléte). Név Cím Beosztás Osztály Azonosító: Név, Idegen kulcs: Osztály Osztály Főnök Azonosító: Osztály Név Pénz Dátum Azonosító: Név, Dátum, Idegen kulcs: Név A táblázat 3NF-ban van. Megjegyzés: az adatbázis két törzstáblából és egy forgalmi táblából áll. 1.4 Relációs műveletek Adatbázison végzendő feladatok végeredményben relációkon elvégzendő műveletekre vezethetők vissza. Jellemző, gyakran használt műveletek: - korlátozás: feltételek megfogalmazásával a sorok számának csökkentése - vetület: kiválasztással az oszlopok számának csökkentése Koczka György, 2007 65 RELÁCIÓS ADATBÁZISOK - keresztszorzat: m+n fokszámú és M*N sorú új reláció metszet: két reláció azonos sorai különbség: az

első tábla azon sorai, melyek nincsenek a másodikban unió: két reláció összes sora, az azonosak egyszer csoportképzés: a reláció azonos tulajdonsággal bíró csoportjaira adunk meg, vagy képezünk jellemző értéket 2. SQL nyelv SQL a Structured Query Language rövidítése. Valójában több ennél, egy teljes relációs adatbázis-kezelő nyelv. 2.1 Az SQL szabvány Sikerének alapja, hogy kifejlesztésében a számítástechnika gyakorlati szakemberei és elméleti tudósai lényegében közös úton jártak. A nyolcvanas évek végére már megjelent az első szabványa. Manapság a legtöbb magasszintű nyelv lehetőséget ad az SQL utasítások beépítésére Formalizmusát tekintve a nem-procedurális nyelvek közé tartozik. A felhasználó csak azt mondja meg mit akar, hogy ez hogyan történjen azt a fordító, vagy a parancsértelmező szabja meg. 2.2 Adattípusok Ezen típusokkal írhatjuk elő a rendszer adatainak tárolási, illetve belső ábrázolási

módját. Jellemző gyűjtő típusok: numerikus, szöveges, dátum jellegű, logikai Ezek egyszerű típusok, illetve kifelé egyszerű típust mutató objektumok. 2.3 Az utasítások csoportosítása Az SQL utasításokat négy nagy csoportra osztjuk: • adatleíró utasítások, • adatkezelő utasítások • vezérlő utasítások, • egyéb utasítások. 2.31 Adatleíró utasítások Ide tartoznak az adatbázis szerkezetét leíró és módosító utasítások. Legfontosabbak: CREATE – tábla, nézet és index létrehozása DROP – megszüntet Koczka György, 2007 66 RELÁCIÓS ADATBÁZISOK ALTER – módosít 2.32 Adatkezelő utasítások A meglévő táblákból választanak ki, törölnek, módosítanak, illesztenek be sorokat. • SELECT – kiválaszt – utasítás alapformája: SELECT miként, mit FROM honnan WHERE kiválasztási feltétel GROUP BY csoportosítás HAVING csoport-kiválasztási feltétel ORDER BY oszlopnév ASC/DESC oszlopfüggvények: AVG,

MAX, MIN, SUM, COUNT kiválasztási feltételek leírása: összehasonlítás, BETWEEN, IN, LIKE • DELETE – töröl: DELETE FROM honnan WHERE kiválasztási feltétel • UPDATE – módosít: UPDATE hol SET értékadási sorozat WHERE kiválasztási feltétel • INSERT – bővít INSERT INTO hova (oszlopnevek sorozata) VALUES (értékek sorozata) 2.33 Vezérlő utasítások Engedélyezés, tranzakciók vezérlése. GRAND – jogosultság BEGIN – tranzakció kezdés COMMIT – véglegesít ROLLBACK – visszaállít 2.34 Egyéb utasítások Ezen utasítások erősen rendszer függőek. Ide sorolhatók az operátori parancsok is SHOW – adminisztrátori információ mutató Koczka György, 2007 67 RELÁCIÓS ADATBÁZISOK HELP – segítség CANCEL – megszakít Példa: Az 1.3-as fejezet 3NF tábláiból készítsünk lekérdezéseket Listázzuk a műszaki osztály dolgozóit névsor szerint, beosztásukkal (relációs műveletek korlátozás, vetület): SELECT

Név,Beosztás FROM Dolgozók WHERE Osztály="Műszaki" ODER BY Név Listázzuk a cég osztályait, dolgozóinak számával (csoportképzés számlálással): SELECT Osztály, count(Név) FROM Dolgozók GROP BY Osztály Listázzuk a műszaki osztály dolgozóit főnökük nevével (keresztszorzat, korlátozás): SELECT Név,Főnök FROM Dolgozók,Osztályok WHERE Dolgozók.Osztály=OsztályokOsztály Módosítsuk a műszaki osztály vezetőjét (korlátozás): UPDATE Osztályok SET Főnök="Vékony" WHERE Osztály="Műszaki" Figyeljük meg, hogy itt egyetlen rekordban módosítunk. Az 1NF-ás táblában is működik a parancs, de több rekord változik. Irodalom Quittner Pál: Adatbázis-kezelés a gyakorlatban, Akadémia Kiadó, 1993 Stolniczki Gyula: SQL kézikönyv, ComputerBooks, 1996 Koczka György, 2007 68