Information Technology | Higher education » Informatika alkalmazása szigorlati tételek, 2004

Informatika alkalmazása szigorlati tételek Budapest 2004 Tartalomjegyzék 1. TÉTEL 5 A SZÁMÍTÓGÉPEK ISKOLAI ALKALMAZÁSI TERÜLETEI. 5 A SZÁMÍTÓGÉPES SZIMULÁCIÓ ALAPJAI . 6 VÉLETLENSZÁMOK . 11 VÉLETLEN-ESEMÉNYEK . 12 2. TÉTEL 16 A KÍSÉRLETKIÉRTÉKELÉS MÓDSZEREI . 16 STATISZTIKAI BECSLÉSEK . 17 HIBÁS ADATOK KISZŰRÉSE . 18 OSZLOP- ÉS KÖRDIAGRAMOK . 18 3. TÉTEL 20 SZÁMÍTÓGÉPES SZIMULÁCIÓ . 20 SZIMULÁCIÓS PROGRAMOK FELÉPÍTÉSE, KERETMODELLEK . 21 ELEMI MODELLEK, SZEREPÜK . 22 ELEMI NÖVEKEDÉSI MODELLEK . 24 SEJTAUTOMATA ELVŰ KERETMODELL. 28 4. TÉTEL 29 SZIMULÁCIÓS MODELLEK A FIZIKÁBAN . 29 Gázmodellek . 29 Folyadékmodellek . 31 SZIMULÁCIÓ A KÉMIÁBAN . 33 Kémiai reakciók, reakciórendszerek . 33 Mintázatképződés . 36 METEOROLÓGIAI (FELHŐFIZIKAI) MODELLEK . 37 5. TÉTEL 40 SZIMULÁCIÓS MODELLEK A BIOLÓGIÁBAN . 40 Populációdinamika . 40 Demográfia . 40 Populációgenetika . 42 Ökológia . 48 6. TÉTEL 51

NAGYPONTOSSÁGÚ ARITMETIKA . 51 Egész számok . 51 Racionális számok . 52 Fixpontos valós számok . 53 Lebegőpontos számok . 53 SZÁMRENDSZEREK KÖZÖTTI KONVERZIÓ: X A X B . 53 NEVEZETES SZÁMOK KÖZELÍTÉSE . 54 KOMBINATORIKAI ALGORITMUSOK . 54 Az összes lehetőség előállítása . 55 Az i. előállítása 55 Egy véletlen előállítása. 55 FÜGGVÉNYÁBRÁZOLÁS . 55 Egyváltozós függvények ábrázolása . 55 Kétváltozós függvények ábrázolása . 56 2 7. TÉTEL 59 GEOMETRIAI ÉS RASZTERES KÉPEK ELEMEI . 59 Raszteres kódolás . 59 Geometriai kódolás . 59 Képelemek és attribútumok . 60 LOGIKAI MŰVELETEK AZ ÚJ KÉPELEM ÉS A MEGLÉVŐ KÉP KÖZÖTT . 61 GRAFIKAI INPUT ÉS OUTPUT PERIFÉRIÁK . 61 RAJZBEVITEL . 62 RAJZTÁROLÁS . 62 KOORDINÁTARENDSZEREK ÉS TRANSZFORMÁCIÓIK . 62 8. TÉTEL 63 RASZTERGRAFIKAI ALAPALGORITMUSOK . 63 Nagyítás . 63 Kicsinyítés . 63 Logikai műveletek . 64 Megjelenítés. 64 Adott tulajdonságú elemek kiemelése

. 65 TERÜLETKITÖLTÉSI ALGORITMUSOK. 66 9. TÉTEL 68 KÉPKIVÁGÁS . 68 Egyenes szakaszok vágása a síkban . 68 Sokszögvonal vágása a síkban. 70 Sokszöglemezek vágása a síkban . 70 Raszteres pontlapok vágása. 70 Feliratok vágása . 70 Térbeli vágás . 71 RASZTER-KONVERZIÓ . 71 Egyenes szakaszok raszter-konverziója . 71 Kör raszter-konverziója . 72 10. TÉTEL 74 HOMOGÉN LINEÁRIS TRANSZFORMÁCIÓK . 74 11. TÉTEL 78 KOORDINÁTARENDSZEREK . 78 A KÖZÉPPONTOS ÉS PÁRHUZAMOS VETÍTÉS. 79 A középpontos vetítés . 80 A párhuzamos vetítés . 83 Síkvetületek osztályozása . 83 12. TÉTEL 84 LÁTHATÓSÁG . 84 ÁRNYALÁS . 85 SZÍNMODELLEK . 86 Az RGB színmodell . 86 A CMY színmodell . 86 A HLS színérzet modell . 86 VRML NYELV . 87 Geometriai formák és szövegek . 87 Geometriai transzformációk . 88 Színek és formák . 88 Fények és megvilágítások, kamerák . 88 Csoportnode-ok . 89 Hálózati illesztés . 89 3 13. TÉTEL 90 AZ ADATBÁZIS

FOGALMA. 90 ADATBÁZISOKKAL KAPCSOLATOS FOGALMAK. 90 Adatmodell. 90 Szintek. 90 Adatfüggetlenség . 91 Nyelvek . 91 14. TÉTEL 92 ADATBÁZIS-KEZELŐ RENDSZEREK TULAJDONSÁGAI, FOGALMAK . 92 15. TÉTEL 94 MODELLEZÉSI ALAPFOGALMAK . 94 TÁRGY-KAPCSOLAT MODELL ÉS DIAGRAM . 95 TÁRGY-KAPCSOLAT MODELL LEKÉPEZÉSE RELÁCIÓS MODELLRE. 96 16. TÉTEL 98 RELÁCIÓS ALGEBRA . 98 Relációs műveletek . 98 TELJES, TÖBB MINT TELJES NYELVEK . 99 17. TÉTEL 100 RELÁCIÓS ADATMODELL . 100 FUNKCIONÁLIS FÜGGŐSÉG . 100 NORMÁLFORMÁK . 100 18. TÉTEL 102 SQL . 102 4 1. tétel A számítógépek iskolai alkalmazási területei Az oktatóprogramok több nagy kategóriába sorolhatók be: - Számítások elvégzése. - Egyéb oktatási segédprogramok. - Tesztek elvégzése és kiértékelése. - Ismeretközlő programok. - Egyéni gyakoroltatás. - Információtároló és visszakereső programok. - Oktatásszervező programok. - Logikai játékok. - Számítógépes mérés és

vezérlés. - Számítógépes szimuláció. Számítások elvégzése Ha a számítás menete az érdekes, akkor nem szabad számítógépet használni. Csak bonyolult számítási rendszer esetén lehet szerepe a számítógépnek. Hangsúlyozandó hogy a számítógépnek itt erősen segédeszköz szerepet kell játszania. Egyéb oktatási segédprogramok Ide a számításokat végzőkhöz hasonló funkciójú programokat soroljuk. Ilyen például versek hangtani, ritmikai elemzését segítő program, szövegek gyakorisági vizsgálata, kottarajzolás billentyűzeten lejátszott zenéhez, stb. Ezek hasznos eszközök, de csupán miattuk nem lenne sok értelme a számítógépes programnak. Tesztek elvégzése és kiértékelése A számítógép egyik legsematikusabb felhasználási területe. A hagyományos tesztekhez képest gyorsabb a kiértékelés, míg a kitöltés nem. Egyetlen programmal elkészíthető az összes lehetséges teszt, ami lehet feleletválasztásos és

feleletalkotásos. Ez a program a tanárnak kell, míg egy másik a diáknak, mely segítségével kitölti a tesztet. Ismeretközlő programok Több jelentős érv is szól ellene. Egyrészt kétséges a pedagógiai haszna, másrészt a jelenlegi számítógépes kiépítettség nem teszi lehetővé a szükséges mennyiségű anyag tárolását, kezelését. Egyéni gyakoroltatás A tananyagból kiemelhetők olyan részek, amelyek alkalmasak arra, hogy a számítógép segítségével a tanuló alaposan begyakorolja. Például idegen nyelv szavainak gyakorlása, idegen nyelvű szabályok gyakorlása, elválasztási szabályok gyakorlása, stb. Információtároló és visszakereső programok Néhány egyszerű példa (növényhatározó, telefonkönyv) elkészítése alapján egyértelművé válhat, hogy ilyen feladatok megoldására csak olyan rendszereken van reális lehetőség, amelyek legalább mágneslemezt tartalmaznak, lehetővé téve így nagy mennyiségű adat tárolását

és gyors visszakeresését. 5 Oktatásszervező programok Kétségtelen haszna lenne a tanároknak adminisztratív munkáját segítő programoknak is (órarend készítés támogatása, kimutatások készítése), de ez elképzelhetetlen nyomtató és megbízható háttértár nélkül. Játékok A logikai játékok a kezdeti érdeklődés felkeltésén túl a programozás tanulás időszakában hasznosak. A tanulók szívesen, nagy lelkesedéssel írnak játékprogramokat, s közben sok programozási ismeretet szereznek. Az értelmes játékprogramok írása ráadásul precíz logikai készséget is igényel. A szituációs játékok, összerakó játékok a nyelvek tanulásában játszhatnak fontos szerepet. Számítógépes mérés és vezérlés Ez a számítógép használat egyik leglényegesebb területe, de sajnos még nem állnak rendelkezésre megfelelő eszközök a jelenlegi iskola számítógépekhez. A valódi mérések legtöbbjének elvégeztetéséhez nem

megfelelő a magas szintű nyelvű programok sebessége, ezért általában gépi kódú programokat kell készíteni. A mérési eredmények kiértékeléséhez, az eredmények ábrázolásához már elegendő a magas szintű nyelvű programok. Számítógépes szimuláció A számítógépes szimuláció valamilyen természeti, társadalmi esemény számítógépes lejátszása. A számítógépes szimuláció alapjai Modellezésen a modell elkészítésének folyamatát, szimuláción a modell használatának folyamatát értjük. Általános szempontokból feladatmegoldó tevékenységünket három részre bonthatjuk: - A feladat megfogalmazása. - A megoldás elkészítése. - Az eredmények értékelése. A feladat megfogalmazása Ez nagyon fontos tevékenység. Ez az, amely meghatározza további tevékenységeink célját, illetve döntően befolyásolja azoknak eredményességét, hatékonyságát. Meg kell adni azt a rendszert, amelynek vizsgálatával foglalkozunk, azokat a

szempontokat, amelyeket fontosnak tartunk, és a várható eredményeket. A feladat megoldása Feladatok megoldásának módszere: - Megfigyelés. - Hipotéziskészítés. - Modellkészítés. - Kísérletek a modellel. - Törvény (szabály) alkotás. E megismerési módszer szerint a valós rendszer helyett annak csak egy mását, hozzá valamennyire hasonló rendszert vizsgálunk, és ennek viselkedéséből következtetünk az eredeti rendszer viselkedésére. 6 Tevékenységünket a következő tevékenységekből álló folyamat jellemzi: - Megfigyelés. - Modellezés. - Programozás. - Szimuláció. - Összevetés. - Eredmények értékelése. Általános értelemben szokták ezt az egész folyamatot is szimulációnak nevezni. Mielőtt részletesebben megvizsgálnánk az egyes tevékenységeket, tekintsük át a modellek lehetséges osztályozásait. A modellek osztályozása A modelleket sokféle szempont szerint csoportosíthatjuk: - A modell jellege szerint: - Anyagi. -

Gondolati. - A modellezési szempont szerint: - Szerkezeti modellezés. - Működési modellezés. - Formai modellezés. - A változók időfüggősége szerint: - Időfüggő modell: Az egyes eseményei nem ismételhetők meg. - Időfüggetlen modell: Eseményei általában megismételhetők. - Az eredményváltozók függősége szerint: - Determinisztikus modell: A bemenete és a kezdőállapota egyértelműen meghatározza az eredményt. - Sztochasztikus modell: A bemenete és a kezdőállapota csupán az eredmény lehetséges értékeinek eloszlását határozza meg. Megfigyelés A megfigyelés lényege a valós rendszerből azon adatok megszerzése, összefüggések felismerése, amelyek a rendszerre a vizsgálat szempontjából jellemzőek. A megfigyeléseket úgy kell végezni, hogy azok lehetőleg ne befolyásolják a vizsgált rendszert. Mintavételi módszereinket két csoportra oszthatjuk: - A megfigyelt rendszernek véges sok állapota van. - A megfigyelt rendszernek

végtelen sok állapota van. Ha a megfigyelt rendszernek véges sok állapota van, akkor úgy kell mintát választani belőle, hogy mindegyik állapot azonos valószínűséggel kerüljön bele a mintába. A mintavétel lehet: - Egyszerű véletlen mintavétel: Adott N darab lehetséges elem. Ezekből véletlenszerűen válasszunk ki M darabot. A módszer nagy problémája, hogy előre nagyon ritkán tudjuk megmondani, hogy hány megfigyelésre van szükségünk. - Kétfokozatú mintavétel: Adott N darab lehetséges elem, ezekből véletlenszerűen válasszunk ki M1 darabot. Ha ebből kielégítő eredményt kapunk, akkor készen vagyunk Ha nem, akkor válasszunk ki további M2 darabot, s az így kapott M1+M2 elemű mintát használjuk a továbbiakban. Ez a módszer kiküszöböli az előbbi hibát, viszont sokszor nem gazdaságos. 7 - - Sorozatos vagy szekvenciális mintavétel: Adott N darab lehetséges elem, addig vegyünk egyesével új mintaelemet, amíg nem kapunk

kielégítő eredményt. Ez a módszer az előbbi gondolat szélsőséges esete, így ennek segítségével lehet a legkisebb elemszámú mintát kiválasztani, és ha egy megfigyelés költséges, akkor ez valóban nagyon gazdaságos módszer. Csoportos mintavétel: A csoportos mintavétel lényege, hogy a megfigyelt rendszerünkből először nem mintaelemeket, hanem mintacsoportokat választunk. Ezután vagy a kiválasztott mintacsoportok összes elemét mintaelemnek tekintjük, vagy a mintacsoportokból újabb választással mintaelemeket határozunk meg. Akkor alkalmazható, ha a megfigyelt rendszer részrendszerekből áll. Lehetséges esetei: - Egylépéses mintavétel: Kiválasztunk véletlenszerűen egy vagy több csoportot, majd ezek minden elemét belevesszük a mintába. Ezt a módszert gyakran használják minőségellenőrzésnél. - Kétlépéses mintavétel: Kiválasztunk véletlenszerűen egy vagy több csoportot, vagy esetleg az összeset, majd mindegyik csoportból

választunk véletlenszerűen egy vagy több elemet. A csoportokból való választásoknak egymástól függetleneknek kell lenniük. Modellezés A modell önmagában sohasem lehet a modellezés célja, hanem mindig a modellezett vizsgálatára kell, hogy alkalmas legyen, ezért a modellnek mindig működőképesnek kell lennie. Mielőtt a következő tevékenységbe kezdenénk, meg kell győződni arról, hogy a modell megfelel céljainknak. Ha valamilyen matematikai módszert használtunk, akkor a feladat matematikai megoldását, esetleg részmegoldását elvégezve meg kell vizsgálnunk, hogy a várt eredményt kapjuk-e. Ha a modellünk szemléltetési céllal készül, akkor a szemléltetés érdekében megengedhetők a modell belső felépítésének olyan kapcsolatok, amelyek a valódi jelenségben esetleg ilyen formán biztosan nincsenek, mert ilyenkor csak az eredmény a fontos. Ha a modellünk elemzés, akkor a modellt a valós rendszerre vonatkozó feltevéseink alapján

kell elkészíteni, és ilyenkor óvakodni kell a káros analógiáktól. Modellkészítéskor nagyon sokszor felmerülő probléma megfigyeléseink hiányossága, pontatlansága, sokszor nem kellő céltudatossága. Ez minden esetben elkerülhetetlen akadályt jelent. Ha ezekről a hiányosságokról, pontatlanságokról nem veszünk tudomást, akkor nagy kárt okozhatunk magunknak, s ha a modellel nem csak szemléltetési céljaink vannak, akkor másoknak is. A modelltől a következő tulajdonságokat várjuk el: - Elfogadhatóság: Egy modellt elfogadhatónak nevezünk, ha a létrehozásához megvizsgált eseményeket reprodukálni lehet vele. Ez alapvető követelmény, ha ez nem teljesül, akkor a modellben komoly hiba van. - Alkalmazhatóság: Egy modellt alkalmazhatónak nevezünk, ha használatából következtethetünk olyan, a valós rendszerben lezajló eseményekre, amelyeket korábban megfigyeléseinkkel nem tapasztaltunk. - Használhatóság: Egy modellt használhatónak

nevezünk, ha a szimuláció paramétereit a természetes jelenség mérhető jellemzőiből kevés és egyszerű transzformáció segítségével kaphatjuk, illetve eredményeiből közvetlenül következtethetünk a jelenség valós jellemzőire. - Teljesség: A modell csak a lehetséges világ egy megadott tartományában használható. Teljességnek nevezzük e tartomány valamilyen mértékét. A teljesség megfogalmazható egyszerű esetben a figyelembe vehető paraméterek számával és értelmezési tartományával. 8 Programozás A programozás jelen esetben az úgynevezett számítógépes modell létrehozását jelenti. Az első probléma, amit figyelembe kell venni a számítógép memóriakapacitásának véges volta. Ez nagyobb szimulációs programoknál komoly nehézséget okozhat A helyfoglalás csökkentését két úton érhetjük el, két dologra kell figyelnünk: A szimulációs program (lokális) helytakarékossága. A modell (globális) helytakarékossága.

Az első esetben a programon memóriaigényt csökkentő transzformációkat kell végezni. Ehhez ismerni kell egyrészt az adott programozási nyelv jellemzőit, másrészt pedig a program struktúráját. A globális hatékonyság eléréséhez a modellen kell transzformációkat végeznünk A második, problémát okozó tényező, a számítógép sebessége. A szimulációs programnak véges, kivárható időn belül eredményt kell produkálnia, így amikor egy szimulációs program lassúnak bizonyul, akkor meg kell vizsgálnunk gyorsításának lehetőségeit. Hatékonyságról is két szempont szerint beszélhetünk: A szimulációs program (lokális) hatékonysága. A modell (globális) hatékonysága. A lokális hatékonyság eléréséhez újra a programozási nyelv és a programszerkezet ismerete szükséges. A globális hatékonyság növeléséhez a modellt kell átalakítanunk A harmadik tényező a számítógép pontossága lehet. Ez különösen analitikus

megfogalmazású modelleknél okozhat gondot. Amennyiben szimulációs programoknál ilyen előfordul, úgy vagy nagy pontosságú aritmetikai műveletekre van szükségünk, vagy pedig korrekciós műveleteket kell bevezetnünk. Szimuláció – kísérlettervezés Amennyiben rendelkezésünkre áll a szimulációs program, elkezdhetjük a vele való kísérletezést. A kísérletezést meg kell tervezni A legegyszerűbb esetben a szimuláció eredménye egy paramétertől függ. Annyi kísérletet kell végezni, amely már statisztikai módszerekkel értékelhető. Ha ismerjük a paraméterek kritikus értékeit, akkor ezek körüli értékekkel is el kell végezni a szimulációt. Ha több paraméteres modellt készítettünk, akkor bonyolultabb a helyzet. Követendő módszer lehet az, hogy az egyik paraméter értékét rögzítve, a másik paraméter hatását vizsgáljuk. Ezután az első paramétert más értéken rögzítve újra végrehajtjuk a fenti tevékenységet. Ha így

elég információt szereztünk, akkor megpróbálhatjuk a két paraméter szerepét felcserélni. Lehet még próbálkozni olyan módszerrel, hogy a két paramétert változtatjuk úgy, hogy az egyik a másiknak valamilyen függvénye legyen. Összevetés Az összevetés célja annak megállapítása, hogy a modellünk megfelel-e a megfigyelt adatoknak. Ez biztosítja ugyanis, hogy jogunk van a szimulált adatokból következtetni a valós rendszer működésére. Módszerünk az, hogy a kísérletet elvégezzük néhányszor a valós rendszerben, azzal a céllal, hogy a modellt létre tudjuk hozni, illetve helyességét be tudjuk látni, majd a valós rendszerrel kapcsolatos kérdéseinkre a számítógépes modellel kapcsolatos kísérletekből keresünk választ. 9 Ha az összevetésből azt az eredményt kapjuk, hogy a modell nem felel meg a valóságnak, annak három oka lehet: - Hibás a modell. - Hibásan értelmezzük a szimuláció eredményeit. - Nem felel meg a

valóság a modellnek, bár a modell jó. Gyakran vezet hibás értelmezésre két tényező: - Ha nem vesszük figyelembe az induló feltételek hatását. - Ha nem vesszük figyelembe a véletlen ingadozások hatását. Az első tényezőből fakadó hibák kiküszöbölésére néha jó lehet az a módszer, ha elég hosszú futási időt vizsgálunk, de ez nem megoldás abban az esetben, ha a kezdőállapot választásnak lényeges szerepe van a rendszerben, illetve nagyon nehéz megmondani, hogy mennyi az az elég hosszú idő. A második tényezőből fakadó hibák kiküszöbölésére jó módszer sok kísérlet elvégzése azonos körülmények között, és a kapott eredmények átlagának felhasználása. Eredmények értékelése Adott egy N elemű minta. A mért jellemző értékei egy tömbben vannak Határozzuk meg a jellemző tapasztalati várható értékét és szórásnégyzetét. A következő képletek alapján számolunk: - n Várható érték: m(ψ ) = (∑ψ )

/ N . i i =1 - n Szórásnégyzet: σ (ψ ) = (∑ (ψ − m(ψ )) 2 ) / N . 2 i =1 i Jelölések: - Ω : valószínűségi mező, melyekből mintaelemeket választunk. - ψ : Ω -án értelmezett valós értékű függvény. - ψ i : ψ értéke az i. helyen - m(ψ ) : ψ várható értéke. - σ (ψ ) : ψ szórása. Még több információ áll a rendelkezésünkre, ha meg tudjuk adni a konfidencia intervallumot, vagyis az elméleti várható értéket tartalmazó intervallumot. Adott két egyaránt N elemű minta. A mért jellemzők tömbökben vannak tárolva Ha meg szeretnénk adni a mért jellemzők között lévő viszonyt, akkor ezt nevezzük korrelációs együttható számításának. Gyakori feladat sokaság eloszlásának vizsgálata, azaz kíváncsiak vagyunk arra, hogy a vett mintaelemek mennyire felelnek meg az általunk várt elméleti értékeknek. Ehhez a lehetséges értékeket nem túl sok intervallumra osztjuk, majd megvizsgáljuk, hogy melyikbe mennyi

elem esik. Így egy diszkrét eloszlást definiálunk, ami az úgynevezett oszlopdiagrammal ábrázolható. Ezt az ábrát nevezzük hisztogramnak Vizsgálhatjuk a regressziót. A regressziós görbe paramétereinek meghatározása nem más, mint adott pontokon ismert függvény közelítése valamilyen fokszámú polinommal. Lineáris regresszió esetén egy elsőfokú polinomot kell előállítanunk. 10 Gyakran előforduló igény az, hogy adott pontokban ismert függvény tulajdonságait vizsgáljuk. Ehhez meg kell határoznunk egy olyan függvényt, amely közel azonos tulajdonságú az eredeti függvénnyel. Ezután ennek tulajdonságaiból következtethetünk az eredeti függvény jellemzőire. Az ilyen jellegű feladatok megoldását függvényközelítésnek nevezzük. Véletlenszámok A számítógépnél nincsenek véletlenszámok. Egy olyan számalgoritmust keresünk, amely véletlen események gyanánt véletlenszámot eredményez. A véletlentől elvárt

tulajdonságok - A véletlenszerű kísérletektől elvárjuk, hogy minden lehetséges kimenetele előbb-utóbb bekövetkezzék. - Az eseményre vonatkozó kísérleteinket jellemezze az is, hogy addigi bekövetkezésekből ne következtethessünk a továbbiak kimeneteleire. Véletlenszám előállítása két lépésből áll - Kezdő érték meghatározása. - Következő véletlenszám generálása függvény segítségével. Módszerek - Négyzetközép módszer: Induljunk ki egy 2*k jegyű számból, ez lesz a kezdő érték. Emeljük négyzetre, majd az így keletkezett 4*k jegyű szám középső 2k jegyét tekintsük az első véletlenszámnak. Ebből a számból állítjuk elő a fenti módon a másodikat, és így tovább. Problémája ennek a módszernek, hogy észrevehetően periodikus - Szorzatközép módszer: Induljunk ki egy x 0 kezdőértékből, melyet vehetünk a számítógép órájából, és két 2*k jegyű számból (legyen A és B). Az A*x 0 +B képlettel

kapott 4*k jegyű szám középső 2k jegyét tekintjük az első véletlenszámnak. Ebből a számból állítjuk elő a fenti módon a másodikat, és így tovább. Problémája ennek a módszernek, hogy észrevehetően periodikus, illetve gyakoriak az olyan kezdő értékek (x 0 , A, B), amelyekre elfajul a sorozat. - Lineáris kongruencia módszer: Induljunk ki egy x 0 kezdőértékből, melyet vehetünk a számítógép órájából, egy k jegyű számból (legyen A). Még egy számra szükségünk van (legyen B). Van egy M (periódus hossz) is, ami 2k alakú, ez és B közti összefüggés, hogy relatív prímek. Az ((A*x 0 +B) mod M) képlettel kapott szám az első véletlenszám. Ebből a számból számoljuk ki a fenti módon a másodikat, és így tovább. Így az összes lehetséges szám előfordul 0 és 2k között, ami nem más, mint a periódus hossza. Hibája ennek a módszernek, hogy megjósolható, ennek kiküszöbölésére a periódus hosszt növelni kellene. -

Nemlineáris kongruencia módszer: Például: x n+1 ≡A*x n x n-1 +B (M) Az ilyen típusú módszerekre nincs matematikai tétel. Ezek a módszerek bizonytalanok A periódus hossz lehet kisebb és nagyobb is M-nél. - Kombinált módszerek: Adott két P, R periódus hosszú generátor. A két generátor egy integrált rendszerben állítja elő a véletlenszámokat. Az ilyen típusú módszerekre nincs matematikai tétel. 11 Topológiája szerint a következő felosztásban csoportosíthatjuk: - Párhuzamosított: Ahol f egy egyszerű függvénye a két P véletlenszámnak. Például hol az egyiket, hol a másikat adja tovább (mintegy f összefésüli), esetleg a kettőt eggyé szuperponálja. R - Visszacsatolásos: Itt a következő véletlenszámot a két véletlenszám generátor valódi kooperációjával állítjuk elő úgy, hogy mindegyik a másik előzőjét veszi figyelembe a soron következő véletlenszám generálásához. Itt az f hasonló, mint az előző

esetben. P f R - Soros: P R Véletlenszám ellenőrzési módszerek - A generált szám számjegyeinek a gyakoriságát vizsgáljuk (számjegy gyakoriság). Az a jó, ha minden számjegy azonos gyakorisággal fordul elő. - A generált szám, vagy egy adott helyiértékű számjegy két előfordulása közötti hézagokat vizsgáljuk (hézagpróba). Ha számonként, vagy számjegyenként azonosak a hézagok, akkor jó a módszer. - Az egymás után generált számokat ábrázoljuk. Az a jó, ha egyenlő a felfelé és a lefelé tartó szakaszok hossza (futampróba). - A generált számból kiveszünk 4 darab egymás utáni számjegyet és megvizsgáljuk a számjegyek arányát (póker teszt, vagy kombinációk gyakorisága). Az a jó, ha a pókerben meghatározott valószínűségekhez tart. - A generált számban megszámoljuk számjegyenként az átlagos hosszt. Ha számjegyenként azonos az átlaghossz, akkor jó a módszer (széria vizsgálat). Véletlen-események 2 esemény

kizáró és teljes eseményrendszert alkot Például a pénzfeldobás. Mivel nem dobhatunk fejet és írást egyszerre, ezért kizáró, viszont valamelyiket biztos, hogy dobjuk, ezért teljes. Annak a valószínűsége, hogy fejet dobunk (1 esemény) P, annak, hogy írást (2. esemény) Q, ami egyenlő (1-P)-vel, mert 0≤valószínűség≤1 Eljárás Ha véletlenszám < P akkor 1. esemény Különben 2. esemény Eljárás vége 12 2 esemény kizáró és nem teljes eseményrendszert alkot Például kockadobásnál páros vagy 1-es számot dobunk. Mivel az 1-es nem páros szám, ezért kizáró, viszont dobhatjuk még a 3, 5 számokat is, amelyek nem párosak és nem egyenlők 1gyel, ezért nem teljes. Annak a valószínűsége, hogy páros számot dobunk (1 esemény) P, annak, hogy 1-est dobunk (2. esemény) Q Ha ezt a két valószínűséget összeadjuk, akkor 1nél kisebb számot kell kapnunk, vagyis P+Q<1, mert dobhatunk olyan számot is, ami nem tartozik egyik

eseményhez se, például a 3-t, 5-t. Eljárás X:=véletlenszám Ha X < P akkor 1. esemény Különben Ha X < P+Q akkor 2. esemény Eljárás vége 2 esemény nem kizáró és teljes eseményrendszert alkot Például kockadobásnál páros vagy nem 6-os számot dobunk. Mivel a 6-os páros szám, ezért nem kizáró, viszont a dobott szám valamelyik eseménynek megfelel, ezért teljes. Annak a valószínűsége, hogy páros számot dobunk (1. esemény) P, annak, hogy nem 6-ost dobunk (2 esemény) Q. Ha ezt a két valószínűséget összeadjuk, akkor 1-nél nagyobb számot kapunk, vagyis P+Q>1, mert dobhatunk olyan számot is, ami mindkét eseményt kielégíti. Eljárás X:=véletlenszám Ha X < P akkor 1. esemény Ha X > 1-Q akkor 2.esemény Eljárás vége N esemény kizáró, egyenlő valószínűséggel, és teljes eseményrendszert alkot Például kockadobásnál 1-es, 2-es, 3-as, 4-es, 5-ös vagy 6-os számot dobunk. Mivel 1≠2, 1≠3, stb., ezért kizáró,

viszont a dobott szám valamelyik eseménynek megfelel, ezért teljes, továbbá, annak a valószínűsége, hogy 1-t dobunk 1/6, hogy 2-t dobunk 1/6, stb., ezért egyenlő valószínűséggel fordul elő. Általánosan megfogalmazva: generálunk egy véletlenszámot 1 és N között, ennek vesszük az egészrészét, így megkapjuk az esemény sorszámát. N esemény kizáró, nem egyenlő valószínűséggel, és teljes eseményrendszert alkot Például kockadobásnál 1-es, 2-es, 3-as, 4-es, 5-ös vagy 6-os számot dobunk úgy, hogy a kocka egyik oldala meg van ólmozva. Mivel 1≠2, 1≠3, stb, ezért kizáró, viszont a dobott szám valamelyik eseménynek megfelel, ezért teljes, továbbá a kocka egyik oldala meg van ólmozva, ezért nem egyenlő valószínűséggel fordul elő. Az egyes események valószínűsége P1, P2, , P6. Ha a valószínűségeket összeadjuk, akkor 1-t kapunk eredményül, vagyis P1+P2++P6=1. Eljárás X:=véletlenszám H:=P(1) i:=1 Ciklus amíg X ≥ H

