BMF-NIK 2005/2006/2007
Adatstruktúrák, Algoritmusok, Objektumok
BMF-NIK-AAO Adatstruktúrák, algoritmusok, objektumok (AAO) Szemelvénygyűjtemény a 2005/2006-os anyagból Csink László és Miklós Árpád előadásai alapján.
Tartalom ..................................................... 1. Algoritmus leírása, definíciója. ............................................4 Másodfokú egyenlet megoldása ..................................5 Közelítő gyökvonás (Newton módszer) ......................7 2. Egyszerű programozási tételek:............................................8 Sorozatszámítás...........................................................8 Eldöntés.......................................................................9 Kiválasztás ................................................................10 Megszámolás.............................................................11 Keresés ......................................................................12 Maximumkeresés ......................................................12 3. Adatkonverziók, ciklusok, függvények, tömbök................13 Adatkonverziók .........................................................13 Függvények ...............................................................16 4. Kiválogatás, szétválogatás, bináris keresés ........................19 Kiválogatás................................................................19 Szétválogatás (két tömbbe) .......................................20 Szétválogatás (egy tömbbe).......................................20 Bináris keresés...........................................................21 5. Halmazműveletek...............................................................22 Metszet ......................................................................22 Unió...........................................................................23 Összefuttatás (mergesort) ..........................................23 6. Rendezések.........................................................................24 Buborékrendezés (bubble sort)..................................24 Koktélrendezés (cocktail sort)...................................25 Kerti-törpe rendezés (garden gnome)........................26 Fésűs rendezés (combsort) ........................................27 Maximum kiválasztásos rendezés .............................28 Beszúrásos rendezés..................................................28 Galambdúc-rendezés (pigeonhole)............................29
2
BMF-NIK-AAO 7. A gyors-rendezés (quicksort) .............................................30 Rekurzívan ................................................................30 Nem rekurzívan .........................................................31 8. Játékok algoritmusai...........................................................35 9. Labirintusbeli út keresése...................................................39 10. A szóprobléma..................................................................42 11. Algoritmusok mátrixokkal ...............................................45 Ritka mátrixok...........................................................45 Mátrixok láncszorzása...............................................47 Strassen-féle mátrixszorzás .......................................47 12. A bűvös négyzet ...............................................................49 A bűvös négyzet fogalma ..........................................49 Ekvivalens bűvös négyzetek .....................................50 A bűvös összeg levezetése ........................................50 Coxeter módszer........................................................51 Piramis módszer ........................................................52 13. Egyéb algoritmusok..........................................................53 Az euklideszi algoritmus ...........................................53 A Fibonacci sorozat...................................................53 A Horner séma ..........................................................54 Az erathostenesi szita ................................................54 14. Az OOP rész (Miklós Árpád előadásai) ...........................55 Számítási modellek és programozási paradigmák.....55 Az objektum-orientált programozási paradigma .......60 Az objektum-orientált paradigma alapelemei ...........66 Egységbezárás, adatrejtés..........................................74 Öröklés ......................................................................79 Többalakúság ............................................................83 Kód újrafelhasználás (rövidített vázlat) ....................89
3
BMF-NIK-AAO
1. Algoritmus leírása, definíciója. Algoritmus fogalma: Az algoritmus egy eljárás (jóldefiniált utasítások véges halmaza), amelyet valamely feladat megoldására készítünk. A feladat egy adott kezdeti állapotból egy meghatározott végállapotba jut (szakszóval: terminál). Az algoritmus kiszámítási bonyolultsága és hatákony implementációja az alkalmazott adatstruktúrától függ. Az algoritmus tipikusan kisebb-nagyobb alkotórészekből épül fel. Az egyszerű algoritmus egy ételrecepthez hasonlítható. A formális definíció Alan Turing (Turing gép, 1936) és Alonzo Church (lambda kalkulus) matematikusokhoz köthető. Informálisan - hétköznapi szavakkal - egy egyszerű algoritmus egy receptnek tekinthető. A recept tartalmazza az adott étel nevét, elkészítésének idejét, a szükséges alkotórészek nevét és mennyiségét, az elkészítéshez szükséges eszközöket illetve környezetet (pl. mikrosütő), az elkészítéshez szükséges eljárásokat meghatározott sorrendben, az elkészült adagok számát, a kalória tartalmat egy adagra vetítve, az étel eltarthatóságának idejét. Egy program használhatóságához szükséges, hogy az elméleti megalapozás korrekt legyen! Ha nincs megfelelő bizonyítás, akkor nem ad megoldást a program, hiszen nem tudhatjuk hogy véget ér-e, és ha igen akkor korrekt eredményt ad-e? A napi gyakorlatban ritkán készítünk új algoritmust, inkább a már meglévőket használjuk. De ezt nem mindig tehetjük meg: 1. A feladat pontos megértéséhez gyakran el kell kezdeni megoldani a feladatot. Nem mindig van tehát elegendő információnk a feladatmegoldás kezdetén ahhoz, hogy algoritmus adatbázisokat vagy szakirodalmat használjunk. 2. Ahhoz, hogy a megfelelő megoldási változatot (paraméterek, sebesség, környezet stb.) kiválasszuk, algoritmuselmélet ismeretekre – és implementációs gyakorlatra – van szükségünk. 3. Lehet, hogy az adott feladatra nem találunk az igényeinket kielégítő megoldást. 4. Lehet, hogy a talált megoldásnál jobb jut eszünkbe (hiszen azokat is kitalálta valaki valamikor).
4
BMF-NIK-AAO Másodfokú egyenlet megoldása A másodfokú egyenlet receptje: Készítsünk algoritmust a 0=ax2+bx+c egyenlet megoldására. 1.lépés: az input adatok meghatározása: a, b, c valós számok 2.lépés: az output adatok meghatározása: egy valós szám, vagy két valós szám, vagy nincs megoldás A recept adatai: név: masodfoku; elkészítés ideje: 2006-07-11; szerző: Csink László; az elkészítéshez szükséges eszközök, illetve környezet: Turbo C++ 3.0 Windows XP operációs rendszer alatt; az elkészítéshez szükséges eljárások: gyökvonás, abszolút érték (ezek elkészítettnek tekintett programok) A feladat pontosítása: Hasznos megnézni egy konkrét példát: 0=4x212x+8; a megoldás: x1=2, x2=1; erre a feladatra ez a két értékadás tulajdonképpen egy program. Ez a program azonban nem ad megoldást a többi másodfokú egyenletre. Azt szeretnénk, hogy ugyanaz a program minden másodfokú egyenletre megoldást adjon. Mit tegyünk pl a 0=-12x+8 egyenlettel? Ez már elsőfokú. El kell dönteni, hogy eredetileg a másodfokú, vagy a legfeljebb másodfokú egyenlet megoldását tűztük-e ki célul? Megállapítható ezen példa alapján, hogy a feladat pontos mibenléte gyakran a megoldás során tisztázódik. A specifikáció tehát finomodhat a megoldás közben. A Specifikáció: Oldjuk meg a 0=ax2+bx+c egyenletet minden a, b, c valós szám esetén. Nevezzük a {0=ax2+bx+c | a, b, c valós számok} halmazt problémaosztálynak, melynek a megoldását keressük. Lehetett volna a problémaosztályt {0=ax2+bx+c | a, b, c valós számok és a≠0} halmaznak választani, akkor a megoldási algoritmus kicsit egyszerűbb, de kevésbé általános. Létezik-e megoldás? Tudjuk, hogy van megoldóképlet. Mivel komplex számokat nem engedünk meg, ezért nem minden esetben lesz megoldás. Hajlamosak vagyunk azt gondolni, hogy mindig létezik megoldás, de ez nem igaz, nem oldható meg pl. a szögharmadolási probléma: tetszőleges szög harmadának megszerkesztése. Egy probléma algoritmussal való megoldhatóságának kérdése igen mély dolog.
5
BMF-NIK-AAO A program pszeudokódja: PROGRAM MASODFOKU VÁLTOZÓK gy, a, b, c, x1, x2 VALÓS SZÁM; ag EGÉSZ SZÁM BEOLVAS(a, b, c) HA a=0 AKKOR HA b=0 AKKOR HA c=0 AKKOR ag=4 EGYÉBKÉNT ag=5 EGYÉBKÉNT{ ag=6; x1=-c/b; } EGYÉBKÉNT{ gy←(b*b-4*a*c) HA gy<0 AKKOR ag=1 EGYÉBKÉNT{ ag=2; gy←GYOKVONAS(b*b-4*a*c) HA gy=0 AKKOR x1=-b/(2*a) EGYÉBKÉNT{ ag=3 x1=(-b+gy)/(2*a) x2=(-b-gy)/(2*a) } } } ESETEK ag 1: KIIR(nincs valós megoldás) 2: KIIR(egy megoldás van:, x1) 3: KIIR(két megoldás van:, x1, x2) 4: KIIR(minden valós szám megoldás) 5: KIIR(nincs megoldás) 6: KIIR(elfajuló egyenlet, egy megoldás:, x1) ESETEK VÉGE PROGRAM VÉGE
6
BMF-NIK-AAO Közelítő gyökvonás (Newton módszer) Gyn+1=1/2(gyn+A/gyn) Legyen A>0, amelyből gyököt szeretnénk vonni, és gy1 tetszőleges, például 1. Ekkor elég nagy n-re gyn közel van egy számhoz, amely A négyzetgyöke. Más szóval a gyn sorozat konvergens és határértéke A négyzetgyöke. Ilyenkor elég nagy n-re gyn és gyn+1 egy tetszőlegesen előre megadott számnál is közelebb kerülnek egymáshoz. A következőkben gyn helyett gy-t, gyn+1 helyett ujgy-t írunk és iteratíven számolunk. Pszeudokód: VÁLTOZÓK inp, ujgy, gy, d, eps DUPLAPONTOS BEOLVAS(inp) //ebből akarunk gyököt vonni gy=1.0 d=1.0 eps=0.00001 ISMÉTELNI HA(d>eps){ ujgy←(1.0/2)*(gy+a/gy) d←|ujgy-gy| gy←ujgy } KIIR(gy)
7
BMF-NIK-AAO
2. Egyszerű programozási tételek: Sorozatszámítás ,,a múlt évben minden hónapban eltettem a gázszámlát. Szeretném kiszámolni, hogy mennyi pénzbe került az éves gázfogyasztás.” A megoldás lépései: 1. Lenullázok egy gyűjtőváltozót. 2. 12-szer ismétlem a következő két lépést: Megnézem a soron következő számlát, hozzáadom az előző összeghez. 3. Végül megkapom az eredményt. Pszeudokód: VÁLTOZÓK i, sum EGÉSZ, szamla[i] VALÓS(vagy EGÉSZ) i←0; sum←0; ISMÉTELNI HA (i kisebb mint 12){ sum←sum+szamla[i]; } KIÍR(sum)
(a jelölés szerint a hónapok számozása 0-ról indul)
8
BMF-NIK-AAO Eldöntés Egy tanuló érdemjegyei alapján szeretném eldönteni, hogy kitűnő-e, vagy sem. Kétféle ötlet lehetséges: 1.
Ha a jegyei között van olyan, ami nem ötös, akkor nem kitűnő
Nézzük végig a jegyeket, először az elsőt, majd sorra a többit, és ellenőrizzük hogy ötös-e. Ha találunk olyat ami nem ötös, akkor nem kell megnézni a további jegyeket, mert van nem ötös osztályzat, azaz nem kitűnő. Pszeudokód: VÁLTOZÓK tantárgy_szám, i, jegyek[i] EGÉSZ, van_nemotos LOGIKAI i←1 ISMÉTELD HA (i <= tantárgy_szám) és (jegyek[i] != 5){ i←i+1 } van_nemotos←(i <= tantárgy_szám) KIÍR(van_nemotos)
2.
Ha minden jegye ötös akkor kitűnő
Nézzük végig a jegyeket, először az elsőt, majd sorra a többit, és ellenőrizzük, hogy ötös-e. Ha a tömb minden elemét megvizsgáltuk, akkor minden érdemjegy ötös, azaz kitűnő. Pszeudokód: VÁLTOZÓK tantárgy_szám, i, jegyek[i] EGÉSZ, mind_otos LOGIKAI i←1 ISMÉTELD HA (i <= tantárgy_szám) és (jegyek[i] = 5){ i←i+1 } mind_otos←(i > tantárgy_szám) KIÍR(mind_otos)
9
BMF-NIK-AAO Kiválasztás Egy tankör zárthelyi dolgozatai közül válasszuk ki az egyik elégséges dolgozatot. Megoldás: nézzük végig a dolgozatokat, először az elsőt, majd sorra a többit, amíg nem találunk elégséges dolgozatot. Amikor megtaláltunk egy elégségest akkor ő lesz a kiválasztott. Pszeudokód: VÁLTOZÓK i, sorsz, dolg_szama, dolgozatok[i] EGÉSZ i←1 ISMÉTELD HA ( (i<=dolg_szama) és (dolgozatok[i]!=2) ){ i←i+1 } sorsz←i KIÍR(sorsz)
10
BMF-NIK-AAO
Keresés Ismerjük egy üzlet januári napi bevételeit. Adjunk meg egy olyan napot -ha van-, amikor a bevétel több volt, mint 20000Ft. Megoldás: Nézzük végig a bevételeket, először az elsőt majd sorra a többit, amíg nem találunk 20000Ft-nál nagyobbat. Ha találunk ilyet, akkor van megoldás, és a megoldás a megtalált bevétel sorszáma. Különben nincs megoldás. Töltsük fel véletlen egészekkel a januar tömb elemeit. (0-tól indul ezért a 32. lesz jan 31.) int[] januar = new int [32]; Random RandomClass = new Random(); for (int i =1; i<=31; i++) januar[i]=RandomClass.Next(10,30);
Ha pl 14, 18, 26, 28, 12 …. Január 1, 2, 3, 4, 5, …. Bevételei rendre ezer forintban, akkor január 3.-át kell megtalálni. Persze az is lehet, hogy a bevétel egyetlen napon sem haladja meg a 20 ezer forintot. A kód: int i=1; while ( januar[i] < 20 ) i++; Console.Write(januar[i] + ” ”);
Ez akkor nem jó ha nincs megoldás, azaz január 31.-én (i=32) és a bevétel kisebb mint 20ezer. Vagyis ebben az esetben nem áll le a ciklus. A kód javítása: int i=1, napokszama=31; while( (i<=napokszama) && (januar[i]<20) ) i++; if (i > napokszama) Console.WriteLine(”Nincs megoldás”); else Console.Write(i+”dik nap!”);
11
BMF-NIK-AAO Megszámolás Az előző feladatot kicsit módosítjuk. Számoljuk meg hány napon (ha egyáltalán) volt az üzlet bevétele 20 ezer forintnál nagyobb? A megszámolás kódja: int darab=0; for (i=1; i<=napokszama; i++) if (januar[i]>20) darab++; Console.WriteLine(darab+” napon volt az üzlet bevétele 20ezer forint felett”);
Maximumkiválasztás Tegnap este a térképet nézegettem. Kiírtam magamnak 10 magas hegy tengerszint feletti magasságát. Adjuk meg a legmagasabb csúcsot! Megoldás: Megjegyzem az első hegy magasságát. Ezt tekintem a legmagasabbnak. A többi hegyet sorra végignézem: ha valamelyik magasabb, mint az eddigi legmagasabb, akkor az eddigi legmagasabbat elfelejtem, és az újat jegyzem meg. A végén a legmagasabb hegy lesz megjegyezve. Kód: int hegyekszama=10; int[] magas = new int [hegyekszama+1]; //mert 1-től indexelünk int i; Random RandomClass = new Random(); for(i=1; i<=hegyekszama; i++){ magas[i] = RandomClass.Next(10, 26); Console.Write(magas[i]+” ”); } int max=magas[1]; int eddigi=1; for(i=1; i<=hegyekszama; i++) if(magas[i]>max){ max=magas[i]; eddigi=i; } Console.WriteLine(”az (egyik) legmagasabb sorszáma: ”+eddigi+” magassága: ”+max);
Ha mondjuk a 2. hegy és a 7. hegy ugyanolyan magas, és a többi mind kisebb, az eredmény 2 lesz vagy hét? 2 lesz. Azonban ha > helyett >= kerül be, akkor 7.
12
BMF-NIK-AAO
3. Adatkonverziók, ciklusok, függvények, tömbök Adatkonverziók A konverzió a C#-ban lehet implicit vagy explicit. Ha az átalakítás automatikus, akkor implicit konverzióról beszélünk, ilyenkor nincs adatvesztés. Az explicit konverzió kikényszerített, ilyenkor előfordulhat adatvesztés. Konverzió leggyakrabban függvényhívás paraméterátadáskor történik, vagy kevert típusú adatokkal való numerikus számítások esetén. A nyilak mutatják az implicit konverziós lehetőségeket:
Implicit numerikus konverzió: long x1; int y1=25; x1=y1; Console.WriteLine(x1); int x1; long y1=25; x1=y1;
// implicit numerikus konverzió int → long
//long → int nyíl nincs: hibaüzenet…; //de ok mert esetleges adatvesztés lehetséges!
13
BMF-NIK-AAO Megoldás kasztolással (explicit): int x1, x2; long y1=2147483647, y2=21474836470; //y1 ,,belefér” int-be, y2 nem fér bele x1=(int)y1; x2=(int)y2; //(int) kasztolás Console.WriteLine(x1+” ”+x2); //x1=2147483647, x2=-10 //x2 esetében adatvesztés történt
Egész osztás vagy valós osztás? int i=13, j=7; int k=i/j; Console.WriteLine(k); float k1=i/j; Console.WriteLine(k1); float k2=(float) i/j; Console.WriteLine(k2); Console.WriteLine(55/7); Console.WriteLine(55.0/7); float i=13; int j=7; Console.WriteLine(i/j); Console.WriteLine((int)i/j); double i1=13.15; int j=7; Console.WriteLine(i1/j); Console.WriteLine((int)i1/j); float i2=13.15; int j=7; Console.WriteLine((int)i2/j);
//mindkét argumentum eredetileg egész //KIÍR: 1 //KIÍR: 1 //1.857143 // (float) i / (float) j vagy i / (float) j is jó! //7 //7.8571.. //i valós, de egész értékkel //1.85.. //1 //i1 duplapontos, nem egészértékű //1.87.. //1 //i2 valós, nem egész értékű //HIBA: float nem konvertálható
Duplapontos változó konvertálása egészre adatvesztéssel: double i2=13.83; Console.WriteLine((int) i2);
Példa logikai kifejezésre: int a=7; bool log; log=a%2==0; //log=(a%2==0); if (log) Console.WriteLine(”páros”); else Console.WriteLine(”páratlan”);
14
BMF-NIK-AAO String→numerikus (egész) érték string sz=”123”; int sz1=Int32.Parse(sz); int sz2=Convert.ToInt32(sz);
String→numerikus (valós) érték string myDoubleStr=”-12,2”; double x=Double.Parse(myDoubleStr)+5.3; double y=Convert.ToDouble(myDoubleStr)+1.1; Console.WriteLine(x); //-6,9 Console.WriteLine(y); //-11,1 //érdemes tizedespont illetve vessző használatára figyelni
Szöveg szétszedése szavakra string s=”Egyszer volt#hol#nem volt” char[] seps=new char[]{’’, ’#’} foreach (string ss sin s.Split(seps)) Console.WriteLine(ss);
//Ezt kell szétszedni //az elválasztó karakterek //ss az eredmény
Eredmény: Egyszer volt hol nem volt
15
BMF-NIK-AAO Függvények Függvények használata érték visszaadás nélkül public static void change(int b){ b=5; } static void Main(){ int a=0; change(a); Console.WriteLine(a); }
Egy érték visszaadása a metódus nevében public static int change(int b){ b=5; return b; } static void Main(){ int a=0; a=change(a); Console.WriteLine(a); }
//a egyenlő lesz 5-tel
Cím szerinti paraméterátadás (ref) public static void change(ref int b){ b=5; } static void Main(){ int a=0; //ha hívás előtt a nem kapna értéket az hiba! change(ref a); Console.WriteLine(a); //a==5 }
Cím szerinti paraméterátadás (out) public static void change(out int b){ b=5; } static void Main(){ int a; change(out a); Console.WriteLine(a); }
//nem muszály, hogy a értéket kapjon
16
BMF-NIK-AAO Változó argumentumlista A paraméter tömb használata lehetővé teszi változó darabszámú azonos típusú paraméter használatát. A definícióban a params kulcsszónak szerepelnie kell, de híváskor nem. A paraméterlistát a definícióban egy egydimenziós tömb követi, híváskor bármennyi (akár nulla) darab paraméter szerepelhet, feltéve, hogy a típus kompatibilis. Példa a params használatára: static void ShowNumbers(params int[] numbers){ foreach (int x in numbers){ Console.Write(x+” ”); } Console.WriteLine(); } static void Main(){ int[] x={1, 2, 3}; ShowNumbers(x); ShowNumbers(4, 5); Console.ReadKey(); }
Eredmény: 123 45
17
BMF-NIK-AAO Egydimenziós tömb int[] itomb; itomb=new int[3]{0, 1, 2}; for(int i=0; i
//deklarálás //inicializálás // a deklarálás és az inicializálás //össze is vonható
Egydimenziós tömb átlaga: public static double atlag(double[] vektor){ double s=0.0; for(int i=0; i
18
//várakozás
BMF-NIK-AAO
4. Kiválogatás, szétválogatás, bináris keresés Kiválogatás Ez az algoritmus egy t tömb (indexek 0-tól n-1 ig) bizonyos tulajdonságú elemeit (a negatívokat) teszi egy másik tömbbe. db változó számolja, hogy a másik tömbbe hány elem került. Válogassuk ki a negatív számokat. Az eredmény b tömbben lesz (deklarációnál b tömböt n eleműre kell választani, hacsak nem tudjuk előre, hány negatív szám van t-ben). Pszeudokód: KONSTANS n EGÉSZ VÁLTOZÓK i, db EGÉSZ, t[i], b[i] VALÓS db←0; i←0; ISMÉTELNI HA (i
C# kódja: int i=0; int db=0; while(i
19
BMF-NIK-AAO Szétválogatás (két tömbbe) A feladat hasonló az előzőhöz, de a feltételnek nem megfelelő elemeket is egy újabb tömbbe kell elhelyezni (tehát kétfelé válogatjuk az eredeti tömböt). Ez az algoritmus egy t tömb (indexek 0-tól n-1 ig) pozitív elemeit teszi egy p tömbbe, a nem-pozitív elemeket az np tömbbe. pdb illetve npdb változó számolja, hogy az illető tömbbe hány elem került. C# kódja: int n=10; int[] t=new int[n]; int[] p=new int[n]; int[] np=new int[n]; int i, pdb, npdb; i=0; pdb=0; npdb=0; while(i
0){ p[pdb]=t[i]; pdb++; } else{ np[npdb]=t[i]; npdb++; } i++; }
//index 0-tól n-1 ig
Szétválogatás (egy tömbbe) Memóriafoglalás szempontjából a két tömböt használó előző algoritmus nem hatékony: mind a p, mind az np tömböt n eleműre kell deklarálni, de a két tömbben összesen csak n elem van. Használhatunk egy tömböt is, akkor annak első felébe tesszük a pozitív számokat, a második felébe (hátulról kezdve a feltöltést) a többit. Ez az algoritmus egy t tömb (indexek 0-tól n-1 ig) pozitív elemeit teszi egy p tömb elejére, a negatív elemeket a p tömb végére. C# kódja: i=0; pdb=0; veg=n-1; while(i0) p[pdb++]=t[i]; else p[veg--]=t[i]; i++; }
20
BMF-NIK-AAO Bináris keresés Csak rendezett sorozatban lehet keresni vele. k=log2n lépést igényel. (n az elemek száma) Működése: Mindig elfelezi az adatok listáját, és megnézi hogy a keresett adat melyik részben van. Azután abban keres tovább. C# kódja int also, felso, kozep, hely, n; //n=az elemek száma elemtipus adat=new elemtipus(); //a keresni kívánt adat elemtipus[] a=new elemtipus[]; //a lista melyben keresünk bool talalt; also=1; felso=n; kozep=(also+felso)/2; while( (also<=felso) && (a[kozep]!=adat) ){ if adat
21
BMF-NIK-AAO
5. Halmazműveletek Metszet A feladat most két tömb a[0..n-1] és b[0..m-1] azonos elemeinek kiválogatása c tömbbe. A feladat csak úgy értelmezhető pontosan, ha az egyes tömbökben egy elem nem szerepel kétszer. (Mivel a matematikai halmazokat tömbbként ábrázoljuk.) Az algoritmus lényege: menjünk végig az a tömb elemein, és válogassuk ki azokat (kiválogatás), melyek szerepelnek b-ben (eldöntés). Így a feladat a korábbi tételekre visszavezethető. c maximális elemszáma n és m közül a kisebbik. Feltételezzük továbbá, hogy egyik halmaz sem üres. C# kódja int n, m, db=Math.Min(n, m); //tömbméretek int i, j, k; //ciklusváltozók int[] a=new int[n]; //a halmaz elemei 0..n-1 int[] b=new int[m]; //b halmaz elemei 0..m-1 int[] c=new int[db]; //a metszet elemei, db csak a maximális tömbméret //Ha a metszet üres, akkor nyilván nem kerül bele elem. k=0; for(i=0; i
22
BMF-NIK-AAO Unió A feladat most két tömb a[0..n-1] és b[0..m-1] elemeinek egyesítése c tömbbe. Az egyes tömbökben egy elem nem szerepel kétszer. A legegyszerűbb megoldás: tegyük be c-be az a halmaz összes elemét, majd b-ből azokat, melyek nem szerepelnek a-ban. Így c halmaz elemszáma legfeljebb n+m. Feltételezzük, hogy egyik halmaz sem üres. C# kódja for(i=0; i=n) c[k++]=a[j]; //ha volt ilyen, akkor betesszük c-be } --k; //beállítjuk c végét for(i=0; i
Unió speciális esetben (összefuttatás) Az a és b (halmazokat reprezentáló) tömbök rendezettek. C# kódja int i=0, j=0, k=0; while((i
23
BMF-NIK-AAO
6. Rendezések Buborékrendezés (bubble sort) C# kódja: int n=10, i; int[] a=new int[n]; // a tömb 0..n-1, ezt rendezzük Random RandomClass = new Random(); for (i=0; ia[i+1]){ //ha rossz a sorrend cserélünk int cs; cs=a[i]; a[i]=a[i+1]; a[i+1]=cs; csere_volt=1; //még nem biztos hogy jó a sorrend } }
A while ciklus egyszeri lefutásának hatására a legnagyobb elem az utolsó lesz. Ha a sorozat (véletlenül) eleve rendezett, készen vagyunk, ha legalább egy csere történt, újra fut a while, és a következő legnagyobb elem az utolsó előtti lesz. Minden lépésben a helyére kerül egy elem, tehát a while nem futhat n-nél többször. A legrosszabb eset: A buborékrendezés a legrosszabb esetben O(n*n) lépést igényel. Minden elem egy összehasonlítás árán legfeljebb egy pozíciót mozdulhat el (szomszédos elelmeket hasonlítunk). Egy elem legfeljebb n-1 távolságra lehet a sorrendileg megfelelő helyétől, így legfeljebb n-1=O(n) művelettel helyrekerül, így (n-1)*(n-1)=O(n*n) műveletnél nem lehet több a teljes rendezéshez.
24
BMF-NIK-AAO
Koktélrendezés (cocktail sort) C# kódja: int bottom=0; int top=n-1; bool csere_volt=true; while (csere_volt==true){ csere_volt=false; for(int i=bottom; ia[i+1]){ csere_volt=true; cs=a[i]; a[i]=a[i+1]; a[i+1]=cs; } top=top-1; for(int i=top; i>bottom; i--) if (a[i]
Úgy működik mint a buborék rendezés, csak két irányból történik a vizsgálat. A legrosszab esetben itt is O(n*n) műveletre van szükség, de ha a lista majdnem rendezett az elején a műveletek száma közelebb van O(n)-hez mint a buborék rendezés esetén.
25
BMF-NIK-AAO
Kerti-törpe rendezés (garden gnome) C# kódja: int i=1; while (i
//ha jó a sorrend előre
Az algoritmus megkeresi az első olyan helyet, ahol két egymást követő elem rossz sorrendben van, és megcseréli őket. Ha egy ilyen csere után rossz sorrend keletkezik, az csak közvetlenül a legutolsó csere előtt lehet, így ezt is ellenőrizzük. Ez az elképzelhető legegyszerűbb rendezés.
26
BMF-NIK-AAO Fésűs rendezés (combsort) Ez a rendezés a buborék rendezés javítása. A buborék a világ egyik legrosszabb rendezése, azonban egy egyszerű módosítással annyira javítható, hogy vetekszik a quicksorttal. Az eredeti fésűs rendezést Stephen Lacey és Richard Box fejlesztette, és a Byte Magazine publikálta 1991-ben. Futásidő összehasonlítások: 10 ezer kevert egész szám rendezése CPU másodpercben: Quicksort: 0.0038 Combsort: 0.0042 Bubblesort: 1.36 C# kódja: int gap=n; //az a táv, mely az összehasonlítandókat elválasztja for (;;){ gap=(gap*10)/13; //konvertál egészre ha kell if (gap==9 || gap==10) gap=11; if (gap<1) gap=1; bool csere_volt=false; for (int i=0; ia[j]){ int cs=a[i]; a[i]=a[j]; a[j]=cs; csere_volt=true; } } if (gap==1 && !csere_volt) break; }
10 ezer elemű tömbön végzett kísérletek szerint a fésűs rendezés alig rosszabb a quicksortnál (10%-kal); a változtatás a buborékhoz képest nem nagy. Ugyanakkor nem kell gondoskodni az eleve rendezett esetről, ami a quicksortot nagyon lelassítja. A gap beállításával először a távollevő elemeket rendezzük. Ezután a gap csökken, míg végül egy lesz. Ez esetben azonos a program a buborékkal; következésképpen korrekt. Lacey és Richard Box megmutatták, hogy a gap minden lépésben 1.3-mal osztandó. Továbbá felfedezték, hogy 9 és 10 nem alkalmas gap-nek, és 11-gyel helyettesítendő.
27
BMF-NIK-AAO Maximum kiválasztásos rendezés A tömb rendezése a legnagyobb elem segítségével. Kiválassza a legnagyobbat és felcseréli az utolsóval. (n a tömb hossza) C# kódja int max, cs; for(int i=n; i>1; i--){ max=i; for(int j=i-1; j>0; j--) if(a[j]>a[max]) max=j; cs=a[i]; a[i]=a[max]; a[max]=cs; }
Beszúrásos rendezés Vesszük a soron következő elemet és megkeressük a helyét a tőle balra lévő, már rendezett részben. A kereséssel párhuzamosan a nagyobb elemeket rendre eggyel jobbra mozgatjuk. C# kódja elemtipus x=new elemtipus(); elemtipus[] a=new elemtipus[]; int i, j; for(i=2; i<=n; i++){ j=i-1; x=a[i]; while( (j>=1) && (x
28
BMF-NIK-AAO
Galambdúc-rendezés (pigeonhole) Működése: Állítsunk be egy tömböt kezdetben üres rekeszekkel, egy rekeszt minden értéknek a rendezni kívánt elemek területén. Végighaladva az eredeti tömbön, minden objektumot beletesszük a saját rekeszébe. Ciklussal sorban haladva a rendező tömbön, helyezzük vissza az elemeket a nem-üres rekeszekből az eredeti tömbbe. Az algoritmus gyorsaságát legnagyobb mértékben a rendező tömb sűrűsége befolyásolja. Ha sokkal több tömbelem van a rendezni kívánt elemek számánál, az algoritmus nagyon lelassul. Ezt a rendezést ritkán használják, mert a körülmények ritkán felelnek meg. Más, gyorsabb és rugalmasabb rendezések használata sokkal egyszerűbb. C# kódja //n a rendező tömb hossza, max és min a lehetséges szélsőértékei int max=8, min=-2, size=max-min+1, n=10; int[] a=new int[n]; //az eredeti tömb int[] holes=new int[size]; //a rendező tömb int i, j; //ciklusváltozók Random RandomClass=new Random(); for(i=1; i<=n; i++) a[i]=RandomClass.Next(min, max); //tömb feltöltése Console.WriteLine(); for(i=1; i<=n; i++) Console.Write(a[i]+” ”); //tömb kiírása Console.ReadKey(); for(i=0; i<size; i++) holes[i]=0; //a rendező tömböt 0-kal tölti fel for(i=1; i<=n;) holes[a[i]-min]++; //az elemek átkerülnek a rendező tömbbe j=1; for(i=0; i<size; i++){ //az elemek visszakerülnek az eredeti tömbbe while (holes[i]>0){ //amíg több elem van egy rekeszben a[j]=i+min; holes[i]--; j++; } } Console.WriteLine(); for(i=1; i<=n; i++) Console.Write(a[i]+” ”); //a rendezett tömb kiíratása Console.ReadKey();
29
BMF-NIK-AAO
7. A gyors-rendezés (quicksort) Quicksort rekurzívan Működése: Válasszunk ki egy elemet a listából! Rendezzük úrja a listát: minden elem amely kisebb a kiválasztottnál, a kiválasztott elé kerül. A nála nagyobbak mögé kerülnek. (Az egyenlőeknél mindegy, hogy elé vagy mögé kerül) Ekkor a kiválasztott elem a helyére került. Ezután rekurzívan végezzük el ezeket a műveleteket a keletkezett részlistákra. Az algoritmus minden esetben véges, mert legalább egy elem mindig a helyére kerül. C# kódja class qsort{ public static void QuickSort(ref int[] a, int iLo, iHi){ int Lo, Hi, Mid, T; Lo=iLo; Hi=iHi; Mid=a[(Lo+Hi) div 2]; while(Lo<=Hi){ while(a[Lo]<Mid) Lo++; while(a[Hi]>Mid) Hi--; if(Lo<=Hi){ T=a[Lo]; a[Lo]=a[Hi]; a[Hi]=T; Lo++; Hi--; } } if(Hi>iLo) QuickSort(a, iLo, Hi); if(Lo
30
BMF-NIK-AAO Quicksort nem rekurzívan A most következő példa elsősorban azt illusztrálja, hogy lehet egy algoritmus átlagos lépésszámát kiszámolni. A feladat ugyanaz mint az előbb: adott n különböző szám, K1, K2, …, Kn, melyeket növekvő sorrendbe kell átrendezni. A következő algoritmust használjuk. 1. fázis (a K1 szám a helyére kerül): 1. csere: A K1 számot összehasonlítjuk Kn-nel. Ha Kn>K1, akkor továbblépünk, és Kn-1-gyel hasonlítunk össze. Ha Kn-1>K1, megint továbblépünk stb. Ha pl. K1>Kn-2, akkor K1-et kicseréljük Kn-2vel. Az új sorozat (függőleges vonallal vágtuk le a sorozat két végéről azokat a részeket, amelyekkel K1-et már nem kell hasonlítani): Kn-2 | K2K3…Kn-3K1 | Kn-1Kn. 2. csere: A csere után K1-et a legelső olyan számmal hasonlítjuk össze, amivel még nem hasonlítottuk: példánkban K2-vel. Ha K1>K2, akkor továbblépünk és K1-et K3-mal hasonlítjuk össze stb. Ha pl. K5>K1, akkor K1-et kicseréljük. Az új sorozat: Kn-2K2K3K4 | K1K6…Kn-3 | K5Kn-1Kn. 3. csere: Most K1-et megint a legutolsó olyan számmal hasonlítjuk össze, amivel még eddig nem volt összehasonlítva és lefelé haladunk, amíg cserére nem kerül sor. 4. csere: A csere után K1-et a legelső új számmal hasonlítjuk össze stb. Végül K1-et már a sorozat minden elemével összehasonlítottuk és a nála nagyobbak mind mögé, a nála kisebbek pedig elé kerültek. Ha pl. K1 az i-edik helyre került, a következő kép alakul ki: L1, L2, …, Li-1, Ki, M1, M2, …, Mn-1, ahol L1
31
BMF-NIK-AAO Többi fázis: Ami ezután hátravan, az külön az L1, L2, …, Ki-1, és az M1, …, Mn-1 sorozatok rendezése ugyanezzel a módszerrel. Példa: A sorozat legyen 503, 87, 512, 61, 908, 170, 275. 1. fázis (503 helyre tétele): 1. csere: 275, 87, 512, 61, 908, 170, 897, 503 2. csere: 275, 87 |503, 61, 908, 170, 897| 512 3. csere: 275, 87, 170 |61, 908, 503| 897, 512 4. csere: 275, 87, 170, 61 |503| 908, 897, 512 2.1. fázis (275 helyre tétele): 1. csere: 61| 87, 170, 275 2.2. fázis (908 helyre tétele): 1. csere: 512| 897, 908 Eredeti formájában ez az algoritmus rekurzív, azaz önmagára hivatkozást tartalmaz. Ilyen algoritmusra nem lehet blokkdiagramot írni. Az ábra blokkdiagramja a rekurziót iterációvá oldja fel. Bemenetkor: K1, …, Kn különböző számok. Kimenet: K1, …, Kn: ugyanezek a számok jó sorrendben. Segédváltozók: T1, …, Tn: 0 vagy 1 értékeket vehetnek fel. l, m egész számok 1 és n között. K a K1, …, Kn számok valamelyike. Megjegyzés: Az eljárás folyamán Ti=1, ha a Ki szám már nagyság szerint is az i-edik.
32
BMF-NIK-AAO
Ennek az algoritmusnak sok előnye van, pl. hogy az egész 1. fázisban ugyanazt a Ki számot kellett a többivel összehasonlítani. Ezért érdemes kiszámítani, hogy az algoritmus átlagban hány összehasonlítást igényel. Tegyük fel, hogy a K1, K2, …, Kn számok minden lehetséges nagysági sorrendje egyformán valószínű. Az első fázisban K1-et az összes többi számmal össze kell hasonlítani, ez n-1 összehasonlítás. Könnyű belátni, hogy ha pl. az első fázis után az eredmény L1, L2, …, Li-1, K1, M1, …, Mn-i, akkor az L1, …, Li-1 számok minden lehetséges nagysági sorrendje is egyformán valószínű; az M1, …, Mn-i számoké hasonlóan. Jelöljük az n szám sorba rendezéséhez szükséges összehasonlítások átlagos számát F(n)-nel! Ekkor, feltéve, hogy K1 az i-edik helyre került, hátravan még átlagban F(i-1)+F(n-i) összehasonlítás. Mivel pedig K1 egyenlő valószínűséggel kerülhet bármelyik helyre, az összehasonlítások átlagos számára végül a következő rekurzív formulát kapjuk: F(0)=0, F(1)=0,
33
BMF-NIK-AAO F(n)=n-1+1/n[F(0)+F(n-1)+F(1)+F(n-2)+F(2)+F(n-3)+…+F(n1)+F(0)]. Egyszerűsítve: nF(n)=n(n-1)+2[F(0)+F(1)+F(2)+…+F(n-1)].
(1)
Írjuk fel ugyanezt az egyenlőséget n+1-re. (n+1)F(n+1)=(n+1)n+2[F(0)+…+F(n)].
(2)
Vonjuk ki (1)-ből a (2)-t. (n+1)F(n+1)-nF(n)=2n+2F(n). Átalakítva: (n+1)F(n+1)=2n+(n+2)F(n), F(n+1)
/(n+2)-F(n)/(n+1)=2n/(n+1)(n+2).
Adjuk össze a fenti egyenlőséget n=1, 2, …, (k-1)-re: F(k)
/(k+1)=2*1/2*3+2*2/3*4+2*3/4*5+…+2(k-1)/k(k-1).
Az olvasó egy kis számolással ellenőrizheti, hogy innen F(n)=2(n+1)(Hn-2+1/(n+1)), ahol Hn=1+1/2+1/3+…+1/n ~ lnn. Ezért a következő aszimptotikus egyenlőséget kaptuk az átlagos lépésszámra: F(n) ~ 2nlnn. Érdekes megjegyezni, hogy a szóban forgó algoritmus a legrosszabb esetben az összes számpárt összehasonlítja, tehát n(n-1)/2 lépést dolgozik. Paradox módon ilyen legrosszabb eset az, ha a K1, K2, …, Kn számok eleve jó sorrendben vannak, azaz K1
34
BMF-NIK-AAO
8. Játékok algoritmusai Egyszerű játék: 1. Minden játékban két játékos vesz részt, akik felváltva lépnek. 2. Minden játszmának csak egy kimenetele lehet: A kezdőjátékos A nyer (+), vagy a B játékos nyer (-). 3. A játékos minden lépésben kiválaszt egy variánst a lehetőségek összességéből úgy, hogy választásában nem jut szerephez a véletlen (pl. nem a dobókockás eredményét használja fel). 4. Minden lépéskor a játékos ismeri a játszma összes eddigi lépésének eredményét. A játék lehetséges lépéseit fa-gráffal lehet szemléltetni:
A fa pontjaihoz rangot rendelünk. A legnagyobb ezek közül a fa rangja (a játék leghosszabb játszmájának hossza). A páratlan rangúakban A lép, a párosakban B. Egy fának a végponttól különböző minden pontját egy olyan kisebb rangú részfa gyökérpontjának tekinthetjük, amely szintén megad egy játékot. A játékok fával való szemléltetése lehetővé teszi, hogy az A játékos bármelyik stratégiáját olyan nyilakkal ábrázoljuk, amelyek páratlan rangú csúcsokból indulnak ki egy szomszédos, páros rangú csúcsba. Ennek szabályai: Egy csúcsból legfeljebb egy nyíl mehet. Ha a páratlan csúcsba vezet nyíl, akkor ahhoz a csúcshoz minden, egyel nagyobb rangú csúcsból indul ki nyíl.
35
BMF-NIK-AAO
Nyerő stratégia létezése: Tétel: Minden játékban van az egyik játékosnak nyerő stratégiája. Bizonyítás: Y=1 → minden játszma egy lépésből áll. Tegyük fel, hogy A lép a szabályok szerint, Ha a1, a2, …, an között van legalább egy (+) jel, akkor A-nak van nyerő stratégiája. Ha mindegyik jel (-), akkor B-nek van nyerő stratégiája, és A veszít.
Teljesen hasonló a helyzet akkor, ha „a” egy olyan pontot jelöl, ahonnan B lép. Ha az egyel magasabb rangú pontok között van (-) jel, akkor B-nek van nyerő stratégiája, egyébként A-nak.
Tegyük fel, hogy a tételt minden y-nál kisebb rangra már bebizonyítottuk, igazoljuk most y-ra.
36
BMF-NIK-AAO
A háromszög olyan részfát jelöl, amely gyökérpontja α –val jelölt gyökérpontjaihoz csatlakozó y1, y2, …, yn pontok. Tegyük fel, hogy α azt az esetet ábrázolja, amikor A lép. Ekkor ∆1, ∆2, …, ∆n részfákkal jellemzett játékban B lép először, és a leghosszabb játszma a ∆-ekben maximum (y-1) hosszuságú lehet. Tegyük fel, hogy a ∆-ekkel jellemzett részfák közül legalább az egyikben van nyerő stratégiája A-nak. Ekkor A-nak az egész játékban is van nyerő stratégiája, ennek meghatározásához elég megtartani azt a részfát melyben a nyerő stratégia létezik, és kiegészíteni α –ból a kedvező részfa gyökeréhez vezető nyíllal. Ez a stratégiai algoritmus olyan játékokra is érvényes, ahol a két játékos győzelmén kívül döntetlen is előfordulhat. Ekkor természetesen lehetséges, hogy egyik játékosnak sincs nyerő stratégiája, de ekkor az algoritmus mindegyik játékosnak egy olyan stratégiát ad, amely alapján legalább döntetlent érhetnek el. (sakk) A sakk esetében nem lehet megszerkeszteni a döntési fát, mert annyira hosszú, hogy szinte lehetetlen. Ennek ellenére azt mondhatjuk, hogy létezik nyerő stratégia.
37
BMF-NIK-AAO 11 tárgy játék Az asztalon 11 tárgy van, például gyufaszálak. Az első játékos elvehet ezekből tetszése szerint 1, 2 vagy 3 gyufaszálat, ezután a második játékos vehet el a fennmaradók közül megint 1, 2 vagy 3 gyufaszálat tetszése szerint. Ezután ismét az első játékos lép, és így tovább. Tehát minden alkalommal a soron levő játékos legfeljebb 3 gyufaszálat vesz el, de legalább egyet mindenképpen el kell venni. Az veszít aki az utolsó gyufaszálat veszi el. A játék elemzése megmutatja, hogy az A játékos a következő utasításrendszert követve elérheti, hogy B-nek kelljen az utolsó gyufaszálat elvennie: 1. első lépés. A két gyufaszálat vesz el. 2. általános lépés. Ha B az előző lépésben k gyufaszálat vett el (k<=3), és még maradt gyufa, akkor A (4-k) gyufaszálat vesz el. Bizonyítható az is, hogy ha A az első lépésben 1 vagy 3 gyufaszálat vesz el, akkor B képes úgy iránytani a játékot, hogy ő nyerjen. A következő fa a tizenegy-tárgy játék egy leegyszerűsített változatát, a 6 tárgy játékot mutatja be (itt 6 gyufaszál van, és legfeljebb 2-őt lehet elvenni egy lépésben).
38
BMF-NIK-AAO
9. Labirintusbeli út keresése A görög mitológia egyik legendás hőse Thészeusz, aki bátran bement a labirintusba, hogy megkeresse és megölje a szörnyűséges Minotauruszt. A labirintusból való visszatérésben Ariadné segítette, aki Thészeusznak egy gombolyag fonalat adott, és annak egyik végét ő maga tartotta. Amint Thészeusz egyre beljebb ment a labirintusba, legombolyította a fonalat; ezután a fonal felgombolyításával szerencsésen visszatalált a kijárathoz. A labirintust egy véges sok szobából álló rendszerként képzeljük el, amelyben a szobákat folyosók kötik össze. Minden folyó két szobát köt össze (szomszédosak), de lehetnek zsákutcák is. Geometriailag a labirintust pontrendszerrel (szobák) és bizonyos párokat összekötő szakaszokkal (folyosók) lehet ábrázolni. Azt mondjuk, hogy Y szoba X-ből elérhető, ha van olyan út, ami X-ből Y-ba vezet. X és Y vagy szomszédosak, vagy van olyan x1, x2, …, xN sorozat, hogy x és x1, x1 és x2, … végül xN és Y szomszédosak. Ha X-ből Y elérhető, akkor elérhető egyszerű úton is, vagyis olyan úton, amellyel minden szobán és minden folyosón csak egyszer haladunk át. Keresési algoritmus: A módszer lényege, hogy a keresés bármely fázisában 3 típusú folyosót különböztetünk meg. 1. zöld: olyan folyosó, amin még 1-szer sem haladtunk át 2. sárga: olyan folyosó, amin egyszer haladtunk át 3. piros: olyan folyosó melyen kétszer haladtunk át (újra már nem mehetünk át rajta). Valamelyik szomszédos szobába a lépések valamelyikével tudunk eljutni: 1. fonal legombolyítása: az adott zöld folyosón a szomszédos szobába megyünk. A folyosó ezután sárga lesz. 2. fonal felgombolyítása: egy sárga folyosón a szomszédos szobába megyünk. A folyosó ezután piros lesz. Feltételezzük, hogy valamilyen módon meg tudjuk különböztetni a zöld és a piros folyosókat. A sárgát ismerjük, hiszen éppen fonal halad át rajta.
39
BMF-NIK-AAO Egy adott szobában a következő feltételek adódhatnak: 1. Minotaurusz: az adott szobában felfedezzük a Minotauruszt. (teendő: Megállás) 2. Hurok: az adott szobából két sárga folyosó nyílik. (teendő: a fonal felgombolyítása) 3. Zöld út: az adott szobából legalább egy kijárat van ami még zöld (teendő: a fonal legombolyítása) 4. Ariadné: a szobában van Ariadné (ott van ahonnan indult) (teendő: Megállás) 5. Egyéb: Az előzőek közül egyik sem áll fenn. (teendő: a fonal felgombolyítása) Ha egy szobában vagyunk, sorra vesszük a lépéseket egytől ötig, amelyik először teljesül aszerint lépünk. Ezt addig ismételjük, amíg megálláshoz nem jutunk. Az algoritmus használhatósága adódik a következő állításokból: 1. A és M (rajt és cél) bármilyen kölcsönös helyzete esetén véges sok számú lépés után feltétlenül eljutunk a megállás lépéshez a Minotaurusznál vagy Ariadnénél. 2. Ha a megállás M-nél van, akkor A és M kapcsolata létezik. 3. Ha a megállás A-nál van, akkor A és M kapcsolata nem létezik. A keresési algoritmus bizonyítása: Az első állítás bizonyítása: a lépések számára vonatkozó teljes indukcióval megmutatjuk, hogy az eljárás bármelyik fázisában a következő alternatíva áll fenn: 1. a labirintusban nincs sárga folyosó. Ekkor az A szobában vagyunk. 2. A labirintusban vannak sárga folyosók, és ha ezeket abban a sorrendben vesszük, ahogy végigjártuk, akkor egy, az A-ból addig a szobáig vezető utat alkotnak, ahol éppen tartózkodunk. Ebből következik, hogy sohasem haladtunk át piros folyosón. Tegyük fel, hogy a szóban forgó alternatíva az (n-1)-edik lépés után áll fent, és igazoljuk, hogy az n-edik lépés után is érvényes lesz (persze csak akkor, ha az (n-1)-edik nem jelentett megállást). Tegyük fel, hogy az (n-1)-edik lépés után az 1. eset áll fent. Ekkor a következő lépés vagy az, hogy egy zöld folyosón egy A-val szomszédos K szobába megyünk, vagy az, hogy megállunk.
40
BMF-NIK-AAO Tegyük fel, hogy az (n-1)-edik lépés után a 2. eset érvényes a sárga folyosóval, melyek A, A1; A1, A2; A2, A3;…A(k-n), K utat alkotják. Attól függően, hogy melyik feltétel alapján tesszük meg a következő lépést, az n-edik lépés után az alábbi esetek lehetségesek: a. Minotaurusz: a K szobában megállás következik, az előző sárga folyosók megmaradnak. (az n-edik lépés után a 2. eset érvényes) b. Hurok: felgombolyítja a fonalat, azaz ez által a K, A(k-1) sárga folyosón visszamegy az előző szobába, áthaladás után a folyosó piros lesz. A sárga folyosók száma egyel csökken. Az n-edik lépés után, ha k nagyobb 1-nél, akkor a 2. eset érvényes, ha k=1 akkor az 1. eset. c. Zöld út: legombolyítjuk a fonalat, azaz áthaladunk egy zöld folyosón, ami ezután sárga lesz. A 2. eset áll elő k+1 sárga folyosóval. d. Ariadné: ez alapján nem léphetünk, hiszen ha Ariadnéhoz érünk vissza egy másik úton akkor a hurokfeltétel lép életbe. Valamint az is előfordulhat, hogy Ariadné szobájából még nyílik zöld út. e. Egyéb: Ha egyik sem teljesül, akkor felgombolyítja a fonalat, ami ugyanahhoz vezet, mint a hurokfeltétel, azaz az 1. esethez vagy a 2.-hoz ha a sárga folyosók száma nagyobb 1-nél.
41
BMF-NIK-AAO
10. A szóprobléma Asszociatív kalkulus Egy véges sok különböző jelből álló rendszert abécének nevezünk. Az ábécé betűiből álló tetszőleges véges sorozatot ábécébeli szónak nevezzük. Szavaknak bizonyos megengedett helyettesítésé szabályokkal történő átalakítását fogjuk vizsgálni. A megengedett szabályokat P – Q vagy P → Q alakban adjuk meg. A P → Q irányított helyettesítési szabály akkor alkalmazható R szóra, ha P legalább egyszer előfordul R-ben. A P – Q nem irányított helyettesítési szabállyal bármelyiket pótolhatjuk a másikkal. Egy adott ábécébeli szavak összességét helyettesítési szabályok egy véges rendszerével együtt asszociatív kalkulusnak nevezünk.
A szavak ekvivalenciájának problémája Ha az R szót egy megengedett helyettesítési szabály egyetlen alkalmazásával át lehet alakítani az S szóvá, akkor S is ugyanígy átalakítható R-é. Ebben az esetben az R és S szavakat szomszédosaknak nevezzük. Az R1, R2, …, Rn szósorozatról azt mondjuk, hogy az R1-ből Rn-be vezető deduktív lánc, ha R1 és R2, R2 és R3, …, Rn-1 és Rn szomszédos szópárok. Ha van olyan deduktív lánc, ami R-ből S-be vezet, akkor van olyan is, ami S-ből R-be. Ekkor azt mondhatjuk a két szóról, hogy ekvivalensek. Ezt így jelöljük: R~S. Tegyük fel, hogy P~Q és az R szóban P előfordul. Ha R-ben P előfordulását Q-val helyettesítjük, akkor a kapott szó akvivalens Rrel. Bizonyítás: A feltétel szerint az R szó SPT alakban írható fel, ahol S az R-nek a P szót megelőző, T pedig az ezt követő része. Az átalakított szó SQT lesz. Mivel P~Q, van P1, P2, …, Pn, Q deduktív lánc. Ekkor azonban SPT, SP1T, SP2T, …, SQT deduktív lánc is létezik, ami SPT-ből SQT-be vezet.
42
BMF-NIK-AAO Tetszőleges két szóról el kell dönteni, hogy ekvivalensek-e vagy sem. Mivel minden asszociatív kalkulusban végtelen sok különböző szó van, ezért ez a probléma azonos típusú feladatok végtelen sorozata, megoldása olyan algoritmus megadását jelenti, ami tetszőleges két szóról eldönti, hogy ekvivalens-e vagy sem. A szóprobléma és a labirintusbeli út keresése összefügg: a szóproblémát tekinthetjük egy végtelen labirintusban való bolyongásnak. Egy R szóból a Q szóba vezető deduktív lánc megfelel a labirintusban a két szobát összekötő útnak. Két szó ekvivalenciája megfelel annak, hogy a szobák egymásból kölcsönösen elérhetők. Korlátos szóprobléma: egy adott T és R szóról el kell dönteni átalakítható-e egyik a másikba a helyettesítési szabályok k-szori alkalmazásával (k rögzített szám). Erre egyszerű algoritmust találni: T szótól indulva megvizsgáljuk a szomszédait, annak a szomszédait,… k-szor. A kérdésre attól függően lesz igenlő vagy nemleges válasz, hogy az eljárás során szerepel-e az R szó. Algoritmusok konstrukciója: Az egyszerű keresési módszer nem alkalmas arra, hogy a kívánt eredményt elérjük. Próbáljuk meg eldönteni, hogy az abbacada és az accdbada szavak ekvivalensek-e. Ha a helyettesítési szabályok nem változtatják a betűk számát, akkor biztosan nem ekvivalens a két szó, mert a különböző szavakban az egyes betűk száma eltérő. Hasonló deduktív invariánsnak, azaz olyan tulajdonságoknak a megtalálása, amelyek a deduktív lánc összes elemére változatlanok maradnak, bizonyos esetekben lehetővé teszi a keresett eldöntési algoritmus megadását.
A négyzet elemi egybevágósági transzformációi 1. Az O középponton áthaladó függőleges tengelyre való tükrözés. (a-val jelöljük) 2. Az O középponton áthaladó vízszintes tengelyre való tükrözés (b-vel jelöljük) 3. 900-os elforgatás a középpont körül az óramutató járásával egyező irányba. (c-vel jelöljük)
43
BMF-NIK-AAO Az ábécé betűi tehát {a, b, c} A megengedett helyettesítési szabályok: b – acc ca – accc aa – Λ bb – Λ cccc – Λ ahol Λ egy üres szót jelöl. Tehát a bal oldalt egy üres szóval pótolhatjuk, illetve bárhová beszúrhatjuk az adott szón belül. Az ábécéből képzett bármilyen szót ha a megadott helyettesítési szabályokkal átalakítjuk addig ameddig valamelyik szabály még alkalmazható, akkor végül a következő nyolc szó valamelyikéhez jutunk (redukált szavak): Λ, c, cc, ccc, a, ac, acc, accc. Ha a szóban előfordul a b betű, akkor a b→acc szabályt alkalmazzuk. Ezt addig tesszük amíg van a szóban b betű. Ezután a ca→acc szabállyal az összes olyan a, ami közvetlenül c betű mögött áll, a c elé hozható (ha van ilyen). Így az a betűk a szó elejére, a c betűk a szó végére kerülnek. Végül az aa→Λ és a cccc→Λ szabály alkalmazásával eltüntetjük a felesleges betűket. Nyilvánvaló, hogy minden szó ekvivalens a redukáltjával, ezért két szó akkor és csak akkor ekvivalens, ha ugyanaz a redukáltjuk vagy a redukáltjaik ekvivalensek. A négyzetre alkalmazott transzformációk:
44
BMF-NIK-AAO
11. Algoritmusok mátrixokkal Ritka mátrixok A mátrix egy matematikai objektum. Sorokból és oszlopokból áll, amelyek számokat tartalmaznak. Programozói nyelven a mátrix egy kétdimenziós tömb. (A[1..m, 1..n]). Amikor egy elemre rá akarunk mutatni, azt könnyen megtehetjük, a következő módon: A[m, n], vagyis arra a számra mutatunk, ami az m-edik sor n-edik eleme. Az olyan mátrixot, aminek sok 0 eleme van, ritka mátrixnak nevezzük. Arre nincs precíz definíció, hogy mikor ritka a mátrix, mikor nem. A probléma abból adódik, hogy a rengeteg 0 elem is lefoglalja a memóriát. Gondoljuk el, hogy amikor egy 1000x1000-es mátrix (aminek elemszáma 1millió) csak 1000 nem nulla elemet tartalmaz, akkor felesleges az egész tömbnek helyet foglalni. Erre az eljárásra – hogy hogyan lehet csökkenteni a felesleges memória foglalást – keressük a választ. A lehetséges kiindulási pont az, hogy csinálunk egy táblázatot a nem 0 elemekből. Például:
Az A[0, y] elem a fejléc, tartalmazza, hogy mennyi az eredeti mátrix sorainak, oszlopainak és elemeinek száma. Az A[1, y] és A[2, y] elemek tartalmazzák az eredeti mátrixból átvett nem 0 elemek tulajdonságait.
45
BMF-NIK-AAO A következő algoritmus a mátrixok átalakítását végzi: public int[,] MatrixConverter(int[,] a){ int k=0; for(int i=0; i
Algoritmus az átalakított mátrixok transzponáltjának számítására: public int[,] transpose(int[,] a){ int[,] b=new int[a[0, 2]+1, 3]; for(int i=0; i
46
//az új mátrix létrehozása //a sorok és oszlopok felcserélése //az érték átírása az új mátrixba
BMF-NIK-AAO Mátrixok láncszorzása A mátrix szorzás egy nagyon nagy memória igénylő feladat. Gondoljunk csak egy 10x10, egy 15x10 és egy 15x8 méretű mátrixok szorzására. Ez nagyon sok művelet. Ezeknek a számát akarjuk a legkevesebbé tenni. Ellenőrizni kell miként lesz a műveletek száma a legkevesebb, ha (A*B)*C szorzást számoljuk ki, vagy az A*(B*C) szorzást. Amelyik kevesebb művelettel megoldható azt kell alkalmazni.
Strassen-féle mátrixszorzás Ebben a fejezetben Strassen figyelemre méltó rekurzív algoritmusát mutatjuk be, amellyel n x n-es mátrixokat O(nlg7)= O(n2.81) lépésben szorozhatunk össze. Ez tehát elég nagy n-re gyorsabb, mint az O(n3) igényű mátrixszorzási algoritmus. Strassen algoritmusa a jól ismert oszd meg és uralkodj elv alkalmazásaként is felfogható. Tegyük fel, a C=AB szorzatot akarjuk kiszámítani, ahol A, B és C n x n-es mátrixok. Amennyiben n 2-nek a hatványa, mind A-t, B-t és C-t négy n/2 x n/2 méretű mátrixra bontjuk, majd C=AB-t átírjuk az
alakba. A elemeire sorfolytonos, míg B elemeire oszlopfolytonos jelölést alkalmaztunk, a mátrixszorzás definíciójának megfelelően. Az előbbi egyenlőség ekvivalens az alábbi négy egyenlőséggel: r=ae+bf s=ag+bh t=ce+df u=cg+dh E négy egyenlőség mindegyike két n/2xn/2-es mátrix összeszorzását és a szorzatok összeadását jelenti. Ennek alapján két nxn –es mátrix összeszorzásának T(n) műveleti idejére a
47
BMF-NIK-AAO T(n)=8*T(n/2)+O(n2) rekurzív egyenletet vezethetjük le. Sajnos, a fenti egyenlet megoldása T(n)=O(n3), így ez a módszer nem gyorsabb mint a szokásos. Strassen módszerében ezzel szemben csak 7 rekurzív n/2xn/2-es mátrixszorzás és O(n2) skalár összeadás és kivonás szerepel, azaz T(n)=7*T(n/2)+O(n2)=O(nlg7)=O(n2.81). Strassen módszere 4 lépésből áll: 1. Bontsuk fel az A és B mátrixokat n/2xn/2-es részmátrixokra. 2. O(n2) skalár összeadás és kivonás segítségével számítsunk ki 14 n/2xn/2-es mátrixot: az A1, B1, A2, B2, …, A7, B7 mátrixokat. 3. Számítsuk ki a Pi=AiBi mátrixszorzatokat, i=1, 2, …, 7. 4. Számítsuk ki a C szorzatmátrix keresett r, s, t, u részmátrixait a Pi mátrixok különböző kombinációinak az összegeként és/vagy különbségeként, csak O(n2) skalár összeadás és kivonás felhasználásával. A Strassen-algoritmus használhatóságát a futási idejének képletében foglalt nagy konstans megkérdőjelezi, hacsak nem nagy méretű (n legalább 45), vagy sűrű (kevés nem 0 elemet tartalmazó) mátrixról van szó. Kis mátrixok esetén a szokásos algoritmus használata célszerűbb, míg nagyméretű, ritka mátrixokra a speciális technikák alkalmazhatóak előnyösebben. Így Strassen módszere főleg elméleti jellegű. Strassen algoritmusának alkalmazásához nem feltétel, hogy a mátrix elemei valós számok legyenek. Csak az kell, hogy a számkör gyűrűt alkosson. Azonban a módszer néha akkor is alkalmazható, ha a mátrix elemei nem alkotnak gyűrűt.
48
BMF-NIK-AAO
12. A bűvös négyzet a bűvös négyzet fogalma: Egy n-oldalú bűvös négyzet n*n darab, egymástól különböző egész szám egy négyzetes mátrixban való elhelyezése, ahol a sorok összege, az oszlopok összege és mindkét átló összege ugyanaz a szám. Egy normális bűvös négyzetben a tagok 1 és n2 között vannak. Utóbbi esetben a bűvös összegre az alábbi képlet áll fenn: S=(n3+n)/2. 4-oldalú normális bűvös négyzet: 16 5 9 4
3 10 6 15
2 11 7 14
13 8 12 1
A bűvös összeg: 34 4-oldalú nem-normális bűvös négyzet: 1 11 8 13
14 7 10 2
14 6 10 3
4 9 5 15
A bűvös összeg 33, Jézus Krisztus éveinek száma. Minden sora megfeleltethető a Dürer-féle négyzet valamely sorának, de mindegyik sorban az egyik szám 1-gyel kisebb. → A normalitás sérül: 10 és 14 kétszer is előfordul, 12 és 16 pedig hiányzik.
49
BMF-NIK-AAO 3-oldalú bűvös négyzet: 4 3 8
9 5 1
2 7 6
A bűvös összeg: 15 A Lo Shu négyzet Egy Kr.e. 2800 körüli legenda szerint az emberek egy nagy árvíz idején a Lo folyó istenének áldozatot kívántak bemutatni. Ekkor egy teknőc mászott ki a vízből, páncélján egy különös mintával: ez volt az előbbi bűvös négyzet. 15 – a bűvös összeg – egyébként a kínai napév 24 ciklusának ciklusideje, így a napév 360 napig tart.
Ekvivalens bűvös négyzetek: 90 fokos forgatás egy sorösszeget oszlopösszegbe, egy oszlopösszeget sorösszegbe, egy átlót a másik átlóba visz. A függőleges szimmetriatengelyre való tükrözés esetén az oszlopösszegek és a sorösszegek megmaradnak, az átlók egymásba képződnek. Hasonló az eset a vízszintes szimmetriatengelyre való tükrözés esetén is. Azaz a négyzet egybevágósági transzformációi bűvös négyzetet bűvös négyzetre képeznek le, ezeket a bűvös négyzeteket ekvivalenseknek tekintjük.
A bűvös összeg levezetése: Adjuk össze a négyzet összes elemét, amely 1-differenciájú számtani sorozat, 1-től n2-ig. n2(1+n2)/2 Ha az összeadást soronként végezzük, akkor az összeg a sorok száma szorozva S-sel, mert S a sorösszeg. nS=n2(1+n2)/2 N-nel osztva kapjuk az eredményt: S=(n3+n)/2
50
BMF-NIK-AAO Páratlan bűvös négyzet konstruálása Coxeter módszer: A felső sor közepén (van közepe, mert n – a méret – páratlan) indulunk, ide 1-t teszünk. A mozgásirány 1 lépés fel, 1 lépés jobbra, ide az előző kitöltésnél 1-gyel nagyobbat teszünk. Ha már kitöltött cellát találunk, akkor a fenti lépés helyett 1-et lefelé lépünk. Ha a lépéssel elhagyjuk a négyzetet, akkor ,,hengeresen összetekertnek” képzeljük. A Coxeter módszer n=5-re 17 23 4 10 11
24 5 6 12 18
1 7 13 19 25
51
8 14 20 21 2
15 16 22 3 9
BMF-NIK-AAO A piramis módszer:
C# kódja //a piramis előkészítése //n-nek páratlannak kell lennie //piramis méret
int n=5, i, j; int m=2*n-1; int[,]bn=new int[m,m]; string s=” ”; bn[n-1, 0]=1; for(i=0; i
//eredeti méretig //eredeti méretig
for(i=0; ivege) bn[i-n, j]=bn[i, j]; if (i>vege) bn[i, j-n]=bn[i, j]; }
52
//a piramis kiíratása
//igazítás
//a bűvös négyzet előállítása
//ha zöld //ha lila //ha piros //ha kék
BMF-NIK-AAO
13. Egyéb algoritmusok Az euklideszi algoritmus gcd=greatest common divisor=legnagyobb közös osztó A és B számoknak akarjuk meghatározni a legnagyobb közös osztóját. Tegyük fel, hogy T az A-t B-vel osztva kapott maradék. Tehát: A=qB+T, ahol q az osztás hányadosa. A és B bármely közös osztója osztja T-t (mivel T=A-qB). Hasonlóan B és T bármely közös osztója osztja A-t. A és B legnagyobb közös osztója egyenlő B és T legnagyobb közös osztójával. Tehát elegendő Ha B-vel és T-vel folytatjuk az eljárást. Mivel |T|b) a=a-b; else b=b-a; return a; }
//mindig a nagyobból vonjuk ki a kisebbet
A Fibonacci sorozat Fibonacci számsor: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, … A sorozat egy tagját úgy kapjuk, hogy az előző kettőt összeadjuk. (azonban ha n=0 akkor az elem értéke 0, ha n=1 akkor az elem értéke 1). C# kódja //ez a függvény visszaadja az x-edik Fibonacci számot. unsigned int f(int x){ return x<2 ? 1 : f(x-1)+f(x-2); }
53
BMF-NIK-AAO A Horner séma Habár már Isaac Newton is ismerte az algoritmust, William George Horner-ről nevezték el, aki 1819-ben írta le. De ezt az eljárást már a Kínai matematikusok is ismerték 1200 körül. A következő polinom értékét akajuk meghatározni: p(x)=a0+a1x+a2x2+a3x3+…+anxn ha ezt a formát használjuk n darab összeadásra és (n2+n)/2 darab szorzásra van szükség. A cél hogy csökkentsük a szorzások számát, ezáltal gyorsítsuk a számolást. A Horner algoritmus a következő rekurzív formát adja meg: p(x)=a0+x(a1+x(a2+…x(an-1+anx))) Ebben a formában a szorzások és az összeadások száma is n.
Az erathostenesi szita Segítségével megkaphatjuk a prímszámokat (n-ig). Sorban írjuk le a számokat 2-től n-ig. Húzzuk ki azokat a számokat melyek oszthatók kettővel. Keressük meg a legkisebb megmaradt számot, ez a 3. Húzzuk ki az összes olyan számot mely osztható 3-mal. Keressük meg a legkisebb megmaradt számot. Ez az 5. Húzzuk le az 5-tel osztható számokat is. Ezt az eljárást addig folytatjuk amíg a gyök n-nel osztható számokat is ki nem húztuk. A számok amelyek maradnak, azok prímek.
54
BMF-NIK-AAO
14. Az OOP rész (Miklós Árpád előadásai) Számítási modellek és programozási paradigmák
Modellezési alapelvek A modellezés célja A modellezés célja a világ minél teljesebb körű megértése – Elemek, folyamatok, összefüggések, viszonyok
A modellezés során a fenti cél érdekében az ember: – ábrázolásokat készít a világról, majd – leképezi a világ egyes szeleteit az általa használt eszközökben (ennek során egy vagy több szempontot kiemel más szempontokkal szemben).
A modellezés folyamata • Absztrakció – Lényeg kiemelése, a jellegzetességek leegyszerűsített leképezése
• Megkülönböztetés – Elemek meghatározása, elemek és tulajdonságaik szétválasztása
• Osztályozás – Elemek típusokba, csoportokba sorolása
• Általánosítás és specializáció – Elemtípusok bővítése és szűkítése, elemhierarchiák kialakítása
• Kapcsolatok meghatározása – Különböző kapcsolattípusok meghatározása, elemek közötti kapcsolatok felállítása (ismeretség, leszármazás, tartalmazás, kompozíció...)
55
BMF-NIK-AAO Programozási paradigmák A paradigma fogalma • Paradigma: szemléletmód; modellezési, problémadefiníciós és probléma-megoldási módszer – Programozási paradigma: a számítógép konkrét feladatok megoldására történő felhasználásának, irányításának módja
Programozási paradigmák és programozási nyelvek • A programozási nyelveket általában egy-egy paradigma ihleti – Céljuk egy adott programozási paradigma legfontosabb jellemzőinek megvalósítása – A programozási paradigmák egy-egy számítási modellre épülnek
• A programozási nyelvek absztrakciós szintje folyamatosan nő – A kiindulópont a számítógép konkrét hardvermegvalósítása volt – Minden új paradigma növeli az absztrakció szintjét
• Néha „holtágak” is keletkeznek, így egyes magasabb absztrakciós szintet képviselő nyelvek „kihalnak”, de a fenti állítás a fő fejlődési irányokra is igaz
56
BMF-NIK-AAO Programozási megoldások Számítási modellek és programozási paradigmák • Imperatív számítási modellek („hogyan számítsuk ki”) – Turing-modell • Alan Turing nevéhez fűződik (1936) • Nincs hozzá kapcsolódó programozási paradigma (csak elvi jelentősége van)
– Neumann-modell • Neumann János nevéhez fűződik (1945) • Procedurális/strukturált programozási paradigma – Utasításorientált; az egyes műveletek megismételhetők; többszörös értékadás; változók; alapvetően soros végrehajtást feltételező modell
– Objektumorientált modell • Objektumorientált (OO) programozási paradigma – Adatorientált; adatok és a rajtuk végezhető műveletek összerendelése objektumokba; üzenetáramlás az egyes objektumok között; a modell nem feltételez soros végrehajtást
– Adatfolyam-elvű modell • Adatfolyam-elvű programozási paradigma – Adatorientált (bemenő adatokból kimenő adatok); adatok kiértékelése rendelkezésre álláskor
• Deklaratív számítási modellek („mit akarunk kiszámítani”) – Funkcionális/applikatív számítási modell • Funkcionális programozási paradigma – Függvények redukciója automatikus behelyettesítésekkel – Példa (ML programozási nyelv)
– Logikai alapú számítási modell • Logikai programozási paradigma – Egymással összefüggésben levő állítások levezetése (rezolúció) mintaillesztéssel és következtetésekkel – Példa (Prolog programozási nyelv)
57
BMF-NIK-AAO A számítási modellek, számítógép-architektúrák és programozási nyelvek összefüggése
Programozási megoldások fejlődése Különböző számítási modelleken alapuló architektúrák versenye
58
BMF-NIK-AAO A Neumann-architektúra A Neumann-architektúra alapvető felépítése
A Neumann-architektúra főbb jellemzői • Utasítások és adatok tárolása egy közös memóriában – Adatok tárolása nevesített változókban (elkülönített memóriarekeszek) – Nincs külső megkülönböztetés az utasítás és az adat között, csak az aktuális programállapot dönt az értelmezésről – Az utasítások sorozata a programból, külső beavatkozás nélkül is módosítható
• Folyamatos, ciklikus programvégrehajtás – A végrehajtás a memória első rekeszétől indul, majd ha elérte a memória végét, ismét az első rekesztől folytatódik
• Feltételes és feltétel nélküli vezérlésátadás – „A következő utasítás végrehajtása függjön az előző eredményétől” – Megismételhető műveletek, értékadások
• Soros, szinkron működés
59
BMF-NIK-AAO Az objektum-orientált programozási paradigma
A szoftverkrízis Kihívások a szoftverfejlesztés módszereivel szemben 1. A szoftveres megoldások szerepe folyamatosan erősödik – A szoftverek felhasználási aránya (még mindig) igen gyorsan nő
2. A szoftverekkel szembeni elvárások egyre magasabbak – Az élet mind több területen alkalmazunk szoftveres megoldásokat • Tudomány, oktatás, ipar, ügyvitel, bankszektor, államigazgatás, otthonok... – Az olcsóbbodó hardver egyre szélesebb rétegek számára elérhető • Az „átlagos felhasználó” számítástechnikai ismereteinek szintje rohamosan csökken – A hardver teljesítménye rendkívül gyorsan növekszik • A fentiekből következően az ár/teljesítmény arány még gyorsabban javul – Ezzel párhuzamosan a szoftver funkciógazdagságával, sebességével, kényelmével, használhatóságával kapcsolatos követelmények folyamatosan emelkednek • A szoftver fejlődési üteme egyre jobban „lemarad” a hardver fejlődési üteme mögött
60
BMF-NIK-AAO 3. A szoftver rendkívül jól formálható „nyersanyag” – Szinte nincsenek fizikai korlátok • A szoftver nem fizikai (anyagi) jellegű • A szoftver előállítása alapvetően nem jár közvetlen fizikai nyersanyagigénnyel • A szoftver, mint erőforrás mennyisége nem korlátos (végtelenül többszörözhető) • A szoftvernek alapvetően nem kell alkalmazkodnia külső körülményekhez – Viszonylag kevés a jogi korlát • Ezen a téren igen gyors (és sokszor önkényes) a változás – Bármilyen algoritmus és bármilyen adatstruktúra elképzelhető, felépíthető, módosítható
4. A programok minőségi bonyolultsága folyamatosan növekszik – A szoftver eredendően összetett szellemi alkotás – Nincsenek, illetve nehezen önthetők formába jelentősebb ismétlődő elemek • Tervezési minták • „Tudásinverzió” – A működési állapotok száma rendkívül magas • Összetettebb programok elvi helyességének bizonyítása egyelőre nem lehetséges • A teljes körű tesztelés ezért szinte lehetetlen – Rendszeresek és gyakoriak a változtatási igények • A fejlesztők részéről (hibajavítás, platformváltás, fejlesztőrendszerváltás...) • A felhasználók részéről (hibajavítás, új funkciók, funkcionális módosítások...)
5. Az ember áttekintőképessége korlátos – Teljesen automatizált szoftver előállításra egyelőre nincs mód – A bonyolultság újra és újra kezelhetetlenül magas szintet ér el • A szoftverhibák következményei egyre súlyosabbak lehetnek
Kihívások a szoftverfejlesztés módszereivel szemben Folyamatosan új megoldásokra van szükség az egyre növekvő absztrakciós szint és bonyolultság eredményes, hatékony és biztonságos kezeléséhez
61
BMF-NIK-AAO Procedurális/strukturált program Definíció és jellemzők • A problémát az algoritmus (a kód) oldaláról közelíti meg – – – –
A szükséges funkciók meghatározása (funkcionális dekompozíció) A programvégrehajtás (vezérlés) pontos menetének leírása A funkciók számára szükséges adatstruktúrák meghatározása A probléma megoldását a funkciók egymás után, a megfelelő sorrendben történő végrehajtása adja meg
• Jellemzők: – A függvények definíciója határozza meg a program szerkezetét – Globális adatstruktúrák – Egy un. „főprogram” fogja össze, amely „függvényeket” „hív meg” • A főprogram komoly szerepet játszik és gyakran igen bonyolult – A végrehajtás menetét szigorúan megszabja a megírt programkód
Tipikus felépítés
62
BMF-NIK-AAO Objektumorientált program Definíció és jellemzők • A problémát az adatok oldaláról közelíti meg – A szükséges absztrakt rendszerelemek meghatározása – A fenti rendszerelemek adatainak és (az adatokkal végezhető) absztrakt műveleteinek meghatározása, majd ezek összerendelése • Ezzel csoportokba („típusokba”) soroljuk az egyes elemeket – A probléma megoldását az egyes objektumok közötti kommunikáció, az egyes műveletek állapotváltozásoktól függő végrehajtása adja meg • Az objektumok kapcsolódási felülettel rendelkeznek, melynek segítségével üzeneteket váltanak egymással
• Jellemzők: – Az egyes objektumok magukban foglalják az algoritmusokat • Minden objektum a probléma egy részét írja le és magában foglalja a részfeladat megoldásához tartozó algoritmikus elemeket – A főprogram jelentősége igen csekély • Gyakorlatilag csak indítási pontként szolgál, lényegi funkciót általában nem lát el
Tipikus felépítés
63
BMF-NIK-AAO Az OO paradigma alapelvei 1. alapelv: Absztrakció • Meghatározzuk a szoftverrendszer absztrakt elemeit • Meghatározzuk az elemek állapotterét – Adatelemek
• Meghatározzuk az elemek viselkedésmódját – Funkciók végrehajtása – Állapotváltoztatások
• Meghatározzuk az elemek közötti kapcsolattartás felületeit és protokollját – Üzenetváltások típusa – Pontosan definiált, megbízható kapcsolódási felületek
...mindezt a megvalósítás konkrét részleteinek ismerete nélkül.
2. alapelv: Egységbezárás • Az objektumok adatait és a rajtuk végezhető műveleteket szoros egységbe zárjuk – Az adatok csak a definiált műveletek segítségével érhetők el – Más műveletek nem végezhetők az objektumokon
• Az egységbezárás védi az adatokat a téves módosításoktól
3. alapelv: Adatrejtés • Az absztrakciók megvalósításának részleteit elrejtjük a „külvilág” elől • Az objektumokon belül elkülönítjük a belső (privát) és a külső (nyilvános) adatokat és műveleteket – A privát adatok és műveletek a konkrét megvalósításhoz szükségesek – A nyilvános adatok és műveletek a szoftverrendszer többi objektuma számára (is) elérhetők • Tájékozódás az objektum állapotáról • Az objektum állapotának módosítása • Üzenetváltás
64
BMF-NIK-AAO 4. alapelv: Öröklés • A már meglévő objektumtípusok alapján készíthetünk új típusokat, melyek rendelkeznek az „őstípus” tulajdonságaival – Ez egy specializációs művelet („származtatás”) • A „leszármazottak” „öröklik” az őstípus tulajdonságait – A leszármazottak bővíthetik, esetenként akár szűkíthetik az őstípus állapotterét, illetve műveleteit – Teljes leszármazási hierarchiákat is létrehozhatunk – Kiváló lehetőség a közös tulajdonságok, műveletek összevonására és újrahasznosítására
• Az alapelv következetes alkalmazásával elérhető, hogy a már megvalósított funkcionalitás később a megvalósítás részleteinek ismerete nélkül is felhasználható legyen – Jól átgondolt előzetes tervezést igényel
5. alapelv: Többalakúság • A különböző, egymásból származó objektumtípusok hasonló műveletei a konkrét objektumtól függően más-más konkrét megvalósítással rendelkezhetnek – Ugyanaz a művelet némileg eltérő lehet az őstípus és a leszármazott típus esetében – Az alapelv lehetőséget teremt rá, hogy azonos névvel hivatkozzunk az azonos célú, de a leszármazási hierarchia különböző szintjein más-más megvalósítást kívánó műveletekre
• Az egyes őstípusok leszármazottai mindenre alkalmasak, amire az adott őstípus alkalmas volt – Minden olyan helyzetben és funkcióban, ahol az őstípus szerepelhet, annak bármely leszármazottja is szerepelhet
6. alapelv: Kódújrafelhasználás • A már megvalósított objektumtípusokat kész (bináris) formában más programokban is felhasználhatjuk – Jó tervezés és dokumentálás esetén az objektumok nyilvános adatai és műveletei elegendőek a későbbi felhasználáshoz • Szintaktikai bővítésekkel (pl. „tulajdonságok”, „események”) kényelmesebbé tehető a külső felhasználás – Az egyes objektumtípusokat egymásba ágyazva összetettebb típusokat hozhatunk létre – A kész, újrafelhasználható objektumtípusokat csoportokba fogva akár nagyobb „szoftver-építőelemeket” (komponenseket és komponensgyűjteményeket) is létrehozhatunk
• A korábban említett alapelvekre építve a kódújrafelhasználás lehetősége jelenti az igazi áttörést a szoftvertechnológiában
65
BMF-NIK-AAO Az objektumorientált paradigma alapelemei
Objektum Definíció • Az objektum állapottal rendelkező entitás, amely a benne tárolt adatok felhasználásával feladatokat hajt végre és egyéb objektumokkal kommunikál – Adatokat és algoritmusokat tartalmaz – Saját feladatait önállóan végzi • Saját „életciklussal” rendelkezik • A „külvilággal” meghatározott üzeneteken keresztül tartja a kapcsolatot
• Az objektum saját adatait mezőknek, beépített algoritmusait metódusoknak nevezzük – Az objektumok metódusaikkal vesznek részt az üzenetváltásokban – Az üzenetek elemei: célobjektum, metódus, paraméterek, eredmény
Állapotok, viselkedés és azonosság • Az objektum állapotát mezői aktuális értéke határozza meg – Az objektum állapota az elvégzett műveletek hatására megváltozhat – Két objektum állapota akkor egyezik meg, ha minden megfelelő mezőértékük megegyezik – Az objektum mindig „megjegyzi” aktuális állapotát
• Az objektum viselkedését az általa ismert (az objektumba épített) algoritmusok határozzák meg • Minden objektum egyértelműen azonosítható – Az objektumok önállóak (saját életciklusuk határozza meg őket) – Ha két objektum állapota megegyezik, maguk az objektumok akkor sem azonosak
66
BMF-NIK-AAO Osztály Definíció • Az osztály egy adott objektumtípust határoz meg annak adataival (mezők) és beépített algoritmusaival (metódusok) – Az osztályok egyfajta mintát, sablont adnak az objektumokhoz • Az osztályok tehát azonos adatszerkezetű és viselkedésű objektumokat írnak le
• Minden objektum valamilyen létező osztályba tartozik – Más kifejezéssel élve az egyes objektumok azon osztályok példányai, amelyekhez tartoznak – Egy osztályból több példány is létrehozható – Egy osztály összes példánya ugyanazokat a mezőket és metódusokat tartalmazza • Az egyes példányok létrehozásuk pillanatában azonos állapotúak, ezt követően viszont önállóan működnek tovább • Léteznek az osztályra (és nem az egyes objektumpéldányokra) jellemző mezők és metódusok is
Példa: az Autó osztály és két példánya (UML)
67
BMF-NIK-AAO Objektumorientált szoftverciklus Elemzés, tervezés, megvalósítás • Objektumorientált elemzés (OOA) – A megoldandó feladat leírása osztályok és objektumok segítségével
• Objektumorientált tervezés (OOD) – A feladatleírás objektumközpontú részekre bontása (dekompozíciója) • Logikai modell – az osztályok és objektumok • Fizikai modell – a logikai modellt megvalósító modulok és folyamatok • Statikus és dinamikus jellemzők
• Objektumorientált programozás (OOP) – A modell megvalósítása egymással kommunikáló, dinamikusan létrehozott objektumok segítségével, melyek egy-egy osztály példányai • OO stílusú programokat bármilyen nem OO nyelven is lehet írni, csak nagyon nehéz
• Részletesebb, pontosabb információk később (a szoftvertechnológiával foglalkozó tantárgyak keretében)
68
BMF-NIK-AAO Metódusok általános típusai Objektumok létrehozása (példányosítás): konstruktor • Ahhoz, hogy az objektumokat használhassuk, először létre kell hozni őket – Ez a művelet a példányosítás – Alapja az osztály megadott definíciója – A példányosítást követően érhetők el az objektumok metódusai és ekkortól érhető el az objektumok mezőinek értéke
• A konstruktor egy olyan metódus, amelynek segítségével példányok (objektumok) hozhatók létre egy osztályból – Feladatai: • Új objektum létrehozása • Az objektumhoz tartozó mezők kívánt kezdőértékének beállítása • Egyéb szükséges kezdeti műveletek végrehajtása
• Minden osztályhoz tartoznia kell konstruktornak – Ha külön nem definiálunk konstruktort, akkor is létrejön
Objektumok megszüntetése (felszámolás): destruktor • Az objektumokat az utolsó használat után fel kell számolni – Minden objektum külön-külön szüntethető meg (önállóan léteznek)
• A destruktor egy olyan metódus, melynek segítségével létező objektumok szüntethetők meg – Egyetlen feladata az objektum megszüntetése
• Az objektumok felszámolása lehet a programozó feladata vagy történhet automatikusan is – Egy objektum akkor számolható fel automatikusan, ha a későbbiekben már biztosan nincs rá szükség – Az automatikus felszámolás fejlettebb és jóval kevésbé hiba-érzékeny megoldás – Automatikus felszámolás esetén nincs feltétlenül szükség destruktorra
Módosító, kiválasztó és iterációs metódusok • Módosító metódusok – Megváltoztatják az objektum állapotát
• Kiválasztó metódusok – Hozzáférést biztosít az objektum adataihoz, de nem változtatják meg őket (így az objektum állapotát sem)
• Iterációs metódusok – Az objektum adatainak valamely részhalmazán „lépkednek végig”, és az adott részhalmazra vonatkozóan végeznek el műveleteket
69
BMF-NIK-AAO Osztályok közötti kapcsolatok 1. Leszármazás (un. „IS-A” kapcsolat) • Egy osztály leszármazottai „öröklik” az osztály jellemzőit – Rendelkeznek ugyanazokkal a mezőkkel – Tartalmazzak ugyanazokat a metódusokat – Ebben a specializációs kapcsolatban a leszármazottat „utódnak”, az eredeti osztályt „ősosztálynak” nevezzük
• A leszármazottak bővíthetik az ősosztály adatait és algoritmusait – Új mezőket adhatnak a meglévőkhöz – Új metódusokat definiálhatnak – Meglévő metódusok működését módosíthatják
• A leszármazottak minden műveletre képesek, amelyre az ősosztály képes volt – Az utódosztály példányai használhatók az ősosztály példányai helyett
Példa: leszármazás (UML)
70
BMF-NIK-AAO 2. Asszociáció • Az asszociáció osztályok közötti tetszőleges típusú viszony – Általában az asszociáció konkrét elnevezése fejezi ki a viszonyt • Szerep (pl. az ember az autó tulajdonosa) • Cselekvés (pl. az ember vezeti az autót) – Multiplicitás: vannak „egy-egy”, „egy-több” és „több-több” típusú asszociációk – Irányultság: az asszociáció lehet egy- vagy kétirányú
• Asszociációs kapcsolat áll fenn két osztály között, ha az egyiknek a saját helyes működéséhez ismernie kell a másikat – Példa: egy osztály használ egy másik osztályt (un. „USES-A” kapcsolat)
Példa: asszociáció (UML)
71
BMF-NIK-AAO 3. Aggregáció és kompozíció (un. „HAS-A” kapcsolat) • Az aggregáció az asszociáció speciális esete: tartalmazási kapcsolat – A kapcsolat aszimmetrikus és tranzitív – A tartalmazó osztály példányai magukban foglalják a tartalmazott osztály egy vagy több példányát – A tartalmazó és a tartalmazott osztály egymástól függetlenül létezhetnek • A tartalmazott átveheti (de nem örökli) a tartalmazó egyes jellemzőit
• A kompozíció az aggregáció speciális esete: szigorú tartalmazási kapcsolat – Egy tartalmazottnak mindig csak egy tartalmazója lehet • Egy tartalmazó viszont tetszőleges számú tartalmazott példánnyal rendelkezhet – A tartalmazó és a tartalmazott életciklusa közös
Példa: aggregáció és kompozíció (UML)
72
BMF-NIK-AAO Az OOP néhány csapdája Mire kell ügyelni az osztályok kialakításánál? • Rossz döntés az osztályok közötti kapcsolat típusának megválasztásánál – Pl. leszármazás helyett aggregáció vagy fordítva
• Leszármazási kapcsolat helytelen kialakítása – Az ősosztály túl keveset vagy túl sokat „tud”
• Önkéntelenül (nem látható módon) beépített feltételezések – Az ősosztály feltételez bizonyos állapotváltozásokat, a metódusok végrehajtási sorrendjét – ez nem biztos, hogy a leszármazottaknál is igaz lesz
• „Felduzzasztott” osztályok – A túl sok mező és metódus, a túl hosszú metódusok azt jelezhetik, hogy valamilyen módon fel kell bontani az osztályt
• Elnevezési anomáliák
73
BMF-NIK-AAO Egységbezárás, adatrejtés
Egységbezárás Definíció (ismétlés) • Az objektumok adatait és a rajtuk végezhető műveleteket szoros egységbe zárjuk – Az adatok csak a definiált műveletek segítségével érhetők el – Más műveletek nem végezhetők az objektumokon
• Az egységbezárás védi az adatokat a téves módosításoktól
Adatrejtés Definíció (ismétlés) • Az absztrakciók megvalósításának részleteit elrejtjük a „külvilág” elől • Az objektumokon belül elkülönítjük a belső (privát) és a külső (nyilvános) adatokat és műveleteket – A privát adatok és műveletek csak a megvalósításhoz szükségesek – A nyilvános adatok és műveletek a szoftverrendszer többi objektuma számára (is) elérhetők • Tájékozódás az objektum állapotáról • Az objektum állapotának módosítása • Üzenetváltás
74
BMF-NIK-AAO Névterek • Az OO paradigma jellemzője az elnevezések óriási száma – Minden osztálynak, objektumnak, mezőnek, metódusnak egyedi nevet kell adni, hogy a későbbiekben hivatkozni lehessen rá • Nem könnyű jól megjegyezhető, a célt később is felidéző neveket adni
• A programok méretével egyenes arányban nő a névütközések valószínűsége – A programok általában nem csak saját osztályokat használnak fel
• A névtér, mint az elnevezések érvényességének tartománya, hierarchikus logikai csoportokra bontja az elnevezéseket – Minden elnevezésre csak a saját névterén belül lehet hivatkozni • Ennek megfelelően a saját névtéren belül minden elnevezés egyedi – A névterek általában tetszőleges mélységben egymásba ágyazhatók – Azonos elnevezések más-más névtereken belül szabadon használhatók, így erősen lecsökken a névütközési probléma jelentősége
Példa
75
BMF-NIK-AAO Láthatósági szintek Mezők és metódusok védelme • A láthatósági szintek segítségével különítjük el az osztály belső, illetve kívülről is elérhető tagjait – Az egyes mezők és metódusok láthatósága külön-külön szabályozható
• Alapvető láthatósági szintek: – Nyilvános (public) • Az adott tagot az osztály saját metódusai, az osztály leszármazottainak metódusai és az osztályt használó más osztályok metódusai használhatják • Ezzel a szinttel valósul meg az osztály külvilág számára látható „felülete” – Védett (protected) • Az adott tagot az osztály saját metódusai és az osztály leszármazottainak metódusai használhatják • Ez a szint a leszármazottak számára tesz elérhetővé bizonyos funkciókat – Privát (private) • Az adott tagot csak az osztály saját metódusai használhatják • Ezzel a szinttel valósul meg az osztály szigorúan belső jellegű funkcionalitása
Összegzés • A láthatósági szintek segítségével hatékonyan valósítható meg az egységbezárás – Az osztályok a kívülről is látható elemeiket bocsátják más osztályok rendelkezésére • A nyilvános mezők adatokat, a nyilvános metódusok műveleteket tesznek elérhetővé – Az egyes osztályok megvalósítási részletei módosíthatók anélkül, hogy az osztályt használó más osztályoknak erről tudniuk kellene • A megvalósítást végző algoritmusok nincsenek kihatással az osztályt használó kódra – Konkrét OO nyelvi megvalósításokban általában további láthatósági szintek is léteznek
76
BMF-NIK-AAO Példány szintű tagok Objektumokhoz tartozó mezők és metódusok • A példány szintű tagok a példányosított objektumok – saját adatmezői, valamint – saját adatain műveleteket végző metódusai.
• A példány szintű mezők tárolják a példányok állapotát • Az egyes metódusok programkódját általában nem tartalmazza külön-külön az osztály minden példánya – A metódusok minden példánynál azonosak és nem módosíthatók, ezért a metódusok programkódját az osztályon belül szokás tárolni – Szükség lehet azonban arra, hogy a példány szintű metódusok hivatkozni tudjanak arra az objektumra, amelyen a műveletet végzik • Példa: átadás paraméterként vagy eredményként; elnevezések egyértelműsítése – Ezt általában egy rejtett paraméterrel valósítják meg • Megnevezése nyelvi megvalósításonként változik („this”, „Self”, „Me”...) • Mindig minden példánymetódusból elérhető, értéke a példány maga
Osztály szintű tagok Osztályokhoz tartozó mezők és metódusok • Az osztály szintű tagok az egyes osztályokhoz tartozó – egyedi adatmezők, valamint – az ezeken műveleteket végző metódusok.
• Osztály szintű adatmezők – Minden osztály pontosan egyet tartalmaz belőlük, függetlenül az osztályból létrehozott objektumpéldányok számától
• Osztály szintű metódusok – Akkor is elérhetők, ha az osztályból egyetlenegy példány sem létezik – Csak osztály szintű adatmezőket használhatnak – Speciális osztály szintű metódus az osztály szintű konstruktor • Feladata az osztály szintű adatmezők kezdőértékének beállítása • Általában az osztályra történő első hivatkozás előtt fut le automatikusan – Konkrét példányt nem igénylő feladatok végrehajtására is alkalmasak • Példa: főprogram megvalósítása
77
BMF-NIK-AAO Osztály és példány szintű tagok Összehasonlító táblázat
Tulajdonságok Intelligens mezők – egy szintaktikai „cukorka” • A tulajdonság olyan nyelvi elem, amely felhasználás szempontjából adatmezőként, megvalósítás szempontjából metódusként viselkedik – Az adott osztály felhasználói mezőnek „látják” a tulajdonságot • A külvilág mezőként hivatkozhat a tulajdonságra – A tulajdonságot megvalósító osztály külön-külön metódust rendelhet a tulajdonság olvasási és írási műveletéhez • Olvasáskor a megfelelő metódus egy valódi (általában privát) mező értékét is visszaadhatja, de akár számítással is előállíthatja a visszaadott érteket • Íráskor a megfelelő metódus egy valódi (általában privát) mező értékét is módosíthatja, de végezhet egyéb műveleteket is vagy akár módosítás előtt ellenőrizheti az átadott értéket – A tulajdonság tehát felfogható intelligens mezőként
• A tulajdonságok a mezőkhöz és a metódusokhoz hasonlóan különböző láthatósági szintekhez sorolhatók
78
BMF-NIK-AAO Öröklés Definíció (ismétlés) • A már meglévő objektumtípusok alapján készíthetünk új típusokat, melyek rendelkeznek az „őstípus” tulajdonságaival – Ez egy specializációs művelet („származtatás”) • A „leszármazottak” „öröklik” az őstípus tulajdonságait – A leszármazottak bővíthetik, esetenként akár szűkíthetik az őstípus állapotterét, illetve műveleteit – Teljes leszármazási hierarchiákat is létrehozhatunk – Kiváló lehetőség a közös tulajdonságok, műveletek összevonására és újrahasznosítására
• Az alapelv következetes alkalmazásával elérhető, hogy a már megvalósított funkcionalitás később a megvalósítás részleteinek ismerete nélkül is felhasználható legyen – Jól átgondolt előzetes tervezést igényel
1. példa – Geometriai alakzatok kezelése
79
BMF-NIK-AAO 2. példa – Járművek osztályozása
A leszármazottak tényleges felépítése
80
BMF-NIK-AAO Terminológia
Többszörös öröklés Öröklés egynél több ősosztállyal • Többszörös öröklés esetén egy osztálynak több őse van – Ez egy sokat vitatott lehetőség néhány OOP megvalósításban
• Előnyök: – Egyszerre több ősosztály képességei örökölhetők • Több származtatási szempont érvényesíthető egyszerre • Több ős tulajdonságait ötvöző „vegyes” osztálytípusok – Nagyobb rendszereknél gyakran felmerül az igény rá
• Hátrányok: – Igen nehéz megvalósítani • Komoly megvalósítási problémák: adatmezők öröklése, közös közvetett ősök (leszármazás több útvonalon) • Nagyobb rendszereknél szinte lehetetlen jól, következetesen megvalósítani – Bonyolult • Bonyolítja a programozási nyelv eszközeit, a programok tervezését
81
BMF-NIK-AAO Többszörös öröklés – Problémák Adatmezők öröklése, leszármazás több útvonalon
Speciális metódusok öröklődése Konstruktorok és destruktorok • A konstruktorok és destruktorok nem feltétlenül öröklődnek – Az objektumok létrehozásakor végre kell hajtani minden egyes ős valamelyik konstruktorát is • Ez szintén része a konstruktorok alapvető feladatkörének
• Hívási sorrend – A konstruktorok leszármazás szerinti sorrendben hajtódnak végre • Először az ősök adatait kell inicializálni, hiszen a leszármazottak ezeket akár már a saját konstruktorukban is fel kívánhatják használni – A destruktorok leszármazás szerinti fordított sorrendben hajtódnak végre • Először az utódok esetleges belső objektumait kell felszámolni, hiszen az utódok destruktora még hivatkozhat az ősök belső objektumaira
82
BMF-NIK-AAO Többalakúság
Többalakúság Definíció (ismétlés) • A különböző, egymásból származó objektumtípusok hasonló műveletei a konkrét objektumtól függően más-más konkrét megvalósítással rendelkezhetnek – Ugyanaz a művelet némileg eltérő lehet az őstípus és a leszármazott típus esetében – Az alapelv lehetőséget teremt rá, hogy azonos névvel hivatkozzunk az azonos célú, de a leszármazási hierarchia különböző szintjein más-más megvalósítást kívánó műveletekre
• Az egyes őstípusok leszármazottai mindenre alkalmasak, amire az adott őstípus alkalmas volt – Minden olyan helyzetben és funkcióban, ahol az őstípus szerepelhet, annak bármely leszármazottja is szerepelhet
Adatmezők többalakúsága • Az örökölt mezők a leszármazottakban is elérhetők – Az elérést az adott mező hozzáférési szintje szabályozza
• Öröklés során a mezők statikusan viselkednek – A mezők jellemzői (viselkedésük, típusuk, méretük, nevük) nem változtathatók meg öröklés útján – Minden leszármazott tartalmazza minden korábbi ős összes mezőjét, emellett tetszőlegesen bővítheti is a mezők körét
• A mezők ennél fogva (a mai OO programnyelvekben) nem képesek többalakú viselkedésre
83
BMF-NIK-AAO Nemvirtuális metódusok Műveletek statikus jellegű megvalósítása • A nemvirtuális metódusok a leszármazottakban is elérhetők – Az elérést az adott metódus hozzáférési szintje szabályozza
• Öröklés során a nemvirtuális metódusok viselkedése korlátozottan módosítható – A nemvirtuális metódusok a leszármazottakban újra deklarálhatók – Viselkedésük már a program lefordításakor eldől, attól függően, hogy az adott metódust milyen kontextusban használjuk – Az öröklésnek tehát itt minimális szerepe van • Lényegében egy azonos nevű metódust készítettünk a leszármazottban, aminek nincs kapcsolata az ős azonos nevű metódusával • Általában van lehetőség az ősosztály azonos nevű metódusának elérésére a leszármazottból is, így „manuálisan” korlátozott kapcsolat teremthető
• A nemvirtuális metódusok nem alkalmasak többalakúság megvalósítására
A statikus (fordítási idejű vagy „korai”) kötés • Nemvirtuális metódus hívásakor az adott objektum deklarált típusának megfelelő osztály adott nevű metódusa hívódik meg – Az objektumokat a programon belül tagváltozókban tároljuk – A tagváltozók deklarált típusa választja ki a hívandó nemvirtuális metódust – Ez az információ már fordításkor ismert, így a fordítóprogram előre elkészítheti a hívást megvalósító gépi kódot (statikus kötés)
• Előnyök: – Egyszerű megvalósítás; nincs futási idejű teljesítményveszteség
• Hátrányok: – Nem alkalmasak többalakúság megvalósítására
84
BMF-NIK-AAO Virtuális metódusok Műveletek dinamikus jellegű megvalósítása • A virtuális metódusok a leszármazottakban is elérhetők – Az elérést az adott metódus hozzáférési szintje szabályozza
• Öröklés során a virtuális metódusok viselkedése szabadon módosítható – A virtuális metódusok a leszármazottakban felülbírálhatók – Viselkedésük attól függően változik, hogy az adott műveletet végrehajtó konkrét objektum milyen típusú (mely osztály példánya) • A ténylegesen végrehajtandó művelet kiválasztása tehát futási időben történik
• A virtuális metódusok a többalakúság megvalósításának legfőbb eszközei – A virtuális metódus fogalma az objektumorientált programozási paradigma egyik legfontosabb eleme
A dinamikus (futási idejű vagy „késői”) kötés • Virtuális metódus hívásakor az adott objektum tényleges típusának megfelelő osztály adott nevű metódusa hívódik meg – A tagváltozók tartalma nemcsak a deklarált osztály lehet, hanem annak összes leszármazottja is – Csak a hívás pillanatában derül ki, hogy a tagváltozó ténylegesen mely osztály egy példányát tartalmazza – A metódushívást tehát futási időben kell előkészíteni
• Előnyök: – Többalakúság; rendkívüli rugalmasság
• Hátrányok: – Teljesítményveszteség; nagyobb tárigény; bonyolultabb megvalósítás
85
BMF-NIK-AAO Megvalósítás – A virtuálismetódus-tábla (VMT)
86
BMF-NIK-AAO Absztrakt osztályok Az öröklés kötelezővé tétele • Absztrakt osztály: legalább egy absztrakt metódust tartalmazó osztály – Absztrakt metódus: deklarált, de (általában) meg nem valósított virtuális metódus, amelyet az őt tartalmazó osztály valamennyi leszármazottja köteles un. „felülbírálással” megvalósítani
• Az absztrakt osztályok nem példányosíthatók – Céljuk az öröklés „kikényszerítése”, nem a tényleges megvalósítás
• Segítségükkel általános funkcionalitás írható elő az öröklési hierarchia felsőbb szintjein – Mivel az absztrakt metódusokat kötelező megvalósítani, ezek funkciójára a leszármazott osztályokat felhasználó egyéb osztályok biztosan számíthatnak
Lezárt osztályok Az öröklés (és ezzel a többalakúság) megakadályozása • A lezárt osztályok és lezárt metódusok lehetőséget adnak az öröklés eseti jellegű megakadályozására – Véglegesnek szánt osztályok, illetve metódusok esetén lehet célszerű alkalmazni ezt a megoldást • Csak osztályszintű tagokat tartalmazó osztályok • Biztonsági és gyakorlati megfontolások (hatékonyság, támogatás, jogvédelem)
• Lehetőséget adnak a teljesítmény bizonyos optimalizálására – Feltételezhető, hogy az osztály minden tárolt példánya pontosan megegyező adatszerkezettel és viselkedéssel rendelkezik • Mivel nincsenek leszármazottak, nincs többalakúság sem – A lezárt osztályok virtuális metódusai nemvirtuálissá alakíthatók
• Erős korlátozást jelentenek a fejlesztés során – Használatuk alapos megfontolást igényel
87
BMF-NIK-AAO Interfészek Adott funkcionalitás előírása öröklés helyett • Az interfészek olyan „üres osztályok”, amelyek nem tartalmaznak megvalósítást – Általában metódusokat tartalmaznak, de mezőket nem • Egyéb, metódusokhoz kötődő nyelvi konstrukciókat (tulajdonságok, események) szintén tartalmazhatnak
• Egy osztály akkor „támogat” egy interfészt, ha kötelezően vállalja, hogy megvalósítja a benne foglalt funkcionalitást – Egy osztály általában tetszőleges számú interfészt támogathat – Az interfész-fogalom un. „CAN-DO” kapcsolatot valósít meg
• Saját, különálló (az osztályhierarchiától független) öröklési hierarchiával rendelkeznek • Interfész típusú változók segítségével azonos viselkedésű, de más jellegű osztályok használhatók azonos kontextusban
Osztályok önként vállalt megvalósítási kötelezettségei
88
BMF-NIK-AAO Kódúrjafelhasználás (rövidített vázlat)
Kódújrafelhasználás Definíció (ismétlés) • A már megvalósított objektumtípusokat kész (bináris) formában más programokban is felhasználhatjuk – Jó tervezés és dokumentálás esetén az objektumok nyilvános adatai és műveletei elegendőek a későbbi felhasználáshoz • Szintaktikai bővítésekkel (pl. „tulajdonságok”, „események”) kényelmesebbé tehető a külső felhasználás – Az egyes objektumtípusokat egymásba ágyazva összetettebb típusokat hozhatunk létre – A kész, újrafelhasználható objektumtípusokat csoportokba fogva akár nagyobb „szoftver-építőelemeket” (komponenseket) is létrehozhatunk
• A fenti alapelvekre építve ez az alapelv jelenti az igazi áttörést a szoftvertechnológiában
Képviselők (delegáltak) Kapcsolódás külső (akár még nem létező) osztályokhoz • A képviselő (delegált) olyan speciális nyelvi elem, melynek segítségével egy osztályhoz külső osztályok utólag is kapcsolódni tudnak – A képviselő előírja az üzenetek formátumát • A külső osztály tetszőleges lehet, a képviselőn keresztüli kommunikáció egyetlen feltétele a formátum betartása
• Lehetővé teszik, hogy egy osztály metódusai külső osztályok metódusait ismeretlenül is meg tudják hívni – Üzenetküldési funkció külső osztályok részére – Ezzel lehetővé válik, hogy egy osztály képes legyen metódusokat meghívni olyan egyéb osztályokból, amelyek még nem is léteznek • Univerzális visszahívási funkció megvalósítása • Értesítési funkció megvalósítása
89
BMF-NIK-AAO Események Érdekelt osztályok értesítése történésekről • Az esemény olyan állapotváltozás, amelynek bekövetkezése más osztályok érdeklődésére tarthat számot • Szintén eseménynek nevezzük azt a nyelvi elemet, melynek segítségével megvalósul a külső osztályok értesítése – Az értesítési folyamat általános menete: • Az esemény iránt érdeklődő osztály „feliratkozik” az eseményt „közzétevő” osztálynál • A feliratkozás során az osztály meghatározott formátumú saját „eseménykezelőt” ad át a közzétevő osztálynak • A közzétevő osztály valamely metódusában „kiváltódik” az esemény • Erről az eseményről az osztály metódushívás (a megadott eseménykezelő hívása) útján értesíti a feliratkozott osztályt – Objektumorientált megvalósítása képviselővel történhet • Egy eseményre általában akár több osztály is feliratkozhat – Legnagyobb szerepe az eseményvezérelt programozásban és komponensek kialakításánál van
Komponensek Újrafelhasználható szoftver-építőelemek • A komponensek olyan osztályok vagy osztálygyűjtemények, amelyek készen (bináris formában), változtatás nélkül felhasználhatók és összekapcsolhatók – Önálló logikai (és általában fizikai) egységet képeznek – Felhasználásukhoz általában nincs szükség arra, hogy forráskódjuk rendelkezésre álljon – Az őket felhasználó osztályokkal metódusok (interfészek), tulajdonságok és események útján érintkeznek
• Segítségükkel nagyobb rendszerek készíthetők kezelhető keretek között – A rendszereket könnyebb kisebb elemekre bontva megvalósítani – Különböző nyelveken írt komponensek is együttműködhetnek
90