i:=i+1 H:=H+P(i) 13 Ciklus vége Eljárás vége Végtelensok esemény kizáró, nem egyenlő valószínűséggel, és teljes eseményrendszert alkot Például hányadik héten lesz ötösöm a lottón. Általánosan megfogalmazva: A végtelenből kellene N-t csinálni. Ennek megvalósítására azokat az eseményeket, amelyeknek nagyon kicsi a valószínűsége vonjuk össze 1 eseménnyé, így N+1 eseményünk lesz. Binomiális eloszlás Például pénzfeldobásnál N kísérletből hányszor lesz fej. Annak a valószínűsége, hogy fejet dobunk P, annak, hogy i-szer: P(i) = ( Ni ) * P (1-P) i N-i Eljárás i:=0 Ciklus j:=1-től N-ig Ha véletlenszám < P akkor i:=i+1 Ciklus vége Eljárás vége Geometriai eloszlás Például pénzfeldobásnál N kísérletből mikor dobunk először fejet. Annak a valószínűsége, hogy fejet dobunk P, annak, hogy az i. próbálkozásra: P(i) = (1-p)i-1*p Eljárás i:=1 Ciklus amíg véletlenszám ≥ P i:=i+1 Ciklus vége Eljárás

vége Poisson-eloszlás Például pénzfeldobásnál M idő alatt hányszor dobunk fejet. Annak a valószínűsége, hogy fejet dobunk P, annak, hogy i-szer: Pi * e-P P(i ) = i! Az előzőekhez hasonló algoritmust nem lehet írni. Az ilyen eloszlású eseményekre a következő feltételeknek kell teljesülnie: - Adott időtartam alatt az esemény bekövetkezés gyakoriságának eloszlása csak az időtartam nagyságától függ. - Az esemény bekövetkezéseinek gyakoriságát nem befolyásolja, hogy eddig hányszor következett be. 14 - Annak a valószínűsége elhanyagolható, hogy egy kellően rövid időtartam alatt egynél többször következzék be az esemény. Egyenletes eloszlás [A,B) intervallumon az eloszlásfüggvény: (B-A)*véletlenszám+A. Normális eloszlás Bármilyen azonos eloszlású függvény események összege a normális eloszlást közelíti. Eljárás S:=0 Ciklus i:=1-től N-ig S:=S+véletlenszám Ciklus vége Eljárás vége S közelíti a

normális eloszlású véletlenszámot, ha N ∞. χ2-eloszlás Független, azonos eloszlású valószínűségi változók négyzetösszege. F-eloszlás χ2-eloszlású valószínűségi változók hányadosa. t-eloszlás Normális és χ2-eloszlású valószínűségi változó hányadosa. 15 2. tétel A kísérletkiértékelés módszerei Megfigyelés A megfigyelés lényege a valós rendszerből azon adatok megszerzése, összefüggések felismerése, amelyek a rendszerre a vizsgálat szempontjából jellemzőek. A megfigyeléseket úgy kell végezni, hogy azok lehetőleg ne befolyásolják a vizsgált rendszert. Mintavételi módszereinket két csoportra oszthatjuk: - A megfigyelt rendszernek véges sok állapota van. - A megfigyelt rendszernek végtelen sok állapota van. Ha a megfigyelt rendszernek véges sok állapota van, akkor úgy kell mintát választani belőle, hogy mindegyik állapot azonos valószínűséggel kerüljön bele a mintába. A mintavétel lehet: -

Egyszerű véletlen mintavétel: Adott N darab lehetséges elem. Ezekből véletlenszerűen válasszunk ki M darabot. A módszer nagy problémája, hogy előre nagyon ritkán tudjuk megmondani, hogy hány megfigyelésre van szükségünk. - Kétfokozatú mintavétel: Adott N darab lehetséges elem, ezekből véletlenszerűen válasszunk ki M1 darabot. Ha ebből kielégítő eredményt kapunk, akkor készen vagyunk Ha nem, akkor válasszunk ki további M2 darabot, s az így kapott M1+M2 elemű mintát használjuk a továbbiakban. Ez a módszer kiküszöböli az előbbi hibát, viszont sokszor nem gazdaságos. - Sorozatos vagy szekvenciális mintavétel: Adott N darab lehetséges elem, addig vegyünk egyesével új mintaelemet, amíg nem kapunk kielégítő eredményt. Ez a módszer az előbbi gondolat szélsőséges esete, így ennek segítségével lehet a legkisebb elemszámú mintát kiválasztani, és ha egy megfigyelés költséges, akkor ez valóban nagyon gazdaságos módszer. -

Csoportos mintavétel: A csoportos mintavétel lényege, hogy a megfigyelt rendszerünkből először nem mintaelemeket, hanem mintacsoportokat választunk. Ezután vagy a kiválasztott mintacsoportok összes elemét mintaelemnek tekintjük, vagy a mintacsoportokból újabb választással mintaelemeket határozunk meg. Akkor alkalmazható, ha a megfigyelt rendszer részrendszerekből áll. Lehetséges esetei: - Egylépéses mintavétel: Kiválasztunk véletlenszerűen egy vagy több csoportot, majd ezek minden elemét belevesszük a mintába. Ezt a módszert gyakran használják minőségellenőrzésnél. - Kétlépéses mintavétel: Kiválasztunk véletlenszerűen egy vagy több csoportot, vagy esetleg az összeset, majd mindegyik csoportból választunk véletlenszerűen egy vagy több elemet. A csoportokból való választásoknak egymástól függetleneknek kell lenniük. - Rácsmódszerek: Abban az esetben használjuk őket, ha a megfigyelt rendszernek végtelen sok állapota van,

végtelen sok lehetséges megfigyelésből kell kiválasztani egy mintát. A módszerek közös tulajdonsága az, hogy az n-dimenziós megfigyelési térre egy ndimenziós rácsot fektetünk, majd a rácspontokból választunk mintaelemet. Lehetséges módszer az összes rácspont kiválasztása, rácspontok véletlenszerű kiválasztása, bizonyos rácspontok által határolt n-dimenziós kockák további felosztása újabb rácsokkal, stb. 16 Méréskiértékelés: - A várható érték mérőszámai: - Átlag: A mért értéket próbálja becsülni, zavarja a nagy tévedés. - Medián: Becslések középső értéke, a rendezett sorozat közepén lévő érték. - Modus: Leggyakoribb érték, nem zavarja meg a nagy tévedés. - A szóródás mérőszámai: n ∑ Szórásnégyzet: D2 = - [(x i -átlagx)2/n]. i =1 Tapasztalati szórásnégyzet: - n ∑ [|x i -átlagx|/n-1]. i =1 Szórási együttható: szórás/átlag. - Kovariancia n cov(X,Y) = ∑ ( x − M ( X

)) * ( y − M (Y )) i =1 i i n Korreláció r ( X , Y) = cov ( X , Y ) D ( X ) * D (Y) Lineáris regresszió Lineáris regresszió esetén egy elsőfokú polinomot kell előállítani. Nemlineáris regresszió Ha a kapcsolat nem lineáris, akkor vissza kell alakítani lineárissá, és a megfelelő lineáris regressziót kell alkalmazni. Konfidencia-intervallum Az elméleti várható értéket tartalmazó intervallum. Statisztikai becslések Illeszkedés-vizsgálat Adott eloszlású-e a minta? Vegyünk egy intervallumot, amin belül van minden lehetséges érték, osszuk fel részekre. P i jelölje az i. intervallum eloszlását K χ2 = ∑ i =1 (si − nPi )2 nPi Ha a kapott érték az adott intervallumban van, akkor ilyen eloszlású volt a minta. Ha nem az intervallumban van, akkor nem ilyen eloszlású volt a minta. 17 Homogenitás-vizsgálat Két minta azonos eloszlású-e? Akkor azonos eloszlásúak, ha van közük egymáshoz.  si t i  −  K  n m

 2 χ = nm∑ si + t i i =1 2 Az intervallum kiszámolható. Ha a kapott érték az adott intervallumban van, akkor azonos eloszlású volt a két minta. Ha nem az intervallumban van, akkor nem azonos eloszlású volt a két minta. Függetlenség-vizsgálat Két eseményrendszer független-e (K elemre)? F–próba Két normális eloszlású minta azonos szórású-e? t–próba Két normális eloszlású minta várható értéke megegyezik-e? Hibás adatok kiszűrése Hihetőség vizsgálat: Egy (A,B) intervallumot kell megadunk úgy, hogy a lehetséges értékek ebbe a tartományba essenek. Ami beleesik azt jónak tekintjük, ami nem, tehát az intervallumon kívül esik, azt elhagyjuk. Minél pontosabb a becslés, annál többet kell elhagynunk. Szélsőértékek elhagyása: A legkisebb és a legnagyobb értékek elhagyása, ezek a leghibásabb értékek. Szóráson kívüliek elhagyása: A szórásnál messze lévőket és az átlagnál jóval eltérőbbeket elhagyjuk. Ez a

három módszer nem a rendszeres hibát szűri ki, hanem a véletlen hibát találja meg. Mozgóátlagolás. Dixon-próba: Rendezett mintából elhagyjuk-e az első értéket? A két szélét kivéve minden pontot helyettesítünk a 2 szomszéd átlagával. Így a nagyon kilógókat erőteljesen behúzza, elsimítja a hibák hatását. Az átlag nem változik, a szórás viszont csökken Oszlop- és kördiagramok - Álló oszlopdiagram: Képre transzformálás. Növekvő oszlopdiagram: Normálás menet közben. Időben változó oszlopdiagram: - Új ablak. 18 - - Elölről kezdés, törlés nélkül. - Elölről kezdés előtörléssel. - Ablak eltolás. Kördiagram: Körívek + szakaszok + festés. 19 3. tétel Számítógépes szimuláció A szimuláció és a számítógép viszonyáról több szempont szerint beszélhetünk: - A programozási nyelv kérdése. - A számítógépes környezet kérdése. - A számítógéptípus kérdése. Programozási nyelv Szimuláció

céljára vagy általános célú programnyelvet használunk, vagy pedig valamilyen szimulációs nyelvet. A szimulációs nyelvek jellemzői: - Rendelkeznek beépített adatgyűjtéssel. - Képesek automatikusan eseményeket rögzíteni, számlálni. - Elemi utasításaikat szimulációs szempontok alapján választják. - Lehetőséget adnak komplex adatstruktúrák kezelésére is. - Lehetőség van az idő beépített figyelésére. - A szimulált folyamat folyamatszerű leírását teszik lehetővé. - A fentiek következtében módot adnak arra, hogy gyorsan, egyszerű szerkezetű szimulációs programokat készítsünk. A szimulációs nyelvek hátrányai: - Egy szimulációs nyelven megírt program általában lényegesen lassúbb, mint egy hagyományos nyelven megírt, azonos célú program. - Új programozási nyelvet tanulni nehéz, ezért nem számítástechnikai szakember felhasználónak nem is célszerű ilyen nyelvvel foglalkozni. A szimulációs programnyelvek egyik

gyakori elképzelése az eseményleírás. Ezen elképzelés szerint az események a modell állandó elemei működését írják le, egy esemény újabb eseményt aktiválhat, valamint megváltoztathatja egy vagy több állapotváltozó értékét. A generált események egy jósolt eseménylistába kerülnek, amelyből az aktuális eseményeket ki kell választani, majd végre kell hajtani. A másik elterjedt elképzelés a folyamatleírás. Itt folyamatok zajlanak, amelyek egy-egy rendszerelem viselkedését írják le. A nyelv utasításai maguk a statikus objektumok Minden folyamat az aktuális jelen időig hajtható végre, a folyamatok továbbá lehetnek várakozó, vagy felfüggesztett állapotban. Számítógépes környezet Ebben a kérdéskörben azt kell megvizsgálnunk, hogy hogyan használhatja a felhasználó a számítógépet: - A számítógép kötegelt feldolgozással dolgozik. - A számítógép interaktív hozzáférést biztosít. Az első eset jellemző

programhasználati módja az, amikor a programot beadjuk egy számítógépközpontba, majd néhány nap múlva megkapjuk az eredményt. Ha a beadás után rövid időn belül kapjuk az eredményt, akkor is úgy kell megírni a programot, hogy előre gondoskodjunk minden várható esemény, hiba kezeléséről, hiszen nincs lehetőség menet közbeni beavatkozásra. 20 Ezzel szemben az interaktív környezet lehetőséget biztosít arra, hogy: - A felhasználó mindig lássa, hogy mi történik a szimulált rendszerben, és maga kérheti egyes részeredmények nyomtatott formában való megjelenését. - Menet közben bármikor beavatkozhat: Megállíthatja a szimulációt, kérhet részletesebb információt az aktuális állapotról, áttérhet más eredménymegjelenítési módra. - A szimuláció folyamán módosíthatja a paramétereket is, ezek változtatásával megfigyelheti a modell reagálását a változásra. - Mindezek az értékelési folyamatot jelentősen

meggyorsíthatják, kihasználva egyrészt a számítógép nagy sebességét, másrészt pedig az ember intelligenciáját. Számítógép típus Háromféle nagyságrendű számítógépről kell beszélnünk. Az egyszerű konfigurációjú személyi számítógépek elsősorban a számítógépes szimulációval való ismerkedés eszközei. A szimulációs módszerek tanulására használhatók, továbbá kísérletező szerepet kaphatnak modellek létrehozásakor. Ezek nagyobb testvérei (professzionális PC) már a tudományos kutatómunka magasszintű eszközei lehetnek, s még mindig erősen felhasználó-orientáltak, de ugyanakkor teljesítményben már lényegesen felülmúlják az előző kategóriát. A harmadik típusba tartoznak a nagyszámítógépes rendszerek, amelyeket akkor célszerű használni, amikor egy bonyolult, sok paramétertől függő, sok adattal dolgozó, nagy műveletigényű feladatot kell megoldani. Szimulációs programok felépítése, keretmodellek

A modelleket két nagy osztályba soroljuk. Az egyikben a teljes jövőt előre kiszámítjuk, s azután csak a kiszámított jövő megjelenítése a feladat. A másikban az aktuális állapotból csak a következő időegységbeli állapotot határozzuk meg, majd abból számítjuk a következőt. Például, ha egy bolygó Nap körüli mozgását akarjuk szimulálni, akkor eljárhatunk úgy is, hogy egy pillanatbeli helyzetéből, sebességvektorából, a bolygó és a Nap tömege segítségével meghatározzuk a pálya egyenletét, majd ezt megjelenítjük. Eljárhatunk azonban úgy is, hogy az aktuális helyzetéből és sebességéből a bolygóra ható pillanatnyi erők segítségével meghatározzuk a bolygó helyét és sebességét a következő időegységben, majd ebből számoljuk az ezt követő időegység adatait. Mi elsősorban az utóbbi típusú modellekkel foglalkozunk. A valós rendszerek, amelyeket modellezni szeretnénk, olyanok lesznek, hogy a rendszer elemei

osztályokba sorolhatók, a rendszer állapotát ezen osztályok elemszáma fogja meghatározni, illetve egyes esetekben ezen osztályok térbeli eloszlása, mintázata. A rendszer egyes elemei véges sok állapotban lehetnek (diszkrét állapotú modell), s a rendszer elemszáma is mindig véges lesz. Programjainkban az egyes egyedekről kell valamilyen információt tárolnunk. Erre a célra táblázatokat használunk: - Ha az egyedek térbeli elhelyezkedésére nincs szükségünk, akkor vektort. - Ha fontos az egyedek közötti szomszédság megállapítása, akkor pedig kétdimenziós táblázatot (mátrixot). Két alapvető keretmodellt fogunk létrehozni, a következő elvek alapján: - Az előforduló eseményeket folyamatosan figyeljük, egy időpillanatban 1 (esetleg több) esemény következhet be. A modell idejének nincsen szoros kapcsolata a valós rendszer idejével (folytonos keretmodell). 21 - Az előforduló eseményeket diszkrét időközönként figyeljük. Egy

időpontban a rendszer minden elemével történik valami. A diszkrét időközök megfelelnek a valós rendszer idejének valamilyen rögzíthető időtartamával (diszkrét vagy generációs keretmodell). Folytonos keretmodell A változtatást úgy valósítjuk meg, hogy kiválasztjuk – valamilyen szabály szerint – a táblázat egy (vagy több) elemét, majd az ott lévő egyed felhasználásával módosítjuk a táblázatot. Folytonos diffúziós modell A módosítás itt úgy történik, hogy kiválasztunk egy elemet a táblázatból, majd megcseréljük környezetének egy véletlenszerűen kiválasztott elemével. A változás itt mozgást jelent Diszkrét (generációs) keretmodell Egy új táblázatot kell készíteni úgy, hogy az első táblázat valamennyi elemét módosítjuk valamilyen szabály szerint, és a továbbiakban csak az új táblázattal foglalkozunk. Diszkrét diffúziós modell A módosítás folyamata itt úgy történik, hogy a táblázat összes

elemével végzünk valamilyen mozgást. Elemi modellek, szerepük Elemi modelleket fogunk létrehozni, amelyek alapján fizikai, kémiai, biológiai modelleket készíthetünk. Ezekben egy vagy két populációban az egyedszám növekedésével vagy csökkentésével kapcsolatos elemi változások hatását vizsgáljuk. Eseménynek egy objektum változását fogjuk nevezni (például molekula elbomlik, élőlény meghal, stb.) Ismeretünk ezen események valószínűségeire vonatkozik Azt vizsgáljuk, hogy folytonos modellek esetén hogyan lehet kiválasztani azt az elemet, amellyel valami történni fog a szimulációs lépésben. A választás módjától függően e modellek más-más típusú eredményt fognak adni. Szabályok Két populációval foglalkozunk, megadhatjuk mindkét fajta egyed születésének (keletkezésének) és halálozásának (megszűnésének) szabályait (a két populáció stratégiáit). A leggyakoribb stratégiatípusok: - S 0 - indifferens stratégia:

A születések (halálozások) gyakorisága függ a populáció létszámától. - S + - konform stratégia: A születések (halálozások) gyakorisága arányos a populáció létszámával. Születés esetén létszámingadozást erősítő, halálozás esetén stabilizáló szerepe van az ilyen stratégiának. - S - - kontra stratégia: A születések (halálozások) gyakorisága fordítottan arányos a populáció létszámával. Születés esetén stabilizáló, halálozás esetén ingadozást erősítő hatása van a kontra stratégiának. 9 lehetőségből a 4 legfontosabbat vizsgáljuk. Adott egy N*M-es táblázat. Helyezzünk el benne kétféle elemet (A, I betűket) adott arányban Betűket fogunk levenni és feltenni különböző szabályok alkalmazásával. A kétféle betűre mindig ugyanazt a szabályt alkalmazzuk. 1. elemi modell: (S 0 - S 0 ) 22 Pénzfeldobással döntsünk, hogy A-t cserélünk I-re, vagy I-t A-ra (egyenlő esélyek). Megfigyelhető jelenségek: -

Teljesen véletlen létszámingadozás egy-egy populáción belül. - Hosszú idő alatt átlagosan 50%-os a két betű előfordulási aránya. - A betűk mennyiségének bármilyen eloszlása egyenlően valószínű. - A nem egyenlő esélyű esetben az átlag az esélyek arányától függ. - Ha rövid ideig figyeljük az eseményeket, akkor a kezdeti eloszlás gyakran fog visszatérni. Szimulációs lépés: Ha véletlenszám < 0.5 akkor I-t cserél A-ra Különben A-t cserél I-re Eljárás vége A modell szerint a születésnek és a halálozásnak függetlennek kell lennie az egyedszámtól. Ez teljesül, hiszen a választásban az egyedszámtól függetlenül döntöttünk. 2. elemi modell: (S - - S + ) Válasszunk ki véletlenszerűen egy mezőt, és azután az ott levő egyedet cseréljük ki egy másik fajtájúra. Megfigyelhető jelenségek: - Egyensúlyi állapot beállása független a kezdőeloszlástól. - A kezdeti eloszlástól függ, hogy milyen gyorsan áll be az

egyensúly. - A nem egyenlő esélyű esetben az egyensúlyi állapot értéke a megadott valószínűségektől függ. Szimulációs lépés: (i,j):=véletlen hely(n,m) Ha tábla(i,j) = ”A” akkor tábla(i, j):=”I” Különben tábla(i,j):=”A” Eljárás vége Ha az egyik populáció nagy létszámú, akkor nagy valószínűséggel belőle választunk ki egy egyedet, és így az egyedszáma csökken. Ha kicsi, akkor sokkal kisebb eséllyel történik meg ez. Tehát a halálozásra igaz az S + szabály Ennek megfelelően a születésekre pontosan fordított szabály teljesül, hiszen eljárásunk szerint a másikra cseréltük ki, ez az S - szabály. 3. elemi modell: (S + - S - ) Válasszunk ki véletlenszerűen egy mezőt, és az ott található egyedet helyezzük el egy tetszőleges másikféle helyére is. Megfigyelhető jelenségek: - Az egyenlő eloszlás instabil állapot, kis véletlenszerű ingadozással már eltérhetünk tőle. - Az egyenlő elosztástól való

bármilyen eltérés esetén ez az eltérés rohamosan növekszik, azaz már kis különbség is végzetes lehet. - A folyamat az egyik fajta számára mindenképpen katasztrofális, a másik teljesen kiszorítja. - A különböző esélyű változatban nem az egyenlőségtől, hanem az adott valószínűségek által meghatározott értéktől való eltérés a fontos. 23 Szimulációs lépés: (i,j):=véletlen hely(n,m) Ha tábla(i,j) = ”A” akkor I-t cserél A-ra Különben A-t cserél I-re Eljárás vége Ha egy populáció nagy létszámú, akkor nagy valószínűséggel belőle választunk ki egyedet, ha ezt a program szerint egy másik helyére tesszük, akkor a nagy létszámú populáció tovább fog növekedni, a kicsi pedig nem, így teljesül a születésekre az S + szabály. Mivel másik fajtájút veszünk le, ezért a halálozásokra az ellentétes S - szabálynak kell teljesülnie. 4. elemi modell: (S + - S + ) A módosítást két lépésben végezzük.

Először kiválasztunk egy helyet véletlenszerűen és az ott levő egyedet eltávolítjuk a tábláról. Ezután választunk egy újabb mezőt és az ott található fajtából az előbb kiürített helyre is teszünk egyet. Szimulációs lépés: (i,j):=véletlen hely(n,m) Ciklus (k,l):=véletlen hely(n,m) amíg k = i és l = j Ciklus vége tábla(i,j):=tábla(k,l) Eljárás vége Első ránézésre az lehet, hogy a születéseket és a halálozásokat egyforma szabályok szerint végeztük. A második modell szerint, ahol a halálozásokat úgy valósítottuk meg, ahogyan itt, ez a közös szabály az S + . Elemi növekedési modellek A következő elemi modellekkel a növekedés (létszámnövekedés) különböző típusait vizsgáljuk. Két esetet különböztetünk meg: - Korlátlan növekedés. - Korlátozott növekedés. Mindkét növekedésfajta esetén újabb három lehetőséget nézünk meg: - Lineáris növekedés. - Exponenciális növekedés. - Hiperbolikus

növekedés. Jelölje X az egyedszámot, ∆X az egyedszám időegység alatti változását. Ekkor az egyes növekedéseket a következő függvények írják le:  P  ∆X =  P * X P * X 2  24 ahol P a növekedés ütemét jellemző állandó. Mindegyik modellünk úgy fog felépülni, hogy a táblázatunkban nem foglalunk el kezdetben minden mezőt a betűkkel, hanem csak a táblázat bizonyos százalékát töltjük ki, majd meghatározott szabályok szerint helyezünk el további betűket a táblázat üres helyeire, amíg el nem érjük a táblázat teljes betöltöttségét (csak egy fajta betűt használunk). A három modell között a különbség ismét a szabályokban lesz. Egy időegység a táblázat méretének (N*M) megfelelő számú elemi lépésnek felel meg. Egy lépésben átlagosan adott darabszámú egyedet kell a táblázatban elhelyezni. 1. elemi növekedési modell (korlátlan növekedés) Ezt a növekedést csupán a növekedéstípusok

megismerése és megvalósítási lehetőségei céljából vizsgáljuk. Indulásként helyezzünk el átlagosan K darab X betűt táblázatunkban (azaz minden egyes helyre K/(N*M) valószínűséggel). Helyezzünk el további betűket az alábbi 3 stratégia szerint addig, amíg nem telik be a táblázatunk. A betelés üteme szempontjából lesz lényegi eltérés a modellek között. Lineáris növekedés Helyezzünk el elemi lépésenként P/(N*M) paraméterű Poisson-eloszlással X betűket tetszőleges üres helyen. Így, ha az egy időegység N*M elemi lépésből áll, akkor egy időegység alatti növekedés várható értéke P lesz. Szimulációs lépés: Ciklus k:=1-től N*M-ig DB:=Poisson(P/(N*M)) Ciklus l:=1-től DB-ig üres hely keresés(i,j) tábla(i,j):=”X” Ciklus vége Ciklus vége Eljárás vége Modellünk használatakor azt tapasztalhatjuk, hogy az X betűk számának növekedése független. Exponenciális növekedés Válasszunk ki véletlenszerűen egy

helyet táblázatunkban. Ha az már foglalt, akkor helyezzünk el átlagosan P darab X betűt üres helyekre, ugyanis annak a valószínűsége, hogy egy tetszőleges helyen X betűt találunk, pontosan az X betűk száma osztva N*M-mel, így N*M lépés alatt az X betűk találásának várható értéke az X betűk aktuális száma lesz. Szimulációs lépés: Ciklus k:=1-től N*M-ig (i,j):=véletlen hely Ha tábla(i,j) = ”X” akkor DB:=Poisson(P) Ciklus l:=1-től DB-ig üres hely keresés(i,j) tábla(i,j):=”X” 25 Ciklus vége Elágazás vége Ciklus vége Eljárás vége A növekedést ebben az esetben az X betűk számának lineáris függvénye fogja leírni, amelyből azt kapjuk, hogy a létszámot exponenciális függvény írja le. Hiperbolikus növekedés Válasszunk ki véletlenszerűen 2 helyet a táblázatunkban, s ha mindkettőben X betű van, akkor helyezzünk el üres helyekre átlagosan P*NM darab X betűt. Annak a valószínűsége, hogy két

véletlenszerűen választott helyen X betűt találunk az X betűk sűrűségének négyzete, így N*M lépés alatt az X betűk találásának várható értéke (XszámXszám)/(NM), tehát egy ilyen konkrét esetben P*NM darab X betűt kell elhelyeznünk. Szimulációs lépés: Ciklus k:=1-től N*M-ig (i,j):=véletlen hely (a,b):=véletlen hely Ha tábla(i,j) = ”X” és tábla(a,b) = ”X” akkor DB:=Poisson(P*NM) Ciklus l:=1-től DB-ig üres hely keresés(i,j) tábla(i,j):=”X” Ciklus vége Elágazás vége Ciklus vége Eljárás vége Ebben az esetben a növekedés üteme a létszám négyzetétől függ, amelyből az következik, hogy a létszámot egy hiperbolikus függvény írja le. 2. elemi növekedési modell (korlátozott növekedés) A korlátozott növekedési modell abban különbözik a korlátlantól, hogy itt adunk felső határt a populációk méretére (itt már két populációt vizsgálunk), ezt a korlátozást a helyért való versengés határozza meg.

Az előző elemi növekedési modell algoritmusait fogjuk módosítani. Kezdetben K darab betűt helyezünk el, minden helyre P valószínűséggel X betűt, 1-P valószínűséggel Y betűt. Lineáris növekedés Ebben a modellben az új betűk elhelyezésekor véletlenszerűen választunk kétféle betű között. P1 darab X és P2 darab Y betűt teszünk a táblázatba egy időegység alatt. Szimulációs lépés: Ciklus k:=1-től N*M-ig Növekedés(Poisson(P1/(N*M)),”X”) Növekedés(Poisson(P2/(N*M)),”Y”) Ciklus vége Eljárás vége 26 Növekedés(DB, BETŰ) Ciklus l:=1-től DB-ig (i,j):=véletlen hely(N,M) tábla(i,j):=BETŰ Ciklus vége Eljárás vége A program használatakor megfigyelhetjük, hogy a kétféle betű aránya fix érték körül fog ingadozni. Exponenciális növekedés (logisztikus növekedés) Ebben a modellben olyan betűt fogunk elhelyezni a táblázatban, amilyet a véletlenszerűen kiválasztott helyen találunk. Ha X-et találunk, akkor

átlagosan P1 darab X betűt, ha pedig Y-t, akkor P2 darab Y betűt helyezünk el. Szimulációs lépés: Ciklus k:=1-től N*M-ig (i,j):=véletlen hely Ha tábla(i,j) = ”X” akkor Növekedés(Poisson(P1),”X”) Különben Ha tábla(i,j) = ”Y” akkor Növekedés(Poisson(P2),”Y”) Ciklus vége Eljárás vége A modellünkben az egyes populációk szelekciós előnyét a P1, P2 változók értékeivel szemléltethetjük, amelyik rátermettebb az gyorsabban tud szaporodni. Azt tapasztalhatjuk, hogy a rátermettebb populáció akkor is győzhet a helyért folyó versenyben, ha kezdetben kevesebb egyedből állt. Tehát a logisztikus növekedés kedvez az élettérért való versengésnek, a szelekciónak, ugyanis a rátermettebb populáció képes teljesen kiszorítani a kevésbé szapora populációt. Erre a többi növekedési modell esetén nincs mód Hiperbolikus növekedés Ebben a modellben olyan betűt fogunk elhelyezni a táblázatban, amilyent két egymás utáni

kiválasztott helyen találtunk. Ha mindkét helyen X-et találunk, akkor átlagosan P1*NM darab X betűt helyezünk el, ha Y-t, akkor pedig P2*NM darab Y betűt. Szimulációs lépés: Ciklus k:=1-től N*M-ig (i,j):=véletlen hely (a,b):=véletlen hely Ha tábla(i,j) = ”X” és tábla(a,b) = ”X” akkor Növekedés(Poisson(P1*NM),”X”) Különben Ha tábla(i,j) = ”Y” és tábla(a,b) = ”Y” akkor Növekedés(Poisson(P2*NM),”Y”) Ciklus vége Eljárás vége Sokkal gyorsabb változások történnek modellünkben, mint az előzőkben; az egyik betű nagyon gyorsan megszűnik. Azt, hogy melyik lesz ez a betű a P, P1, P2 értéke határozza meg Ebben a modellben már nem igaz az, hogy az előnyösebb mindig győz. Ezzel azt a meglepő 27 eredményt kaptuk, hogy a korlátozott hiperbolikus növekedés nem tesz lehetővé versengést, nem teljesül a „győzzön a rátermettebb” elv. Sejtautomata elvű keretmodell A mozgást szemléltető modellek alapvető

problémája a szimulációs program sebessége lesz. A megfigyelt térrész növelésekor a megoldást kivárhatatlanul hosszú idő alatt kapjuk meg. Erre a problémára adnak választ a sejtautomata elvű modellek. Osszuk fel a vizsgált térrészt azonos méretű cellákra. Minden egyes sejtre meg fogjuk adni az állapotát. A diszkrét keretmodellre építhetünk sejtautomata típusú modelleket, az összes sejt párhuzamos állapotváltozását fogjuk megadni. Minden egyes sejt következő időpillanatbeli állapota függ egyrészt a saját állapotától, másrészt pedig szomszédai, valamilyen környezete állapotától. Ezt az állapotváltozást írja le az úgynevezett állapotátmenet-függvény A választott időegységtől függően többnyire 4 vagy 8 szomszédot veszünk figyelembe. Meggondolandó, hogy hogyan kapjuk a diffúzió véletlenszerű mozgásából az állapotátmenet függvényt. Úgy, hogy minden cellán belül egyenletes az eloszlás Meghatározzuk, hogy

a cellában levő molekulák hány százaléka képes egy időegység alatt elhagyni a cellát. Tartalmazza a sejttér régi állapotát az R(N,M) mátrix, az újat pedig az U(N,M). a modellben nem negatív valós számok fogják azonosítani az egyes sejtek állapotait, illetve –1 fogja jelölni azokat a sejteket, amelyek mintegy falat határoznak meg a sejttérben, azaz nem változhatnak, s rajtuk keresztül mozgás sem történhet. Célszerű lesz kezdetben az a feltételezés, hogy sejtterünk szélein ilyen fal típusú sejtek találhatóak. Ez a modell homogén és izotróp teret feltételez. A változás azt jelenti, hogy a sejttér adott pontjára a környezetből anyag (energia) áramlik. Minden egyes sejtből a teljes anyagmennyiség D-szerese fog kiáramlani 4 szomszédja közül mindegyikbe (D<1/4). 28 4. tétel Szimulációs modellek a fizikában Gázmodellek Adott valahány elemi rész, ismerjük ezek egyedi tulajdonságait, kölcsönhatásaikat, s azt

szeretnénk megvizsgálni, hogy ezek az anyaghalmazok együttesen hogyan viselkednek, milyen tulajdonságok jellemzőek rájuk, mint egészre. Ha e részecskék mozgását semmi sem befolyásolja, akkor hogyan töltik ki a rendelkezésre álló helyet? Darázs modell Van két dobozunk, amelyekbe „darazsakat” zártunk. A darazsak a két doboz között véletlenszerűen röpködnek. Meg kell vizsgálnunk, hogy milyen lesz hosszú idő alatt a darazsak eloszlása. A véletlenszerű röpködést úgy oldjuk meg, hogy kiválasztunk véletlenszerűen egy darazsat, és azt áttesszük a másik dobozba. Jelölések: - N: a darazsak darabszáma. - D(i): az i. darázs melyik dobozban van - A: az 1. dobozban levő darazsak aktuális száma - S(i): hányszor volt az 1. dobozban éppen i darab darázs A folytonos keretmodellt fogjuk használni, mivel a darazsak nem megkülönböztethetők. Diffúzió: i:=véletlenszám(N) Ha D(i) = 1 akkor D(i):=2 A:=A-1 Különben D(i):=1 A:=A+1 Elágazás

vége S(A):=S(A)+1 Eljárás vége Modellünk azonos a 2. elemi modellel A következő párhuzamokat lehet észrevenni: - A születés legyen a darázs berepülése az 1. dobozba - A halálozás legyen a darázs kirepülése az 1. dobozból - Ott véletlenszerűen választottunk egy betűt, itt véletlenszerűen választottunk egy darazsat, s mindegyik az egyedszámmal arányos. Ezek alapján nem meglepő, hogy tetszőleges kezdőállapotból kiindulva, a fele-fele arány lesz a végállapot, a darazsak száma ezen érték körül fog ingadozni. 29 Egyenesmenti molekulaeloszlás Bonyolítsuk eredeti modellünket úgy, hogy itt nem 2, hanem M darab doboz van egymás mellett. Minden darázs átrepülhet egy szomszédos dobozba (balra, illetve jobbra) egyenlő eséllyel. Jelölések: - N: a darazsak darabszáma. - D(i): az i. darázs melyik dobozban van - A(k): a k. dobozban levő darazsak aktuális száma - M: dobozok darabszáma. Itt is a folytonos keretmodellt fogjuk használni,

mivel a darazsak nem megkülönböztethetők. Diffúzió: i:=véletlenszám(N) Ha véletlenszám < 0.5 akkor Balra(i) Különben Jobbra(i) Eljárás vége Balra(i): Ha D(i) > 1 akkor A(D(i)):=A(D(i))-1 D(i):=D(i)-1 A(D(i)):=A(D(i))+1 Elágazás vége Eljárás vége Jobbra(i): Ha D(i) < M akkor A(D(i)):=A(D(i))-1 D(i):=D(i)+1 A(D(i)):=A(D(i))+1 Elágazás vége Eljárás vége Az egyes dobozokat külön-külön vizsgálva, itt is a 2. elemi modell feltételei teljesülnek, ami stabilitásra utal. Az eddigi modellek vizsgálata alapján megadhatjuk a korábban feltett kérdésre a választ: ha az atomok, molekulák mozgását semmi sem befolyásolja, akkor a rendelkezésükre álló teret egyenletesen töltik ki, térrészenkénti eloszlásukra pedig a binomiális eloszlás a jellemző. Gravitációs gázmodell Vizsgáljuk meg, mi történik, ha a molekulák mozgására hat a gravitáció. Az új hatást úgy vesszük figyelembe, hogy a molekulák teljesen véletlenszerű

sebességéhez hozzáadunk egy lefelé irányuló komponenst, azaz így a molekulák nagyobb valószínűséggel mozoghatnak lefelé. Az egydimenziós diffúziós modellt alakítjuk át, melyben most a hely indexe a magasságot jelöli. Minden egyes kiválasztott molekula P valószínűséggel mozduljon el lefelé és 1-P valószínűséggel felfelé. 30 A programot használva azt tapasztaljuk, hogy a molekulák száma a magassággal exponenciálisan csökken. Ez a modell a 2. elemi modellre épül, mégsem egyenletes eloszlást kapunk eredményül Ez azonban nem ellentmondás, hiszen ez az elemi modell csak a stabilitást, azaz a végállapot létét garantálja, az egyenletességet pedig csak abban az esetben, ha a változás kétféle jelensége (születés, halálozás) azonos valószínűségű. Ebben a gravitációs modellben a dobozokba való be-, illetve kilépés helytől függően más-más esélyű, ami kizárja az egyenletes eloszlást. Síkbeli molekulaeloszlás A

szimulációs tér változása annyiból álljon, hogy egy véletlenszerűen kiválasztott molekulát és egyik szomszédját cseréljük fel. Valódi mozgás csak akkor történik, ha az egyik helyen volt molekula, a másikon pedig nem. A valós rendszertől különbözik a modellünk abban, hogy egy molekulának minden lépésben újra választunk irányt. Jelölje Tér(N,M) karakterelemű mátrix a táblázatot, ahol a kétdimenziós diffúziót nyomon követjük, ’*’ a molekulát, szóköz az üres helyet. Diffúzió: (i,j):=véletlen hely(N,M) (k,l):=véletlen szomszéd(i,j) csere((i,j),(k,l)) Eljárás vége Egy tetszőleges térrészre itt is teljesülnek a stabilitást okozó 2. elemi modell feltételei Vezessük be a modellbe a gravitáció jelenségét. A korábbiakból tudjuk, hogy ilyenkor a szomszédválasztást kell befolyásolni, mégpedig lefelé nagyobb valószínűséggel kell szomszédot választani, mint felfelé. A jobboldali vagy a baloldali szomszéd

választását ez a jelenség nem befolyásolja. Ezt a modellt bővíthetjük úgy, hogy ne csak a függőleges, hanem a vízszintes irányú komponenst is figyelembe vesszük. A következő vizsgált jelenség legyen a szél. A legegyszerűbb megvalósításban azt kell megoldani, hogy a molekulák rendelkezzenek egy szélirányú komponenssel is. Mivel egyedi sebességvektorokat nem tárolunk, ezért ez úgy oldható meg, hogy valószínűbbé tesszük abba az irányba az elmozdulást, amerre a szél fúj, s kisebb valószínűségűvé az ellenkező irányú elmozdulást. A molekulák nem torlódhatnak fel a vizsgált térrész egyik szélén, s nem tűnhetnek el a másik széléről. Ennek következtében nem szabad zártként vizsgálni a rendszert, hanem át kell térni nyílt rendszerre. Megoldandó feladat még a molekulák kilépése a rendszerből és a belépés. A kilépést egyszerűen megoldhatjuk, ha a molekula el akarja hagyni a vizsgált térrészt, akkor engedjük ki.

A belépés ennél bonyolultabb, megadjuk azt, hogy a vizsgált tér szélein milyen relatív gyakorisággal található molekula (állandó érték legyen). S ez már a mozgás szabályainak fegyelembevételével léphet be a rendszerbe. Folyadékmodellek A folyadékok a rendelkezésre álló teret sűrűn töltik ki, a folyadék molekulák között gyakorlatilag nincs üres hely. Bernoulli-féle modell Van 2 dobozunk, K darab A- és L darab B-molekulánk. Ezek a két dobozt teljesen kitöltik, mindkét dobozban N darab molekula fér (2*N=K+L). 31 Véletlenszerűen kiválasztunk egy molekulát az 1., s egy molekulát a 2 dobozból, majd megcseréljük őket. Jelölések: - A(N): az 1. dobozban lévő molekulák betűjelei - B(N): a 2. dobozban lévő molekulák betűjelei - ADB: az 1. dobozban lévő A-molekulák száma Diffúzió: (i,j):=véletlen hely(N,N) Ha A(i) = ”A” akkor ADB:=ADB-1 Ha B(j) = ”A” akkor ADB:=ADB+1 csereAB(i,j) Eljárás vége Nagy N, K, L értékek

esetén megfigyelhetjük programunkkal, hogy a molekulák egyenletes eloszlása, a teljes keveredés lesz az eredmény. Ez a modell ugyanazt az eredményt adja, mint a darázsmodell, de a végállapotot a kétféle hatástalan csere miatt lassabban éri el. Síkbeli folyadékmodell Egy új hatóerőt kell figyelembe vennünk, a molekulák közötti vonzóerőt, amely a távolság négyzetével fordítva arányosan hat. A folytonos keretmodellt használjuk. A Tér(N,M) táblázatba kétféle számot (0,1) helyezünk el véletlenszerűen. Az 1 jelenti azt, hogy az adott helyen van molekula, a 0 pedig azt, hogy nincs. A megoldás algoritmusában a molekulát az 1 jelöli, a falat pedig a 0 Szimulációs lépés: (i,j):=véletlen hely(N,M) (k,l):=véletlen szomszéd(i,j) Ha Tér(i,j) = 1 és Tér(k,l) = 0 és Szomszédszám(k,l) ≥ Szomszédszám(i,j) akkor csere((i,j),(k,l)) Eljárás vége Ez a modell megfelel a 3. elemi modellnek Ha a cseppeket (összetartozó molekulahalmazokat)

vesszük egységnek, akkor a csepphez új molekula csatlakozásának valószínűsége a csepp méretével arányos (születés), molekula eltávozása pedig a cseppmérettel fordítva arányos (halálozás). Tehát ebben a modellben nem várhatjuk a molekulák egyenletes eloszlását. A molekulák egyes helyeken csoportosulni fognak cseppekké, más helyeken pedig üresen maradnak. Az pedig, hogy mely helyeken lesznek cseppek, nem jósolható meg előre. Gravitációs folyadékmodell Egy korábbi modellnél tapasztaltuk, hogy ha a molekulára hat a gravitáció, akkor sűrűségük a magassággal exponenciálisan csökken. Modellünkbe bevezetjük a gravitációt úgy, hogy az aktuális hely feletti helyek molekulaszomszédai számából levonunk G-t (G: egy, a gravitációnak megfelelő pozitív egész szám), az alatti helyekéhez pedig hozzáadunk G-t. Beavatkozásunk eredményeként azt várjuk, hogy kialakuljon egy vízszintes folyadékfelület. 32 Szimulációs lépés:

(i,j):=véletlen hely(N,M) (k,l):=véletlen szomszéd(i,j) Ha Tér(i,j) = 1 és Tér(k,l) = 0 és Szomszédszám(k,l)+(k-i)*G ≥ Szomszédszám(i,j) akkor csere((i,j),(k,l)) Eljárás vége Szimuláció a kémiában Kémiai reakciók, reakciórendszerek Egyesülés E folyamat során az egymásra ható anyagokból egyetlen új anyag keletkezik. Az ütközés során új kémiai kötés alakul ki. A folyamat általános reakcióegyenlete: A + B ⇒ C A reakció sebessége függ a hőmérséklettől, a nyomástól és a kezdeti koncentrációktól. A és B molekula találkozásánál átalakulási valószínűséggel (ÁT) a molekulák C molekulává egyesülnek. Egyesülés: (i,j):=véletlen hely(N,M) (k,l):=véletlen szomszéd(i,j) Ha (Tér(i,j) = ”A” és Tér(k,l) = ”B”) vagy (Tér(i,j) = ”B” és Tér(k,l) = ”A”) akkor Ha véletlenszám < ÁT akkor Tér(i,j):=”C” Tér(k,l):=” ” csere(Tér(i,j),Tér(k,l)) Eljárás vége Ha a kiindulási anyagok

részecskéinek száma nagyon eltér, akkor a reakció gyorsan lejátszódik. A program homogén rendszerben lezajló egyesülést szimulál, tehát a részecskék kezdetben is egyenletesen oszlanak el a reakciótérben. Bomlás Ez a reakció az egyesüléssel ellentétes folyamat. Általános egyenlete: C ⇒ A + B A bomlás monomolekuláris, tehát nincs szükség molekulák ütközésére a reakció lejátszódásához. Az átalakulási valószínűség (ÁT) azt mutatja meg, hogy időegység alatt egy molekula milyen eséllyel bomlik el. Szimulációs programunkban a bomlás feltétele az is, hogy a bomló molekula környezetében mindig kell lennie szabad helynek. Ez a feltétel azt jelenti, hogy kezdőállapotként csak kis mennyiséget érdemes megadni az anyagokból. Bomlás: (i,j):=véletlen hely(N,M) Ha Tér(i,j) = ”C” és van szomszéd(i,j,k,l) akkor Ha véletlenszám < ÁT akkor Tér(i,j):=”A” Tér(k,l):=”B” Különben (k,l):=véletlen szomszéd(i,j)

Elágazás vége csere(Tér(i,j),Tér(k,l)) Eljárás vége 33 Megfigyelhető, hogy a C anyag mennyisége az idővel exponenciálisan csökken. A reakciósebesség befolyásolható az átalakulási valószínűség megváltoztatásával. C molekula bomlásával az A és a B molekulákból azonos mennyiségű keletkezik. Disszociáció Az összetett reakciók között aránylag a legegyszerűbbek az egyensúlyra vezető folyamatok, vagyis az olyan egyszerű reakciók, amelyekben előbb-utóbb észrevehetővé válik az ellentétes folyamat, így egy idő múlva beáll az egyensúlyi állapot. Általános egyenlete: A + B ⇔ C A képződés bimolekulás, a bomlás monomolekulás. Az egyensúly dinamikus jellegű. Az egyensúly elérésének ideje függ a kiindulási koncentrációktól és a reakciósebességi állandóktól (ÁT, VISSZA). Disszociáció: (i,j):=véletlen hely(N,M) (k,l):=véletlen szomszéd(i,j) v:=véletlenszám Elágazás (Tér(i,j) = ”A” és Tér(k,l) =

”B”) vagy (Tér(i,j) = ”B” és Tér(k,l) = ”A”) esetén Ha v < ÁT akkor Tér(i,j):=”C” Tér(k,l):=” ” Tér(i,j) = ”C” és van szomszéd(i,j,k,l) esetén Ha v < VISSZA akkor Tér(i,j):=”A” Tér(k,l):=”B” Elágazás vége csere(Tér(i,j),Tér(k,l)) Eljárás vége Megfigyelhető, hogy az egyensúly elérésének ideje függ a kezdőfeltételként megadott anyagmennyiségtől, azaz a kezdő állapot mennyire tér el az egyensúlyi állapottól, és a sebességi állandóktól. Nagyobb reakciósebességi állandók esetén az egyensúly gyorsabban beáll. Az egyensúly dinamikus jellege jól megfigyelhető, mert a molekulák száma ebben az állapotban ingadozik. Sorozatos reakciók A szerves kémia legtöbb átalakulása több egymás után következő reakciótípusban megy végbe, e lépések alkotják a sorozatreakciók rendszerét. Egy ilyen rendszer legegyszerűbb esete két egymás után következő elsőrendű reakció: A ⇒ B ⇒ C. E két

lépésből álló rendszernek a megfelelő reakciósebességi állandói k 1 , k 2 . Ha k 1 és k 2 nem tér el jelentősen, akkor a B molekula mennyisége a folyamat elején jelentősen megnő, majd fokozatosan csökken, végül nullává válik. Az A molekula mennyisége, mivel monomolekuláris reakciókban bomlik, exponenciálisan csökken. A reakció addig tart, amíg a kiindulási anyag és a köztitermék teljes mennyisége végtermékké nem alakul. Párhuzamos reakciók Ugyanazon anyag vagy anyagok különféle kémiai átalakuláson mehetnek át, vagyis adott kiindulási anyagok között sokszor többféle reakció lehetséges: A ⇒ B, A ⇒ C. 34 A két reakció sebessége különböző lehet. Ha a két párhuzamos folyamat sebességi állandói k 1 és k 2 , az A anyag koncentrációja időben exponenciálisan csökken. Legyen k=k 1 +k 2 Legyenek a két párhuzamos lépés sebességi állandói ÁT1 és ÁT2. Párhuzamos: (i,j):=véletlen hely(N,M) (k,l):=véletlen

szomszéd(i,j) v:=véletlenszám Ha Tér(i,j) = ”A” akkor Ha v < ÁT1 akkor Tér(i,j):=”B” Különben Ha v < ÁT1+ÁT2 akkor Tér(i,j):=”C” Elágazás vége csere(Tér(i,j),Tér(k,l)) Eljárás vége Megfigyelhetjük, hogy a párhuzamos folyamatok sebességét főleg a leggyorsabb részfolyamat szabja meg. Ha k 1 jóval nagyobb, akkor szinte csak B molekulák keletkeznek Az A molekulák teljes átalakulása után a reakció leáll. Katalízis A katalizátorok olyan anyagok, amelyek jelenlétükkel meggyorsítják a kémiai reakciókat, illetve megváltoztatják azok irányát anélkül, hogy a reakció folyamán maradandóan megváltoznának, és az egyensúlyt megváltoztatnák. Ha a katalitikus folyamat egynemű fázisban játszódik le, homogén katalízisről, ha viszont a reakció két fázis hatására megy végbe, heterogén katalízisről beszélünk. Ha a katalizátor a reakció folyamán keletkezik, akkor autokatalízisről beszélünk: A + C ⇒ B + C. A

katalizáló hatás általában abban áll, hogy a katalizátor az egymásra ható anyagok valamelyikével aktív átmeneti komplexummá egyesül, s ez alakul át a végtermékké. Legyen ÁT1 az A ⇒ B és ÁT2 az A + C ⇒ B + C folyamat reakciósebességi állandója. Ha ÁT2 nullával egyenlő, akkor a folyamat katalizátor nélküli monomolekulás átalakulási reakciónak felel meg. Az A molekula mennyisége exponenciálisan csökken, a B molekula mennyisége exponenciálisan nő. Ha C molekulák is jelen vannak, illetve ÁT2 jóval nagyobb ÁT1-nél, akkor a katalitikus folyamat lényege megfigyelhető, az A molekula átalakulási sebessége jelentősen megnő. Autokatalízis Katalitikus folyamatok esetében előfordul az is, hogy a katalizátor csak a reakció során termelődik, és a mennyisége a reakció előrehaladtával folyton nő: A + B ⇒ C, C ⇒ B + B. E rendszer különleges sajátossága az, hogy egyik ciklikus komponense maga a B végtermék. Ezekre a

reakciókra az a jellemző, hogy katalizátor hiányában először a sebességük igen kicsi, majd a B termék megjelenésével rendkívül felgyorsulnak, végül a teljes átalakulás környezetét elérve, az A molekula mennyiségének lecsökkenése miatt újból lassul a reakció. Az autokatalitikus rendszer öngyorsuló jellegét úgy indokolhatjuk, hogy benne a katalizátor összes mennyisége a reakció előrehaladtával növekszik. Kémiai körfolyamatok Nyílt rendszer esetén a legegyszerűbb kémiai körfolyamat: A + D ⇒ B, B ⇒ C + E, C ⇒ A. A kémiai rendszerbe D molekulák belépnek, illetve a reakciótérből az E molekulák kilépnek. Molekulák be- és kilépése diffúzióval történik. Megfigyelhető, hogy a rendszer belső komponenseinek arányai egy idő után stabil értéket vesznek fel, a folyamat stacionáriussá válik. Beáramlás csak akkor történhet, ha a határon szabad helyet találunk, akkor oda a 35 beáramlás valószínűségétől

függően D molekula léphet. A reakciótér határáról E molekula meghatározott valószínűséggel kiléphet. Mintázatképződés Kis foltok A foltképződési modellek általában kémiai körfolyamatokra vezethetőek vissza. A foltok általában több körfolyamat egymásra hatása miatt alakulnak ki. Ebben a modellben két önreprodukáló kémiai körfolyamatot veszünk, amelyek egymás termékeit fogyasztják. Összegképletük: A + X ⇒ Y + A + A, Y + B ⇒ X + B + B. Az X és Y molekulák mozoghatnak, A és B pedig különböző festékanyagot tartalmazó sejtek, amelyek mozdulatlanok. A molekulákat tároljuk a MOL(N,M) mátrixban, a sejteket pedig a SEJT(N,M) mátrixban. Az A és B sejtek elpusztulhatnak, a pusztulásuk valószínűségét jelölje P, illetve Q. Szimulációs lépés: (i,j):=véletlen hely(N,M) (k,l):=véletlen szomszéd(i,j) csere(MOL(i,j),MOL(k,l)) Elágazás SEJT(i,j) = ”A” és véletlenszám < P esetén SEJT(i,j):=” ” SEJT(i,j) = ”B”

és véletlenszám < Q esetén SEJT(i,j):=” ” Elágazás vége Elágazás MOL(i,j) = ”X” és SEJT(i,j) = ”A” esetén Keletkezés(i,j,”A”,”Y”) MOL(i,j) = ”Y” és SEJT(i,j) = ”B” esetén Keletkezés(i,j,”B”,”X”) Elágazás vége Eljárás vége Keletkezés(i,j,SE,MO): MOL(i,j):=MO véletlen üres szomszéd keresés(i,j,k,l) SEJT(k,l):=SE Eljárás vége Nagy foltok Ebben a modellben minden sejt alakuljon olyanná, amilyen szomszédjából több van. A sejttáblázat legyen mindig tele A- és B-típusú sejtekkel. Szimulációs lépés: (i,j):=véletlen hely(N,M) szomszédszámolás(i,j,”A”,a) szomszédszámolás(i,j,”B”,b) Elágazás SEJT(i,j) = ”B” és a > b esetén SEJT(i,j):=”A” SEJT(i,j) = ”A” és a < b esetén SEJT(i,j):=”B” Elágazás vége Ha SEJT(i,j) = ”A” és b = 0 akkor SEJT(i,j):=”B” Ha SEJT(i,j) = ”B” és a = 0 akkor SEJT(i,j):=”A” Eljárás vége 36 Érdekes módon függ a foltosodás a

vizsgált tér méretétől is. Ha a szimulációs terünk kicsi a szomszédszámolás távolságához képest, akkor az eredmény egy egyszínű tér lesz, vagy esetleg egy-két folt látható. Ha a tér mérete nagy, akkor több nagyméretű folt fog keletkezni, véletlenszerű eloszlásban. Ha a szomszédszámot nagyobb távolságra számoljuk, a foltok határvonala simább lesz. Ha a szomszédszámok között 1-nél nagyobb különbséget várunk el, akkor görbébb lehet a határ. A tér formáját megváltoztatva egészen érdekes mintázatokat is kaphatunk. Nagy foltok pöttyökkel Módosítsuk az előző modellt úgy, hogy ne engedjük meg olyan sejtek kialakulását, amelyeket csak velük azonos típusú sejt vesz körül. Szimulációs lépés: (i,j):=véletlen hely(N,M) szomszédszámolás(i,j,”A”,a) szomszédszámolás(i,j,”B”,b) Elágazás SEJT(i,j) = ”B” és a > b esetén SEJT(i,j):=”A” SEJT(i,j) = ”A” és a < b esetén SEJT(i,j):=”B”

Elágazás vége Eljárás vége Ha nagyobb pöttyöket akarunk megengedni, akkor az A=0, B=0 feltételeket kell kicserélnünk a pötty lehetséges mérethatárára (MH), azaz b<MH, a<MH feltételekre. Csíkok Szabálytalan, kanyargó csíkok alakulnak ki, ha a két sejtre különböző szabályok érvényesek. Egy A-típusú sejt alakuljon B-vé, ha van B szomszédja, a B-típusú pedig A-vá, ha az A szomszédjai száma kisebb, mint a B szomszédjai száma. A csíkok vastagsága, egyenletessége itt is a szomszédság méretétől függ. Meteorológiai (felhőfizikai) modellek Homogén kondenzáció Első modellünkben a felhő alsó részét vizsgáljuk, ahol a felfelé mozgó légáramlat hatására a vízmolekulák is mozognak felfelé, a vizsgált térben összeállnak cseppekké, s fönt kilépnek e térrészből. Csapadék még nem esik, így a lefelé mozgással nem kell törődnünk A vízmolekulák, vízcseppek a levegőben rendszertelenül mozognak, egy vízcsepp

párologhat, egy vízmolekula elpárologtatásához szükséges energia a magasságtól és a vízmolekula méretétől függ, a vízcseppre újabb molekulák kondenzálódhatnak. Két vízcsepp nem olvadhat össze. Definiálunk egy Párol nevű függvényt, amely megadja minden egyes vízcseppre a párolgás valószínűségét. A vízcseppek, molekulák elhagyhatják az általunk megfigyelt térrészt, illetve újabb vízmolekulák léphetnek be. Legyen BV a belépésük relatív gyakorisága Egyelőre mindegyik csak felfelé mozoghat. A folytonos keretmodell szerint válasszunk egy helyet véletlenszerűen, s ami ezen a helyen van, azzal történjen valami. Ha ez a hely a legalsó sor alatt lenne (N+1 sor), akkor lépjen be alulról új vízmolekula. 37 Cseppképződés: (i,j):=véletlen hely(N+1,M) (k,l):=véletlen szomszéd(i,j) Elágazás i = N+1 esetén Belépés(k,l) i = 1 esetén Kilépés(i,j) egyéb esetben Ha Tér(i,j) csepp akkor Párolgás(i,j) Ha Tér(i,j) nem üres

akkor Kondenzálódás(i,j,k,l) Elágazás vége Eljárás vége Minden belépés esetén véletlenszerűen döntünk, hogy jöjjön-e be vízmolekula vagy sem. Kilépésnél a molekula vagy csepp a rendszerből eltűnik. Párolgásnál a vízcsepp mérete eggyel csökken és keletkezik mellette egy szabad vízmolekula, illetve, ha a szomszéd helyen már van egy csepp, akkor annak mérete eggyel nő. Ha egy csepp felfelé mozog és találkozik egy molekulával, akkor összeolvadnak. Ez a kondenzáció jelensége Belépés(k,l): Ha véletlenszám < BV akkor Tér(k,l):=Tér(k,l)+1 Eljárás vége Kilépés(i,j): Tér(i,j):=0 Eljárás vége Párolgás(i,j): (p,q):=véletlen szomszéd(i,j) Ha véletlenszám < Párol(i,Tér(i,j)) akkor Tér(i,j):=Tér(i,j)-1 Tér(p,q):=Tér(p,q)+1 Eljárás vége Kondenzálódás(i,j,k,l): Ha Tér(i,j) nem csepp vagy Tér(k,l) nem csepp akkor Tér(k,l):=Tér(k,l)+Tér(i,j) Tér(i,j):=0 Eljárás vége Heterogén kondenzáció Bonyolítjuk a

feladatot. A levegőbe elhelyezünk különböző szennyező anyagokat (kondenzációs magokat), amelyekre az a jellemző, hogy rajtuk a kötési energia nagyobb, azaz a párolgás valószínűsége kisebb lesz. Ehhez szükséges, hogy vagy oldható legyen a vízben a fenti anyag, vagy ha nem oldható, akkor nedvesíthető legyen, azaz felületén rögzítse a vízmolekulákat. Hogyan kódolhatjuk a kondenzációs magot, illetve a rajtuk képződött vízcseppeket? A kondenzációs magot valamilyen törtszámmal (például: 0.5) jelöljük, s ehhez adjuk hozzá a vízmolekulák számát ezeknél a cseppeknél. A vízcseppek egyesülésén kívül itt a kondenzációs magok egyesülését is meg kell tiltanunk. Megfigyelhető, hogy kondenzációs magvakon sokkal könnyebben keletkezhet vízcsepp. 38 Koaguláció Most a felhő egy az előbbinél magasabban levő tartományát fogjuk vizsgálni. Itt alulról már vízcseppek is léphetnek be, de ezek még mindig csak felfelé

mozognak, azaz az eső még mindig nem esik. Modellünkben a vizsgált térrészbe vízcseppek fognak belépni, a vízcseppek felfelé mozognak, ha összeérnek egy másik vízcseppel, akkor összeolvadnak, s a rendszerből kiléphetnek. A vízcseppek mozgási sebessége a méretükkel fordítottan arányos. A csepp a fölötte levő három hely egyikére mozdulhat el. Ha a csepp túlságosan nagyra nőne, akkor szétesik két kisebb cseppre. A cseppek koagulációs növekedése arányos környezetük víztartalmával. Ahhoz, hogy a koaguláció elég hatékony legyen, szükség van néhány nagyobb méretű vízcseppre, a kisebbek ugyanis könnyebben elkerülik egymást, s ha nem nőnek meg elég nagyra, abból sosem lesz eső. Jégképződés A kondenzációs mag szerepét gyakran játsza megfagyott vízcsepp, ezért most a jégmagok keletkezésével foglalkozunk. Ebben a modellben új jelenség a fagyás Első közelítésben tegyük fel, hogy a jégmagok nem olvadhatnak meg és nem

is párologhatnak. Meg kell határoznunk a jégkristályok ábrázolását. A heterogén kondenzációhoz hasonlóan itt is egy számmal ábrázoljuk az új elemet, a jégkristályt, méghozzá úgy, hogy ehhez a számhoz hozzáadjuk a benne levő vízmolekulák számát. A vizsgált térrészből cseppek, jégkristályok, vízmolekulák kiléphetnek. A fagyásnál figyelembe vehetünk másodlagos jégképződési jelenségeket is. A nagy vízcseppek ugyanis kívülről befelé fagynak meg, s mivel a víz térfogata fagyáskor megnövekszik, ezért leválhatnak róla jégszilánkok. Azt tapasztaljuk, hogy a nagyobb méretű cseppek gyorsabban fagyhatnak meg. A jégmag nem párolog, így növekedése a cseppnél gyorsabb lesz. Csapadékképződés Most azt vizsgáljuk, amikor a környező levegő felszálló mozgása ellenére a cseppek, kristályok lefelé tudnak mozogni, ez lesz a csapadék. Az új modellünket a homogén koaguláció modelljéből készíthetjük el, a cseppek

mozgását módosítva. A felhőben a vízcseppek mozogjanak felfelé a méretüktől függő sebességgel. Ha a méret elér egy kritikus értéket, akkor a vízcsepp tömege egyensúlyt tart a felhajtó mozgással, ha ennél nagyobb, akkor lefelé fog mozogni. Ha a fagyás, illetve az olvadás jelenségét is megengedjük, akkor a jégképződés modelljéből kell kiindulnunk. Megállapítható, hogy a csapadékképződés szempontjából fontos a cseppek által a felhőben megtehető út hossza, azaz a felhő vastagsága. Általában igaz az, hogy nagyobb cseppsűrűség esetén több esőcsepp keletkezhet. 39 5. tétel Szimulációs modellek a biológiában Populációdinamika Elemi populációnövekedéssel foglalkozunk. Exponenciális növekedés A legegyszerűbb esetben az egyedenkénti szaporodási, illetve halálozási ráták semmitől sem függnek, a vizsgált időszakaszban állandóak, a létszám az újszülöttekkel nő, a meghaltakkal csökken. A modellhez

tároljuk az aktuálisan létező egyedek számát az N változóban. Minden egyed D valószínűséggel hal meg, és B paraméterű, Poisson eloszlású véletlenszám adja meg utódai számát. Alkalmazzuk a generációs keretmodellt Szimulációs lépés: M:=N Ciklus i:=1-től N-ig M:=M+Poisson(B) Ha véletlenszám < D akkor M:=M-1 Ciklus vége N:=M Eljárás vége Eredményként azt kapjuk, hogy a populáció mérete exponenciálisan nő vagy csökken. Logisztikus növekedés Módosítsuk az előző modellt, tegyük létszámfüggővé. Ebben az esetben a populáció nem növekszik tovább, ha a létszám elér egy határértéket. A modell háromféle eredményt adhat: a populáció létszáma az egyensúlyi állapot felé haladva növekszik vagy csökken, illetve a populáció kihal. Ha azonban a létszámváltozást nem az aktuális időpillanatbeli létszámtól, hanem egy múltbeli állapottól tesszük függővé, akkor túllengés is bekövetkezhet. Demográfia Egyetlen

populációt vizsgálunk, amelyet korcsoportok szerint osztályokra bontunk. Megadjuk minden korcsoport szaporodásának és halálozásának szabályait, majd a populáció növekedését, illetve korcsoporteloszlását vizsgáljuk. Alapmodell Jelölések: - N: populáció egyedszáma. - K: korcsoportok száma. - T(i): az i. egyed kora - E(i): valaki i éves korában milyen valószínűséggel hal meg. - M(i): valakinek i éves korában milyen valószínűséggel van – egyetlen – utódja. 40 Szimulációs lépés: j:=N Ciklus i:=1-től N-ig Ha véletlenszám < E(T(i)) akkor T(i):=0 Különben Ha véletlenszám < M(T(i)) akkor j:=j+1 T(j):=1 T(i):=T(i)+1 Elágazás vége Ciklus vége Táblázat tömörítése Eljárás vége Módosíthatjuk modellünket úgy, hogy egy évben több utód is születhessen. Ekkor M(i) az évi utódszám várható értékét jelenti. Járvány Modellünkben további módosításokat végzünk. Legyen JV annak a valószínűsége, hogy egy

évben van járvány, s ilyenkor a betegség miatti halálozások relatív gyakorisága JH. Vizsgáljuk meg, hogy van-e járvány, s ha van, akkor végezzük el a járvány miatti vizsgálatokat (halálozás). Elképzelhető, hogy járvány esetén az egyes korcsoportokban mások a halálozási ráták. Ebben az esetben JH(k) tárolja a halálozási rátákat. Járvány: Ha véletlenszám < JV akkor Ciklus i:=1-től N-ig Ha véletlenszám < JH(T(i)) akkor T(i):=0 Ciklus vége Táblázat tömörítése Elágazás vége Eljárás vége Mesterséges beavatkozás Ha a populáció egy állattenyésztő telep állataiból áll, akkor van értelme egy másfajta kérdés feltevésének is. Mennyi, s milyen korú állatot célszerű levágni, hogy a létszám állandó maradjon, a szaporodás pedig a lehető legnagyobb ütemű legyen? Jelölje V(i) az adott évben az i. korcsoportból levágandó egyedek számát Vágás: Ciklus i:=1-től N-ig Ha V(T(i)) > 0 akkor V(T(i)):=V(T(i))-1

T(i):=0 Ciklus vége Táblázat tömörítése Eljárás vége 41 Populációgenetika Az ősmodell A populáció életét genetikai arányainak, illetve ezek változásainak tükrében vizsgáljuk. A populációt osztályokra bontjuk vizsgált genetikai sajátosságaik alapján. Az osztályok lehetnek adott allélok szerinti genotípusok, vagy fenotípusok. Az osztályokra ható erőket váltogatva, esetleg egyeseket kihagyva, vagy másokkal helyettesítve újabb modellekhez jutunk. Strukturális alapon a modellcsalád újabb alcsaládjait kapjuk meg. A populáció életét, mint generációk egymásutánját tekintjük. Kiindulunk egy ős populációból, alkalmazzuk rá a generációváltáskor ható erőket, képezzük az utódgenerációt, amely egyben a következő generáció szülő-generációja lesz. Célszerű a modellben mindkét (szülő, utód) generáció megfelelőjét definiálni. Jelölések: - S-gen, U-gen: N darab egyedből áll; egy-egy egyedét a szülők

generációjának az S-gen(i), illetve az utódok generációjának az U-gen(i) jelenti. Az ősmodell érvényességi köre Az ősmodell filozófiája: Rögzített számú (N, esetleg N+M) egyed, amelyek születésük pillanatától halálukig rendelkeznek a kifejlett egyed minden, az annak az osztálynak jellemző tulajdonságaival, amelybe beletartozik. Érvényességek: - Rögzített egyedszám. - Időtől független egyedi lét. Születéstől a halálig teljes kifejlettség, azaz egyetlen korcsoport. Teljesen helyes a modell, ha a vizsgált tulajdonság korcsoporttól független - Generáció-váltás gongütésre. Az egyes generációk termékenységi időszakai nem átfedők. - Teljes generációváltás. Minden generáció egységnyi ideig él - Stacionárius (változatlan) hatóerők. Diploid, 1 lokuszos, 2 allélos alcsalád Az első alcsalád modelljeinek megalkotásakor a következő feltételeket vesszük figyelembe: - Diploid genotípusokat vizsgálunk. - A két nemet nem

különböztetjük meg. - Egy lokuszban előforduló alternatív allélokat vizsgálunk. - Egy lokuszban két allél fordulhat elő. Ezekben a modellekben minden egyedet két jellemzővel adhatunk meg, azzal a génpárral, amely a genotípusát meghatározza. Ezért N sorból és 2 oszlopból álló táblázatokat fogunk használni. Az ősmodellben megadott objektumok kódolása: - S-gen(N): S(N,2). - U-gen(N): U(N,2). Génkeveredés A diploid genotípus-gyakoriságok (bizonyos véletlenszerű ingadozástól eltekintve) illeszkedni fognak a megfigyelt géngyakoriságokon alapuló binomiális eloszláshoz, ha - Az allélok nem változhatnak (nincs mutáció). - A populáció zárt (nincs ki-, illetve bevándorlás). - A populáció egyedszáma elég nagy (nincs sodródás). - A heterozigóták a kétféle allélt egyforma arányban adják tovább gamétáikban (nincs meiotikus irányítottság, ivarsejt szelekció). 42 - Az egyes fenotípusok egyformán életképesek, szaporák

(nincs szelekció). A populáció pánmiktikus (a párválasztás teljesen véletlenszerűen történik). Ekkor látható, hogy a gének összekeveredése nem hoz létre evolúciót, a géngyakoriságok állandók maradnak, a diploid genotípusok gyakoriságai számíthatók ezekből. A vizsgált populáció legyen egy N egyedből álló egérpopuláció. A populáció egyedszáma minden szaporodás, generációváltás után azonos marad a korábbival, ezért csak az N szülő, illetve N utódegér megadásával kell foglalkoznunk. A modellekben a vizsgált tulajdonság az egerek színe lesz, amelyről feltesszük, hogy egy génpár határozza meg. Feltevésünk szerint az SS, illetve SF génpárral rendelkező egerek szürke színűek, az FF-ek pedig fehérek. Generáció váltás: Ciklus i:=1-től N-ig Ciklus j:=1-től 2-ig Szülőválasztás(k) Génválasztás(l) Génátadás(i,j,k,l) Ciklus vége Ciklus vége Eljárás vége Szülőválasztás(k): k:=véletlenszám(N) Eljárás

vége Génválasztás(l): l:=véletlenszám(2) Eljárás vége Génátadás(i,j,k,l): U(i,j):=S(k,l) Eljárás vége A modell működése során megfigyelhetjük, hogy a génkeveredés nem hoz létre evolúciót, így ilyen modell esetén nem beszélhetünk fejlődésről. Mutációs nyomás és egyensúly Mutációk előfordulásakor nemcsak új genetikai anyag keletkezik, amelyre az evolúciós erők hatást gyakorolhatnak, hanem bizonyos mértékig a géngyakoriságok is szükségszerűen megváltoznak. Mutáljon egy allél (R/generáció)-sebességgel egy más alléllá R-t mutációs rátának nevezzük. Modellünkben új genetikai anyag keletkezésével nem foglalkozunk, a mutációk csak a létező két allél között következhetnek be. Mutáció esetén három esetet különböztethetünk meg: - Az S allél P valószínűséggel átalakul F alléllá. - Az F allél Q valószínűséggel átalakul S alléllá - Az S allél P valószínűséggel átalakul F alléllá, s

ugyanakkor az F allél Q valószínűséggel átalakul S alléllá. 43 A mutációt modellünkben úgy értelmezzük, hogy a szülő bizonyos valószínűséggel nem azt az allélt adja tovább utódjának, amit ő kapott a szülőjétől, hanem éppen a másik allélt. Génátadás(i,j,k,l): Ha S(k,l) = ”S” akkor Ha véletlenszám < P akkor U(i,j):=”F” Különben U(i,j):=”S” Különben Ha véletlenszám < Q akkor U(i,j):=”S” Különben U(i,j):=”F” Elágazás vége Eljárás vége Megfigyelhetjük, hogy az első esetben az S relatív gyakorisága és így a szürke fenotípus relatív gyakorisága a P valószínűségtől függő sebességgel fog csökkenni, a fehér fenotípus nagyon lassan fog növekedni a populációban, elterjedése később jelentősen felgyorsul. A második esetben az F allél relatív gyakorisága csökken ilyen sebességgel, a fehér fenotípus viszont lényegesen gyorsabban fog csökkenni. A harmadik esetben a kezdeti

eloszlástól független egyensúly fog kialakulni. Ha csak egyszeri mutációt szeretnénk vizsgálni, akkor a szimulációs lépés végén a mutációs rátákat nullázni kell. Génáramlás A géngyakoriságok megváltoztatásának leggyorsabb módja genetikailag különböző egyedek bevándorlása egy populációba. Mi csak a fajon belüli génáramlással foglalkozunk, ahol a bevándorlási rátát változtatva vizsgáljuk a populáció génösszetételét. Legyen generációnként M darab bevándorló, s a genotípusukat tároljuk az S( , ) mátrix N+1N+M soraiban. Ha csak egyszeri bevándorlásról van szó, akkor a szimulációs lépés végén az M változó értékét nullára kell állítani. Az N+M egérnek ebben a modellben is pontosan N utódja szülessen. A génkeveredési modellben most ezért a szülőválasztást kell módosítani. Szülőválasztás(k): k:=véletlenszám(N+M) Eljárás vége Ez a leggyorsabb evolúciós hatóerő, egy generáció alatt is

lényeges változást hozhat létre. A génáramlás másik esete a kivándorlás. Ez modellezési szempontból akkor lehet érdekes, ha azt a populációt is kezeljük, ahova az egyedek kivándorolhatnak. Genetikai sodródás A genetikai sodródás a géngyakoriságok mintavételi hiba okozta megváltozása. Folyamatos sodródásról beszélünk, ha ez a helyzet több generáción keresztül is fennáll, egyszeri sodródásról pedig akkor, ha csupán egyetlen esetben fordul elő. A modellbe egyetlen új változót kell bevezetni, jelölje SK a szaporodóképes szülők számát a populáción belül. Ha egyszeri sodródásról van szó, akkor a szimulációs lépés végén SK értékét N-re kell állítani. Ebben a modellben is a szülőválasztást kell módosítani. 44 Szülőválasztás(k): k:=véletlenszám(SK) Eljárás vége Meiotikus sodródás Meiotikus sodródás miatt a génválasztást kell módosítani, méghozzá a heterozigóta szülők esetében. Megadjuk, hogy

egy heterozigóta szülő milyen arányban tudja továbbadni a kétféle allélt. Legyen R a domináns allél továbbadásának valószínűsége Génválasztás(l): Ha S(k,1) = S(k,2) akkor l:=1 Különben Ha véletlenszám < R akkor Ha S(k,1) = ”S” akkor l:=1 Különben l:=2 Különben Ha S(k,1) = ”F” akkor l:=1 Különben l:=2 Elágazás vége Eljárás vége Ebben a modellben a kétféle allél relatív gyakorisága folyamatosan változni fog. Irányító szelekció A természetes szelekció a genotípusok relatív gyakoriságainak megváltozása, ami annak köszönhető, hogy fenotípusaik különböző mértékben képesek képviseltetni magukat a következő nemzedékben. Megadható mindhárom relatív rátermettsége Ezek W1, W2, W3 Teljes dominancia esetén W1=W2, hiszen a szelekciós erő a fenotípusokra hat. Ebben az esetben a szülőválasztást kell módosítanunk, a különböző rátermettségű szülőket különböző valószínűséggel kell választani.

Szülőválasztás(k): Ciklus k:=véletlenszám(N) R:=véletlenszám amíg (S(k,1) ≠ S(k,2) és R ≥ W2) vagy (S(k,1) = ”S” és S(k,2) = ”S” és R ≥ W1) vagy (S(k,1) = ”F” és (S(k,2) = ”F” és R ≥ W3) Ciklus vége Eljárás vége Nem pánmiktikus populáció Az eddigi modellekben mindig teljesül a pánmixia feltétele, most azt vizsgáljuk, hogy az ettől való eltérés hogyan hat a géngyakoriságokra. A pánmixiától kétféle irányban lehet általában eltérni: - A hasonló típusok előnyben részesítik egymást (pozitív preferencia). - Az eltérő típusok részesítik egymást előnyben a párosodás során (negatív preferencia). Sokallélos alcsalád Ebben az alcsaládban a következő feltételeket vesszük figyelembe: 45 - Diploid genotípusokat vizsgálunk. A két nemet nem különböztetjük meg. Egy lokuszban előforduló alternatív allélokat vizsgálunk. A modellek objektumainak tárolásában az első alcsaládhoz képest nem lesz

változás, csupán az változik, hogy az S és U tömbökben nem kétfajta elem lehet, hanem sokféle. Az egyes jelenségek paramétereinek száma azonban ettől jelentősen megváltozik. Sokallélos génkeveredés Egy olyan populációban, amelyre semmilyen külső erő nem hat, a genetikai variabilitás gyors csökkenése figyelhető meg, az allélok száma fokozatosan csökken. Sokallélos mutáció A mutációt olyan erőnek tekinthetjük, amely képes a polimorfizmust fenntartani. Kis mutációs ráták esetén az allélok átlagos száma kicsi lesz, de ekkor sem szűnik meg véglegesen egyetlen allél sem. Nagy mutációs ráták elég biztosítékot jelentenek a nagy variabilitás fenntartására, ekkor kisebb a sodródás jelentősége, az allél gyakoriságok a mutációs rátáknak megfelelően fognak alakulni. Tiltott allélpárok Az eddigi modelljeinkben az utódok a szülőktől tetszőleges allélokat kaphattak, így tetszőleges allélpárok kialakulhattak. Most

vizsgáljuk meg azt az esetet, amikor ez nem áll fenn, azaz bizonyos allélpárok tiltottak. A modell továbbra is a kétallélos génkeveredésre alapozható, de nem lehet fenntartani a két szülőtől a független génválasztást. A homozigóta allélpárok képződését kell megakadályozni Ennek érdekében mindkét szülőt meg kell határoznunk, ki kell választani a tőlük kapott 2 allélt, s ha ezek megegyeznek (tiltott allélpár), akkor újra kell szülőket választani. A modell eredménye valamilyen stabil állapothoz való lassú közelítés. Kétlokuszos alcsalád Ebben az alcsaládban a következő feltételeket vesszük figyelembe: - Diploid genotípusokat vizsgálunk. - A két nemet nem különböztetjük meg. - Minden lokuszban két-két alternatív allél fordulhat elő. Újdonság, hogy nem egy, hanem több (jelen esetben két) lokuszt vizsgálunk. Itt a két lokusz miatt a táblázatnak négy oszlopa lesz. Az objektumok kódolása: - S-gen(N): S(N,4). -

U-gen(N): U(N,4). Szabad kombinálódás Modellünkben azzal az esettel fogunk foglalkozni, amikor a két lokuszban levő gének egymástól függetlenül öröklődhetnek (különböző kromoszómán vannak). Vizsgáljunk egy borsópopulációban a színek, illetve a formák öröklődését, azaz sárga-zöld (S,Z), illetve szögletes-gömbölyű (s,g) tulajdonságokat. Ez 9 genotípust jelent A két szülőtől kapott gének bármilyen kombinációja előfordulhat, a két szülő választása független egymástól, ezért használhatjuk az egylokuszos génkeveredés algoritmusát azzal a módosítással, hogy mindkét lokuszról kell választani, s átadni a gént. 46 A 9 genotípus gyakorisága hosszú idő elteltével kerül egyensúlyi állapotba. Adott létszámú populáció esetén itt sokkal nagyobb a sodródás jelentősége, mint az egylokuszos modellben volt. Kapcsolt gének Más a helyzet, ha a két lokuszon levő gének egymástól nem függetlenül öröklődnek

(azonos kromoszómán vannak). Ebben az esetben az öröklődési mechanizmus megakadályozza az egyensúlyi állapot kialakulását. A gének olyan kombinációja, amely kezdetben egyetlen kromoszómán sem fordult elő, a populációban sohasem fog megjelenni. Rekombináció Ritkán fordul elő, hogy a lokuszok között átkereszteződéses génkicserélődés történik. Ebben a modellben ezt fogjuk vizsgálni. A rekombináció relatív gyakorisága legyen R A modellben a rekombinációs gyakoriság értékétől függ az egyensúly beállásának a sebessége. Tetraploid alcsalád Ebben az esetben a következő feltételeket vesszük figyelembe: - A két nemet nem különböztetjük meg. - Egy lokuszban előforduló alternatív allélokat vizsgálunk. - Egy lokuszban két allél fordulhat elő. Tetraploid génkeveredés A diploid, egylokuszos génkeveredési modellnél láthattuk, hogy az egyensúlyi genotípus eloszlás az első generációban létrejön, tetraploid esetben ez nem

fog teljesülni. A gének kiválasztása lesz bonyolultabb, az első a négyből bármelyik lehet, a másodikat viszont a maradék háromból kell választani. Ebben a modellben az egyensúlyi genotípus gyakoriságok lassan alakulnak ki. Nemhez kötött tulajdonságok alcsaládja Ebben a modellben a következő feltételeket vesszük figyelembe: - Diploid genotípusokat vizsgálunk. - Egy lokuszban előforduló alternatív allélokat vizsgálunk. - Egy lokuszban két allél fordulhat elő. A nemet egy kromoszómapár határozza meg, amely kétféle kromoszómát tartalmazhat: X és Y. A nőnemű egyedeknek XX, a hímneműeknek XY kromoszómapárjuk van Génkeveredés X-kromoszómán Az X kromoszómán öröklődő tulajdonságokat vizsgáljuk. A diploid, egylokuszos alcsaládban létrehozott táblázatot fogjuk használni, azzal a különbséggel, hogy az Y kromoszómán a megadott gén nem fordulhat elő, ezt a táblázatban *-jel jelöli. Ebben a modellben két különböző nemű

szülőt kell választani. Itt az egyensúlyi genotípus gyakoriságok fokozatosan állnak be. Egyensúly esetén a két nem allélgyakoriságai azonosak lesznek Génkeveredés Y-kromoszómán Most a megadott gén az X kromoszómán nem fordulhat elő, így ez csak a hímnemű egyedeknél fordulhat elő. Az előzőhöz hasonlóan tehát az X kromoszómán helyezzük el a *ot. 47 Ökológia Egy modellcsaládot fogunk létrehozni. Mindegyik modellben szerepe lesz annak, hogy a különböző egyedek találkozzanak egymással, így a szimulációt egy N*M-es mezőn fogjuk lejátszani. Ezen a mezőn betűk fogják jelölni az egyes egyedeket A folytonos keretmodellt fogjuk használni. A modellcsalád érvényességi köre A modellcsaládban néhány szűkítő feltételt veszünk figyelembe: - Időfüggetlen egyedi lét (nincs korlát az életkorra). - Adott eloszlású élettartam. - Születéstől a halálig teljes kifejlettség. - Homogén fajok (nincs szelekciós különbség). - A

nemeket nem különböztetjük meg, a születéshez egy egyed elegendő. - Irányítatlan mozgás. - Az egyéb külső erőket csak statisztikus hatásuk eredőjével vesszük figyelembe. - A születés-halálozás a táplálkozáshoz képest erősen felgyorsított. - A táplálkozás a mozgáshoz képest erősen felgyorsított. - Egyszerre csak egy utód születhet. Zsákmányszerzés Első közelítésben két alapesettel foglalkozunk: állatok állatok általi megevésével (ragadozás) és a növényevéssel. Ragadozás Vizsgáljuk két állatfaj (ragadozó, zsákmány) egyedszámának egymásra hatását, a ragadozó csupán az egyetlen zsákmány faj egyedeiből él, a zsákmány szaporodását pedig a maximális élettéren kívül más tényező nem befolyásolja. A modellben megadjuk mindkét fajta egyed szaporodásának, illetve halálozásának szabályait, továbbá egymásra hatásukat: - Egy időegység alatt minden egyednek RS, illetve ZS valószínűséggel van utódja.

Az utód a szülő mellett helyezkedik el. - Egy időegység alatt minden egyed adott valószínűséggel (RH, illetve ZH) hal meg. - Egy ragadozó mindenképpen meghal, ha nincs mellette zsákmány. - A ragadozó a mellette levő zsákmányállatok közül egyet megeszik. - A ragadozó éhenhal, ha nincs mellette zsákmány. Szimulációs lépés: (i,j):=véletlen hely(N,M) Elágazás Tér(i,j) = ”R” esetén Ragadozó változása(i,j) Tér(i,j) = ”Z” esetén Zsákmány változása(i,j) Elágazás vége Mozgás(i,j) Eljárás vége Ragadozó változása(i,j): Szomszédkeresés(”Z”,VAN,SI,SJ) Ha nem VAN vagy véletlenszám < RH akkor Tér(i,j):=” ” Különben Ha véletlenszám < RS akkor Tér(SI,SJ):=”R” Különben Tér(SI,SJ):=” ” 48 Elágazás vége Eljárás vége Zsákmány változása(i,j): Ha véletlenszám < ZH akkor Tér(i,j):=” ” Különben Szomszédkeresés(” ”,VAN,SI,SJ) Ha VAN és véletlenszám < ZS akkor Tér(SI,SJ):=”Z”

Elágazás vége Eljárás vége Mozgás(i,j): (k,l):=véletlen szomszéd(i,j) csere(Tér(i,j),Tér(k,l)) Eljárás vége Megfigyelhetjük, hogy nagyon sok esetben a két populáció egyedszáma periodikusan ingadozik, az egyik populáció valamilyen késéssel követi a másikat. Növényevés Vizsgáljuk most egy növény és egy ezt fogyasztó állatfaj létszámának alakulását, ha más erő nem hat rájuk. Az egymásra hatást és a születés-halálozás szabályait itt is megadjuk: - Mindkét faj egy egyede minden időegység alatt AH, illetve NH valószínűséggel hal meg. - A növényevő minden időegység alatt AS valószínűséggel hoz létre egyetlen utódot. - Üres helyen növény nőhet, ha van szomszédos növény, ami erre a helyre szórja a magját, a mag NS valószínűséggel kel ki. - A növényevő éhenhal, ha nincs mellette növény, egy növényt mindenképpen elfogyaszt. Felmerül néhány probléma: - A növény nem tud mozogni. - Ha a növényre

rálépnek, attól még megmarad. - Ha a növényt lelegelik, akkor még a gyökere megmarad. - Ha a növény elszárad, a gyökere akkor is épségben marad. A mozgás megoldására a vizsgált teret bontsuk fel két síkra. Az egyikben élnek a növények (NT(N,M)), a másikban az állatok (AT(N,M)). Ekkor mozgás csak az AT( , ) táblázatban lesz Növényből vezessünk be kétfajtát: N legyen a teljesen kifejlett növény, n pedig a nem teljesen kifejlett növény. Szimulációs lépés: (i,j):=véletlen hely(N,M) Ha AT(i,j) = ”A” akkor Növényevő változása(i,j) Elágazás NT(i,j) = ”N” esetén Növény változása(i,j) NT(i,j) = ”n” esetén Kis növény változása(i,j) NT(i,j) = ” ” esetén Növény születése(i,j) Elágazás vége Mozgás(i,j) Eljárás vége 49 Növényevő változása(i,j): Szomszédkeresés(NT(),”N”,VAN,SI,SJ) Ha nem VAN vagy véletlenszám < AH akkor AT(i,j):=” ” Különben NT(SI,SJ):=”n” Szomszédkeresés(AT(),”

”,VAN,SI,SJ) Ha VAN és véletlenszám < AS akkor AT(SI,SJ):=”A” Elágazás vége Eljárás vége Növény változása(i,j): Ha véletlenszám < NH akkor NT(i,j):=” ” Különben Ha véletlenszám < NE akkor NT(i,j):=”n” Eljárás vége Kis növény változása(i,j): Ha véletlenszám < NH akkor NT(i,j):=” ” Különben NT(i,j):=”N” Eljárás vége Növény születése(i,j): Szomszédkeresés(NT(),”N”,VAN,SI,SJ) Ha VAN és véletlenszám < NS akkor AT(i,j):=”n” Eljárás vége A modell használata során megállapítható, hogy a növényevés hatása hasonló a ragadozáshoz. Közvetett kapcsolattípusok Ezután populációk versengésével, szimbiózisával foglalkozunk. Állatok együttélése Vizsgáljunk két fajt (A és B). Egy időegység alatt minden egyedük AS, illetve BS valószínűséggel születik utódja; AH, illetve BH valószínűséggel hal meg. Minden egyednek a környezetében AK, illetve BK mennyiségű táplálékra van

szüksége. Van csak az A által, van csak a B által, és van közösen fogyasztott táplálék. A rendelkezésre álló összes táplálékmennyiség OM. A két populáció egymásra hatását a BA és az AB paraméterekkel befolyásolhatjuk. Amikor mindkettő pozitív értékű, akkor a két faj versengéséről beszélhetünk. Alapvetően 3 eset fordulhat elő: - Stabil egyensúlyi állapot alakul ki. - Az egyik populáció kihal. - A két populáció aránya teljesen véletlenszerűen változik. 50 6. tétel Nagypontosságú aritmetika Egész számok A szám: x n x n-1 x 2 x 1 x 0. Sok számjegy esetében praktikus az előjelet és a számot külön tárolni. Tárolni kell: Hossz, számjegyek, előjel, számrendszer (alapszám). Alapműveletek: +, -, *, div, mod, relációk. Összeadás Legyen a két szám: x = (x n x n-1 x 1 x 0 ) és y = (y m y m-1 y1 y 0 ). Két szám összeadásánál 4 esetet különböztetünk meg. Ha - x ≥ 0 és y ≥ 0. - x < 0 és y < 0:

-(|x|+|y|). - x ≥ 0 és y < 0: x-|y|. - x < 0 és y ≥ 0: -(y-|x|). Mindig az első számnak kell a hosszabbnak lennie. A rövidebb szám hosszáig adunk össze, utána csak átvitelt számolunk. A rövidebb számot ki kell egészíteni 0-kal Kivonás Mindig a hosszabb számból vonjuk ki a rövidebbet. Az összeadáshoz hasonlóan történik Az eredmény elejéről a felesleges 0-at el kell távolítani. Szorzás Az eredmény hossza előre kiszámolható a két tényezőből. Mivel a hagyományos számolás túl sok helyet foglalna és túl sok számolást igényelne, ezért helyette azt a módszert alkalmazzunk, hogy amikor megvan egy szám az eredményből, azt azonnal megadjuk, így kevesebbet kell számolni. Osztás Hányados: h:=x div y. Maradék: m:=x mod y Osztás: h:=0 m:=x Ciklus amíg m ≥ h m:=m-y h:=h+1 Ciklus vége Eljárás vége Ezzel az eljárással a baj, hogy nagyon lassú. Hatékonyabb, ha N : M számoknál: N-1 : M-1, ahol N és M a két számnak a

hossza, megbecsüljük az eredményt. Például: 123 : 45 ⇒ 12 : 4 De a becslés lehet rossz is, amit javítani tudni kell, maximum 2 korrigálással megvan a hányados. 51 Relációk X < Y? (X: N hosszú, Y: M hosszú) Ha mindkét szám azonos előjelű, akkor - Igaz, ha N < M. - Hamis, ha N > M. - Ha N = M, akkor a legmagasabb helyi értéktől kezdve meg kell keresni az első eltérést, és az dönti el, hogy melyik a nagyobb. Ha a két szám különböző előjelű, akkor - Igaz, ha X negatív és Y pozitív. - Hamis, ha X pozitív és Y negatív. Speciális eset - X*Y:= - XY:= { { X, ha Y = 1. (2*X)(Y/2), ha Y páros. X+X*(Y-1), ha Y páratlan. X, ha Y = 1. (X*X)Y/2, ha Y páros. X*(XY-1), ha Y páratlan. Racionális számok A szám: u s /v n = u s u s-1 u 1 u 0 /v n v n-1 v 1 v 0 (számláló/nevező). Tárolni kell: Hossz, számláló számjegyei, nevező számjegyei, előjel, számrendszer (alapszám). Alapműveletek: +, -, *, osztás. Összeadás,

kivonás Közös nevezőre hozás, aztán a művelet elvégzése, majd egyszerűsítés a legnagyobb közös osztóval. Szorzás Számlálót a számlálóval, nevezőt a nevezővel kell megszorozni, majd egyszerűsítés a legnagyobb közös osztóval. Osztás Osztásnál az osztó reciprokával kell szorozni, majd egyszerűsítés a legnagyobb közös osztóval. Legnagyobb közös osztó 1, ha u = 1 és v = 1.  u, ha u = v.   2*LNKO(u/2,v/2), ha u és v páros.  LNKO(u,v):=  LNKO(u/2,v), ha u páros és v páratlan. LNKO(u,v/2), ha u páratlan és v páros.   LNKO(u-v,v), ha u > v és mindkettő páratlan.  LNKO(u,v-u), ha u < v és mindkettő páratlan.  52 Fixpontos valós számok A szám: x n x n-1 x 1 x 0 *x -1 x -2 x -m Tárolni kell: Előjel, számrendszer (alapszám), n, m, számjegyek. Alapműveletek: +, -, *, osztás. Összeadás, kivonás Feltétel, hogy x,y ≥ 0 és x ≥ y. Egymás alá kell helyezni a tizedespontokat Szorzás

Ugyanúgy, mint az egész számoknál. Azt, hogy a tizedespont hova kerül, ki lehet számolni A végéről a felesleges 0-at el kell hagyni. Lebegőpontos számok A szám: 0.x -1 x -2 x -m *szk Tárolni kell: Előjel, számrendszer (alapszám), m, k, számjegyek. Alapműveletek: +, -, *, osztás. Összeadás Közös kitevőre kell hozni a két számot, így egymás alá igazodnak a tizedespontok. Végül az eredménynél léptetni kell a tizedespontot, hogy ismét 0.xxxxxx alakú számot kapjunk Szorzás Ugyanúgy, mint az egészeknél, csak itt is léptetni kell a tizedespontot. Számrendszerek közötti konverzió: XAXB Nincs garancia arra, hogyha A-ban véges a tört, akkor B-ben is véges lesz, és fordítva. Speciális esetek - A=BK 1 számjegyből lesz több. - AK=B több számjegyből lesz 1. Egészrész - B-vel való osztás A alapú számrendszerben. - A-val való szorzás B alapú számrendszerben. x 0 +x 1 *A+x 2 A2++x n An=x 0 +A(x 1 +A(x 2 +)) Törtrész - B-vel való

szorzás A alapú számrendszerben. - A-val való szorzás B alapú számrendszerben. x -1 *A-1+x -2 A-2++x -m A-m=1/A(x -1 +1/A()) Speciális számrendszerek - Reciprok számrendszer: Például 1/10-ed alapú. - Negatív alapú számrendszer: Például –10 alapú. - Faktoriális: Helyi értékenként más az alapszám. 53 Nevezetes számok közelítése 2 1  2   *  x n + 2  x n  Pell-egyenlet: P2–N*Q2 = 4 végtelen sok megoldása van, ha N nem négyzetszám. Héron képlet: x n +1 := N=2 esetén: P 1  2  Pn2 − 2 P  = Ha xn = n alakú, akkor x n +1 := *  x n + = n +1 szintén megoldása a PellQn 2  x n  Pn * Q n Q n +1 egyenletnek. P lim n = 2 . n ∞ Qn (P0,Q0) megkeresése: (P,Q):=(1,1) Ciklus amíg P2-2*Q2 ≠ 4 Ha P2-2*Q2 < 4 akkor P:=P+1 Különben Q:=Q+1 Ciklus vége Eljárás vége Tehát csak egész számokkal kell dolgozni, szorzás és kivonás műveletre van szükség. e ∞ 1 1  1 1  e = lim(1 + t ) t =

∑ = 1 + 1 + * 1 + (.) t 0 2  3  i = 0 i! π - Nevezetes törtek (256/81 ≈ 3.16, 22/7 > π > 223/71) π 2 * 2 4 4 6 6. 1 * 3 3 5 5 7. - Wallis formula: - Kör közelítése szabályos sokszögekkel - π = 24 * arctg + 8 arctg 2 = 1 1 1 + 4 * arctg 8 57 239 3 5 7 x x x arctg(x ) = x − + − + . 3 5 7 Kombinatorikai algoritmusok Általában a backtrack algoritmust használjuk, de bizonyos speciális esetekre megy nem a backtrack algoritmussal. 54 Az összes lehetőség előállítása Csak kis n-re ábrázolható (n < 10). Permutáció: Ha n-1 elem összes permutációja kész, akkor szúrjuk be az n.-et minden lehetséges helyre, mindegyikbe! Részhalmazok: Minden részhalmazhoz rendelünk egy n hosszú 2-es számrendszerbeli számot (ha n elemű az eredeti halmaz), és 1-es áll benne azon a helyiértéken, amelyik szám benne van a részhalmazban. Kompozíciók (k db részhalmaz diszjunkt uniójaként előállítás): Olyan

k-jegyű számok, ahol a számjegyek összege pontosan n. Kombináció: Az n elemből k elemet kiválasztunk, a sorrend nem számít. Variáció: Az n elemből k elemet kiválasztunk, számít a sorrend. Partíció (m db részhalmaz nem diszjunkt előállítása): Olyan m-jegyű számok, ahol a jegyek összege n. Az i. előállítása Variáció: Az i felírása k alapú számrendszerbe. Részhalmaz: Az i szám bináris alakjának meghatározása. Egy véletlen előállítása Variációk: Kombináció+permutáció. Permutációk: Rendezés tétel módosításával előállítható úgy, hogy egy véletlenszámút cseréljen fel az 1.-vel Akkor jó, ha minden helyre egyenlő valószínűséggel kerülhet a kiválasztott elem. Függvényábrázolás Egyváltozós függvények ábrázolása Jelölések: - OX: Az X=0-hoz tartozó oszlopkoordinátája a képernyőn. - OY: Az Y=0-hoz tartozó sorkoordinátája a képernyőn. - NX, NY: X-, illetve Y-irányú nyújtási tényező. Ahogy

jön egymásután a pont, úgy rajzoljuk a képernyőre. Annyit transzformálunk csupán, hogy az origó a képernyő (OX,OY) pontjára essék, s az Y koordinátatengelyt megfordítjuk. Ez a legegyszerűbb rajzolási módszer, azonban nagyon sok probléma léphet fel használata során. Elképzelhető az is, hogy az ábra nem fér rá a képernyőre, vagy éppen ellenkezőleg, nagyon kis részét használjuk ki. Képernyőre normálás Az előbbi problémák kiküszöbölése érdekében most a kirajzolás közben a pontokat normáljuk, mégpedig úgy, hogy a lehető legjobban használjuk ki a képernyőt. A normálás során elmozdulhatnak a koordinátatengelyek, ezért ezek helyét számolni kell az X=0, illetve Y=0 értékekből. 55 Az előző változathoz képest újabb problémák jelentek meg. Mivel NX és NY különböző lehet, ezért a függvény képe torzult lesz. A normálás miatt az origó elmozdul a kép közepéről, sőt elképzelhető, hogy valamelyik tengely

nem lesz rajta a képen. Elkerülhetjük ezt a nem kívánt effektust, ha a két nagyítási tényezőből a kisebbet használjuk mindkét irányú nagyításra. Ez a megoldás a problémákból egyet megold, vagyis az aránytalanság megszűnik. Az origó akkor marad a helyén, ha az ábrázolt értékkészlet, illetve értelmezési tartomány is szimmetrikus az origóra. Ezt úgy érhetjük el, ha a függvény értékkészlete, illetve értelmezési tartománya szerint is az abszolútértékekből számoljuk a megjelenítendő tartomány méretét. Az origó helyét itt újra a képernyő méreteiből számolhatjuk. Most már csak egyetlen probléma maradt, vagyis az egyetlen, gyorsan változó függvények menete a kirajzolt pontok alapján nem túl jól látszik. Pontok összekötése egyenessel A függvény menetét az eddigi módszerek nemigen tudták visszaadni. A probléma okozója az volt, hogy a függvény diszkrét pontokból állt, s nem volt folytonos. A legkézenfekvőbb

megoldás, ha minden egyes kirajzolt pontot összekötünk az előzőleg kirajzolt ponttal. Ezzel az ábrázolással a függvény már folytonos görbeként jelenik meg, csupán az lehet csúnya egyes függvényeknél, hogy a képen jelentős törések is látszhatnak. A pontoknak megfelelő magasságú téglalap rajzolása Rajzoljunk a kép aljától a függvényértékeknek megfelelő magasságig egy téglalapot. A téglalap értelmezési tartománybeli pontra szimmetrikus, a képernyőn látható lépésköznek megfelelő szélességű legyen. Kifejezőbb, ha a téglalapok egyik éle mindig az X-tengelyen nyugszik. Tetszőleges pontban kiszámítható függvény A tapasztalataink az mutatják, hogy sokkal szebb képet kapunk, ha a függvényt elég sűrű felosztás esetén számítjuk ki, s akkor csúnya az ábra, ha csak kevés pontban rendelkezünk róla információval. Erre épül az újabb módszerünk Ha a függvényt tetszőleges pontban kiszámítjuk, akkor úgy válasszuk

meg az értelmezési tartománybeli pontokat, hogy a szomszédos pontok képei a képernyőn is szomszédos pontban legyenek. Paraméteres görbék Vannak olyan görbék, amelyeknél a fenti módszer nem alkalmazható, egy X értékhez ugyanis több Y érték tartozhat. Ilyen például a kör, az ellipszis, stb Ezek esetén úgy járhatunk el, hogy az f(x,y)=0 egyenletet átírjuk egy új változó (paraméter) függvényébe: x(t)=f 1 (t), y(t)=f 2 (t) alakba. Kétváltozós függvények ábrázolása Szintvonalas ábrázolás Lényege, hogy adott magasságértékekhez tartozó pontokat valamilyen vonallal összekötjük, s ez a vonalas minta adja meg a magasságeloszlást. Ennél a módszernél felülnézeti képet rajzolunk. Probléma lehet, hogy a szintvonalak nagyon szögletesek, azaz éles törések láthatók rajtuk. Ez abból adódik, hogy egy négyzetháló szakaszaiból állítjuk össze a képet. Másik baj, hogyha egy pont pár között két vagy több szintvonalnak

kellene haladnia, akkor a szintvonalak egymásra érnek, s így a különböző magasságú területek erősen összeolvadhatnak. Ezt viszont 56 az okozza, hogy első elképzelésünk szerint a szintvonalakat a két ismert érték helye között pontosan középen húzzuk. Színezett szintvonalas ábrázolás Még jobban megkülönböztethetnénk az egyes szinteket, ha különböző színűre festhetnénk őket. Tegyük fel, hogy minden szint olyan, hogy a zárt tartományai tartalmaznak legalább egy ismert pontot is. Ekkor ugyanis lehetőségünk lesz arra, hogy egy elkészült szintvonalas képet az ismert pontokból kiindulva befessünk. Gradiens ábrázolás Egy másfajta ábrázolás az, amikor minden egyes ponthoz a legnagyobb növekedés irányát határozzuk meg, s ábrázoljuk valamilyen módon. Színárnyalatos ábrázolás A domborzat visszaadásának másik módja lehet, ha az adott pontbeli magasságot valamilyen globálisabb vizuális jellemzővel szimbolizáljuk,

például színnel vagy tónussal. Kifejező ábrát akkor kapunk, ha széles skálája áll rendelkezésünkre a színeknek vagy árnyalatoknak. Minden ponthoz rendeljünk hozzá egy a magasságának megfelelő színárnyalatot. Pszeudoplasztikus ábrázolás Egy nagyon érdekes ábrázolásban nem az egyes pontok értékei alapján rajzolunk, hanem a pontokban megfigyelt változás alapján. Ekkor olyan jellegű képet kapunk, mint amit akkor láthatnánk, ha a háromdimenziós felülettől valamilyen irányban elhelyeznénk egy fényforrást, s a megvilágítottság fokától függően rajzolnánk. Ebben az esetben a fényforrás irányába néző felületek magas fényűek lesznek, az éppen ellenkező irányba nézőek pedig sötétek. Pontfelhős ábrázolás Ha szerényebb képességű a gépünk, akkor is van módunk a fenti elven megjeleníteni a felületet: csak utánoznunk kell valamiképpen az árnyalatokat. Legkézenfekvőbb, ha az árnyalatoknak pontsűrűséget

feleltetünk meg; a sötétebbnek kisebb sűrűségűt, a világosabbnak nagyobbat. Így létre kell hoznunk egy mintázatsorozatot, s a megfelelőt kell az egyes pontokhoz tartozó cellába belerajzolni. Ehhez azonban az összes mintát vagy raszter mintaként vagy mintát rajzoló eljárásként kell tárolnunk, ami kellően memóriaigényes. Árnyékolt téglalapos ábrázolás Az elkövetkezendő módszerek mindegyikének legfőbb gondja az lesz, hogy miként tüntesse el a nem látszó, úgynevezett takart részeket. Az elsőként tárgyalt eljárás lényege, hogy minden felületbeli ponthoz egy arányos magasságú oszlopot rendel. A takarás problémáját igen egyszerű ötletre építve oldja meg: hátulról előrefelé haladva rajzolja az oszlopokat úgy, hogy kicsit nagyobb oszlopnyit letöröl a háttérből. Y szerinti függvénymetszetek, tömör testként Ezen eljárás lényege, hogy a felületet mint valahány egymástól független (Y szerinti) függvényt tekinti,

melyeket vonalas ábrával jelenít meg. A függvényeket a görbéjük alatti területtel együtt tömör, tehát átlátszatlan lapként szemléli. Itt is a függvény oldalnézeti képét ábrázoljuk. A nem látszó vonalrészek elhagyását azzal oldjuk meg, hogy már ki sem rajzoljuk őket. 57 X és Y szerinti függvénymetszetek, tömör testként Az előző algoritmus annyiban módosul, hogy minden pontot kössünk össze az előzőleg rajzolt függvény megfelelő pontjával. X és Y szerinti függvénymetszetek, lepelként Az előző két eljáráshoz képest lényeges filozófiabeli eltérést mutat ez és a következő eljárás. Ugyanis itt a függvények, mint egy háló egyetlen fonalsora képzelendők el. Festett négyszögek pontnégyesként Az eddigi módszerekkel ellentétben itt úgy oldjuk meg a nem látszó vonalak elhagyását, hogy a takaró lapokkal töröljük le őket. Hátulról előre haladva rajzolunk minden pontnégyeshez egy-egy négyszöget, a

négyszög belsejét töröljük, határvonalát rajzoljuk. Itt csupán az okozhat problémát, ha olyan torzult négyszöget kellene ábrázolni, amelynek oldalai a képen egymást metszenék. Ekkor a négyszögrajzolás állhat négy szakasz kirajzolásából, a négyszögtörlést viszont úgy kell megoldani, hogy csak az ilyen furcsa négyszög belsejében levő két háromszöget töröljük. 58 7. tétel Geometriai és raszteres képek elemei Raszteres kódolás A raszteres képkódolás egy téglalap alakú képfelület diszkrét, rendezett mintavételezését (sampling) jelenti: a téglalap alakú képmezőt véges számú vízszintes pásztára, sorra (scan-line) és függőleges oszlopra bontjuk és az így kapott képpontokban (pixel) látható színárnyalatot egy-egy képpontértékkel adjuk meg. Árnyaltnak nevezzük azokat a képeket (shaded picture), amelyeken jellemző alakú képelemek nem írhatók le egyértelműen (reprodukálható módon). Ezekben a

szomszédos képpontok színe helyenként folytonos átmenetet követ, és ezért kódolásánál a kép valamennyi pontjának színét külön-külön meg kellene adni. Az így kódolt kép kirajzolása esetén az egyes képpontokba az ezen értéknek megfelelő színű négyzet, vagy kör alakú foltot festünk, amelyek az eredeti képhez közeli ábrát eredményeznek. Színes képek esetén az egyes képpontokban tárolt színérték vagy a szín három összetevőjének viszonylagos erősségét megadó számhármas („közvetlen színérték”), vagy egy közvetlen színértékeket tartalmazó színtáblára, palettára vonatkozó színindex. A sorokba és oszlopokba rendezett képpontokat nevezzük raszternek. A raszteres (raszteresen kódolt) képet egyszínűnek, nevezzük, ha a képpontok értéke kétféle – 0 és 1 – lehet: háttérszín és rajzoló szín. Színesnek nevezzük, ha többféle színezetet jelenthet és szürkeárnyalatosnak, ha a képpontok értéke

fehéret, feketét és különböző szürke árnyalatokat jelenthet. Színes és szürkeárnyalatos képek esetén a képpont értéke többféle is lehet, minden képpont tárolva egynél több bitet foglal el. Geometriai kódolás A geometrikus képek jól elkülöníthető, geometriailag jellemezhető képelemekből állnak. Ilyenek például a műszaki rajzok. Az ilyen képek kódolhatók a képet alkotó elemek fölsorolásával; az elemek geometriai alakjának megnevezésével és paramétereik megadásával. Az így kódolt képből előállított (látható-) kép lehet vonalas ábra, vagy raszteres megjelenítőkön lehet árnyalt ábra (shaded picture), amelyben a térbeliséget különböző színárnyalatokkal is érzékeltetjük. A képeket kódolhatjuk leíró nyelven, kódolhatják a képrögzítő eszközök és beviteli perifériák, kódoltan tároljuk adatszerkezetekben, kódoltan sorolják föl a képek elemeit a rajzoló eljárások, és kódoltan tárolnak a

képfájlok. Ezek a kódolások hasonló, egymáshoz hasonló elemeket és szerkezetet használnak, az egyes esetekben a célnak megfelelő formában. A kódolt kép mindezen esetekben képelem fölsorolása; megadva az egyes elemek típusát, paraméterként helyét a képsíkban és méretadatait, valamint a további látványelemeit meghatározó „attribútumokat”. A leírónyelvek olvasható, szöveges formában kódolják a képeket. Az ilyen képleírás célja lehet adatok előkészítése egy program kipróbálásához, teszteléséhez, lehet a képek archiválása, vagy képek átvitele (export-import) programok között adatátvitellel, vagy fájlokon keresztül. Gyakran nem képelemeket, hanem geometriai alakzatokat sorolunk fel, akkor geometriai modell leírásról beszélhetünk. Térbeli testek leírására alkalmazzák a VRML nyelvet 59 Képelemek és attribútumok Pontszerű képelemek - Pontjelölő (marker, markerjel): A rajzok egyes pontjainak jelölésére

szolgál. Geometriai paramétere a megjelölt pont koordinátái. A látványát befolyásoló attribútumok általában: a markerjel típusa (pont, kereszt, X, csúcsára állított rombusz, stb.), mérete, színe, stb - Poly-marker: Pontjelölők sorozata egyetlen képelemként. Paramétere a pontok száma és a pontok koordinátái. Attribútuma az előbbieken kívül lehet még az a választás, hogy a pontsorozatot kösse össze vonal (függvénygörbe közelítése), vagy ne. Vonalas képelemek - Egyenes szakasz (line, straight line segment): Paramétere: a két végpont koordinátái. - Sokszögvonal (polyline): Egymáshoz csatlakozó szakaszok. Paramétere: a pontok száma és azok koordinátái. - Szakaszok sorozata (disjoint polyline): Paramétere: a szakaszok száma, a szakaszok kezdő- és végpontjainak koordinátái. - Téglalap vonal (rectangle): Paramétere: két átellenes sarokpont koordinátái. - Kör (circle), ellipszis (ellipse): Paramétere: középpontja és a

kör sugara, illetve az ellipszis kis és nagy tengelyének egy-egy végpontja. - Körív (circular arc), ellipszis ív (elliptic arc): Paramétere: az előbbieken kívül az ív kezdő és végpontja. - Közelítő görbék: Például spline-görbék. - Vonalak: Attribútumai általában: a vonal színe, típusa, vastagsága. Előfordul még: a vonal végződése, sokszögvonal lekerekítése, stb. Tömör területelemek - Sokszög-lemez (polygon): Paramétere: a csúcsok száma és ezek koordinátái. - Téglalap lemez: Paramétere: bal alsó és jobb felső csúcsának koordinátái. - Kör és ellipszis lemez: Paramétere: mint a vonalas elemeknél. - Kör és ellipszis cikk, illetve szelet: Paraméterek: mint a kör és ellipszis ívnél. - Sokszöghalmaz: Paraméterei: sokszögek száma a halmazban és minden sokszögre csúcsainak száma és ezek koordinátái. - Attribútumok: Az alakzat körvonalának vonalas attribútumai és a kitöltés tulajdonságai: színe, mintázata.

Feliratok, szöveges képelemek - Felirat (text): Paraméterei: egy szövegfüzér (string) és az elhelyezésére kitüntetett pont koordinátái. - A felirat legtöbbször a kép síkjában helyezkedik el, néha a tér egy tetszőleges síkjában, ritkán egy görbült irányt követően. - Leggyakoribb attribútumok: A szövegszerkesztőkben használt stílusjegyek némelyike, a felirat illesztésének módja az adott ponthoz. Összetett képelemek - Egyes rendszerekben több, egymás utáni elem vonal összevonható egyfajta zárójelezéssel. - Több, egymással összefüggő szakasz és görbe vonaldarab összevonható zárt kontúrrá. Használható akár vonalas elemként, akár egy tömör terület határaként. - Az összevonás lehet egyszintű, vagy lehet hierarchikus. - Célja lehet: Ismétlődő képrészek definíciója és többszöri, esetleg paraméteres fölhasználása, vagy az interaktív manipuláció egységeinek megadása. 60 Térbeli görbék - A tér egy

síkjában előforduló vonalas elemek. - A tér egy síkjában előforduló valódi térgörbék. Térbeli felület elemek A tér egy síkjában előforduló területelemek, illetve felületek közelítéseként: - Háromszögsáv: Egymáshoz csatlakozó háromszögek sorozata. - Négyszögháló. Logikai műveletek az új képelem és a meglévő kép között A képpont-pufferba való beírásnál a másolt pontlap pontjai legtöbbször egy másik pontlap helyére kerülnek. Előírható azonban az is, hogy a forrás minden képpontjának értéke és a rendeltetési helyén lévő érték között egy bitenkénti logikai művelet kerüljön végrehajtásra a beírás előtt. Ennek a két operandusú rasterOp műveletnek a kódja legtöbbször a következők valamelyike lehet: - GPUT, vagy GCOPY: Egyszerű beírás, a tárgytól függetlenül. - GNOT: A forrás bitenkénti ellentettjének beírása. - GXOR: A forrás és tárgy bitenkénti xor-jának beírása. - GOR: A forrás és

tárgy bitenkénti or-jának beírása. - GAND: A forrás és tárgy bitenkénti and-jének beírása. Több bites képpont értékeken bitenként végzett rasterOp műveletek eredménye újabb képpont érték, de ennek színhatása nem magától érthető. Különösen akkor nem, ha a képpont érték szín index; két színindex xor-ja egy újabb színindexet ad. Ilyenkor a művelet eredménye a színtábla tartalmától függően különböző látványt eredményezhet. Egybites képpont értékek esetén azonban az eredmény jól követhető a logikai műveletek meghatározása alapján (a not művelet például a kép inverzét állítja elő). Egyes rendszerekben a rasterOp kód még más értékeket is fölvehet, illetve vannak három és négy operandusú rasterOp műveletek is. Grafikai input és output perifériák A lapolvasó (szkenner) egy papírlap képét (ami szöveg is lehet) raszteresen kódoltan küldi be a számítógépbe, ahol a kódolt kép ugyanígy, raszteres

adatszerkezetben tárolódik. A digitális fényképezőgép, kamera, ugyancsak raszteresen kódolja a téglalap alakú látómezejébe eső térrész vetületét. A képernyők és a nyomtatók raszteres rajzperifériák, a raszteresen kódolt képet maguk is a képfelület raszterén jelenítik meg; vízszintes pásztákban elhelyezkedő képpontokba elhelyezett színes foltokkal. Egy fekete vonalakból álló műszaki rajz képe a képernyőn ténylegesen raszteres kép (fehér felületen fekete raszterpontokból áll), bár tartalmát tekintve geometrikus képnek, vonalas ábrának nevezzük. A digitalizáló tábla és a kisebb méretű tablet geometrikus képek bevitelére szolgál. A táblára fektetett papíron egy mutatóval (kurzor, vagy ceruza formájú stílus) pontok koordinátáit olvastatjuk le, nyomógombok, vagy egy menü segítségével kódolva a képelemek típusát: szakasz, körív, stb. Az így kódolt képet a program geometrikus adatszerkezetben tárolja, amely

adathordozókra geometrikus rajzfájlokba írható ki. A geometrikus rajzfájlokat tárolhatjuk olvasható, szöveges formában, vagy tömörebb, bináris alakban. 61 Nem olyan régen még használtak rajzgépeket, amelyek a vezérlő egységükkel vezérelt rajztollakkal vonalas rajzokat készítettek papírra. Rajzbevitel A számítógépbe rajzot vinni kétféleképpen lehet: - A már kész rajzot valamilyen periféria segítségével viszem a számítógépbe. - Egy rajzprogram segítségével berajzolom. Rajztárolás Rajzok tárolása a lemezen helyigényes, ezért mentése, tárolása lassú. Sokfajta formátum létezik: - Raszteresek: BMP (bitmap), GIF (tömörít is), JPG, PCX, TIFF. - Vektoros: CDR (CorelDRAW). Koordinátarendszerek és transzformációik A geometriai modellben a tárgyak helyét és méreteit az alkalmazásnak megfelelő valamilyen koordinátarendszerben adjuk meg, ezt világkoordináta-rendszernek (VKR), vagy alkalmazási koordináta-rendszernek

(AKR), néha modellkoordináta-rendszernek (MKR) nevezzük. A pontok koordinátái legtöbbször valós számok, az alkalmazástól függő valamilyen természetes mértékegységben. Gyakran előfordul, hogy ha egy részlet – például egy épület ablakai – többször is előfordul a modellben, akkor ezt megadhatjuk saját koordináta-rendszerében (SKR), és minden egyes előfordulásának helyét, állását és méretét egy elhelyező transzformációval adjuk meg. Ez legtöbbször hasonlósági transzformáció; tartalmazhat egy eltolást, egy elforgatást és egy léptékezést (nagyítást-kicsinyítést). A kép a képernyő (vagy nyomtató) képkoordináta-rendszerében (KKR) keletkezik. Ennek kezdőpontja a képernyő bal-felső sarkában van, az X tengely jobbra, az Y tengely lefelé mutat. A képpontok koordinátái egész számok, amelyek nulla és a képernyő fölbontásától függő legnagyobb érték közé esnek (egy 800x600-as fölbontású képernyőnél 799

illetve 599). A különböző műveletek további koordináta-rendszerek használatát kívánhatják. Előfordul, hogy a képet először egy normált képkoordináta-rendszerben (NKKR) képfelületként kijelölt egységnégyzetben állítja elő (a koordináták 0 és 1 vagy -1 és +1 közé eső valós számok), majd innen másolják át a képernyőre. NKKR helyett használnak néhol virtuális képkoordináta-rendszert (VKKR), amelyben a képkoordináták 16 bites egész számok. A tárgy egy adott pontjához rögzítve, a tárgyra jellemző tengely irányokkal adható meg a TKR (tárgykoordináta-rendszer), más szóval RKR (referenciakoordináta-rendszer). Egy elképzelt szemlélőhöz, vagy kamerához viszonyítjuk a SZKR-t (szemkoordinátarendszer, kamerakoordináta-rendszer). A középpontos vetítésnél alkalmazott projektív transzformációval a nézetmező csonka gúlája egy téglatestre képezhető le, amelyhez az NPKR (normált projektív koordináta-rendszer)

tartozik. A VKR (AKR, MKR), TKR és a SZKR használata esetén, minden olyan esetben, ahol a tárgyak adatai természetes nagyságukban adottak tárgytérről beszélünk: ezekben a testek alakja és méretei megegyeznek. A KKR-rel leírt tárgyak esetén képtérről beszélünk 62 8. tétel Rasztergrafikai alapalgoritmusok Nagyítás Az elemi nagyítási algoritmusok a képet mindig kétszeresére nagyítják. Az alábbi algoritmusokban az eredeti képet az A N*M-es mátrix tartalmazza, a transzformált képet pedig a B 2N*2M-es mátrix. Nagyítás pontsokszorozással A módszer alapelve, hogy az eredeti kép minden egyes képpontját négyszerezzük meg. Nagyítás: Ciklus i:=1-től N-ig Ciklus j:=1-től M-ig B(2*i-1,2j-1):=A(i,j) B(2*i,2j-1):=A(i,j) B(2*i-1,2j):=A(i,j) B(2*i,2j):=A(i,j) Ciklus vége Ciklus vége Eljárás vége Nagyítás pontátlagolással A módszer alapelve, hogy az eredeti kép minden egyes képpontját egy pontnégyessel helyettesítjük. Az egyik az

eredeti, a másik három pedig az eredeti három szomszéddal vett átlaga lesz. Nagyítás: Ciklus i:=1-től N-ig Ciklus j:=1-től M-ig B(2*i-1,2j-1):=A(i,j) B(2*i,2j-1):=(A(i,j)+A(i+1,j)) div 2 B(2*i-1,2j):=(A(i,j)+A(i,j+1)) div 2 B(2*i,2j):=(A(i,j)+A(i+1,j+1)) div 2 Ciklus vége Ciklus vége Eljárás vége Kicsinyítés Az elemi kicsinyítési algoritmusok a képet mindig felére kicsinyítik. Az alábbi algoritmusokban az eredeti képet az A N*M-es mátrix tartalmazza, a transzformált képet pedig a C N/2*M/2-es mátrix. Kicsinyítés pontelhagyással A módszer alapelve, hogy az eredeti kép minden egyes képpont négyeséből csak a bal felső sarkot hagyjuk meg. 63 Kicsinyítés: Ciklus i:=1-től N-ig Ciklus j:=1-től M-ig C(i,j):=A(2*i-1,2j-1) Ciklus vége Ciklus vége Eljárás vége Kicsinyítés pontátlagolással A módszer alapelve, hogy az eredeti kép minden egyes képpont négyezése helyére az átlagukat tesszük. Kicsinyítés: Ciklus i:=1-től N-ig Ciklus

j:=1-től M-ig C(i,j):=(A(2*i-1,2j-1)+A(2i-1,2j)+A(2i,2j-1)+A(2i,2j)) div 4 Ciklus vége Ciklus vége Eljárás vége Logikai műveletek - NOT: A kép inverzét adja vissza. AND: Maszkolásra, megtartja azt a képpontot, ahol a maszkban 1 van, és nulláz minden olyat, ahol a maszkban 0 van. XOR: Kiemelésre, minden pontban egy eltérő színt ad meg, újabb XOR-nál visszakapjuk az eredeti színt. Megjelenítés Ekvidenzitás képek A legegyszerűbb megjelenítési módszer az elsőrendű ekvidenzitás kép, amiben rögzítettünk egy intervallumot, amihez fehér színt rendelünk, az azon kívül esőkhöz pedig feketét (háttérszín). SZ(i,j):= ha AH≤A(i,j)<FH { fehér, fekete egyébként Rajzolás(AH, FH): Ciklus i:=1-től N-ig Ciklus j:=1-től M-ig Ha AH ≤ A(i,j) és A(i,j) < FH akkor SZ(i,j):=fehér Különben SZ(i,j):=fekete Ciklus vége Ciklus vége Eljárás vége Ennek módosítása a kevert rendű ekvidenzitás kép, amikor nem két-, hanem többárnyalatos

képet állítunk elő, ekkor az egyenlő nagyságú beosztás esetén az algoritmus így módosul (MAXA a legmagasabb, sehol sem szereplő fényesség): 64 Rajzolás(MAXA): Ciklus i:=1-től N-ig Ciklus j:=1-től M-ig SZ(i,j):=(A(i,j)*k/MAXA) Ciklus vége Ciklus vége Eljárás vége Adaptív vágás Bármilyen lineáris vágást is alkalmazunk, mindenképpen fontos információt veszítünk: a kép egyes, eltérő átlagfényességű részei rossz minőségűek lesznek. Az egyik legegyszerűbb módszer, hogy határozzuk meg minden pont adott környezetének átlagos fényességét, majd rendeljünk a ponthoz fehér színt, ha az átlagosnál fényesebb volt, s feketét, ha az átlagosnál sötétebb. Rajzolás: Ciklus i:=1-től N-ig Ciklus j:=1-től M-ig Ha SZ(i,j) > átlag(i,j) akkor SZ(i,j):=fehér Különben SZ(i,j):=fekete Ciklus vége Ciklus vége Eljárás vége Adott tulajdonságú elemek kiemelése Az A mátrixban tárolunk egy N*M-es képet, melyben minden képpontot

egy 1 byte-os értékkel adunk meg. Az egyes képpontokat a szomszédaik értékétől függően transzformálva, különböző jellegű ábrákat kapunk. Képfeldolgozás: Ciklus i:=2-től N-1-ig Ciklus j:=2-től M-1-ig B(i,j):=128+(A(i,j)-A(i,j-1)) div 2 C(i,j):=|A(i,j)-A(i,j-1)|+|A(i,j)-A(i-1,j)| div 2 D(i,j):=128+(2*A(i,j)-A(i,j-1)-A(i-1,j)) div 4 E(i,j):=128+(4*A(i,j)-A(i,j+1)-A(i+1,j)-A(i,j-1)-A(i-1,j)) div 8 Ciklus vége Ciklus vége Eljárás vége B mátrix: Balról jobbra haladva az emelkedő felületek lesznek fényesek, a sík felületek átlagosak, a lejtők pedig sötétek (mintha a felületet nyugati irányból világítanánk meg). C mátrix: Azok a pontok lesznek fényesek, amelyeknél az eredeti képen a fényesség jelentősen változott, s azok lesznek sötétek, ahol az eredeti képen nem volt változás (így az éleket emeljük ki). D mátrix: Balról jobbra és felülről lefelé haladva az inkább emelkedő felületek lesznek fényesek, a sík felületek

átlagosak, az inkább lejtő felületek pedig sötétek (mintha a felületet északnyugati irányból világítanánk meg). 65 E mátrix: Azok a pontok lesznek az átlagosnál fényesebbek, amelyek a 4 szomszédjuk átlagánál fényesebbek (domború felület), azok lesznek sötétebbek, amelyek a szomszédaik átlagánál sötétebbek (homorú felület), a többiek pedig átlagos fényességűek lesznek. Az élek mentén az alacsonyabb fényességűek még sötétebbek, a magas fényességűek még világosabbak lesznek. Területkitöltési algoritmusok Rekurzív festés pontonként Ez az eljárás egy belső pontból kiindulva festi be az alakzatot. A rekurzió miatt nagy alakzatokhoz túl nagy a memóriaigénye. Festés(x,y): Ha üres(x-1,y) akkor Festés(x-1,y) Ha üres(x,y-1) akkor Festés(x,y-1) Ha üres(x+1,y) akkor Festés(x+1,y) Ha üres(x,y+1) akkor Festés(x,y+1) Eljárás vége Sort alkalmazó festés pontonként Ez az eljárás az előző egy gazdaságosabb

változata, egy hullámfrontot ábrázol sor adatszerkezettel. Vermet alkalmazó festés pontonként Ez az eljárás az előző egy másik változata, vermet használ a még feldolgozandó belső pontok ábrázolására. Háromszögfestés Egy háromszöget könnyű festeni, ha megadjuk a vízszintes szakaszokat, amelyekkel teljesen befesthető. Ezen szakaszok végpontjai az oldal egyenesek egyenleteiből számolhatók, azaz nincs szükség a képmemória leolvasására. Rekurzív festés szakaszonként Egy alakzat kiszínezéséhez meg kell adni egy belső pontját. Ekkor a színezést a következőképpen végezzük el. Húzzuk meg azt a függőleges vonalat, amely ezen a ponton keresztül halad, s a kiszínezendő ábra legközelebbi határvonaláig tart. Ez a vonal a kiszínezendő ábrát 2 részre vágja. A feladat ezek után e két rész kiszínezése Ezt úgy oldjuk meg, hogy végigmegyünk a vonal mindkét oldalán, s ha belső, még színezetlen pontot találunk, akkor a

fenti eljárást végrehajtjuk ebből a pontból kiindulva. A feladat nem rekurzív változata ennél jóval bonyolultabb lesz. Itt verembe tesszük a megrajzolandó vonal végpontjai koordinátáit, miközben az előbb megrajzolt szakasz oldalait járjuk be, s csak ezután fogunk hozzá a verem tetején levő szakasz tényleges feldolgozásához. Sokszög festése háromszögenként Konvex sokszög mindig felbontható háromszögekre egy tetszőleges csúcsából kiindulva, így alkalmazható rá a felbontás, majd a háromszögfestés. Konkáv sokszög esetén is alkalmazható a fenti eljárás, de ekkor a sokszögön kívüli területeket is befest ez az eljárás. Megállapíthatjuk ugyanakkor, hogy a sokszögön kívüli területeket mindig páros sokszor, a belülieket pedig páratlan sokszor festi. Ekkor XOR műveletet alkalmazva a festéskor, végeredményként éppen a befestett alakzatot kapjuk. 66 Sokszög festése metsző vonalakkal A képernyő széléről a másik

széle felé haladva számoljuk, hogy hány határoló szakaszon haladunk át. A belső pontokban ez a szám mindig páros, a külső pontokban pedig páratlan Kivételt jelentenek sajnos a vízszintes szakaszokat, illetve alsó vagy felső csúcspontokat tartalmazó sorok. A megoldás: ne a képpontokon, hanem pontosan két képpont között húzzuk a képzeletbeli vonalat, s ez alapján figyeljünk a párosságra, páratlanságra. Egy másik megoldásnál számoljuk ki az összes határoló szakasz és képernyő vízszintes szakaszai metszéspontját, majd ezeket képernyő soronként rendezzük sorba. Ekkor minden esetben páratlan számú ponttól a következő páros sorszámúig kell egy vízszintes szakaszt rajzolni a képernyőre. 67 9. tétel Képkivágás A képkivágás feladata: képelemek egy megadott tartományon kívüli részének elhagyása. A vágó tartomány legtöbbször egy tengelyekkel párhuzamos állású téglalap, vagy egy félsík, illetve hasonló

térbeli téglatest, illetve féltér. Ami a tartományon belül van, azt „láthatónak” mondjuk, a kívülre eső részeket elhagyjuk, vagy „levágjuk”. A vágást legtöbbször a képtérben hajtjuk végre (a képmezőre), de végrehajtható a leképezés előtt a tárgytérben is. Különböző fajtájú képelemek vágására különböző eljárások szolgálnak. Egyenes szakaszok vágása a síkban A feladat meghatározása Adott egy egyenes szakasz két végpontjával: P = (P.x,Py) és Q = (Qx,Qy) A két végpontot a szakaszhoz tartozónak vesszük. Meghatározandó a szakasznak a vágó tartományba eső része, illetve az, hogy van-e egyáltalán ilyen. A PQ szakasz egyenesét a szövegben e-vel jelöljük. A P és Q pontok az e egyenest három részre vágják: két félegyenesre és a PQ szakaszra. Lehet, hogy a PQ szakasz teljesen a tartományon kívül van, lehet, hogy egy közös pont van – ha az e egyenes kívülről érinti a téglalap egyik sarkát, vagy P

vagy Q valamelyike a határon van és a másik kívül – és lehet, hogy a PQ több pontja esik a tartományba. Ez utóbbi esetben ezek a pontok a PQ szakasz egy összefüggő részét alkotják, a PQ látható szakaszt (ami lehet a teljes PQ). Normálvektoros vágás a síkban Adott a síkban egy félsík h határ egyenesével, annak R= (R.x,Ry) pontjával és n=(n.x,ny) normálvektorával Az ezek által kijelölt síkot belső félsíknak, a másikat külső félsíknak nevezzük, a határt is a belső félsíkhoz számítjuk. Keressük a PQ szakasznak a belső félsíkba eső „látható” részét. A látható szakasz két végpontjára három jelöltünk van: P, Q és az e egyenes M metszéspontja a határral. A megoldás geometriai alapja: - Ha P és Q az egyenes egyező oldalán van, a szakasz minden pontja ott van. - Ha különböző oldalon vannak, akkor a szakasznak van metszéspontja a határral. - A P pont akkor és csak akkor van a belső tartományban (vagy annak

határán), ha a határ R pontjából kiinduló RP vektor hegyesszöget (vagy derék szöget) zár be az n vektorral. Ennek megfelelően a P pont helyzetét az RP⋅n = (P-R)⋅n = (P.x-Rx)⋅nx+(Py-Ry)⋅ny skalárszorzat előjele szerint állapíthatjuk meg: P belül van, ha ez pozitív, a határon van, ha ez nulla és kívül van, ha ez negatív. A két végpontjával adott PQ szakasz mindkét pontra kiszámítjuk ezt a skalárszorzatot. - Ha mindkettő pozitív, a szakasz teljes egészében a belső félsíkban van, a szakasz „triviálisan látható”. - Ha mindkettő negatív, a szakasz teljes egészében a külső félsíkban van, a szakasz „triviálisan nem látható”; nincs látható szakasz. - Ha előjelük különböző, akkor a látható szakasz a belső félsíkban lévő ponttól az M metszéspontig terjed. 68 Egy téglalapra - például a képernyőre - való vágásnál ezt az eljárást négyszer egymásután kell alkalmazni a téglalap négy határára. A

négy határ egyenletében az R pontként a sarokpontok, normálvektorokként a vízszintes illetve függőleges irányú egységvektorok: (1,0), (0,1), (-1,0) és (0,-1) választhatók. Ekkor a képletek eléggé egyszerűvé válnak és a négy vágást szorosan egybe lehet építeni. Az eljárás többszöri alkalmazásával nem csak téglalapra, hanem tetszőleges konvex sokszögre is lehet vágni. A Cohen-Stherland-féle vágó eljárás a síkban „Klasszikus” vágó eljárás: a PQ szakasznak egy téglalap alakú tartományba eső részét határozza meg. A látható szakasz két végpontjára hat jelölt van: maga a P és Q, valamint az e egyenesük és a téglalap határ egyeneseinek négy lehetséges metszéspontja. Az eljárás két részből áll, a kezdeti triviális vizsgálatokból és egy metszéspontokat számító részből. A triviális vizsgálatok a P és Q pontok „BAJF-kódján” alapulnak. A sík egy pontjának helyzete jellemezhető a téglalap oldalai

által meghatározott 9 síkrésszel: egy pont BAJF-kódján azt a négybites számot értjük, amelynek egy-egy bitje akkor 1, ha a pont rendre balra, alul, jobbra illetve felül helyezkedik el a határokhoz képest. A téglalapon belüli pontokra ez nulla, az oldalak mentén kívül egy bit egyes, a sarkoknál kívül kettő. Vegyük észre, hogy kettőnél több bit nem lehet 1-es Egy pont BAJFkódját a pont koordinátáinak a téglalap határaival való összehasonlításával kapjuk Az eljárás először kiszámítja a két végpont BAJF kódját. - Ha mindkét végpont BAJF-kódja nulla, akkor mindkét pont, és így az egész szakasz triviálisan belül van. - Ha a két végpont BAJF-kódjának logika ÉS-e (and) nem nulla, akkor bennük ugyanazon a helyen 1 áll, ezért az egész szakasz arra felé triviálisan kinn van. - Minden más eset nem triviális, metszéspontokat kell számolni. Ha a helyzet nem triviális, a szakasz kívülre eső részeit levágjuk, és ehhez

legfeljebb négy lépésre van szükség. Ehhez felhasználhatjuk a P és Q már kiszámított BAJF-kódját Végighaladva előbb a P utána a Q BAJF kódjának bitjein balról jobbra a legelső 1-es bitnél megtudjuk, hogy melyik pont merre van kinn. Ha például a P pont balra kint van, akkor a Q a bal határ másik oldalán van, a P pont helyettesíthető a bal határral való metszésponttal. Az egyenes paraméteres egyenlete alapján: x’ = P.x + t⋅dx = bal, ahonnan t = (bal - Px)/dx y’ = P.y + t⋅dy = Py + (bal-Px)⋅dy/dx Ezután ennek a P-nek is meg kell határozni a BAJF-kódját. Ezt folytatjuk P-Q, bal-jobb sorrendben, amíg a két BAJF-kód nulla, vagy a kettő ÉS-e nullától különböző nem lesz. Az eljárásnak ebben a második részében legrosszabb esetben négy lépést kell végrehajtani, a PQ egyenes metszéspontjait kiszámítva a téglalap oldal egyeneseivel. 69 Sokszögvonal vágása a síkban Sokszögvonalat félsíkra lehet szakaszonként vágni,

de a csatlakozó pontok helyzetét elég egyszer kiszámítani. A vágás eredményeképpen a sokszögvonal széteshet több, különálló darabra. A sokszöglemez vágása ennél bonyolultabb, ezt külön tárgyaljuk Sokszöglemezek vágása a síkban Sokszöglemez vágása esetén nem csak a határt, hanem a sokszög belsejének szerepét is figyelni kell. A képmezőt teljesen lefedő sokszög határa például teljesen kívül van, de a sokszög belsejének egy része belül van, maga a teljes képmező. Teljes eljárás helyett itt csak a megoldás és a fölmerülő problémák lényegét mutatjuk be. A sokszög csúcsainak darabszáma és a csúcsok koordinátáinak P tömbje adott. A vágást félsíkra végezzük a normálvektoros vágással. A vágás lényege: körbemegyünk a sokszög csúcsain, és a belső félsíkban lévőket átmásoljuk egy másik, Q tömbbe, menetközben feljegyezve a határral való metszéspontot is, ha azon át ki- vagy belépünk a látható

félsíkba. Két szomszédos A és B csúcs esetén a következők fordulhatnak elő: - Ha A belül volt, azt már átmásoltuk az új tömbbe. - Ha B is belül van, azt is átmásoljuk - Ha B kívül van, akkor az AB szakasz és a határ metszéspontját kell átmásolni. - Ha A kívül volt, akkor nem került át az új tömbbe. - Ha B is kívül van az sem kerül át. - Ha B belül van, a metszéspontot kell bemásolni. A sokszög csúcsain így végighaladva, a végén a Q tömbben kapjuk a vágott sokszög csúcsait. Eközben ügyelnünk kell a határra eső szakaszokra és a határt elérő, de onnan visszaforduló szakasz párokra. Ez az eljárás tökéletesen működik konvex sokszögek esetén. Konkáv sokszögek esetén is helyesen számolja ki az új csúcspontokat, de a terület szétdarabolódhat, és esetleg fölösleges összekötő szakaszokat vezethet be. Ezért a végén az új csúcspontok Q tömbjét a határ mentén rendezni kell, és az elsőtől kezdve minden

második párt kell csak összekötni. Raszteres pontlapok vágása Egy pontlap a képmezővel párhuzamos állású téglalap, és vágásának eredménye is ilyen. A vágás egyszerűen a határkoordinátákat meghaladó rész elhagyását jelenti. Ez általában része a pontlapot a képernyőre bemásoló eljárásnak is. Feliratok vágása Ez elvileg nem jelent újabb problémát, hiszen raszteres jelkészlet esetén pontlapokként, vonalas jelkészlet esetén vonal-szakaszonként lehet vágni. A vonalas jelkészlettel írt felirat vágása azonban nagyon sok időt igényel, amit néha el lehet kerülni. Mindenképp érdemes először az egész szöveg befoglaló dobozát (text extent), majd az egyes írásjelek dobozát vágni. Néha megfelelő megalkuvás, hogy ha a felirat kezdőpontja, vagy a felirattal magyarázott hely nincs a téglalapban, akkor a teljes feliratot elhagyjuk. 70 A vágás pontosságára háromféle fokozatot szoktak megengedni: -

„Szöveg-pontosság” (text precision) esetén az egész feliratot elhagyják, ha egy része kívül esik. - „Betű-pontosság” (character precision) esetén a felirat minden egyes betűjére külön-külön vonatkozik ez. - „Vonal-pontosság” (stroke precision) esetén minden betű minden vonalát külön-külön vágni kell. Térbeli vágás Térben a normálvektoros vágásnál egy pontjával és normálvektorával egy vágó félsíkot adunk meg. A módszer elve és a metszéspont kiszámításához használt egyenletek alakja változatlan, de itt a pontoknak három összetevőjük van, és a PQ egyenes paraméteres egyenlete három skalár-egyenletet jelent. A módszert minden határoló lapra alkalmazva téglatestre, illetve tetszőleges konvex sokszöglapra (poliéderre) lehet vágni . A Cohen-Sutherland eljárás a térben is alkalmazható egy téglatestre, ha a téglatest határsíkjai által meghatározott 27 térrészt tekintjük, és a BAJF kódot

kiegészítjük egy elöl és egy hátul bittel. A nem triviális esetekben legfeljebb hat metszéspontot kell számítani (ha ügyelünk a sorrendre). A térben néha külön végezzük el a mélységvágást: a nézet Z irányára merőlegesen álló két síkkal (közelsík és távolsík), illetve az oldalvágást: a képkeret által meghatározott oldalsíkokra, XY irányban. Ha az ábrázolandó testekről biztosan tudjuk, hogy a nézőpont előtt vannak, a mélységvágást ki lehet kapcsolni. Egy bejárási feladatnál – épületben, vagy utcán – a közelsíkkal a projektív transzformáció előtt kell vágni, ha el akarjuk kerülni az ilyenkor fellépő képhibákat (és a nullával való osztást). Vágni lehet akármelyik koordináta-rendszerben, ahol mindegyik képelem megjelenik (egyegy elemet saját rendszerében (SKR) nem lehet vágni). Raszter-konverzió A raszter-konverzió – más néven: pászta-konverzió – feladata raszteres képernyőknél (és

nyomtatóknál) a geometrikus képelemeket ábrázoló képpontok és ezek színének meghatározása. Ezt általában a KKR-ben végezzük el – a leképezés, és legtöbbször a vágás után – eredménye közvetlenül a képpont-pufferbe kerül. Egyenes szakaszok raszter-konverziója Adva van egy egyenes-szakasz kezdő és végpontja kép-koordinátáikkal: P= (P.x, Py) és Q=(Q.x, Qy) Feladatunk ezek között egyenes szakaszt húzni, azaz olyan képpontokba 1-et írni, amelyek egy ilyen egyenes szakasz képét eredményezik. Vágás után vagyunk: a szakasz teljes egészében látszik. A bemutatott módszerek mindegyikénél föltesszük, hogy dx= Q.x-Px és dy= Qy-Py nem nulla, hiszen ha úgy lenne, akkor egyszerűen egymás melletti, vagy egymás alatti pontokat kellene „kigyújtani”. Hasonlóan egyszerű a dx=dy eset is, ha a képpontok oldalaránya 1 Föltesszük általában azt is, hogy 0<dy≤dx – vagyis az egyenes meredeksége ≤1, – a többi eset ehhez

hasonlóan intézhető el. A koordináták, N, dx és dy egész számok 71 Durva erőszak „Józan, paraszti ésszel” (brute force) így gondolkodhatunk. Az egyenes y= m⋅(x-Px)+Py egyenletében: - Kiszámítjuk a valós m=dy/dx iránytangenst. - Majd a pontraszter egymás utáni pontjaira, az i=0,1,2, ., N értékekre: - xi=P.x+i, (egész) - yi=m⋅i+P.y (valós) és vi=Round(yi) - putPixel(xi,vi,c), azaz c színt teszünk a képpont-puffer ezen pontjaiba. Ez a módszer helyesen adja a kezdőpontot és jó függőleges közelítéssel adja a többit. Ezzel szemben lassú lesz, mert minden ponthoz végre kell hajtani egy lebegőpontos szorzást, egy összeadást. A felezőpont eljárás Ez növekményes eljárás, itt – a kerekítési hibák elkerülése végett – bevezetünk egy ugyancsak növekményesen számított „eltérés” értéket. Ennek előjeléből állapítható meg minden lépésben, hogy ott melyik közelítő pontot kell vennünk, és ettől függ majd

az eltérés érték következő értéke is. Föltesszük itt is, hogy 0<dy≤dx. A kezdőpont a (Px,Py) pont és innen x irányban mindig 1-et lépünk. A következő közelítő rácspontot minden lépésben vagy az utolsó közelítő ponttól (Pi) „keletre” (K), vagy „északkeletre” (ÉK) keressük. Attól függően választunk e kettő közül, hogy kettejük felezőpontja (F) az egyenes itteni pontja alatt vagy fölött van-e. Ha éppen egybeesnek, megegyezés szerint akkor is az alsó, K pontot vesszük. Ily módon a választott képpontok függőleges eltérése mindig≤1/2. Vonalak raszter-konverziójának értékelése A raszter-konverzióval egy vonal közelítő pontjait határozzuk meg azért, hogy a képernyőn a vonalnak megfelelő látványt érjenek el. Módszereinkkel szemben van néhány kézenfekvően teljesíthető és néhány nehezen teljesíthető követelmény. - Legyen hézagmentes. - A legjobb közelítés elve. Amelyik jobban közelít, azt a

módszert használjuk - Sebesség, illetve műveletigény. - Irány-független. A P1 és P2 között húzott szakasz képe egyezzen meg a P2 és P1 között húzott szakaszéval. - Minden pontot csak egyszer rajzoljunk. - A vágás torzító hatása. - Többféle vonalvastagság. - A „lépcsőhiba” - a raszterpontokkal való közelítés látványhibája - egyszínű képernyőknél kiküszöbölhetetlen. - A vonalak fényessége állásuktól független legyen. - Nagy, virtuális képpont-pufferek esetén a 16 bites számábrázolás esetleg nem elegendő. Kör raszter-konverziója Elegendő az origó középpontú körrel foglalkoznunk, a többi eltolással adódik. A kör szimmetriája miatt elegendő egy kör nyolcadívének pontjait meghatározni. A kör középpontja tehát a (0,0) pont, sugara R A rajzolást 72 a kör legészakibb, (0,R), pontjából kezdjük kelet felé, az északkeleti irányig. Ezen a szakaszon - a második nyolcadban - az érintő irányszögének

abszolút értéke < 45 fok. Itt is alkalmazhatók a felezőpont eljárás elvei, de itt egy ismert pont után vagy keletre, vagy délkeletre kell lépnünk. Egy már kiválasztott Pi=(xi, yi) közelítő pontban itt is definiálható az eltérésfüggvény: e(xi) =G(xi+1, yi-1/2). Az eljárás szerkezete itt is ugyanaz, mint az egyenes rajzolásnál, de itt az e függvény változását minden lépésben újra ki kell számítani. 73 10. tétel Homogén lineáris transzformációk Az { ( x, y) x, y ∈R} halmaz a geometriai axiómarendszer modellje. E halmaz elemei között műveleteket definiálunk. A sík egy P (x,y) pontjának homogén koordinátája P (x,y,1). A homogén koordinátákra azért van szükség, mert az eltolás nem valósítható meg anélkül, valamint nem függ a koordinátáktól, csak azok arányától. Adott P és Q a síkon. A PQ egyenes paraméteres egyenlete: X=P+t(Q-P) Ha t∈(0,1) akkor PQ pontjait; t=1 akkor Q-t; t=0 akkor P-t; t<0 akkor a P-n

túli; t>0 akkor a Q-n túli pontokat kapjuk. Az egyenes egyenletének homogén alakja: a ⋅ x + b ⋅ y + c = 0= (x y  a   1) ⋅  b  c   Két egyenes (X=P+t(Q-P) és X=A+u(B-A)) akkor metszi egymást, ha azok egyenlők. X pont rajta van az egyenesen, ha det(A)=0, ahol  x1 x 2 x3    A =  p 2 p 2 p3  q3 q 2 q3    Azért jó, hogy mátrixokkal végezzük a transzformációkat, mert így a transzformációk elvégzése egyszerűen egy szorzás. Transzformációk homogén koordinátás megadása Ezeket mátrix-alakban fogjuk megadni: P′ = P ⋅ M , ahol M a transzformáció mátrixa.  m 11  P ′ = (x ′, y ′,1) = P ⋅ M = (x , y ,1) ⋅  m 21   m 31 m 12 m 22 m 32 0  0 =  1 = ( m 11 ⋅ x + m 21 ⋅ y + m 31 , m 12 ⋅ x + m 22 ⋅ y + m 32 ,1)       x′ y′ 74 Elemi affin transzformációk A párhuzamos

egyeneseket párhuzamos egyenesekbe átvivő transzformációt affin transzformációnak nevezzük. Eltolás - Síkban: x′ = x + dx, y′ = y + dy. 1  P ′ = (x ′, y ′,1) = (x , y ,1) ⋅  0   dx - 0 1 dy 0  0 = (x + dx , y + dy ,1) .  1 Térben: x′ = x + dx, y′ = y + dy, z′ = z + dz. 1  0 P ′ = (x ′, y ′, z ′,1) = (x , y , z ,1) ⋅  0   dx 0 1 0 dy 0 0 1 dz 0  0 = (x + dx , y + dy , z + dz ,1) . 0  1 Forgatás A sík forgatása az origó körül x′ = x ⋅ cosα − y ⋅ sin α, y′ = x ⋅ sin α + y ⋅ cosα . A transzformáció mátrixa:  cos α   − sin α   0 sin α cos α 0 0  0 .  1 A tér forgatása koordináta-tengely körül  cos α   − sin α  0   0 sin α cos α 0 0 0 0 1 0 Z-tengely körül 0  cos α   0  0 , 0  − sin α   1  0 0 sin α 1 0 0 cos α 0 0 0  1 0  

0  0 cos α , 0  0 − sin α   1  0 0 Y-tengely körül A pontokat mindig sorvektorral ábrázoljuk. 75 0 sin α cos α 0 X-tengely körül 0  0 . 0  1 Oszlopvektor esetén:  x ′   T  y ′ = M    1 x    T  y  , ahol M transzponált mátrix.    1 A transzformációk egymásutánja általában nem cserélhető fel, mint ahogy a mátrixok körében használatos szorzás sem kommutatív művelet. A sík tetszőleges pontja körüli elforgatás P ′ = P ⋅ ( T −1 ⋅ R ⋅ T ) 3 elemi affin transzformáció szorzata, ahol forgatás (rotáció). T transzláció, azaz elviszi az origót K-ba, és R a Térbeli forgatás tetszőleges tengely körül Előáll több elemi affin transzformáció szorzataként: P′ = P ⋅ (T ⋅ R1 ⋅ R2 ⋅ R⋅ R2−1 ⋅ R1−1 ⋅ T −1 ) , ahol R1 beforgatás egy koordinátasíkba, R2 beforgatás egy koordináta-tengelyre.

Lépték - Síkban x′ = sx ⋅ x, y′ = sy ⋅ y . - Térben x′ = sx ⋅ x, y′ = sy ⋅ y , z′ = sz ⋅ z. Ha sx= sy, akkor ez kicsinyítés, illetve nagyítás, izotróp hasonlósági transzformáció; különben anizotróp. A megfelelő mátrixok:  sx  0  0 0 sy 0  sx 0  0  0 ,  0  1  0 0 sy 0 0 0 0 sz 0 0  0 síkban, illetve térben. 0  1 76 Tükrözés  −1 0 0   Például síkban az Y-tengelyre:  0 1 0 a megfelelő transzformációs mátrix.    0 0 1 1  0 Például térben az XY-síkra:  0  0 0 0 0  1 0 0 a megfelelő transzformációs mátrix. 0 −1 0  0 0 1 Permutációs mátrixok: A mátrix minden sorában és minden oszlopában pontosan egy darab 1-es szerepel, a többi helyen 0 áll. Például:  0 1 0   (x , y ,1) ⋅  1 0 0 = ( y , x ,1) : a sík 45°-os egyenesére való tükrözés.    0 0

1 Ez általában három mátrix szorzataként áll elő. Nyírás  1  x′ = x + ny ⋅ y, y′ = y , és ennek mátrixa:  n y   0 0 0  1 0  0 1 . Minden affin transzformáció felírható elemi affin transzformációk szorzataként: A = T ⋅ R ⋅ S⋅ N 77 11. tétel Koordinátarendszerek Manapság a megjelenítők két dimenziósak, ezért ha 3 dimenziós objektumokat, felületeket, stb. akarunk láthatóvá tenni a monitoron, elkerülhetetlen, hogy bizonyos transzformációkat végezzünk. Ezek a transzformációk a következő hierarchiában szereplő koordinátarendszerek közötti átmenetet biztosítják. Modell koordinátarendszer (MKR): Ha egy képet sok hasonló, vagy ismétlődő alakzatból teszünk össze, érdemes definiálni egy, az alakzathoz tartozó MKR-t. Ennek a koordinátarendszernek az origója az alakzat középpontja. Így lehetséges, hogy például egy ellipszoid a saját koordinátarendszerében gömb. Világ

koordinátarendszer (VKR): Ahhoz, hogy megtudjuk, hogy az alakzat a világban hogy néz ki, transzformálnunk kell a VKR-be. Az adatokat a grafikus szerelőszalagon általában ebben a VKR-ben adjuk meg A VKR origóját nem adjuk meg, mert az origótól függetlenül az alakzat úgyis olyan, amilyen valójában. Szem koordinátarendszer (SZKR): Megadunk egy vetítési középpontot (nézőpontot): C. Megadjuk a vetületi sík normálvektorát: n, és egy up felfelé irányt meghatározó vektort. A koordinátarendszer origója legyen a már felvett C, tengelyirányú vektorai pedig: u = up x n , v = n x u , w = n jobbsodrású ortogonális rendszer: A VKR-beli koordinátákat le kell képeznünk SZKR-beliekre: Kiszámítjuk az u, v, w egységvektorokat: u = u / u, v = v / v, w = w / w. P = P , azaz a P VKR-beli pont képét úgy kapjuk meg SZKR-ben, hogy megszorozzuk az mátrix-szal, ahol: 78  u 1 v1 w1   u 2 v2 w2 = u 3 v3 w3   0 0 0  0

 0 0  1  1 0 0  0 1 0 0 0 1   cx cy cz  0  0 , 0  1  amiben bal felső 3x3-asa a bázisvektorok képe (u, v, w felírva x, y, z segítségével), második fele pedig a szem" koordinátáival való eltolás mátrixa, amiben " c=(cx, cy, cz) eltolásvektor - C koordinátái. Normalizált projektív koordinátarendszer (NPKR): Az NPKR olyan koordinátarendszer, aminek tengelyirányai megegyeznek SZKR-éivel, középpontja eltolódik a vetítési síkra, azaz C a w ideális pontjába kerül. Ez az SZKR NPKR transzformáció valójában az egyetlen projektív transzformáció, tehát olyan, hogy bizonyos pontokat a végtelenbe visz. Az SZKR NPKR transzformáció tulajdonságai: pontot pontba, egyenest egyenesbe visz, metszés-, de nem szög- és távolságtartó. A láthatóság és a vágás is NPKR-ben történik. Kép koordinátarendszer (KKR): Origója a képernyő bal felső sarka, és tengelyei vízszintes

illetve függőleges irányúak. A homogén koordinátáival adott objektumokat (pontokat) a felbontásnak és a megjelenítőnek megfelelően képezzük le (skálázás, vágás, stb.) a képernyőre (általában a 3 koordináta elhagyásával). A középpontos és párhuzamos vetítés Vetítésnek az olyan dimenzióveszteséggel járó ponttranszformációkat nevezzük, melyeknél bármelyik képpont és a neki megfelelő összes tárgypont egy egyenesen helyezkedik el. Az összetartozó tárgy- és képpontokon áthaladó egyenest vetítősugárnak nevezzük. Az egyes tárgypontok képe a vetítősugarak döféspontja a képfelületen. Általában síkfelületre vetítünk a műszaki gyakorlatban, de lehetséges más felületek (például hengerpalást) használata is. Mi csak sík képfelületre történő vetítéssel foglalkozunk! Ha a vetítősugarak egymással || -k, akkor párhuzamos vetítésről beszélünk. Ha ezen kívül a vetítősugarak még ⊥-ek is a képsíkra,

akkor merőleges – ortogonális – a vetítés, különben ferde – diagonális. A párhuzamos vetítéssel keletkezett ábra axonometrikus A középpontos vetítés esetén a vetítősugarak mindegyike áthalad egy vetítési középponton (centrumon). Az így létrejövő kép nagyon közel áll az emberi szem illetve a fényképezőgép által alkototthoz. Tehát perspektivikus ábrához jutunk A perspektivikus hatás elsősorban a tárgy és a centrumpont távolságától függ. Ha ez a távolság minden határon túl nő, a középpontos vetítés párhuzamos vetítésbe megy át. 79 A középpontos vetítés Adott egy 3D tárgy VKR-ben. A VKR SZKR transzformációhoz adottak: - C (cx, cy, cz): a szem pozíciója. - n: a nézés iránya. - up: a "felfelé" irány meghatározására. - k: a közelsík, C-től k távolságra. - t: a távolsík (nem olyan fontos), C-től t távolságra, úgy, hogy 0 < k < t ≤ ∞. (Az ábrázolásnál csak a k és t közé

eső objektumokat vesszük figyelembe.) A koordinátarendszereknél említett eljárásokkal előállítjuk u, v, w vektorokat, majd az u, v, w egységvektorokat, illetve az alakzat pontjainak a képeit. Adottak még: - αu, αv: u illetve v irányú látószög. - A k, t, αu, αv-re azért van szükség, hogy egy behatárolt, zárt térrészre (egy csonkagúlára) "koncentrálhassunk". És így csak ebbe a térrészbe eső dolgokkal foglalkozunk Ugyanígy a vízszintes síkban van αv, így a határegyenesek egy (téglalap alapú) csonkagúlát fognak közre. SZKR NPKR: Ahhoz, hogy NPKR-be jussunk, először az origót kell a közelsíkra tolnunk az n irányában: 1  0 = 0  0  0 0 1 0 0 1 0 −k 0  0 , 0  1  azaz eltolás (-k)-val, ahol k a közelsík 3. koordinátája SZKR-ben Ezután, egy léptékezést kell végrehajtani, hogy a közelsíkon keletkező síkrész egységnyi magasságú legyen. A léptékezés után

C(0,0,-k,1), a közelsík (x,y,0,1), a távolsík (x,y,t,1) típusú pontokból áll, ahol k C távolsága, t pedig a távolsík távolsága a közelsíktól, x,y∈R, tetszőleges. 80 Egy kis projektív geometriai áttekintés A projektív geometriában a sík minden egyenespárjának pontosan egy metszéspontja van. A || egyenesek a végtelenben metszik egymást. Egy sík minden irányához tartozik egy ilyen ideális pont. Ezek a pontok határozzák meg az úgynevezett ideális egyenest A projektív síkot az XYZ derékszögű koordinátarendszer origóján átmenő egyeneseinek, és az euklideszi tér XY síkkal ||, (0,0,1) ponton átmenő síkjának (projektív!) metszéspontjai adják. Tehát a projektív sík az előbb definiált euklideszi sík pontjai, kiegészítve az ideális pontokkal. Az euklideszi tér origón átmenő egyeneseinek bármely pontjával a projektív síknak ugyanazt a pontját adjuk meg (a döféspontot). Például az (a,b,c) koordinátájú pont

pontosan ugyanaz, mint az (a/c,b/c,1) pont, ha c≠0, és ez az euklideszi (a/c,b/c) ponttal egyezik meg. Ha c= 0, akkor a pont ideális pont. Ha átgondoljuk, az ezeket meghatározó egyenesek éppen az XY síkkal || egyenesek (a (0,0,0) nem eleme a projektív síknak, mert nem határoz meg egyértelműen az origóval (azaz önmagával) egy egyenest). Ezt még nem olyan nehéz elképzelni, ezért kezdtük ezzel, de minket most a projektív tér "érdekel". Hasonlóan az előzőekhez, definiáljuk most a projektív teret: ez az euklideszi tér ideális síkkal kiegészítve. Pontjait (x,y,u,v) koordinátanégyesek határozzák meg Ugyanezt a pontot jelenti (x/a,y/a,u/a,v/a), ha a≠0. v= 0 esetén ideális a pont Természetesen nem ∃ (0,0,0,0) projektív térbeli pont. Hogy a képernyőn perspektív kép jelenjen meg, szükségünk van egy olyan transzformációra, ami az eddigi csonkagúlát hasábba viszi, hogy például egy nézett" kocka élei – ahogy látjuk

" – összetartóak legyenek. Ezért most először a C pontot a w tengely ideális pontjába kell juttatnunk: C(0,0,-k,1)C(0,0,1,0). Másrészt, hogy a fenti képet kapjuk, a közelsík koordinátáit, (x,y,0,1) alakú pontokat a mi transzformációnknak helyben kell hagynia. Ennek a transzformációnak ezek szerint az első két koordinátával nem kell foglalkoznia. 81 A mátrix alakja a következő: 1  0 = 0  0  0 1 0 0 0 0  0 0 a b  c d  Kell: 1  0 (0,0,-k’,1) *  0  0  1  0 (x,y,0,1) *  0  0  0 0 0  1 0 0 = (0,0,1,0), 0 a b  0 c d  0 0 1 0 0  0 = (x,y,0,1), 0 a b  0 c d  I.) szerint:(0,0,-ak+c,-bk+d) = (0,0,x,0) és ⇒ II.) ) c=0, d=1 II.) szerint: (x,y,c,d) = (x,y,0,1). Így: -bk=-1 ⇒ b=1/k. a-ról semmi konkrétumot nem tudunk még Tehát mátrixunkban már csak egy ismeretlen szerepel, az "a". 1  0 = 0

 0  0 0 0   1 0 0  . 0 a 1 / k   0 0 1  Még egy valamit nem használtunk ki: a transzformáció a távolsík pontjait a w-re ⊥, w-n átmenő sík megfelelő pontjaiba viszi. Például w tengelyi pontja: (0,0,t,1), a (0,0,1,1)-be kerül: (0,0,t,1) = (0,0,at,t/k+1) = (0,0,at/(t/k+1),1) ⇒ at/(t/k+1)=1 ⇒ a=1/k+1/t. Az SZKR-ben egy vetítősugárra eső pontok az NPKR-ben szintén egy, a w -vel || egyenesen (a vetítősugár képén) lesznek, de közülük csak a legelső" fog látszani. " Itt a vágás egyszerűen elvégezhető, hiszen pontosan a közel- és a távolsík közötti térrészre kell vágnunk. Az x és y koordináták a közelsíkra való vetületeket adják meg, amelyből megfelelő nagyítás után megkapjuk a grafikus képernyőn szükséges koordinátákat. 82 A párhuzamos vetítés Itt, mint már az elején említettük, az SZKR helyett egy (hasonló tulajdonságokkal rendelkező) referencia koordinátarendszer (

továbbiakban RKR) van. A VKR RKR transzformációhoz szükségünk van a következő néhány adatra: - R: referenciapont. - n: az R-en átmenő vetületi sík normálvektora. - up: a felfelé irányt meghatározó vektor. Az u, v, w meghatározása ugyanúgy történik, mint a középpontos vetítésnél. Szükségünk van még umin, umax, vmin, vmax értékekre, valamint egy d távolságra, hogy a megjelenítendő területet meghatározzák az RKR-ben. Kell még egy vetítési irány, amely egy ponttal adható meg, az úgynevezett referenciaponttal: PRP (projection reference point). Ezek után a vetítés iránya: c - prp Innen az NPKR-re való átmenethez szükséges transzformáció a következő: s = d - PRPn gu = (Cu - PRPu) /s gv = (Cv - PRPv) /s 0  1  1  0 = − gu − gv   dgu dgv  0 0 1 0 0  0 0  1  Síkvetületek osztályozása Vetíthetünk: - Síkra. - Gömbre. - Hengerre. Vetítés lehet: - Merőleges (ez az alapeset). - Nem

merőleges. Általában a grafikában síkra vetítünk. 83 12. tétel Láthatóság Láthatóság-takarás (hidden line, hidden surface removal, visible line, visible surface selection): A szemlélő irányából látható képelemek kiválasztása, illetve a takart képelemek eltávolítása. Síkbeli elemek a rajzban legtöbbször nem takarják egymást, de némely alkalmazásoknál (például a térképészetben) a képelemek rétegekbe sorolhatók, és ezek meghatározott sorrendben egymásra fektethetők. Térbeli elemeknél a nézőpont felől nézve takart elemek elhagyása jelentősen hozzájárul a térlátás élményéhez. Vonalas ábráknál a rajzolt vonalak (élek) takarásban lévő részeit el kell hagyni (vagy szaggatottan rajzolni). Többféle módszer van árnyalt képekre és drótváz képekre különböző. Általában leképezés és vágás után a nézetmező az NPKR téglatestben, vagy az SZKR csonkagúlában. Drótváz ábráknál a látható

szakaszokat keressük (vagy a takartakat, azért, hogy eltávolítsuk őket), árnyalt képeknél a képernyő minden pontjában keressük az ott látható felületelemet. A fölmerülő problémák szemléltetése: A sokszögek több darabra eshetnek szét, egy lapot több másikkal összehasonlítva, az így keletkező darabok tovább darabolódhatnak. Három sokszög kölcsönösen takarhatja egymás egy-egy részét. Két konkáv sokszög kölcsönös fedésben lehet egymással. (Ez ellen is jók a háromszögek!) A láthatósági eljárásnál minden lapot minden (más) lappal össze kell hasonlítani, ezért nagyon sok időt vesz igénybe. Drótvázas képek takart éleinek elhagyása Konkáv sokszögek egy élet több látható darabra vághatnak szét. A sokszögek között, még konvex esetben is, előfordulhatnak kölcsönös takarások. Egy élet az őt tartalmazó két lap kivételével bármelyik eltakarhatja (csak síkokban elhelyezkedő sokszöglapokkal foglalkozunk).

Ezért minden élet (a színtér minden testének, ezek minden lapjának valamennyi élét) össze kell hasonlítani a színtér minden, ettől különböző lapjával a takarás szempontjából. (Ha a színtérben L lap van, átlagban E éllel, akkor ez egy (L*E)L lépéses ciklus!) A leképezés és vágás után az NPKR téglatestben a vetítősugarak képe párhuzamos a Z tengellyel, ezért a takarást XY vetületben lehet vizsgálni; egyező x, y koordináták esetén a z koordináta dönti el a takarást. 84 Láthatóság teljes térfelosztással Ennél az eljárásnál a teret, és a benne lévő lapokat, elvileg teljesen földaraboljuk a lapok befoglaló dobozainak csúcsain átmenő síkokkal. Az így keletkező térrészek egy részében nem látható semmi. Azokban a térrészekben, ahol vannak lapdarabok, ott kevesen vannak, és a láthatóság egyértelmű, nincsenek kölcsönös fedések, így két-két lapdarab egymáshoz viszonyított helyzetet egyetlen z

értékpár összehasonlításával eldönthető. Valójában nem kell a teljes földarabolást előre elvégezni. Elég a lapokat például xmin szerint rendezni, és sorban haladni a fölosztással keletkező x szerinti sávokon, és ezeken belül az y szerinti sávokon, minden térdarabban elvégezve a szükséges vizsgálatokat. Ez a módszer használható árnyalt képekre is és vonalas képekre egyaránt. Megjegyezzük, hogy egy másik módszer -Warnock eljárása - a tér fokozatos XY irányú negyedelésével próbálja meg a helyzetet egyszerűbbé tenni a keletkező részekben. Kétváltozós függvények képének láthatósága A kétváltozós z=f(x,y) függvényt szemléltető felület pontjait diszkrét x,y értékek mellett gyakran ábrázoljuk a koordináta-rendszer párhuzamos vetítésével. Eközben a láthatósági feladatnak az ábrázolási módnak megfelelő változatait próbálhatjuk ki a korábban elmondottak alapján. Ha csak a konstans y mellett felvett

értékeket kötjük össze, akkor az ezeknek megfelelő „kartonokat” hátulról-előre sorrendben lehet kifesteni - a kartonok belsejét mindig kitöltve fehérrel. Ha a konstans x melletti értékeket is kirajzoljuk, akkor a felületre fektetett négyszöghálót kapunk, amelynél a láthatóság megoldása kissé bonyolultabb. Először is vegyük észre, hogy ezek a négyszögek torzak, általában a csúcsok nincsenek egy síkban. Ezért a négyszögeket egy-egy átlóval ketté kell osztani. Itt a „kartonokat” nem is kell festeni, csak a köztük lévő háromszög-sávokat. Ezeket viszont itt is hátulról kezdve, először a leghátsó „kartonközben” lévőt, majd sorban haladva előre. Végül, a legelső kartont érdemes fehérrel kitölteni. Árnyalás Árnyalt képek előállításánál geometriai módszerekkel állapítjuk meg, hogy a képernyő egyes pontjaiban mit, melyik felületelemet, és annak melyik pontját lehet látni. Ezután számítjuk ki az

egyes képpontok színét (amit vagy közvetlenül a képpont-pufferbe, vagy egy képfájlba írunk). Árnyalás (shading): A tárgyak képét alkotó képpontok színének kiszámítása a felületek színjellemzői és a megvilágítás adatai alapján. A színárnyalatok folytonos átmenete egy-egy felületen. A legegyszerűbb esetben a képpontok színét a felület tárolt színadata alapján adjuk meg, ez a lapos árnyalás, színezés. Igényesebb esetben a képpontok színét a testek felületi tulajdonságait és a színtérben érvényesülő fényforrások valamilyen megvilágítási modellje, a fizikai fényviszonyok valamilyen közelítő matematikai modellje alapján számítjuk ki. Lokális megvilágítási modell: Az egyes képpontok színét, az ott látott felületi pontban a helyi geometriai és fényviszonyok alapján vizsgáljuk. Globális megvilágítási modell: Egy körülhatárolt térrészben modellezzük a fényviszonyokat, a benne előforduló alakzatok és

fényforrások adatai alapján. Ez utóbbi lényegesen hosszabb ideig tart. 85 Színmodellek Az RGB színmodell A képernyő festékrétegei a becsapódó elektronok hatására fényt (energiát) sugároznak ki, ezek színét fényszíneknek nevezzük. A különböző színű fénysugarak erőssége szemünkben összegződik, ezért a színek ilyen keverődését „additív színkeverésnek” nevezzük. A legnagyobb színtartomány (érzetének) előállítását ily Az RGB színtér módon egy-egy meghatározott hullámhosszúságú vörös (Red), zöld (Green) illetve kék (Blue) szín teszi lehetővé. Ezért alkalmaznak a képernyőn három ilyen színű festékréteget. A számítógép képernyője számára a különböző színeket ezután ezek RGB összetevőivel, a három alapszín viszonylagos erősségével adjuk meg. A képernyők úgy vannak beállítva, hogy a (0, 0, 0) számhármas a feketét adja (nincs kisugárzott fény), a (max, max, max) számhármas pedig

fehér színű fényt. Az egyes színösszetevők erőssége változtatható 0 és max (pl. 63 vagy 256) között, amivel különböző keverék színek (és monokróm színek) érzete is előállítható. Ha a három összetevő megegyezik, a semleges szürke különböző erősségű árnyalatait kapjuk. A három összetevős színértékek természetes módon szemléltethetők egy térbeli koordináta-rendszer kockájával. A CMY színmodell A színes papírképek, textíliák, a körülöttünk lévő tárgyak többsége nem bocsát ki fényt, ezek színeként a külvilágból rájuk eső fény visszaverődését érzékeljük. Ezeknek valójában nincs is saját színük (!); ugyanazt a tárgyat egyszer zöld, másszor vörös fénnyel megvilágítva előbb ilyen, majd olyan színűnek látjuk őket. A tárgyak felülete a különböző hullámhosszúságú fényeket különböző mértékben nyelik el, illetve verik vissza. Amit egy tárgy színének nevezünk az a Nap

fényéből visszavert színkeverék. Az így látott színeket festékszíneknek nevezzük. Az ember számára a mindenütt látható, legfeltűnőbb fényforrás, a Nap az ősi, természetes viszonyítási alap. A Nap fényét nevezzük fehér fénynek (habár magát a Napot, a kék égen sárgának látjuk). A tiszta papírlap változatlan összetételben veri vissza a Nap fényét, ezt „fehérnek” nevezzük. Ha a papírlapra festékréteget helyezünk el, az a Nap fényéből elnyeli bizonyos hullámhosszú fények egy részét. Többféle festék elnyelő hatása összeadódik, ezért ezt „szubtraktív színkeverésnek” nevezzük. Ennél három másik alapszín bizonyul legjobbnak: egy bizonyos türkiz (Cyan), sárga (Yellow) és a bíbor (Magenta). Mindháromból nullát alkalmazva a papír visszavert fénye fehér marad, mindegyikből a maximális mennyiséget alkalmazva elvileg semmit sem ver vissza, feketét látunk (valójában csak nagyon sötét szürkét tudunk

így elérni). Ezen alapulnak a színes nyomtatók és a színes nyomdatechnika. A számítógépek nyomtatóinál a CMY alapszíneken kívül gyakran, negyedikként a feketét is alkalmazzák, ezt jelölik CMYK alapszíneknek. A HLS színérzet modell Az RGB és a CMY színmodellekben kódolt színek egy-egy fizikai berendezés számára érthető formában kódolják a színeket. Az ember azonban nehezen tudná megbecsülni, hogy miféle színt jelent például a (23, 37, 14) számhármas, illetve ez a szín hogyan változik meg, 86 ha az egyik összetevőt tízzel megnöveljük. Az ember számára a színeket a színérzékelés három független összetevőjével célszerű jellemezni, ezt teszik a különböző színérzet modellek. A HLS modell a színeket az ember által legjobban észlelt két színjellemző: a fény világossága (Lightness) és színezete (Hue) mellett, az ezeknél kissé nehezebben észlelt, ezektől független telítettség (saturation, élénkség

illetve tompaság) mértékével jellemzi. A színezetet a „színkörön” elhelyezve 0 és 360 közötti szögértékkel jellemzik, a telítettséget a színkör középpontjától mért 0 és 100 közé eső sugárirányú távolsággal - középen vannak a telítetlen, a kör kerületén az élénk, telített színek - míg a világosságot a színkör középpontján átmenő, arra merőleges tengelyen ugyancsak 0 és 100 közötti értékkel jellemezzük. Az így jellemzett színek egy orsó alakú kettős kúpban, helyezkednek el. Egy tengelyre merőleges állású, vele koncentrikus köríven csak a színezet változik, míg a tengelyből, rá merőleges irányban kiindulva csak a telítettség változik. Bármely függőleges egyenes mentén azonos színezetű és azonos telítettségű, de különböző világosságú színek vannak. Egy ilyen egyenes két pontban kilép az orsóból: itt van az adott színezetű és telítettségű szín fényességének alsó és fölső

határa. A tengelyen a teljesen telítetlen színek: a fekete és a fehér, valamint közöttük különböző világosságú szürke árnyalatok vannak. Megjegyzendő, hogy az orsó főköre helyett, igényesebb tárgyalásnál, egy hullámos peremet kell elképzelni. A főkör mentén ugyanis a teljesen telített színek vannak és ezek világossága a mérések és az emberi érzékelés szerint is, különböző. A telített R, G, B színek közül a zöld világosabb a vörösnél és ez sokkal világosabb a kéknél. VRML nyelv A nyelv megjelenésével a virtuális világok ugrásszerűen gyarapodtak, hiszen a nyelv a felhasználok kezébe egy olyan eszközt ad, amit könnyű használni, és mindenki felépíthet vele egy saját világot. A VRML fájl egy szöveges fájl, kiterjesztésként a .wrl-t használják Geometriai formák és szövegek Cube – kocka: Téglatestet alkothatunk megadva a tulajdonságokat: szélesség, magasság és mélység. Sphere – gömb: Megadott

sugárral az aktuális rajzpontból, mint középpontból rajzolja meg a gömböt. Cylinder – henger: Magasság, alapkör sugár és rajzolandó részek meghatározásával rajzol hengert. A rajzolandó részek lehetnek: minden, felső lap, alsó lap, palást Cone – kúp: Magasság, alapkör sugara, megrajzolt részek segítségével rajzolhatunk. Megrajzolt részek lehetnek: minden rész, palást, alaplap. Coordinate3 – pontok: Pontokat lehet megadni a háromdimenziós koordináták alapján. Egyetlen mezője van, ez a point. IndexedLineSet – élek megadása: Négy mezője van, a koordináta indexlista, anyag indexlista, normálvektor indexlista, textúra indexlista. A koordináta indexlistában a pontok indexeivel adjuk meg az éleket. A másik három indexlista sorrendben a következőkre szolgál: fényesség, illetve szórt fény megadása, normálvektorok megadása, és a textúra megadása. 87 IndexedFaceSet – lapok megadása: Ugyanaz a négy mezője van, mint az

előbbinek, csak itt lapokat adunk meg a pontokkal. PointSet – pontrajzoló: Két mezője van, a kezdőpont indexe, és a rajzolandó pontok száma. AsciiText – szövegek: Négy mezője van. A string mezővel lehet a szöveget kiírni A másik három mező az igazítás, a szövegszélesség, és a sorköz mérete. FontStyle – szövegformázás: Három mezője van, a betű típusa, stílusa, és mérete. Geometriai transzformációk Translation – eltolás: Egyetlen mezője van, ugyanaz, mint a node neve, csak kis betűvel kell írni. Az eltolás értékeit az x, y, z tengelyre kell megadni Rotation – forgatás: Ennek is egy mezője van, ugyanaz, mint a node neve, csak kis betűvel kell írni. Négy értéket kell beírni, az első három értékkel állítjuk be, hogy melyik tengely körül forgatunk, a negyedikkel pedig a szöget kell megadni radiánban. Scale – léptékezés: Egy mezője van, a scaleFactor, melyben három értéket kell megadni, a három koordináta

szerinti léptékezést. Transform – transzformáció: Öt mezője van. Az első hármat (translation, rotation, scaleFactor) ugyanúgy kell megadni, mintha külön node-ok lennének. A negyedik a léptekezés irányát meghatározó forgatás, az ötödik mező a középpont megadása. MatrixTransform – transzformációs mátrix: Egyetlen mezője van, a neve matrix. Ezután egy 4*4-es mátrixot kell megadni. Színek és formák Material – színek megadása: Hat mezője van, a diffúzszínérték, kibocsátott fényérték, átlátszóság mértéke, környezeti színérték, tükrözőszín mértéke, fényesség mértéke. Az átlátszóság mértéke és a fényesség mértéke mezőkbe egy, míg a többi mezőbe három számot kell írni az RGB kódnak megfelelően. MaterialBinding – színhozzárendelés: Egyetlen mezője van, a hozzárendelés típusa. TextureCoordinat2 – koordinátaindexek definiálása: Egy mezője van, a point, itt tudjuk felsorolni a textúraként,

használni kívánt képet határoló koordinátákat. Texture2Transform – anyagkép transzformáció: A kitöltő anyagot transzformálhatjuk más formátumra. Négy mezője van: translation, rotation, scaleFactor, center A transzformációk a már ismertetett módon működnek. Texture2: Ezzel lehet hozzárendelni a textúrákat a testekhez. Négy mezője van: filename, warpS, warpT, image. A filename mezőben adjuk meg a kívánt fájlnevet A warpS mező az X irányú módot határozza meg, a warpT az Y tengely irányában határozza meg a kitöltés milyenségét. Az image mezőben bitenként írhatjuk le a képet, ha nem adtunk meg fájlt Fények és megvilágítások, kamerák PointLight – pontlámpa: Pontszerű fényforrás, minden irányban egyformán világít. Négy mezője van, a kapcsoló, fényintenzitás, szín, relatív hely. DirectLight – irányított fényforrás: Ez a fényforrás csak egy irányba világít, a fénysugarak egy irányba mutatnak, egymással

párhuzamosan. Négy mezője van Az első három mező maradt az előző, a negyedik mező változott, itt az irányát adja meg a fényforrásnak. SpotLight – reflektorfény: A reflektorfény egy irányba kibocsátott fénykúpot bocsát ki, és az ezen belüli tárgyakat világítja meg. Hat mezője van, az első négy megegyezik az irányított fényforrás mezőivel. A másik két mező a kioltási faktor, és a fénykúp nyílásszöge 88 PerspectiveCamera – perspektivikus kamera: Ez a kameratípus érvényesül a világunkban. Hat mezője van, a helyzet, forgatási tengelyérték, fókusztávolság, látószög, elülső távolság, hátulsó távolság. OrtographicCamera – ortografikus kamera: Erre a kamerára nem érvényesek a megszokott rövidülési szabályok. Ennek is hat mezője van, öt megegyezik a perspektivikus kameratípussal. A hatodik (látószög) helyett a látónégyzet mértékét lehet megadni Csoportnode-ok Group, TransformSeparator: Nincs

speciális mezőjük. Separator: Egy kötelező mezője van, a renderCulling. Ezzel állíthatjuk be a browsernek, hogy a csoport minden tagját megrajzolja-e, vagy csak a befogadó térrész koordinátáit és láthatóságát. Switch: Egy mezője van, a whichChild. Ezzel állíthatjuk be, hogy hány utódot rajzoljunk meg. DEF – definíció: Lehetőségünk van egy node-ot vagy egy csoportot elnevezni vele, majd a USE kulcsszóval meghívhatjuk anélkül, hogy újra begépelnénk. Hálózati illesztés WWWAnchor: Arra szolgál, hogy egy tárgyra kattintva követhessünk egy linket. Három mezője van, a link címe, szöveg a kapcsolathoz, és a map. WWWInline: Arra szolgál, hogy egy térrészre kattintva követhessünk egy linket. Három mezője van, a link címe, a térrész mérete, és a térrész középpontja. 89 13. tétel Az adatbázis fogalma Az adatmodellnek megfelelően az adatbázis-kezelő rendszerek az adatokat összefüggéseikben, kapcsolataikkal együtt

egyetlen integrált rendszerben, az adatbázisban tárolják. Adatbázisokkal kapcsolatos fogalmak Adatmodell Az adatbázis-kezelő rendszerek által használt leképezési módot adatmodellnek nevezzük. Az adatmodell a valós világ leképezése valamilyen tárolási struktúrába. Az adatmodell meghatározza a tárolási szerkezetet, mely úgynevezett modellezési alapelemben történik. Ilyen alapelem lehet például a táblázat. Az adatmodellhez szabályok is tartoznak, melyeket a tárolt adatnak az adatbázis élete során mindig ki kell elégíteni. Az azonosítást és kapcsolatleírást szolgáló adatokra vonatkoznak az úgynevezett integritási szabályok, amelyekkel garantálhatjuk az adatbázis hibátlanságát. Más adatokra is előírhatunk az adatmodellben szabályokat, amelyeket megszorításoknak nevezünk. Az adatmodell negyedik részét az adatokon elvégezhető műveletek adják. Az évek során többféle adatmodellt dolgoztak ki, és alkalmaztak a gyakorlatban.

Hierarchikus adatmodell: Az egyed adatait, tulajdonságait logikailag összetartozó adatsorban, úgynevezett rekordban tárolják. A rekordokhoz kapcsolómezőket fűznek, amelyek a rekorddal kapcsolatban álló további rekordokra mutatnak. A modell hátránya, hogy csak 1:1 és 1:N típusú kapcsolatok leírására alkalmas. Hálós adatmodell: Az egyed adatait rekordban tárolja, a kapcsolatok leírására kapcsoló mezőkből álló kapcsolórekordot alkalmaz. Mindhárom típusú kapcsolatot képes leírni Relációs modell: Az egyedhalmazok és a kapcsolatok adatait, tulajdonságait táblázatokban tárolja, mindhárom kapcsolattípust kezeli. Egyed-kapcsolat modell: Elméleti adatmodell, számítógépes gyakorlati megvalósítása nincs. A modellezési alapfogalmakhoz külön grafikus jeleket rendel, az adatmodell egy grafikus diagram. Mindhárom kapcsolattípust kezeli Szintek A gyakorlatban először az adatbázis szerkezetét kell kialakítani. Az adatbázis szerkezetét

három szinten kell definiálni, ezek a fizikai, a koncepcionális és a külső szint. A koncepcionális szintet szokás sémának, a külső szintet alsémának, a fizikai szintet pedig belső szintnek is nevezni. A koncepcionális szint tartalmazza az adatbázisnak a tervezés során létrehozott absztrakt leképezését, az adatmodellt. Ezen a szinten definiáljuk, hogy milyen tárolási alapelemek, például táblázatok tartalmazzák az adatbázis adatait, továbbá azt is, hogy milyen adatok állnak kapcsolatban egymással. A koncepcionális szint tartalmazhat az egyes adatokra 90 vonatkozó előírásokat is, melyeket megszorításoknak nevezünk, és amelyek teljesülését az adatbázis-kezelő rendszer automatikusan ellenőrzi. Ugyancsak automatikusan ellenőrzi a kapcsolatok helyességét, és amennyiben a felhasználó kéri, automatikus kapcsolatmódosítást is végrehajt. A fizikai szint írja le a koncepcionális szint elemeinek fizikai tárolási és elérési

rendszerét. A fizikai tárolásnál kerül kialakításra, hogy az egyes adatok milyen lemezen, azon belül melyik cilinderen, sávon és blokkban tárolódnak. Az elérési mód meghatározza az adatok elérési sorrendjét, például fizikai tárolási rendben, közvetlenül, stb. A koncepcionális szint fizikai szintre történő leképezését általában maga az adatbázis-kezelő rendszer hajtja végre, ebbe a felhasználónak nincs beleszólása. A külső szint valójában a valós világnak egy közvetett leképezése oly módon, hogy a koncepcionális szint elemeiből újabb adatbáziselemeket képezünk, amelyeket ugyan megjelenítünk a képernyőn vagy nyomtatásban, de nem tárolunk az adatbázisban. Például az adatbázis két táblázat adataiból létrehozunk egy harmadik táblázatot, amit megjelenítünk, de nem tárolunk. A tárolás felesleges lenne, és többszörös tárolást eredményezne, hiszen a kívánt táblázat az adatbázis két táblázatából

bármikor előállítható. Adatfüggetlenség Az adatbázis-kezelő rendszereknek biztosítani kell az adatfüggetlenséget. Ha a szerkezetet megváltoztatjuk, az nem vonhatja maga után az összes felhasználói program módosítását, csupán azokét, amelyek miatt a szerkezet megváltoztatása szükségessé vált. Például, ha egy új táblázattal bővítjük az adatbázist, akkor csak azokat a programokat kell módosítani, amelyek az új táblázatot kezelik. Ezt a megoldást logikai adatfüggetlenségnek nevezzük A fizikai tárolás és elérési mód megváltoztatásának sem lehet a felhasználói programok módosítását igénylő hatása. Például nem kell a felhasználói programot módosítani, ha új típusú lemezen tároljuk az adatbázist. Ezt a jelenséget fizikai adatfüggetlenségnek nevezzük Ha a fizikai és logikai adatfüggetlenség is teljesül, akkor adatfüggetlenségről beszélünk. Nyelvek Az adatbázis-kezelő rendszerek az adatbázis kezelését

valamilyen adatbázis-kezelő nyelv segítségével biztosítják, melyek három fő részből állnak. Az adatleíró nyelv (DDL – Data Definition Language) tartalmaz olyan utasításokat, amelyek segítségével az adatbázis elemeit létrehozhatjuk, törölhetjük, illetve módosíthatjuk a szerkezetüket. Az adatkezelő nyelv (DML – Data Manipulation Language) segítségével a felújítási és lekérdezési műveletek hajthatók végre. Az adatfelügyelő nyelv (DCL – Data Control Language) körébe soroljuk a jogosultságok, tranzakciók, zárolások kezelését biztosító utasításokat. 91 14. tétel Adatbázis-kezelő rendszerek tulajdonságai, fogalmak Az adatbázis-kezelő rendszerek olyan általános célú szoftverek, amelyek lehetővé teszik a valós világ dolgainak számítógépes leképezését, beleértve a különböző dolgok között fennálló kapcsolatokat is. Az adatbázis-kezelő rendszerek kezelik az adatbázist, biztosítják az adatbázis

adatainak elérését, biztosítják az adatbázis adatai hibátlanságának megőrzését, és szabályozzák az adatbázishoz való hozzáférést. Az adatbázis-kezelő rendszernek biztosítani kell az adatfüggetlenséget. Az adatbázis-kezelő rendszernek biztosítani kell az adatok védelmét. Ennek érdekében az adatbázis-kezelő rendszerek hozzáférési jogosultságokat definiálnak. A jogosultságokkal egyrészt szabályozhatjuk, hogy mely felhasználók használhatják az adatbázist, másrészt azt is megadhatjuk, hogy az adatbázis egyes elemekhez kik férhetnek hozzá, és milyen műveleteket hajthatnak végre rajtuk. Az adatbázis-kezelő rendszernek gondoskodnia kell az adatbázis hibátlanságáról. Az adatbázisban tárolt adatsorokat az adatok visszanyerésének érdekében egyértelmű, egyedi értékű adattal azonosítják. Az adatbázis-kezelő rendszernek ellenőriznie kell, hogy az azonosító egyedi értékű-e, a kapcsolat leírásánál létező

azonosítóra hivatkozik-e. Ha az azonosítót módosítják, a legtöbb adatbázis-kezelő rendszer automatikusan végrehajtja a módosítást minden olyan helyen, ahol az azonosító előfordul, így biztosítva a hibátlan adatbázist. Ha valamilyen előre nem látható hiba folytán az adatbázis megsérül, az adatbázis-kezelő rendszernek képesnek kell lennie a helyreállításra. Ezt úgy érik el, hogy az adatbázisban végrehajtott műveleteket naplózzák. Ez a naplózás azt is lehetővé teszi, hogy bizonyos műveletsorozatot, úgynevezett tranzakciót érvényesítsünk, és visszaállítsuk a műveletsor előtti állapotot. Az adatbázisok többségét egy időben egyszerre több felhasználó kezeli. Ez felvet bizonyos problémákat. Ha egyidejűleg ugyanazt az adatsort több felhasználó is módosítja, hibás adatok keletkezhetnek. Az ilyen és hasonló problémák elkerülése érdekében az adatsort zárolják, azaz nem teszik hozzáférhetővé más felhasználó

számára mindaddig, amíg egy megkezdett felújítási művelet be nem fejeződik. A zárolás nem csak adatsor, hanem fizikai összetevők, azaz lap, blokk szintjén is megvalósulhat, de történhet az adatbázis tárolási alapegysége, például táblázat szintjén is. Az adatbázis-kezelő rendszerek az adatbázis kezelését valamilyen adatbázis-kezelő nyelv segítségével biztosítják, melyek három fő részből állnak, az adatleíró, az adatkezelő és az adatfelügyelő nyelvből. Az adatbázis-kezelő rendszerek napjainkban úgynevezett aktív elemeket használnak. Az aktív alatt itt azt értjük, hogy az adatbázis adott komponense mindig elérhető és készen áll arra, hogy a rendszer végrehajtsa, amikor szükség van rá. Két fajtáját különböztetik meg: - A megszorítások logikai értékű függvények, amelyek által visszaadott értéktől azt várjuk el, hogy igaz legyen. - A trigger egy programkód részlet, amelyik egy esemény bekövetkezésére

vár. A lehetséges események például a beszúrás, a módosítás vagy a törlés. Amikor az esemény bekövetkezik, a megfelelő műveletsorozat végrehajtódik, vagy más szóval kiváltódik (trigger = kivált). 92 Adatbázis-kezelő rendszerek például a dBASE, Access, Foxpro, MS SQL Server, Oracle, Ingres, Paradox, DB2. Az első négy PC-s adatbázis-kezelő rendszer, míg a többieknek különböző típusú számítógépre fejlesztett változatai léteznek. Tranzakció kezelés Van néhány fontos szempont, amit az adatbázis-kezelőnek garantálnia kell azok számára, akik az adatbázison műveleteket hajtanak végre. Az adatbázis-kezelők többnyire megengedik a felhasználóknak, hogy egy vagy több lekérdezést vagy módosítást egy tranzakcióba csoportosítsanak. A tranzakció tulajdonképpen olyan műveletek egy csoportja, amelyeket egymás után egy egységként kell végrehajtani. Az adatbázisrendszerek gyakran sok tranzakció egyidejű végrehajtását

engedik meg. Annak biztosítása, hogy mindezek a tranzakciók helyesen fussanak le, a tranzakció-kezelő feladata. A tranzakciók helyes lefutásán értjük a következőket: - Atomosság: Megköveteljük, hogy a tranzakció vagy teljes egészében hajtódjon végre, vagy semmi ne hajtódjon végre belőle. - Következetesség: Egy adatbázisban általában beszélhetünk a következetes állapotok fogalmáról, amelyekben az adatok megfelelnek bizonyos elvárásoknak. Ezt a feltételt megsérthetjük egy rövid időre egy tranzakció alatt, a tranzakció-kezelőnek kell biztosítani, hogy a tranzakciók befejeződése után az adatbázis ismét következetes állapotba kerüljön, vagyis elégítse ki az összes következetességi feltételt. - Elkülönítés: Amikor két vagy több tranzakció egyidejűleg fut, azok kihatását el kell különíteni egymástól. Ez azt jelenti, hogy semmiféle olyan eredményt vagy kihatást nem tapasztalhatunk az adatbázisban, amit a két

tranzakció egyidejű futása okozott, és ami nem fordult volna elő, ha a két tranzakció egymás után fut le. - Tartósság: Ha egy tranzakció befejezte a munkáját, akkor annak eredménye nem veszhet el rendszerhiba esetén sem, még akkor sem, ha a rendszer közvetlenül a tranzakció befejezése után hibásodik meg. A tranzakció-kezelő az összes megkezdett tranzakciót, a tranzakciók által az adatbázisban végzett módosításokat, és a tranzakciók végét feljegyzi egy naplóba. A napló mindig olyan tárolóeszközökre íródik, ami nem érzékeny az esetleges áramkimaradásra. Ilyenek például a lemezek. Ezért noha a tranzakció a munkájának egy részéhez a sokkal érzékenyebb memóriát használja, a napló minden esetben azonnal lemezre íródik. Az összes művelet naplózása fontos szerepet játszódik a tartósság biztosításában. A tartósság és az atomosság érdekében a tranzakciók egyfajta „puhatolózás” jelleggel kerülnek

végrehajtásra, ami azt jelenti, hogy az adatbázisbeli módosítások kiszámításra kerülnek, de ténylegesen az adatbázisban még nem történnek meg. Amikor a tranzakció készen áll a befejezésre, arra, hogy érvényesítse az elvégzett munkát, a módosítások a naplóba kerülnek. Először ezek a naplóbejegyzések íródnak lemezre, és csak ezután történik meg az adatbázis tényleges módosítása. 93 15. tétel Modellezési alapfogalmak A valós világot önállóan létező dolgok alkotják. Ezeket az önálló létű dolgokat az adatmodellezésben egyednek nevezzük. Az azonos fajtájú, közös jellemzőkkel rendelkező egyedek együttese az egyedhalmaz. Az egyedhalmaz a matematikai értelemben vett halmaz fogalmat jelenti, a halmazban nincs ismétlődés, minden egyed csak egyszer fordul elő. Az egyedekre és egyedhalmazokra hivatkoznunk kell. Az egyedek azonosítása általában valamilyen egyértelmű jellemzőjükkel történik. Bizonyos esetekben

előfordulhat, hogy nem találunk olyan egyedjellemzőt, ami egyértelműen azonosít, ilyenkor mi hozunk létre egy azonosítót. Ennek legegyszerűbb módja az egytől kezdődő, folyamatos sorszámozás Az egyedek és egyedhalmazok nem függetlenek egymástól, közöttük különféle viszonyok állnak fenn. Két egyedhalmaz között fennálló viszonyt kapcsolatnak nevezünk Az egyedek közötti viszonyt kapcsolat-előfordulásnak nevezzük. A kapcsolatokat és kapcsolatelőfordulásokat is tudnunk kell azonosítani A kapcsolatokat megnevezzük egy egyértelmű névvel. A kapcsolat-előfordulásokat a résztvevő egyedek azonosítóival azonosítjuk. A kapcsolatokat kétféle szempont szerint szoktuk osztályozni. Az egyik az úgynevezett típus szerinti osztályozás, amikor is azt vizsgáljuk, hogy az egyik egyedhalmaz egy egyede a másik egyedhalmaz hány egyedével áll kapcsolatban. Ebben az értelemben megkülönböztetünk 1:1, 1:N és N:M típusú kapcsolatokat.

Természetesen az is előfordulhat, hogy két egyedhalmaz egyedei között semmilyen viszony nem áll fenn, ez esetben e két egyedhalmaz független egymástól. Az egy-egy (jelölése: 1:1) típusú kapcsolat olyan kölcsönösen egyértelmű viszony, amelyben az egyik egyedhalmaz egyedei a másik egyedhalmazból pontosan egy egyeddel állnak kapcsolatban és viszont. Ilyen típusú kapcsolat például az országok és zászlók közötti kapcsolat. Az egy-több (jelölése: 1:N) típusú kapcsolatban az egyik egyedhalmaz egyedei a másik egyedhalmaz több egyedével vannak kapcsolatban, azonban a másik egyedhalmaz egyedei pontosan egy kapcsolatban szerepelnek. Ilyen típusú kapcsolat áll fenn többek között az anyák és gyermekek között. A több-több (jelölése: N:M) típusú kapcsolatban az egyik egyedhalmaz egyedei a másik egyedhalmaz több egyedével vannak kapcsolatban, és a másik egyedhalmaz egyedei is az első egyedhalmaz több egyedével lehetnek kapcsolatban.

Ilyen típusú kapcsolat áll fenn például a kiadók és művek között. A kapcsolat típusát csak a valóság pontos ismeretében lehet meghatározni. Két egyedhalmaz közötti, azonos célú kapcsolat a körülményektől függően más-más típusú lehet. A kapcsolatok másik típusú osztályozása a résztvevők száma alapján történik. Ez alapján megkülönböztetünk egy résztvevős (unáris), két résztvevős (bináris) és három résztvevős (trináris) kapcsolatokat. Természetesen háromnál több résztvevője is lehet egy kapcsolatnak Az egyedek, egyedhalmazok, kapcsolatok jellemzőit tulajdonságoknak, vagy más néven attribútumoknak nevezzük. A tulajdonságokat egyértelmű névvel látjuk el A tulajdonságok konkrét adatértékekkel rendelkeznek, melyeket tulajdonság-értékeknek nevezünk. A tulajdonságokat megkülönböztetjük a jellemzőik alapján, az alábbiak szerint: - Azonosító tulajdonság, amely az egyedeket egyértelműen azonosítja,

és egyedi értékkel rendelkezik, például személyi szám. - Egyértékű tulajdonság, amely egyetlen adatértékkel rendelkezik, például születési idő. - Többértékű tulajdonság, amely több adatértékkel rendelkezik, például nyelvvizsga. - Egyszerű tulajdonság, amely további tulajdonságokra nem bontható. - Összetett tulajdonság, amely további tulajdonságokra bontható, például cím. 94 - Származtatott tulajdonság, amely más tulajdonságokból meghatározható, például a születési időből az életkor kiszámolható. Tárgy-kapcsolat modell és diagram Ez a modell elméleti adatmodell, számítógépes megvalósítása nem létezik. A kapcsolatokban szereplő dolgokat a következő jelölésekkel illetjük: : a tárgyak jele. : a kapcsolatok jele. : az attribútumok jele. Tekintsünk egy igen egyszerű példát: A dolgozik nevű kapcsolat fejezi ki a két rekord: ember(név, .) illetve cég() viszonyát (A zárójelekben lévő

"."-ok további attribútumokat jelent(h)e(t)nek) Egy-egy kapcsolat Egy bizonyos személy munkahelye számára fontos adatai szerepelnek a dolgozó, személyi adatai pedig az ember nevű tárgy attribútumaiként. Minden egyes dolgozó tárgyhalmazbeli tárgyhoz (esetünkben ez egy személy) egyértelműen létezik egy emberbeli tárgy (szintén személy), és fordítva. Ez egy kölcsönösen egyértelmű megfeleltetés Több-egy kapcsolat Minden személynek egyértelműen létezik egy édesanyja, de egy anyának lehet több gyereke is. Ez már NEM kölcsönösen egyértelmű megfeleltetés Több-több kapcsolat 95 Egy gyerek szülőjének (általában) többen is mondhatják magukat, és egy szülőnek is lehet több porontya. Nézzünk egy testesebb diagramot: Ebben a példában az ország(név, elnök, .), cég(név, hely, ), áru(kód, név, ) tárgyhalmazokat a termel kapcsolat köt össze. Itt a kulcs a vastagon szedett attribútumok halmaza.

Tárgy-kapcsolat modell leképezése relációs modellre A két modell között a kapcsolatot a következő egyszerű átírás mutatja: Tárgy-kapcsolat modell Relációs modell tárgy tárgynév tulajdonságok ← ← ← reláció relációnév attribútumok kapcsolat kapcsolatnév kulcstulajdonságok ← ← ← reláció relációnév attribútumok Az iménti példa átírása relációs modellé: CÉG ORSZÁG 96 ÁRU A kapcsolat leírására ez a táblázat (adatbázis) szolgál: TERMEL 97 16. tétel Relációs algebra A relációs algebra néhány egyszerű, de hathatós módszert ad arra nézve, hogy miként építhetünk új relációkat a régi relációkból. Egy reláció megadható nevével, vagy közvetlenül sorainak egy listájával. Egy lekérdezés tulajdonképpen egy relációs algebrai kifejezés Relációs műveletek A halmazműveletek relációkra történő alkalmazásakor néhány feltételt kell szabnunk: - Az R és S

relációk sémája ugyanazt az attribútum halmazt kell, hogy tartalmazza. - Mielőtt kiszámolnánk a halmazelméleti egyesítést, metszetét vagy különbségét a sorhalmazoknak, az R és S oszlopait rendezni kell úgy, hogy az attribútumok sorrendje egyforma legyen mindkét reláció esetén. Egyesítés R és S egyesítése, azon elemek halmaza, amelyek vagy az R-ben vagy az S-ben vannak. Egy elem csak egyszer szerepel az egyesítésben, még akkor is, ha jelen van az R-ben is és az Sben is. Jelölése: R∪S. Metszet R és S metszete, azon elemek halmaza, amelyek az R-ben és az S-ben is jelen vannak. Jelölése: R∩S. Különbség R és S különbsége, azon elemek halmaza, amelyek benne vannak R-ben, de nincsenek S-ben. Jelölése: R–S. Vetítés A vetítés operátorral a régi R relációból olyan új reláció hozható létre, amelyik csak az R bizonyos oszlopait tartalmazza. Jelölése: π ( R) . A1, A2,., An Kiválasztás Az R relációra alkalmazott kiválasztás

operátor olyan új relációt hoz létre, amely az R sorainak egy részhalmazát tartalmazza. Az eredménybe azok a sorok kerülnek, amelyek teljesítenek egy adott, az R attribútumaira megfogalmazott C feltételt. A C egy olyan feltételes kifejezés, amilyet megszoktunk a hagyományos programozási nyelveknél. Jelölése: σ C (R) . Descartes-szorzat Két halmaz, R és S Descartes-szorzata azon párok halmaza, amelynek első eleme az R tetszőleges eleme, a második pedig az S egy eleme. Amikor R és S relációk, a szorzat is reláció. Jelölése: R×S. 98 Természetes összekapcsolás Két reláció szorzásánál jóval gyakrabban van szükségünk arra, hogy összekapcsoljunk relációkat oly módon, hogy csak azokat a sorokat párosítjuk, amelyek valamilyen módon összeillenek. Az összeillesztés legegyszerűbb módja két reláció természetes összekapcsolása, amelyben R-nek és S-nek csak azokat a sorait párosítjuk össze, amelyek értékei megegyeznek az R

és S sémájának összes közös attribútumán. Jelölése: R  S . A természetes összekapcsolás kifejezhető a vetítés, a Descartes-szorzás és kiválasztás segítségével: R  S = π L (σ C ( R × S )) , ahol L olyan attribútum lista, amelyben szerepel az R összes attribútuma és emellett S-ből mindazok az attribútumok, amelyek nincsenek benne az R sémájában. Théta-összekapcsolás A természetes összekapcsolás előírja, hogy egyetlen speciális feltétel szerint párosítsuk a sorokat. Néha szükség lehet két reláció sorainak más szempontból történő párosítására Erre szolgál a Théta-összekapcsolás. A „théta” egy tetszőleges feltételre utal, amit θ helyett inkább C-vel jelölünk. Jelölése: R  C S . A Théta-összekapcsolás kifejezhető a Descartes-szorzás és kiválasztás segítségével: R  C S =σ C ( R × S ) Teljes, több mint teljes nyelvek Azokat a lekérdező nyelveket, amelyek lekérdező ereje

ugyanakkora, mint a relációs algebráé teljesnek, amelyeknek nagyobb több mint teljesnek nevezzük. Előfordulhat, hogy az adatbázisra vonatkozó kérdés kifejezésére több, egymással ekvivalens relációs algebrai kifejezés létezik, amelyek különbözhetnek egymástól számítási időben, bonyolultságban stb. 99 17. tétel Relációs adatmodell A relációs modellben az egyedhalmazok és a kapcsolatok attribútumainak tárolására egy kétdimenziós táblázat szolgál, amelyet szokás relációnak is nevezni. Ennek a táblázatnak a következő tulajdonságokkal kell rendelkeznie: - Minden táblázatnak egyértelmű névvel kell rendelkeznie. - A táblázat minden sorában azonos számú oszlop található. - Két azonos nevű oszlopot a táblázat nem tartalmazhat. - Az oszlopok csak elemi típusú adatokat tartalmazhatnak. - Egy oszlopbeli értékeknek ugyanabból az értékhalmazból kell származnia. - A táblázat egy sorában vagy egy egyed, vagy egy

kapcsolat-előfordulás adatai szerepelhetnek. - A táblázatban két egyforma sor nem szerepelhet. - A táblázatban kell lennie egy olyan minimális oszlopkombinációnak (elsődleges kulcsnak), amely a táblázat sorait egyértelműen azonosítja. Kulcsok fajtái - Egyszerű kulcs. - Összetett kulcs: 2 vagy több attribútum alkotja. - Minimált kulcs: összetett kulcs esetén bármelyik attribútumot vesszük is el belőle, akkor már nem kulcs, azaz a legkisebb részhalmaz, ami még azonosít. - Kulcsjelöltek: minimális kulcsok közül választhatunk. - Elsődleges kulcs: a kulcsjelöltek közül kiválasztott kulcs, nem lehet NULL. - Alternatív kulcsok: a kulcsjelöltekből nem elsődleges kulcsként kiválasztott elemek. - Idegen kulcs: olyan attribútum (attribútum halmaz), amelyik egy másik relációban elsődleges kulcsként szerepelt. Funkcionális függőség Akkor mondjuk, hogy a B oszlop funkcionálisan meghatározza a C és D oszlopot, vagy más szóval a C és D

oszlop funkcionálisan függ a B oszloptól, ha a táblázat két sorában a B oszlop értékei megegyeznek, akkor a C és D oszlop értékei is megegyeznek. A függőségi viszony jelölése: B C, D. Teljes funkcionális függőségről beszélünk, ha a funkcionálisan meghatározó tulajdonságok egyetlen valódi részhalmazától sem függnek a meghatározott tulajdonságok, azaz ha A, B C, D igaz, de A C, D és B C, D egyike sem áll fenn. Normálformák Egy táblázat akkor van első normálformában, ha soraiban minden tulajdonságérték atomi, azaz további adatértékekre nem bontható. Más szóval a táblázat minden mezője csak egy adatértéket tartalmaz. Egy táblázat akkor és csak akkor van második normálformában, ha első normálformában van és minden, az elsődleges kulcs részét nem képező tulajdonsága funkcionálisan teljesen függ a táblázat elsődleges kulcsától. 100 Egy táblázat akkor és csak akkor van harmadik normálformában, ha

második normálformában van és az elsődleges kulcs részét nem képező tulajdonságai között nem áll fenn funkcionális függőség. További normálformák is léteznek, de a normalizálás során legalább a harmadik normálformát követeljük meg. 101 18. tétel SQL Az SQL, a Structured Query Language angol elnevezésből alkotott mozaikszó, a relációs adatbázis-kezelő rendszerek ma legelterjedtebb, szabványosított adatbázis-kezelő nyelvének elnevezése. Az angol elnevezés szószerinti magyar fordítása strukturált lekérdező nyelv Az SQL nyelv valójában egy komplett adatbázis-kezelő nyelv, amely tartalmaz adatdefiníciókat, adatmanipulációs és az adatfelügyelet körébe tartozó utasításokat is. Az SQL deklaratív nyelv, tehát csak azt kell leírni az utasítással, hogy mit szeretnénk eredményként látni, azt nem, hogy kell azt a rendszernek előállítani. Ez utóbbit maga az adatbázis-kezelő rendszer határozza meg. Az SQL nyelv

utasításai záradékokból épülnek fel. A záradékok sorrendje kötött A nyelv maga szabad írásmódú, az utasításokat pontosvessző zárja. Adattípusok - CHAR (n): Egy rögzített hosszúságú (n) karaktersort jelöl. - VARCHAR (n): Egy legfeljebb n hosszúságú karaktersort jelöl. - BIT (n): Egy n hosszúságú bitsort jelképez. - INT, INTEGER, SHORTINT: Egész számokat jelképeznek. - REAL, FLOAT: Lebegőpontos értékek tárolására szolgál. - DECIMAL (n, d): Fixpontos valós számok tárolására szolgál, ahol n a számjegyek száma, és d a tizedes jegyek száma. - DATE: Dátumot jelképez. - TIME: Időt jelképez. Tábla létrehozása A legegyszerűbb módja egy tábla létrehozásának a CREATE TABLE kulcsszavakból, a relációnévből, az attribútumokból és típusaiknak zárójelek közé tett listájából áll. Például: CREATE TABLE FilmSzínész ( név CHAR (30), cím VARCHAR (255), nem CHAR (1), születésnap DATE ); Tábla módosítása A

megfelelő utasítások az ALTER TABLE kulcsszavakkal és a reláció nevével kezdődnek. Ezután több lehetőségünk is van, a legjelentősebbek a következők: - ADD: új attribútum hozzáadása a relációhoz. - DROP: attribútum törlése a relációból. Például: ALTER TABLE FilmSzínész ADD telefon CHAR (16); ALTER TABLE FilmSzínész DROP születésnap; 102 Megszorítások A megszorításokat bármikor módosíthatjuk, törölhetjük, vagy újakat hozhatunk létre belőlük. A megszorításnak adhatunk nevet. Ezt úgy tehetjük meg, hogy a megszorítás elé beírjuk a CONSTRAINT kulcsszót és a megszorítás nevét. Például: nem CHAR (1) CONSTRAINT FérfiVagyNő CHECK (nem IN (’F’, ’N’)), Kulcsok megadása Az elsődleges kulcs a reláció egy vagy több attribútumából állhat. Az elsődleges kulcsot a CREATE TABLE utasításon belül kétfajta módon adhatjuk meg. - Az attribútumot deklarálhatjuk elsődleges kulcsként akkor, amikor az

attribútumot felsoroljuk a relációsémában. Hozzáadhatunk a sémában deklarált elemek listájához egy további deklarációt, amelyik azt adja meg, hogy egy attribútum vagy egy attribútumhalmaz kulcsot alkot. Az első módszer esetén a PRIMARY KEY kulcsszót kell az attribútum neve és típusa után írnunk. Például: CREATE TABLE FilmSzínész ( név CHAR (30) PRIMARY KEY, cím VARCHAR (255), nem CHAR (1), születésnap DATE ); A második módszer esetén egy új elemet kell az attribútumok listája után írnunk, amelyik a PRIMARY KEY kulcsszóból és a kulcsot alkotó attribútum vagy attribútumok zárójelezett listájából áll. Ha a kulcs több attribútumból áll, akkor a második módszert kell használnunk Például: CREATE TABLE FilmSzínész ( név CHAR (30), cím VARCHAR (255), nem CHAR (1), születésnap DATE, PRIMARY KEY (név) ); A másik lehetőség a kulcsok deklarálására a UNIQUE kulcsszó használatával történik. Ez a kulcsszó pontosan

ott fordul elő, ahol a PRIMARY KEY kulcsszó. Ennek a deklarációnak is ugyanaz az értelme mint az elsődleges kulcs deklarációnak, de amíg elsődleges kulcsból csak egyet adhatunk meg egy táblához, addig a UNIQUE deklarációból akármennyit. Például: CREATE TABLE FilmSzínész ( név CHAR (30) UNIQUE, cím VARCHAR (255), nem CHAR (1), születésnap DATE ); 103 Egy reláció azon attribútumát vagy attribútumait idegen kulcsnak deklarálhatjuk, amelyek egy másik reláció bizonyos attribútumaira hivatkoznak. Ez a deklaráció két dolgot jelent egyszerre. - A másik reláció azon attribútumát vagy attribútumait, amelyekre hivatkozunk, elsődleges kulcsként kell deklarálni abban a relációban. Minden értéknek, ami az első relációban az idegen kulcs egy attribútumában szerepel, szerepelnie kell a második reláció megfelelő attribútumában is. Ez azt jelenti, hogy van egyfajta hivatkozásiépség-megszorítás, ami a két attribútumot vagy

attribútumhalmazt összekapcsolja. Ha az idegen kulcs egyetlen attribútum, akkor az attribútum neve és típusa után adhatjuk meg, hogy az egy másik tábla egy attribútumára hivatkozik. Például: CREATE TABLE Stúdió ( név CHAR (30) PRIMARY KEY, cím VARCHAR (255), elnökazon INT REFERENCES GyártásIrányító (azonosító) ); A másik lehetőség, hogy a CREATE TABLE utasításban az attribútumok listája után egy külön deklarációban adjuk meg, hogy bizonyos attribútumok idegen kulcsot alkotnak. Például: CREATE TABLE Stúdió ( név CHAR (30) PRIMARY KEY, cím VARCHAR (255), elnökazon INT, FOREIGN KEY elnökazon REFERENCES GyártásIrányító (azonosító) ); Tábla törlése Néha szükség van arra, hogy megszüntessünk egy táblát az adatbázissémában. A feltételek megváltozása miatt lehet, hogy felesleges az adatok karbantartása ebben a táblában. Az is lehetséges, hogy a reláció csak ideiglenes, valamely bonyolult közbülső lekérdezés

eredményeképpen. Ilyen esetben a relációt a DROP utasítással szüntethetjük meg Tábla feltöltése A tábla feltöltése, azaz sorok beszúrása egy relációba változtatásokat hoz létre, megváltoztatja az adatbázis állapotát. Például: INSERT INTO Szerep (filmcím, év, színésznév) VALUES (’Titanic’, 1998, ’Kate Winslet’); Lekérdezés Az egyszerű lekérdezés azon sorokra vonatkoznak, melyek egy bizonyos relációban eleget tesznek egy adott feltételnek. Egy ilyen lekérdezés a relációs algebra kiválasztási műveletének felel meg. 104 Például: SELECT * FROM Film WHERE stúdiónév = ’Disney’ AND év = 1990; A FROM záradék azon relációt vagy relációkat adja meg, melyekre a lekérdezés vonatkozik. A WHERE záradék egy feltétel, melyet a lekérdezésnek megfelelő sorok, ki kell, hogy elégítsenek. A SELECT záradék megadja a feltételeknek megfelelő sorok azon attribútumait, melyeket a lekérdezésre adott válasz

tartalmazni fog. A * azt jelzi, hogy a teljes sort tartalmazni fogja a válasz. Ha azt szeretnénk, hogy a kiválasztott sorok bizonyos komponenseit kizárjuk az eredményből, akkor levetítjük (vetítés) a lekérdezéssel előállított relációt néhány attribútumára. Például: SELECT cím, hossz FROM Film WHERE stúdiónév = ’Disney’ AND év = 1990; Néha a reláció sorait csoportosítanunk kell egy vagy több oszlop értékei szerint. Ekkor a WHERE záradék helyett a GROUP BY záradékot kell használni, amit a csoportosító attribútumok listája követ. A legegyszerűbb esetben a FROM záradék csak egy sorváltozót tartalmaz, és a reláció sorait csoportosítjuk a csoportosító attribútumoknak megfelelően. Például: SELECT stúdiónév, SUM (hossz) FROM Film GROUP BY stúdiónév; A példában a Film relációból kérdeztük le stúdiónként a gyártott percek összegét. Szükség lehet arra, hogy egy lekérdezés eredménye bizonyos sorrendbe

legyen rendezve. Az eredmény rendezése érdekében a select – from – where utasításhoz az ORDER BY záradékot kell még adni. Például: SELECT * FROM Film WHERE stúdiónév = ’Disney’ AND és = 1990 ORDER BY hossz, cím; A példában a filmeket hossz szerint szeretnénk lekérdezni növekvően, és az egyenlő hosszúakat ábécérendben. Feltételek Az SQL lehetővé teszi, hogy mintákkal összehasonlíthassunk karakterláncokat. Az összehasonlítás ilyen jellegű formája: s LIKE p, ahol s egy karakterlánc, p pedig egy minta. A minta egy karakterlánc, melyben használhatjuk a speciális % (bármilyen karakter) és (egy karakter) karaktereket. Például: SELECT cím FROM Film WHERE cím LIKE ’Halálos ’; 105 Összesítések Összesítés alatt egy olyan műveletet értünk, amely egy oszlop értékeiből egy értéket hoz létre. A SUM, az oszlopok értékeinek összegét határozza meg. Például: SELECT SUM (hossz) FROM Film; A MAX,

az oszlop értékeinek maximumát határozza meg. Például: SELECT MAX (hossz) FROM Film; A COUNT, az oszlopban található elemek számát határozza meg. Például: SELECT COUNT (hossz) FROM Film; Adatok törlése Az utasítás azt eredményezi, hogy a relációból kitörlődik minden olyan sor, amely megfelel a feltételnek. A törlés alakja: DELETE FROM táblanév WHERE (feltétel) Például: DELETE FROM Szerep WHERE filmcím = ’Titanic’ AND év = 1998 AND színésznév = ’Kate Winslet’; Tábla adatainak módosítása A módosítás az adatbázis egy speciális változtatása, melyben egy vagy több létező sor bizonyos komponenseinek értékét megváltoztatjuk. Például: UPDATE GyártásIrányító SET név = ’Ig.’ | | név WHERE azonosító IN ( SELECT elnökazon FROM Stúdió); A példában a 3. sor ellenőrzi, hogy a gyártásirányító azonosítója megegyezik-e a Stúdió reláció valamelyik sorának elnökazon komponensével. A 2 sor végrehajtja

a módosítást a megfelelő sorokon. A | | operátor karaktersorok összeillesztését jelenti Az így kapott karaktersor lesz a név komponens új értéke. 106