Programozás | Programozás-elmélet » Galántai Aurél - Bevezetés a programozáselméletbe

Bevezetés a programozáselméletbe Galántai Aurél ME, 2003/2004, I. félév September 20, 2003 Contents 1 Alapfogalmak 1.1 Relációk 1.2 Sorozatok és projekciók 3 4 5 2 A programozás alapfogalmai 2.1 SpeciÞkáció 2.11 A változó fogalma 2.2 Elemi programok 2.3 Programkonstrukciók 2.4 A programkonstrukciók programfüggvényei 2.5 Levezetési szabályok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 9 14 15 17 20 24 3 Programszerkezetek analízise 3.1 Gráfelméleti alapfogalmak 3.2 Vezérlési gráfok, blokkdiagramok 3.3 A struktúrált programszerkezet 3.4 A struktúrálatlanság jellemzý oi . 3.5 Programok szerkezeti bonyolultsága . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

29 32 37 43 45 4 Adattípusok és adatszerkezetek 4.1 A tömb típus 4.11 Többdimenziós tömbök (mátrixok) 4.2 A rekord típus 4.3 Egyesítés típus 4.4 Halmaztípus 4.5 Megjegyzések a tömb és rekord típusokról 4.6 Sorozat típusok 4.61 Szekvenciális fájl 4.62 Verem 4.63 Sor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 50 51 52 53 54 55 56 57 60 61 1 . . . . . . . . . . 5 Programozási tételek 5.1 Elemi programozási tételek 5.11 Sorozatszámítás 5.12 Eldöntés 5.13 Kiválasztás 5.14 Lineáris keresés 5.15 Megszámolás 5.16 Maximumkiválasztás

5.2 Összetett programozási tételek 5.21 Másolás 5.22 Kiválogatás 5.23 Szétválogatás 5.3 Rendezések 5.31 Egyszerý u cserés rendezés: . 5.32 Minimumkiválasztásos rendezés 5.4 Keresések 5.41 Lineáris keresés rendezett sorozatban 5.42 Logaritmikus keresés rendezett sorozatban 5.5 Programozási tételek egymásra építése 5.51 Másolással összeépítés 5.6 A gyorsrendezés 5.7 Programhelyesség igazolása . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 63 63 65 66 67 67 68 69 69 70 70 71 72 72 72 73 73 74 74 76 80 6 Listák 82 6.1 Mûveletek listákban 84 6.2

Megjegyzések 89 7 Irodalom 91 2 1 Alapfogalmak Halmaz: ”Azonos tulajdonságú” elemek összessége. Halmaz jelölése: Latin ABC nagybetý ui (általában). Halmaz elemeinek jelölése: Latin kisbetý uk (általában). Halmaz megadása: a) elemeinek felsorolásával, pl. A = {1, 2, 3, 5, 7}; b) az elemeit jellemzý o közös tulajdonság megadásával : A = {x | P (x) igaz} , ahol P (x) egy x-týol függýo tulajdonság (állítás). Pl A = {x | 1 ≤ x ≤ 7, x prímszám} . Feltevés: Adott a objektum és A halmaz vonatkozásában el tudjuk dönteni, hogy a eleme-e az A halmaznak, vagy sem. Jelölés: a ∈ A ( a eleme A-nak), a∈ / A ( a nem eleme A-nak). Részhalmaz: B ⊆ A, ha ∀b ∈ B ⇒ b ∈ A. Halmazmý uveletek: A ∪ B = {x | x ∈ A, vagy x ∈ B} , A ∩ B = {x | x ∈ A és x ∈ B} . 1.1 DeÞníció: A1 , A2 , , An tetszý oleges halmazok direkt, vagy Descartes féle szorzata: A1 × A2 × . × An = {(a1 , , an ) | ai

∈ Ai , i = 1, n} Jelölés: ×ni=1 Ai . ¤ Megjegyzés: A direkt szorzat elemei rendezett elem n-esek. További jelölések: N - természetes számok halmaza N0 - nemnegatív egész számok halmaza (N0 = N ∪ {0}) Z - egész számok halmaza o n Q - racionális számok halmaza (Q = pq | p, q ∈ Z, q 6= 0 ) C - komplex számok halmaza (C = {a + bi | a, b ∈ R}, ”i = ∅ - üres halmaz [a.b] - az [a, b] ⊂ R intervallum egész számainak halmaza [a.b] := [a, b] ∩ Z ⊂ ⊆ |A| ∧ ∨ - valódi részhalmaz - részhalmaz - az A halmaz számossága (elemeinek száma) - logikai ”és” - logikai ”vagy” 3 √ −1”) 1.1 Relációk 1.2 DeÞníció: Legyenek A és B tetszý oleges halmazok. Tetszý oleges S ⊆ A × B részhalmazt (bináris) relációnak nevezünk. Az a ∈ A és b ∈ B elemek S relációban állnak egymással (jelölés aSb) akkor és csak akkor, ha (a, b) ∈ S. ¤ Megjegyzés: A deÞníció rövidebben: aSb ⇐⇒ (a, b) ∈ S. 1.3

DeÞníció: Reláció értelmezési tartománya: DS = {a ∈ A | ∃b ∈ B : (a, b) ∈ S} . 1.4 DeÞníció: Reláció értékkészlete: RS = {b ∈ B | ∃a ∈ A : (a, b) ∈ S} . 1.5 DeÞníció: Reláció értéke (metszete) egy adott helyen: S (a) = {b ∈ B | (a, b) ∈ S} . 1.6 DeÞníció: Az S relációt determinisztikus, vagy parciális függvénynek nevezzük, ha |S (a)| ≤ 1 (∀a ∈ A) . Megjegyzés: Determinisztikus reláció esetén S (a) vagy üres, vagy egyelemý u halmaz. 1.7 DeÞníció: Az S relációt függvénynek nevezzük, ha |S (a)| = 1 (∀a ∈ DS ). 1.8 DeÞníció: A H ⊆ A halmaz S reláció szerinti képe (metszete): S (H) = {b ∈ B | ∃a ∈ H : (a, b) ∈ S} . 1.1 Feladat: Igazoljuk, hogy S (H) = ∪a∈H S (a) . 1.9 DeÞníció: Az S (−1) reláció az S ⊆ A × B reláció inverze, ha S (−1) = {(b, a) ∈ B × A | (a, b) ∈ S} . 1.10 DeÞníció: A H ⊆ B halmaz S reláció szerinti inverz képe: S (−1) (H) = {a ∈ A | S (a) ∩ H

6= ∅} 1.2 Feladat: Igazoljuk, hogy az inverz kép az inverz reláció szerinti kép! 1.11 DeÞníció: Az R ⊆ A × C reláció a P ⊆ A × B és Q ⊆ B × C relációk kompozíciója (szorzata) (jelölés: R = Q ° P ), ha R = {(a, c) ∈ A × C | ∃b ∈ B : (a, b) ∈ P ∧ (b, c) ∈ Q} . 4 1.2 Sorozatok és projekciók 1.12 DeÞníció: Legyen A ( A 6= ∅) tetszý oleges halmaz. Ekkor α = hα1 , α2 , . , αn i ( αi ∈ A) egy A-beli véges sorozat. ¤ 1.13 DeÞníció: Az α = hα1 , α2 , , αn i véges sorozat hossza |α|¤ Megjegyzés: Tulajdonképpen |α| = n, illetve a sorozat, mint halmaz számossága. 1.14 DeÞníció: Az A halmazbeli véges sorozatok halmaza A∗ ¤ Megjegyzés: A∗ az hα1 i, hα1 , α2 i, hα1 , α2 , α3 i, . sorozatok összessége 1.15 DeÞníció: A-beli végtelen sorozat: α = hα1 , α2 , . , αk , i , ahol αi ∈ A ( ∀i). 1.16 DeÞníció: A-beli végtelen sorozatok halmaza A∞ ¤ 1.17 DeÞníció: Az A-beli

véges és végtelen sorozatok halmaza A∗∗ ¤ Megjegyzés: A∗∗ = A∗ ∪ A∞ 1.18 DeÞníció: α ∈ A∗∗ sorozat értelmezési tartománya Dα , ahol ½ [1. |α|] , ha α ∈ A∗ Dα = N, ha α ∈ A∞ Megjegyzés: A sorozat egy N A tipusú függvény értékkészlete. 1.19 DeÞníció: Az α1 , α2¡, , αn−1 ∈ A∗ és α¢ n ∈ A∗∗ sorozatok egymásután írása, konkatenációja kon α1®, α2 , . , αn−1 , αn ¤ ­ Ha αi = αi1 , αi2 , . , αiki (1 ≤ i ≤ n − 1) és αn = hαn1 , αn2 , i, akkor a konkatenáció alakja: n n hα11 , . , α1k1 , α21 , , α2k2 , , αn−1 , . , αn−1 1 kn−1 , α1 , α2 , . i } | {z } | {z } | {z } | {z n α1 α2 αn−1 α Példa: A = {a, . , z}, α1 = ho, k, o, si, α2 = hm, i, n, t, a, t, o, ri, α3 = hd, a, ii, α4 = hk, o, si. ¡ ¢ kon α1 , α2 , α3 , α4 = ho, k, o, s, m, i, n, t, a, t, o, r, d, a, i, k, o, si 1.20 DeÞníció: α ∈ A∗∗ sorozat redukáltja az a

sorozat, amelyet úgy kapunk, hogy az α sorozat minden azonos elembý ol álló véges részsorozatát a részsorozat egyetlen elemével helyettesítjük. Jelölése: red (α) Példa: A = {a, . , z}, α = he, n, n, i, k, e, l, l, e, n, ei 5 red (α) = he, n, i, k, e, l, e, n, ei . 1.21 DeÞníció: Utolsó elem függvény τ : A∗ A, ahol τ (α) = α|α| ( α ∈ A∗ ) ¤ Megjegyzés: τ (α) = αn , ha α = hα1 , α2 , . , αn i Az utolsó elem függvényt csak véges sorozatokra értelmezzük! Példa: A = {a, . , z}, α = hu, b, u, l, k, u, t, y, u, li, |α| = 10, α10 = l, τ (α) = l 1.22 DeÞníció: Legyen m, n ∈ N , m ≤ n, 1 ≤ i1 < i2 < i3 < < im ≤ n, A = ×ni=1 Ai és B = ×m j=1 Aij . A prB : A B függvényt projekciónak nevezzük ( A ortogonális projekciója B-re), ha prB (a) = (ai1 , ai2 , . , aim ) (∀a = (a1 , a2 , . , an ) ∈ A) Példa: A1 = A2 = R, vetítés x, vagy y tengelyre. A deÞnícióban szereplýo B-t az A

alterének nevezzük. Ha m < n, akkor valódi altér. Csak m 6= 0 lehetséges ⇒ ∅ nem altere egyetlen direkt szorzatnak 1.23 DeÞníció (Projekció kiterjesztése ”terek” direkt szorzataira): Legyen A és B mint elý obb, (a1 , a2 ) ∈ A × A. Ekkor prB ((a1 , a2 )) = (prB (a1 ) , prB (a2 )) ∈ B × B. 1.24 DeÞníció (Projekció kiterjesztése ”sorozatterekre”): Legyen A és B mint elý obb, α = hα1 , α2 , . , αi , i ∈ A∗∗ Ekkor prB (α) = hprB (α1 ) , prB (α2 ) , . , prB (αi ) , i ∈ B ∗∗ Megjegyzés: Más formában ugyanez: prB (α) = β ∈ B ∗∗ , ahol β i = prB (αi ) 2 (∀i ∈ Dβ = Dα ) . A programozás alapfogalmai Öt alapvetýo fogalmat deÞniálunk: 1. Állapottér (a számítógép memória modellje) 2. Feladat (a programozási feladat modellje) 3. Program (a programfutás modellje) 4. Programfüggvény (a programfutás eredménye) 5. Feladat megoldása (a feladat és a program viszonyának modellezése) 2.1

DeÞníció: Legyenek A1 , A2 , , An tetszý oleges véges, vagy megszámlálhatóan végtelen halmazok. Az A = A1 × A2 × × An halmazt állapottérnek nevezzük, az Ai halmazokat pedig tipusértékhalmazoknak. ¤ Megjegyzés: 1. Az állapottér a számítógép memória modellje Az állapottér egy eleme a memória egy adott állapotának felel meg. 6 2. Az állapottér Ai komponensei az egyes jellemzý ok lehetséges értékeinek halmazai. Az állapottér komponensei között ugyanaz a (tipusérték) halmaz többször is szerepelhet. 3. A tipusértékhalmaz elnevezés azt jelzi, hogy ezek a halmazok bizonyos közös tulajdonságú (azonos tipusú) elemekbý ol állnak. 2.2 DeÞníció: Legyen A állapottér Az F ⊆ A × A relációt (programozási) feladatnak nevezzük. ¤ Megjegyzés: A feladat egy ”leképezés” az állapottéren: az állapottér minden DF -beli pontjára megmondjuk, hogy hova kell belý ole eljutni. Az állapottér megadása nem egyszerý u.

Példa: P pont koordinátái R2 -ben, polárkoordináta rendszerben. Egy program futásakor a számítógép memóriájának tartalma dinamikusan változik. Egy Þlm tkp fényképek sorozata Ehhez hasonlóan a program futását az állapotok, vagyis állapottérbeli sorozatok megadásával modellezzük. 2.3 DeÞníció: Az S ⊆ A × A∗∗ relációt programnak nevezzük, ha 1. DS = A, 2. ∀a ∈ A : ∀α ∈ S (a) : α1 = a, 3. ∀α ∈ RS : α = red (α) A deÞníció jelentése a következýo: 1. triviális; 2. A program futását jellemzýo α ∈ A∗∗ sorozat mindig abból az a ∈ A pontból indul el, amelyhez hozzárendeltük; 3. RS = {α ∈ A∗∗ | ∃a ∈ A : (a, α) ∈ S}, bármelyik α ∈ RS olyan sorozat, amelyben az állapotok nem ismétlýodnek. Összefoglalva: A program egy reláció, amelynek értékkészlete az állapottéren értelmezett sorozatokból áll. Ezek a sorozatok egy-egy konkrét program végrehajtást jellemeznek. Kérdés: Az F ⊆ A × A

feladat és az S ⊆ A × A∗∗ program viszonya? Az F feladat reláció az a ∈ A ”kezdeti memóriaállapothoz” egy (vagy több) olyan b ∈ A ”végsýo memóriaállapotot” (tkp. megoldást) rendel, amelyre igaz, hogy (a, b) ∈ F . Az S program reláció ugyanehhez az a kezdeti állapothoz egy (vagy több) α ∈ A∗∗ sorozatot rendel. Ha ez a sorozat véges (α ∈ A∗ ), akkor a végsýo állapot, amely a sorozat utolsó eleme, a programfutás eredménye. Ennek a végsýo állapotnak a feladat b ”megoldásához” való viszonyát kell jellemezni. A közbülsýo memóriaállapotok ebbýol a szempontból nem érdekesek, ill. ezeket nem vizsgáljuk. A viszony jellemzése két lépésben történik. 2.4 DeÞníció: A p (S) ⊆ A × A relációt az S ⊆ A × A∗∗ program programfüggvényének nevezzük, ha 1. Dp(S) = {a ∈ A | S (a) ⊆ A∗ }, 2. p (S) (a) = {b ∈ A | ∃α ∈ S (a) : τ (α) = b} A deÞníció jelentése a következýo: 1. Csak olyan

pontokban vizsgáljuk azt, hogy hova jut el a program, amelyekben a futás véges (a program nem száll el); 7 2. Tetszýoleges b ∈ A ponthoz, amelyre (a, b) ∈ p (S), létezik véges, a program által elýoállított α ∈ A∗ sorozat ((a, α) ∈ S), amelynek utolsó eleme (utolsó programállapota) éppen b. A programfüggvény a program futásának eredményét jellemzi. A függvény jelzýo nem igazán korrekt, ui. nem feltétlenül függvény, de a hagyomány ezt követeli. Megjegyzés: p (S) (a) = {τ (α) | α ∈ S (a)} = τ (S (a)) = (τ ° S) (a) . 2.5 DeÞníció: Az S ⊆ A × A∗∗ program megoldja az F ⊆ A × A feladatot, ha 1. DF ⊆ Dp(S) , 2. ∀a ∈ DF : p (S) (a) ⊆ F (a) A deÞníció jelentése a következýo: 1. A DF = {a ∈ A | ∃b ∈ A : (a, b) ∈ F } ⊆ Dp(S) = {a ∈ A | S (a) ⊆ A∗ } feltétel miatt az állapottér azon pontjaihoz, ahol a feladat értelmezve van, a program csak véges sorozatokat rendelhet; 2. A p (S) (a) = {b ∈ A |

∃α ∈ S (a) : τ (α) = b} ⊆ F (a) = {c ∈ A | (a, c) ∈ F } feltétel azt fejezi ki, hogy a sorozatok végpontjait a feladat hozzárendeli a kezdýoponthoz. Tehát a program által generált ”véges” sorozatok végpontjai a feladat megoldásai. Ezzel a program és a feladat viszonyát jellemeztük. ¡ ¢2 2.1 Példa: Legyen A = Z és az x y (x) = x2 − 1 +1 leképezés kiszámítása a ”feladat”. Ekkor o n ¢2 ¡ F = (x, y) | y = x2 − 1 + 1 ⊂ A × A, DF = A és ∀a ∈ A esetén F (a) = ”programot”: n¡ o ¢2 a2 − 1 + 1 . Tekintsük a következýo ¢2 f1 f2 ¡ x x2 − 1 x2 − 1 + 1. A fenti formába átírva ez a következýoképpen néz ki: Eo n D ¡ ¢2 ⊂ A × A∗ ⊂ A × A∗∗ . S = (x, α) | α = x, x2 − 1, x2 − 1 + 1 Igazoljuk,nD hogy S program. Világos, Eo hogy DS = A (1. tulajdonság) és ∀α ∈ ¡ 2 ¢2 2 S (a) = a, a − 1, a − 1 + 1 esetén α1 = a (2. tulajdonság) A 3 tulajdonság belátásához vegyük észre, hogy D E

¡ ¢2 α ∈ RS ⇔ ∃a ∈ A : α = a, a2 − 1, a2 − 1 + 1 . 8 6 αi+1 (∀i). Esetünkben Egy α sorozat akkor és csak akkor redukált, ha αi = √ 1± 5 2 ∈ /A a=a −1 ⇔a= 2 és s √ ¡ ¢ 1 ± −3 2 −1∈ / A. a2 − 1 = a2 − 1 + 1 ⇔ a = ± 2 Tehát az α ∈ RS sorozatok redukáltak. Ezzel a 3 tulajdonságot is beláttuk Tehát S program. A programfüggvény deÞníciója (Miért?): p (S) = {(a, b) | S (a) ⊂ A∗ , ∃α ∈ S (a) : τ (α) = b} . nD Eo ¡ ¢2 Minthogy ∀a ∈ DF = DS = A esetén S (a) = a, a2 − 1, a2 − 1 + 1 , ¢2 ¡ azért α ∈ S n (a) esetén τ (α) = a2 − 1 + 1. Tehát Dp(S) = A (Miért?) és o ¢2 ¡ 2 p (S) (a) = a − 1 + 1 . Igazoljuk, hogy az S program megoldja az F feladatot. Világos, hogy DF = A ⊆ Dp(S) = A (1 tulajdonság) A fentiek alapján ugyancsak világos, hogy n¡ o n¡ o ¢2 ¢2 ∀a ∈ DF : p (S) (a) = a2 − 1 + 1 ⊆ F (a) = a2 − 1 + 1 . n D ¡ Eo ¢2 Kérdés: Miért nem program az S 0 = (x, α) |

α = x, x2 − 1 + 1 ⊆ A× A∗∗ reláció? 2.1 SpeciÞkáció A fejezetben programok helyességével, ill. részleges (parciális) helyességével foglalkozunk. Ehhez szükségünk van a következýo logikai fogalmakra és eredményekre Jelölés: (Logikai értékek halmaza) L = {igaz, hamis} = {i, h}. 3.1 DeÞníció: A halmazon értelmezett (logikai) állítás: Q : A L függvény 3.2 DeÞníció: Legyen Q az A halmazon értelmezett állítás A Q állítás igazsághalmaza [Q] = {a ∈ A | Q (a) = igaz} . 3.3 DeÞníció: Legyenek Q1 és Q2 az A halmazon értelmezett állítások A Q1 és Q2 állítások ekvivalensek, ha [Q1 ] = [Q2 ]. Jelölés: Q1 ≡ Q2 3.4 DeÞníció: Legyen R ⊆ A tetszý oleges részhalmaz. P (R) olyan állítást jelöl, amelyre [P (R)] = R. Következmény: Tetszý oleges Q állításra igaz, hogy Q ≡ P ([Q]). 3.5 DeÞníció: Legyenek P és Q az A halmazon értelmezett állítások A következý o logikai mý uveleteket deÞniáljuk, un.

igazságtáblával: 9 1. P ∧ Q (konjunkció/és/logikai szorzás): P Q P ∧Q i i i i h h h i h h h h A P ∧ Q állítás igaz ⇐⇒ P és Q is igaz; 2. P ∨ Q (diszjunkció/vagy/logikai összeadás): P Q P ∨Q i i i i h i h i i h h h A P ∨ Q állítás igaz ⇐⇒ P és Q közül legalább az egyik igaz; 3. qQ (negáció/ tagadás): Q qQ i h h i A qQ állítás igaz ⇐⇒ Q hamis, az állítás hamis⇐⇒ Q igaz; 4. P ⇒ Q (implikáció/ következés/ha P , akkor Q): P Q P ⇒Q i i i i h h h i i h h i A P ⇒ Q állítás hamis⇐⇒ P igaz és Q hamis. 3.1 Állítás: Legyenek P és Q az A halmazon értelmezett állítások Ekkor (i) [P ∧ Q] = [P ] ∩ [Q]; (ii) [P ∨ Q] = [P ] ∪ [Q]; (iii) [qQ] = A [Q]; (iv) Ha P ⇒ Q, akkor [P ] ⊆ [Q]. Egy S program akkor és csak akkor oldja meg az F feladatot, ha DF ⊆ Dp(S) ∧ {a ∈ DF ⇒ p (S) (a) ⊆ F (a)} . A megoldás deÞníciójának közvetlen ellenýorzése helyett elégséges feltételt

adunk meg a program helyességének ellenýorzésére. Ezt az eredményt speciÞkáció tételnek nevezzük A tétel megfogalmazásához két fogalmat vezetünk be: 1. Leggyengébb elýofeltétel 2. Paramétertér Legyen R : A L egy olyan feltétel (utófeltétel), amelyet az S program eredményétýol megkövetelünk, azaz teljesülése esetén az eredményt helyesnek tekintjük. Ehhez keresünk egy olyan Q : A L elý ofeltételt, amelyet a program kezdýoállapotára rovunk ki és amelynek teljesülése esetén a program terminál és végállapotára (eredményére) fennáll az R feltétel: [Q] ⊆ Dp(S) ∧ {a ∈ [Q] ⇒ p (S) (a) ⊆ [R]} . 10 A legbýovebb igazsághalmazzal rendelkezýo elýofeltételt leggyengébb elýofeltételnek nevezzük. 3.6 DeÞníció: Legyen S ⊆ A×A∗∗ program, R az A állapottéren értelmezett állítás Az S program R utófeltételhez tartozó leggyengébb elý ofeltétele az lf (S, R) állítás, amelyre ª [lf (S, R)] = a ∈ Dp(S) | p

(S) (a) ⊆ [R] . Megjegyzés: Egy feladat megoldásakor olyan programot keresünk, amelyik bizonyos feltételeket kielégítý o pontokban terminál. Ha a számunkra kedvezý o végállapotokra megadjuk a program leggyengébb elý ofeltételét, akkor a programfüggvény nélkül tudjuk jellemezni a program mý uködését. Az R utófeltétel megválasztásától függý oen [lf (S, R)] és DF különbözhet. Ezért a program helyességének ez a jellemzése csak részleges (parciális). 3.1 Példa: Legyen A = N0 , F = {(x, y) | y = 2x + 1} ⊆ A×A, S = {(a, α) | α = ha, 2a + 1i} Ekkor p (S) (a) = {2a + 1} és Dp(S) = A. Legyen az utófeltétel R : y = 13, ahol y a program eredményét jelöli. Az R utófeltétel igazsághalmaza: [R] = {13} A p (S) (a) = {2a + 1} ⊆ [R] = {13} feltételbýol a = 6 adódik. Tehát [lf (S, R)] = {6} és lf (S, R) : a = 6. Ha az S programot az ”y := 2a + 1” formában adjuk meg, akkor az eredményt a következýoképpen is megkaphatjuk: lf (S, R)

= lf (”y := 2a + 1”, y = 13) = {2a + 1 = 13} = {a = 6} . Kérdés: Program lesz-e S, ha N0 helyett Z-t választunk A gyanánt? 3.2 Példa (A 21 Példa folytatása): Legyen A = Z, n o ¡ ¢2 F = (x, y) | y = x2 − 1 + 1 n D Eo ¡ ¢2 és S = (x, α) | α = x, x2 − 1, x2 − 1 + 1 . Ekkor p (S) (a) = n¡ o ¢2 a2 − 1 + 1 és Dp(S) = A. Legyen az S program utófeltétele R : y ≥ 1 ∧ y ≤ 17, ahol y a program eredménye. Az R utófeltétel igazsághalmaza: [R] = {1, 2, , 17} = [1.17] A n¡ o ¢2 p (S) (a) = a2 − 1 + 1 ⊆ [R] = [1.17] feltételbýol −2 ≤ a ≤ 2 adódik. Tehát [lf (S, R)] = [−22], amelyhez választhatjuk az lf (S, R) : −2 ≤ a ≤ 2 állítást, mint leggyengébb elýofeltételt. 3.1 Feladat: Adjunk meg más elýofeltételt is! 3.3 Példa (A 32 Példa n¡ folytatása): o Legyen az S program új utófeltétele: R : ¢2 2 y = 18 ∨ y = 19. Az a − 1 + 1 ⊆ [R] = {18, 19} tartalmazási feltételnek egész a-ra nincs megoldása. Tehát csak

[lf (S, R)] = ∅ és lf (S, R) ≡ h lehetséges Ha viszont az R : y ∈ N feltételt választjuk, akkor [R] = N , [lf (S, R)] = Z = A és lf (S, R) ≡ i. 11 3.1 Tétel (Dijkstra): Legyen S ⊆ A × A∗∗ program, R és Q az A halmazon értelmezett állítások, és HAMIS az azonosan hamis állítás. Ekkor 1. lf (S, HAM IS) = HAMIS, 2. Ha Q ⇒ R, akkor lf (S, Q) ⇒ lf (S, R), 3. lf (S, Q) ∧ lf (S, R) = lf (S, Q ∧ R), 4. lf (S, Q) ∨ lf (S, R) ⇒ lf (S, Q ∨ R) Bizonyítás: 1. Indirekt: Tegyük fel, hogy ∃a ∈ [lf (S, HAM IS)] Ekkor deÞníció szerint a ∈ Dp(S) és p (S) (a) ⊆ [HAM IS] = ∅. Ez ellentmondás 2. Tegyük fel, hogy a ∈ [lf (S, Q)] Ekkor p (S) (a) ⊆ [Q] Minthogy [Q] ⊆ [R], azért p (S) (a) ⊆ [R] és a ∈ [lf (S, R)]. 3. ª [lf (S, Q)] = a ∈ Dp(S) | p (S) (a) ⊆ [Q] ª [lf (S, R)] = a ∈ Dp(S) | p (S) (a) ⊆ [R] miatt ª a ∈ Dp(S) | p (S) (a) ⊆ [Q] ∧ p (S) (a) ⊆ [R] ª = a ∈ Dp(S) | p (S) (a) ⊆ [Q ∧ R] = [lf (S, Q

∧ R)] . [lf (S, Q)] ∩ [lf (S, R)] = 4. Legyen a ∈ [lf (S, Q) ∨ lf (S, R)] Ekkor a ∈ [lf (S, Q)], vagy a ∈ [lf (S, R)]. Felhasználjuk, hogy Q ⇒ Q ∨ R és R ⇒ Q ∨ R Ha a ∈ [lf (S, Q)], akkor a 2. állítás alapján a ∈ [lf (S, Q ∨ R)] Ha a ∈ [lf (S, R)], akkor a 2 állítás alapján ismét a ∈ [lf (S, Q ∨ R)]. QED Megjegyzés: 1. Az 1 állítás a ”csoda kizárása” 2. A 2 állítást monotonitási tulajdonságnak nevezzük 3.7 DeÞníció: Legyen F ⊆ A × A feladat A B halmazt a feladat paraméterterének nevezzük, ha van olyan F1 ⊆ A × B és F2 ⊆ B × A reláció, hogy F = F2 ° F1 . ¤ Megjegyzés: 1. A paramétertér általában az állapottér egy olyan altere, amelytý ol a feladat függ. 2. Triviális paraméterteret mindig tudunk választani: F1 = idA = {(a, a) | a ∈ A} , B = A, F2 = F. 3.2 Tétel (SpeciÞkáció tétele): Legyen F ⊆ A×A feladat, B az F egy paramétertere, F1 ⊆ A × B, F2 ⊆ B × A, F = F2 ° F1 Legyen

b ∈ B és legyenek Qb és Rb olyan állítások, amelyek igazsághalmazai (−1) [Qb ] = {a ∈ A | (a, b) ∈ F1 } = F1 (b) , [Rb ] = {a ∈ A | (b, a) ∈ F2 } = F2 (b) . 12 Ha ∀b ∈ B esetén Qb ⇒ lf (S, Rb ), akkor az S program megoldja az F feladatot. Bizonyítás: Két tulajdonságot kell belátnunk: 1. DF ⊆ Dp(S) és 2 ∀a ∈ DF : p (S) (a) ⊆ F (a). Legyen a ∈ DF tetszýoleges Ekkor ∃b ∈ B : a ∈ [Q ª b ]. A tétel feltevése miatt [Qb ] ⊆ [lf (S, Rb )] = a ∈ Dp(S) | p (S) (a) ⊆ [Rb ] ⊆ Dp(S) . Tehát DF ⊆ Dp(S) . A b ∈ F1 (a) tartalmazási feltétel miatt F2 (b) ⊆ F2 (F1 (a)) és p (S) (a) ⊆ [Rb ] = F2 (b) ⊆ F2 (F1 (a)) = F (a) . Q.ED Megjegyzés: A tétel csak elégséges és nem megfordítható. A tétel jelentý osége sokrétý u: (i) Adott S program esetén csak a Qb ⇒ lf (S, Rb ) ( ∀b ∈ B) tulajdonságot kell belátnunk a program helyességéhez; (ii) Adott Qb és Rb esetén olyan S programot kell keresnünk, amelyik

kielégíti a Qb ⇒ lf (S, Rb ) ( ∀b ∈ B) feltételt; (iii) Az F feladat szerencsés paraméterezése segítheti a program helyességének ellený orzését, vagy akár a megfelelý o program keresését. 3.4 Példa (A 21 Példa módosítása): Legyen A = Z, n³ ¡ ´ o ¢2 F = x, x2 + 1 − 1 | x ∈ A és Eo n D ¡ ¢2 ⊆ A × A∗∗ . S = (x, α) | α = x, x2 + 1, x2 + 1 − 1 A 2.1 Példához hasonlóan beláthatjuk, hogy S program és megoldja az F feladatot Alkalmazzuk tételét! Legyen B = N , F1 = ¢ ª ¢ ª azonban ¡a speciÞkáció ¡ x, x2 + 1 | x ∈ A és F2 = u, u2 − 1 | u ∈ N . Ekkor F = F2 ° F1 és B paramétertér. Legyen b ∈ N = B rögzített DeÞníció szerint kapjuk, hogy ª [Qb ] = {a ∈ Z | (a, b) ∈ F1 } = a ∈ Z | a2 + 1 = b és Qb : a2 + 1 = b. Hasonlóképpen adódik, hogy ª ª [Rb ] = {a ∈ Z | (b, a) ∈ F2 } = a ∈ Z | a = b2 − 1 = b2 − 1 2 és n¡ Rb : ¢a2 = bo − 1. Ugyancsak deÞníció szerint kapjuk, hogy p (S) (a) =

2 a +1 −1 , o n n¡ ªo ¢2 ª [lf (S, Rb )] = a ∈ A | a2 + 1 − 1 ⊆ b2 − 1 = a ∈ A | a2 + 1 = b és lf (S, Rb ) : a2 + 1 = b. Ha b ∈ B olyan, hogy Qb = i, akkor a2 + 1 = b és lf (S, Rb ) = i. Ha Qb = h, akkor a2 + 1 6= b és lf (S, Rb ) = h Tehát minden b ∈ B esetén Qb ⇒ lf (S, Rb ) (tkp. Qb ≡ lf (S, Rb )) A speciÞkáció tétele miatt az S program megoldja az F feladatot (azaz S helyes program). 13 2.11 A változó fogalma A változók használata egyszerý usítéseket tesz lehetýové. 3.8 DeÞníció: Legyen A = A1 × A2 × × An állapottér A prAi : A Ai projekciós függvényeket változóknak nevezzük: prAi (a) = ai (∀a = (a1 , a2 , . , an ) ∈ A) A változók jelölése: vi = prAi . Megjegyzés: A változókra fennáll, hogy Dvi = A = DprAi , Rvi = Ai = RprAi . Az Rvi = Ai összefüggés miatt beszélünk a változó tipusáról, amely azonos Ai típusával. Legyen B = Ai1 × . × Aim Ekkor a prB : A B projekciót a prB =

(vi1 , . , vim ), azaz a prB (a) = (vi1 (a) , , vim (a)) elýoírással adhatjuk meg Tetszýoleges f ° prB = f ° (vi1 , . , vim ) alakú összetett függvényt, ha ez nem okoz félreértést, az f (vi1 , . , vim ) alakban is írunk A speciÞkáció tételében szerepelnek a Qb , Rb : A L állítások, illetve ezek [Qb ] = {a ∈ A | (a, b) ∈ F1 } és [Rb ] = {a ∈ A | (b, a) ∈ F2 } igazsághalmazai. Tegyük fel, hogy Fe1 : A × B L és Fe2 : A × B L olyan predikátumok, amelyekre Qb ≡ Fe1 (a, b) és Rb ≡ Fe2 (a, b). Legyen vi : A Ai az A állapottér i-edik változója (i = 1, , n), pj : B Bj a B = B1 × × Bm paramétertér j-edik változója (j = 1, . , m) Ekkor a = (v1 (a) , , vn (a)) és b = (p1 (b) , . , pm (b)) miatt írhatjuk, hogy és Qb = Qp1 ,. ,pm = Fe1 (a, b) = Fe1 (v1 , , vn , p1 , , pm ) Rb = Rp1 ,. ,pm = Fe2 (a, b) = Fe2 (v1 , , vn , p1 , , pm ) 3.5 Példa: Legyen A = Z × Z, x, y : A Z változó Az R = (x > 0

∧ y > 0) jelölés az (x (a) > 0 ∧ y (a) > 0 ∧ a ∈ A) állítást jelöli és [R] = {(a1 , a2 ) ∈ A | a1 > 0 ∧ a2 > 0} . Ha π predikátum (A L tipusú logikai függvény), akkor a π = (x > y) azt jelenti, hogy ½ igaz, ha x (a) > y (a) π (a) = hamis, ha x (a) ≤ y (a) . 3.6 Példa: Legyen a feladat két egész szám maximumának meghatározása Legyen az állapottér A = Z × Z × Z, az állapottér változói pedig legyenek 14 x, y, z. A feladat paramétertere legyen B = Z × Z a paramétertér változói pedig legyenek x0 , y 0 , F1 = {((x, y, z) , (x0 , y 0 )) | x = x0 ∧ y = y 0 } , F2 = {((x0 , y 0 ) , (x, y, z)) | z = max {x0 , y 0 }} , Qb = Qx0 ,y0 = (x = x0 ∧ y = y 0 ) , Rb = Rx0 ,y0 = (z ≥ x0 ∧ z ≥ y0 ∧ (z = x0 ∨ z = y 0 )) . Tehát olyan S programot kell találnunk, amelyikre ∀b ∈ B esetén fennáll x (a) = x0 (b) ∧ y (a) = y0 (b) ⇒ = lf (S, (z (a) ≥ x0 (b) ∧ z (a) ≥ y 0 (b) ∧ (z (a) = x0 (b) ∨ z (a) =

y 0 (b)))) . Ezt rövidebben is írhatjuk: x = x0 ∧ y = y 0 ⇒ lf (S, (z ≥ x0 ∧ z ≥ y0 ∧ (z = x0 ∨ z = y 0 ))) . 3.2 Feladat: Kétféleképpen is igazoljuk, hogy az ½ ¿ µ ¶À¾ x + y |x − y| + S = ((x, y, z) , α) | α = (x, y, z) , (x + 1, y, z) , x, y, 2 2 program megoldja a 3.6 Példa feladatát! Miért nem program S, ha elhagyjuk az α sorozat második tagját? 2.2 Elemi programok 4.1 DeÞníció: Az S ⊆ A × A∗∗ program elemi, ha ∀a ∈ A : S (a) ⊆ {hai , ha, a, a, . i , ha, bi | b 6= a} A deÞníció alapján könnyen látható, hogy egy elemi program tényleg program. Speciális elemi programok a kövekezýok: 4.2 DeÞníció: Üres, vagy skip program: ∀a ∈ A : SKIP (a) = {hai} . A SKIP program nem csinál semmit. 4.3 DeÞníció: A törlý odés, vagy abort program: ∀a ∈ A : ABORT (a) = {ha, a, a, . i} Az ABORT program soha nem terminál (soha nem fejezýodik be). 15 4.1 Feladat: Mely feladatok megoldásai lehetnek a SKIP és

ABORT programok? 4.4 DeÞníció: Legyen F ⊆ A × A Az S programot általános értékadásnak nevezzük, ha S = {(a, red (ha, bi)) | a, b ∈ A ∧ a ∈ DF ∧ b ∈ F (a)} ∪ {(a, ha, a, a, . i) | a ∈ A ∧ a ∈ / DF } . 4.5 DeÞníció: Legyen S ⊆ A × A∗∗ általános értékadás program a) Ha DF = A, akkor az S programot értékkiválasztásnak nevezzük és a :∈ F (a)-val jelöljük. b) Ha az F reláció függvény, akkor az S programot értékadásnak nevezzük és a := F (a)-val jelöljük. c) Ha DF ⊂ A, akkor S parciális értékkiválasztás. d) Ha DF ⊂ A és F determinisztikus ( F parciális függvény), akkor S parciális értékadás. 4.6 DeÞníció: Identitásfüggvény: idA = {(a, a) | a ∈ A} ⊆ A × A. 4.1 Tétel (elemi programok programfüggvénye): 1. p (SKIP ) = idA , 2. p (ABORT ) = ∅, 3. p (a := F (a)) = F , 4. p (a :∈ F (a)) = F Bizonyítás: Házi feladat. A következýokben elemi programok leggyengébb elýofeltételeit

határozzuk meg, Legyen R egy tetszýoleges utófeltétel. Ekkor p (SKIP ) (a) = {a} miatt [lf (SKIP, R)] = {a ∈ A | p (SKIP ) (a) ⊆ [R]} = {a ∈ A | {a} ⊆ [R]} = [R] és lf (SKIP, R) = R. Hasonlóan p (ABORT ) (a) = ∅ miatt lf (ABORT, R) = hamis. Az általános értékadás leggyengébb elýofeltétele négy esetben: 1. F : A A függvény, DF = A [lf (a := F (a) , R)] = {a ∈ A | F (a) ⊆ [R]} = F (−1) ([R]) . 2. F : A A függvény, DF ⊂ A [lf (a := F (a) , R)] = {a ∈ A | F (a) ⊆ [R]} ∩ DF = F (−1) ([R]) ∩ DF . 16 3. F ⊆ A × A, DF = A, F nem determinisztikus [lf (a :∈ F (a) , R)] = {a ∈ A | F (a) ⊆ [R]} = F (−1) ([R]) . 4. F ⊆ A × A, DF ⊂ A, F nem determinisztikus [lf (a :∈ F (a) , R)] = {a ∈ A | F (a) ⊆ [R]} ∩ DF = F (−1) ([R]) ∩ DF . Minthogy deÞníció alapján F (−1) ([R]) = [R ° F ], azért az 1. és 3 esetekben a leggyengébb elýofeltétel R ° F Az értékadást változókkal is leírjuk. Legyen A = ×ni=1 Ai , F

⊆ A × A és F (a) = F1 (a) × F2 (a) × . × Fn (a) (a ∈ DF ) , ahol Fi ⊆ A × Ai . Legyenek az állapottér változói x1 , x2 , , xn a := F (a) program jelölése: Ekkor az x1 , . , xn := F1 (x1 , , xn ) , , Fn (x1 , , xn ) A jelölésbýol elhagyhatjuk az xi -t és Fi (x1 , . , xn )-t, ha Fi (x1 , , xn ) = xi Ha valamely Fj nem függ valamelyik xi -týol, akkor ezt is elhagyhatjuk a jelölésbýol. Ha a fenti értékadásban csak egy komponens szerepel, akkor egyszerý u, egyébként pedig szimultán értékadásról beszélünk. 4.1 Példa: Legyen A = Z × L, x a Z, l pedig az L állapottér komponenshez x l tartozó változó. Legyenek az értékadás komponensei: ∀a = (a1 , a2 ) ∈ A: F1 (a1 , a2 ) = a1 , azaz F1 = prZ , és F2 (a1 , a2 ) = (a1 > 0) . Ekkor az a := F (a) értékadás változókkal felírva: x, l := x, (x > 0) . A jelölés fent leírt egyszerýusítéseit elvégezve az l := (x > 0) egyszerý u értékadást

kapjuk. 2.3 Programkonstrukciók Olyan mý uveletekkel foglalkozunk, amelyekkel meglévýo programjainkból újakat állíthatunk elýo. Sokféle konstrukció képzelhetýo el, de mi csak háromféle konstrukciós mýuveletet fogunk megengedni: - szekvencia (sorozat), - elágazás, - ciklus. 17 A struktúrált programozás alaptétele (Böhm-Jacopini, 1966) kimondja: bármely program megadható ekvivalens struktúrált program formájában is, amelyben csak a fenti három konstrukciós mý uvelet szerepel. Két program ekvivalens, ha ugyanazon input értékekre ugyanazon output értékeket számolják ki. Az elsýo konstrukciós technika a szekvencia, vagy sorozat. Itt két program közvetlen egymásután való végrehajtásáról van szó. Legyen S1 és S2 a két program, a ∈ A és α ∈ S1 (a) ∩ A∗ az S1 program által elýoállított véges sorozat Az S2 program az S1 program τ (α) végállapotából indul és a β ∈ S2 (τ (α)) véges, vagy végtelen sorozatot

állítja elýo. Tehát az a ∈ A állapotból kiindulva a két program egymásutáni végrehajtása a kon (α, β) egyesített sorozatot eredményezi. Ez azonban nem redukált, mert τ (α) = β 1 Ezért az egyesített sorozat redukáltját tekintjük a szekvencia eredményének. Legyen α ∈ A∗ , β ∈ A∗∗ és χ2 (α, β) = red (kon (α, β)) . 5.1 DeÞníció: Legyenek S1 , S2 ⊆ A × A∗∗ programok Az S ⊆ A × A∗∗ relációt az S1 és S2 programok szekvenciájának nevezzük, és (S1 ; S2 )-vel jelöljük, ha ∀a ∈ A : S (a) = {α ∈ A∞ | α ∈ S1 (a)} ∪ ∪ {χ2 (α, β) ∈ A∗∗ | α ∈ S1 (a) ∩ A∗ ∧ β ∈ S2 (τ (α))} . Megjegyzés: 1. Ha a két program értékkészlete csak véges sorozatokat tartalmaz, akkor a szekvencia is csak véges sorozatokat rendel hozzá az állapottér pontjaihoz. 2. Determinisztikus programok szekvenciája is determinisztikus reláció (függvény) A programkonstrukciókat többféleképpen is ábrázolhatjuk.

Ezek egyike a struktogram Legyen S1 , S2 program Az S = (S1 ; S2 ) szekvencia struktogramja: S | S1 S2 5.1 Feladat: Adjuk meg az S = (S1 ; S2 ) szekvencia által megoldott feladatot, ha S1 és S2 általános értékadás program! A második konstrukciós technika az elágazás (feltételes utasítás, case szerkezet), ahol más-más programot hajtunk végre feltételtýol függýoen. 5.2 DeÞníció: Legyenek π 1 , , π m : A L feltételek, S1 , , Sm programok ol képezett πi -k által meghatározott A-n. Ekkor az IF ⊆ A×A∗∗ relációt az Si -kbý elágazásnak nevezzük, és (π 1 : S1 , . , πm : Sm )-vel jelöljük, ha ∀a ∈ A : IF (a) = (∪m i=1 wi (a)) ∪ w0 (a) , ahol ∀i ∈ [1.m]: wi (a) = ½ Si (a) , ha a ∈ [πi ] ∅, különben 18 és w0 (a) = ½ ha, a, a, . i , ha a ∈ / ∪m i=1 [π i ] ∅, különben. Megjegyzés: 1. Ha a feltételek nem diszjunktak, akkor az elágazás bármelyik olyan Si ág választását megengedi, amelyre π i

igaz. 2. Az elágazásoktól a gyakorlatban azt is megköveteljük, hogy a feltételek diszjunktak legyenek és ∪m i=1 [π i ] = A teljesüljön (Miért?). Az IF = (π1 : S1 , . , π m : Sm ) elágazás struktogramja: Âπ1 S1 Âπ2 S2 IF | Â. . . . Âπm Sm 5.2 Feladat: Milyen Pascal szerkezetnek felel meg a (π : S; qπ : SKIP ) elágazás? A harmadik konstrukciós technika a ciklus, amelyben egy meglévýo programot egy adott feltételtýol függýoen valahányszor végrehajtunk. Legyen S a program és π az adott feltétel. Ezután a következýoképpen járunk el: 1. Ha az a ∈ A kiinduló pontban π nem igaz, akkor az S programot nem hajtjuk végre és a ciklusból kilépünk. 2. Ha π igaz, akkor az S programot végrehajtjuk és eredményül kapunk egy α sorozatot. 3. Ha α véges és a τ (α) pontban π nem igaz, akkor kilépünk a ciklusból 4. Ha α véges és a τ (α) pontban π igaz, akkor a τ (α) pontból indulva megismételjük az elýozýo lépéseket a

2. ponttól A vázolt eljárással - n ismétlést (iterációt) feltéve- az α1 , α2 , . , αn soroza1 n−1 tokat amelyekre¡ fennáll, ∈ A∗ , α1 ∈ S (a), α2 ∈ ¡ n−1 ¢¢hogy α n, . , α ¢¢ ¡ ¡ kapjuk, 1 n . Ha α végtelen, akkor sem S, sem a cikS τ α , ,α ∈ S τ α lus nem fejezýodik be. Ha αn véges, akkor két eset lehetséges Ha π igaz a τ (αn ) pontban, akkor folytatjuk a ciklust a τ (αn ) pontból kiindulva. Ha π¢ ¡ nem igaz, akkor a ciklust befejezzük. Ez esetben a ciklus a kon α1 , , αn egyesített sorozatot eredményezi. Ez¡ a ¢sorozat a szekvencia esetéhez hasonlóan ¡ ¢ nem redukált, mert τ α1 = α21 , τ α2 = α31 , stb. Ezért az egyesített sorozat redukáltját tekintjük a ciklus, vagy iteráció eredményének. Szükségünk van a következýo jelölésekre: Legyen α1 , α2 , . , αn−1 ∈ A∗ és n α ∈ A∗∗ . Ekkor ¡ ¢ ¡ ¡ ¢¢ χn α1 , α2 , . , αn = red kon α1 , α2 , , αn Ha αi

∈ A∗ (i ∈ N ), akkor ¢ ¡ ¡ ¢¢ ¡ χ∞ α1 , α2 , . = red kon α1 , α2 , 5.3 DeÞníció: Legyen π feltétel és S program A-n A DO ⊆ A × A∗∗ relációt az S-bý ol a π feltétellel képezett ciklusnak nevezzük, és (π, S)-sel jelöljük, ha 19 1. ∀a ∈ / [π]: DO (a) = {hai}, 2. ∀a ∈ [π]: ¡ ¢ DO (a) = α ∈ A∗∗ | ∃n ∈ N : α = χ¡n ¡α1 , ¢¢ α2 , . ¡, α¢n ∧ α1 ∈ S (a) ∧ ∧∀i ∈ [1.n − 1] : αi+1 ∈ S τ αi ∧ τ αi ∈ [π] ∧ ∗ n / [π]))} ∪ ∧ (αn ∈ A∞ ∨ (αn ∈ A ¡ 1∧ τ2(α )¢∈ ∞ 1 ∪ α ∈ A | α = χ∞¡ α , α , . . . ¡ i ¢¢ ¡ ∧i ¢α ∈ Sª(a) ∧ i+1 ∧∀i ∈ N : α ∈ S τ α ∧ τ α ∈ [π] . Megjegyzés: 1. Determinisztikus programból képezett ciklus is determinisztikus 2. A ciklus értékkészlete tartalmazhat végtelen sorozatot akkor is, ha az S program csak véges sorozatokat generál (soha nem jutunk ki a π feltétel igazsághalmazából). A DO =

(π, S) ciklus struktogramja: DO | π S Igazoljuk a következýo eredményt. 5.1 Tétel: A szekvencia, az elágazás és a ciklus program Bizonyítás: Mindhárom program A×A∗∗ tipusú reláció és mindhárom esetben DS = A. A másik két tulajdonság igazolása a következýo: 1. Szekvencia: a ∈ A, α ∈ S (a) Ha α¡ ∈ S1 (a), ¢ akkor1 S1 program volta 1 2 = a és α = red (α). Ha α = χ , α α , ahol α ∈ S1 (a) és α2 ∈ miatt α 2 ¡ ¡ 11 ¢¢ S2 τ α , akkor χ2 deÞníciója miatt α redukált és α1 = α11 = a. 2. Elágazás: a ∈ A, α ∈ IF (a) Ekkor α ∈ ∪m i=0 wi (a) . Ha α ∈ w0 (a), akkor α = ha, a, . i kielégíti a két kritériumot Ha ∃i ∈ [1m] : α ∈ wi (a), akkor α ∈ Si (a) és mivel Si program, α1 = a és α = red (α). 4. Ciklus: a ∈ A, α ∈ DO (a) Ha a ∈ / [π], akkor α = hai, ami teljesíti a program követelményeit. Ha a ∈ [π], akkor ¡ két eset lehetséges: ¢ (a) Ha α ∈ A∗∗ és ∃n ∈ N : α = χn

α1 , α2 , . , αn , α1 ∈ S (a), akkor χn deÞniciója miatt α redukált és α1¡ = α11 = a.¢ (b) Ha α ∈ A∞ és α = χ∞ α1 , α2 , . , α1 ∈ S (a), akkor χn deÞníciója miatt α redukált és α1 = α11 = a. Q.ED 2.4 A programkonstrukciók programfüggvényei A három programkonstrukció programfüggvényeit határozzuk meg. 20 olük 6.1 Tétel: Legyen A állapottér, S1 , S2 programok A-n, S = (S1 ; S2 ) a belý képezett szekvencia. Ekkor p (S) = p (S2 ) ° p (S1 ) . Bizonyítás: Emlékeztetünk arra, hogy a programfüggvény deÞníciója: p (S) = {(a, b) | S (a) ⊆ A∗ ∧ ∃α ∈ S (a) : τ (α) = b} . Esetünkben (feltéve, hogy minden sorozat véges): (a, a0 ) ∈ p (S2 ) ° p (S1 ) ⇐⇒ ∃b ∈ A : (a, b) ∈ p (S1 ) ∧ (b, a0 ) ∈ p (S2 ) ⇐⇒ ∃α ∈ S1 (a) : τ (α) = b ∧ ∃β ∈ S2 (b) : τ (β) = a0 ⇐⇒ χ2 (α, β) ∈ S (a) ∧ τ (χ2 (α, β)) = a0 ⇔ (a, a0 ) ∈ p (S) . Q.ED 6.2 Tétel: Legyen A állapottér,

S1 , S2 , , Sm programok A-n, valamint π1 , π2 , . , πm : A L feltételek A-n, IF = (π 1 : S1 , , πm : Sm ) Ekkorª 1. Dp(IF ) = a ∈ A | a ∈ ∪m i=1 [π i ] ∧ ∀j ∈ [1.m] : a ∈ [π j ] ⇒ a ∈ Dp(Sj ) 2. ∀a ∈ Dp(IF ) : p (IF ) (a) = ∪m i=1 pwi (a) , ahol pwi (a) = ½ p (Si ) (a) , ha a ∈ [πi ] ∅, különben Bizonyítás: a ∈ Dp(IF ) ⇐⇒ IF (a) ⊆ A∗ ⇐⇒ ∗ ∃i ∈ [1.m] : a ∈ [πi ] ∧ ∪m i=1 wi (a) ⊆ A ⇐⇒ ∃i : a ∈ [πi ] ∧ ∀j ∈ [1.m] : a ∈ [πj ] ⇒ a ∈ Dp(Sj ) Legyen a ∈ Dp(IF ) . Ekkor m p (IF ) (a) = τ (∪m i=1 wi (a)) = ∪i=1 pwi (a) . Q.ED Megjegyzés: Ha az elágazásfeltételek lefedik az egész állapotteret, akkor mindig van olyan πi állítás, amelyik igaz. Szükségünk van a következýo fogalmakra. 6.1 DeÞníció: Legyen R ⊆ A × A és n ∈ N Az R reláció n-edik hatványa ( n ≥ 1): R(n) = {(a, a0 ) ∈ A × A | ∃a0 , a1 , . , an ∈ A : (∀i ∈ [1.n] : (ai−1 , ai )

∈ R) ∧ a0 = a ∧ an = a0 } 21 Az R reláció 0-adik hatványa (tkp. idA ): R(0) = {(a, a0 ) ∈ A × A | a = a0 } . Megjegyzés: R(n) = R ° R(n−1) , R(1) = R és (idA )(n) = idA . Értelemszerý uen R(n) (a) = {a0 ∈ A | ∃a0 , a1 , . , an ∈ A : (∀i ∈ [1.n] : (ai−1 , ai ) ∈ R) ∧ a0 = a ∧ an = a0 } , R(1) (a) = R (a) , R(0) (a) = {a} . 6.2 DeÞníció: Az R ⊆ A × A reláció lezártján az R ⊆ A × A relációt értjük, amelyre DR = {a ∈ A | @α ∈ A∞ : (a, α1 ) ∈ R ∧ ∀i ∈ N : (αi , αi+1 ) ∈ R} és ∀a ∈ DR : n o R (a) = b ∈ A | b ∈ / DR ∧ ∃k ∈ N0 : b ∈ R(k) (a) . Megjegyzés: A reláció lezártja olyan pontokban van értelmezve, amelyekbý ol kindulva a relációt nem lehet végtelen sokszor egymás után alkalmazni (a pontból nem indulhat végtelen ”lánc”, csak véges). Ezekhez a DR -beli pontokhoz olyan pontokat rendel, amelyek nincsenek benne az eredeti reláció értelmezési tartományában. Tkp a

véges láncok kivezetnek DR -bý ol. Tehát DR ∩ RR = ∅ Vizsgáljuk meg az R reláció lezárását. Az eredeti DR értelmezési tartományt felbonthatjuk két diszjunkt halmaz uniójára: ∗ ∞ DR = DR ∪ DR , ∗ ∞ azon pontok halmaza, amelybýol csak véges lánc indulhat, DR pedig ahol DR azoké, amelyekbýol indul végtelen lánc. Bontsuk fel az A állapotteret három diszjunkt halmaz uniójára: ∗ ∞ ∪ DR . A = (A DR ) ∪ DR Legyen a ∈ ADR . Minthogy @b ∈ A : (a, b) ∈ R, azért a ∈ DR Következésképpen ∗ . DR = (A DR ) ∪ DR Tekintsük az R (a) halmaz (a ∈ DR ) o n b∈A|b∈ / DR ∧ b ∈ R(0) (a) 22 / DR . Ez csak a ∈ A DR esetén részhalmazát: b ∈ R(0) (a) ⇐⇒ a = b ∈ lehetséges, amikor b = a. Tehát ½ {a} , ha a ∈ A DR ª R (a) = ∗ b∈A|b∈ / DR ∧ ∃k ∈ N : b ∈ R(k) (a) , ha a ∈ DR Vegyük észre, hogy itt N0 helyett N-et írhattunk és R (a) = idA (a) (a ∈ A DR ) . Összegezve: a lezárás egyrészt

leszý ukíti az R reláció értelmezési tartományát, másrészt kiterjeszti a relációt az A DR halmazra, ahol az identitás relációval lesz azonos. Legyen A tetszýoleges állapottér, S ⊆ A × A∗∗ program, π feltétel A-n és DO = (π, S). Vizsgáljuk a DO ciklus programfüggvényét! Emlékeztetý o: Az S program programfüggvénye: Dp(S) = {a ∈ A | S (a) ⊆ A∗ } , p (S) (a) = {b ∈ A | ∃α ∈ S (a) : τ (α) = b} = τ (S (a)) = (τ ° S) (a) . Esetünkben a ∈ Dp(DO) ⇐⇒ DO (a) ⊆ A∗ csak két esetben lehetséges: DO (a) = {a} , DO (a) = ha a ∈ / [π] , ¡ ¢ 2 , . ¡, αn¢ ∧ α1 ∈ S (a) ∧ α ∈ A∗ | ∃n ∈ N : α = χn¡ α¡1 , α¢¢ ∧∀i ∈ [1.n − 1] : αi+1 ∈ S τ αi ∧ τ αi ∈ [π] ∧ ∧τ (αn ) ∈ / [π]} , ha a ∈ [π] . Vegyük észre, hogy τ (α) = τ (αn )! Ezért a fenti két esetben p (DO) (a) = {a} , ha a ∈ / [π] és p (DO) (a) = . , αn ¡: α¢1 ∈ S (a) ∧ τ (αn ) ∈ A | ∃n ∈ N

: ∃α1¡, α¡2 , . ¢¢ i+1 i ∧∀i ∈ [1.n − 1] : α ∈ S τ α ∧ τ αi ∈ [π] ∧ n / [π]} , ha a ∈ [π] . ∧τ (α ) ∈ Az utóbbi kifejezést a b ∈ S (c) ⇒ τ (b) ∈ τ (S (c)) = p (S) (c) összefüggés miatt felírhatjuk a következýo formában is: 23 p (DO) (a) = ¡ ¢ ¡ ¢ τ (αn ) ∈ A | ∃n ∈ ¡N : ∃τ¢ α1 , . ¡ ,¡τ (α¢¢n ) : τ ¡ α1¢ ∈ p (S) (a) ∧ ∧∀i ∈ [1.n − 1] : τ αi+1 ∈ p (S) τ αi ∧ τ αi ∈ [π] ∧ ∧τ (αn ) ∈ / [π]} , ha a ∈ [π] . Vegyük észre, hogy τ (αn ) ∈ (p (S))(n) (a), a ∈ [π], a ∈ Dp(S) és a τ (αn )-hez ¡ ¢ ¡ ¢ ¡ ¢ vezetýo τ α1 , . , τ αn−1 lánc minden tagjára τ αi ∈ [π] teljesül Indokolt bevezetnünk a következýo fogalmat. 6.3 DeÞníció: A p (S) reláció megszorítása a [π] igazsághalmazra: p (S)|[π] = p (S) ∩ ([π] × A) . Ekkor Dp(S)|[π] = Dp(S) ∩ [π] . Könnyen látható, hogy az a ∈ Dp(S) ∩ [π] pontban p (DO) (a)

tulajdonképpen a p (S)|[π] reláció lezárása. Bontsuk fel p (S)|[π] értelmezési tartományát ∗ ∞ ∪ Dp(S) Dp(S)|[π] = Dp(S) |[π] |[π] alakban. Értelemszerýuen ∗ . Dp(DO) = [qπ] ∪ Dp(S) |[π] A p (S)|[π] reláció lezárásának értelmezési tartománya: ´ ³ ¡ ¢ ∗ ∗ = [qπ] ∪ [π] D . ∪ Dp(S) Dp(S) = A Dp(S)|[π] ∪ Dp(S) p(S) |[π] |[π] |[π] Az a ∈ [qπ] esetben p (S)|[π] (a) = {a} = p (DO) (a) . Ezt Þgyelembevéve a következýo eredményt kapjuk. 6.3 Tétel: Legyen A tetszý oleges állapottér, S ⊆ A × A∗∗ program, π feltétel ∗ A-n, DO = (π, S). Ekkor Dp(DO) = [qπ] ∪ Dp(S) és |[π] p (DO) (a) = p (S)|[π] (a) 2.5 Levezetési szabályok ¢ ¡ a ∈ Dp(DO) . A programkonstrukciók és a speciÞkáció kapcsolatát vizsgáljuk. Emlékeztetünk arra, hogy egy S program R utófeltételhez tartozó leggyengébb elýofeltételének neveztük azt az lf (S, R) állítást, amelyre ª [lf (S, R)] = a ∈ Dp(S) | p (S)

(a) ⊆ [R] . 24 Legyen Q és R két állítás A-n, S program. A {Q} S {R} szimbólum azt jelöli, hogy a ∈ [Q] esetén p (S) (a) ⊆ [R]. A Q állítást (predikátumot) elýofeltételnek nevezzük Világos, hogy [Q] ⊆ [lf (S, R)] és Q ⇒ lf (S, R) 7.1 Tétel (A szekvencia levezetési szabálya): Legyen S = (S1 ; S2 ) szekvencia, Q, R és Q0 állítások A-n. Ha (1) Q ⇒ lf (S1 , Q0 ) és (2) Q0 ⇒ lf (S2 , R), akkor Q ⇒ lf (S, R). Bizonyítás: Legyen q ∈ [Q]. Ekkor (1) miatt q ∈ Dp(S1 ) és p (S1 ) (q) ⊆ [Q0 ]. A (2) feltétel miatt [Q0 ] ⊆ Dp(S2 ) és ∀q0 ∈ Q0 : p (S2 ) (q0 ) ⊆ [R] Ezért p (S2 ) ° p (S1 ) (q) ⊆ [R], azaz q ∈ [lf (S, R)]. QED 7.1 Következmény: A speciÞkáció tételébý ol (Ha ∀b ∈ B esetén Qb ⇒ lf (S, Rb ), akkor az S program megoldja az F feladatot.) és 71 Tételbý ol következik, hogy ha S1 és S2 olyan programok, amelyekre a paramétertér minden pontjában Qb ⇒ lf (S1 , Q0b ) és Q0b ⇒ lf (S2 , Rb ) teljesül,

akkor (S1 ; S2 ) megoldja a Qb , Rb párokkal megadott feladatokat. 7.2 Tétel (A szekvencia levezetési szabályának megfordítása): Legyen S = (S1 ; S2 ) szekvencia, Q és R olyan állítások A-n, amelyekre Q ⇒ lf (S, R). Ekkor ∃Q0 : A L állítás, hogy (1) Q ⇒ lf (S1 , Q0 ) és (2) Q0 ⇒ lf (S2 , R). Bizonyítás: Legyen Q0 = lf (S2 , R). Ekkor (2) teljesül Tfh (1) nem teljesül Ekkor ∃q ∈ [Q] : q ∈ / [lf (S1 , lf (S2 , R))]. Két eset lehetséges: a) q ∈ / Dp(S1 ) , ami ellentmondás a [Q] ⊆ Dp(S) ⊆ Dp(S1 ) feltétellel; b) p (S1 ) (q) * [lf (S2 , R)]. Legyen r ∈ p (S1 ) (q) [lf (S2 , R)] Két eset lehetséges: r∈ / Dp(S2 ) , ami ellentmondás a q ∈ Dp(S2 )°p(S1 ) feltétellel. p (S2 ) (r) * [R]: Legyen s ∈ p (S2 ) (r) [R]. Ekkor s ∈ p (S) (q) és s∈ / [R], ami ellentmond a p (S) (q) ⊆ [R] feltételnek. QED 7.3 Tétel (Az elágazás levezetési szabálya): Legyen IF = (π 1 : S1 , , πm : Sm ) elágazás, Q és R állítások A-n. Ha

∀i ∈ [1m] : Q ∧ πi ⇒ lf (Si , R), akkor Q ∧ (∨m i=1 π i ) ⇒ lf (IF, R) . Bizonyítás: Legyen q ∈ [Q] és tfh. ∃i ∈ [1m] : q ∈ [π i ] Ekkor q ∈ Dp(IF ) , ui ∀j ∈ [1.m] : q ∈ [πj ] ⇒ lf (Sj , R) ⇒ q ∈ Dp(Sj ) Mivel ∀j ∈ [1.m] : q ∈ [πj ] ⇒ p (Sj ) (q) ⊆ [R], azért p (IF ) (q) = ∪j∈[1.m] p (Sj ) (q) ⊆ [R] q∈[πj ] Tehát q ∈ [lf (IF, R)]. QED 7.2 Következmény: Legyen adott az F feladat speciÞkációja (A, B, Q, R) Ekkor, ha ∀b ∈ B paraméterre és ∀Si programra Qb ∧ π i ⇒ lf (Si , Rb ), és 25 ∀b ∈ B paraméterhez van olyan πi feltétel, amelyre b ∈ [πi ], akkor az IF program megoldja a Qb , Rb párokkal deÞniált feladatot. 7.4 Tétel (Az elágazás levezetési szabályának megfordítása): Legyen IF = (π1 : S1 , . , π m : Sm ) elágazás, Q és R olyan állítások A-n, amelyekre Q ∧ (∨m i=1 π i ) ⇒ lf (IF, R) . Ekkor ∀i ∈ [1.m] : Q ∧ π i ⇒ lf (Si , R) Bizonyítás:

Indirekt: tfh. ∃i ∈ [1m] : [Q ∧ πi ] * [lf (Si , R)]. Legyen q ∈ [Q ∧ πi ] [lf (Si , R)]. Két eset lehetséges: q∈ / Dp(Si ) , ami ellentmond a q ∈ Dp(IF ) feltevésnek. p (Si ) (q) * [R]. Ekkor p (Si ) (q) ⊆ p (IF ) (q) ⊆ [R] miatt ellentmondás Q.ED Megjegyzés: Nem elég az elágazás levezetési szabályának teljesülését vizsgálni. Ellený orizni kell, hogy a feltételek lefedik-e a feladat értelmezési tartományát. A ciklus levezetési szabálya bonyolultabb. A cél: DO véges lépésben termináljon. Olyan P feltételt keresünk, amely: 1. Igaz a ciklus/iteráció megkezdése elýott; 2. Igaz az iteráció alatt; 3. Igaz az iteráció befejezése után A ciklus befejezésekor qπ, tehát P ∧qπ igaz. Ha P ∧qπ ⇒ R, akkor a ciklus helyességét igazoltuk. A P feltétel elnevezése: invariáns feltétel/tulajdonság Bevezetünk továbbá egy t : A Z egész értéký u függvényt, amely 1. A program változóitól függ; 2. Korlátot ad a

szükséges iterációk számára; 3. Minden végrehajtott iteráció legalább 1-el csökkenti t értékét; 4. t alulról korlátos: t > 0 terminálás elýott A t függvény elnevezése: korlátozó/termináló függvény. A korlátozó függvény biztosítja, hogy a ciklusnak terminálnia kell. 7.5 Tétel (A ciklus levezetési szabálya): Legyen P állítás A-n, DO = (π, S) és t : A Z. Ha (1) P ∧ π ⇒ t > 0, (2) P ∧ π ⇒ lf (S, P ), (3) P ∧ π ∧ ∀t = t0 ⇒ lf (S, t < t0 ), akkor P ⇒ lf (DO, P ∧qπ). Megjegyzés: Ha Q ⇒ P és P ∧qπ ⇒ R, akkor Q ⇒ lf (DO, R). A 7.5 Tétel bizonyítása: Legyen g a p (S) leszý ukítése [π]-re, azaz g = p (S) ∩ ([π] × A). 1. állítás: Legyen q ∈ [P ∧ π] Ekkor ∀k ∈ N0 : g (k) (q) ⊆ [P ] . Az állítást teljes indukcióval igazoljuk: k = 0 esetén g(0) (q) = q ∈ [P ]; Tfh. g (q) ⊆ [P ]. Legyen r ∈ g(k) (q) tetszýoleges Két eset lehetséges: (k) 26 r ∈ [P ∧qπ]. Ekkor a ciklus

terminál, g (r) = r ∈ [P ] r ∈ [P ∧ π]. Ekkor (2) miatt r ∈ Dp(S) és g (r) = p (S) (r) ⊆ [P ] Tehát g(k+1) (q) ⊆ [P ]. 2. állítás: Legyen q ∈ [P ∧ π] Ekkor ∃n ≤ t (q) : g (n) (q) ⊆ [qπ] . Indirekt bizonyítás: Tfh. ∀n : g (n) (q) ⊆ [π] A q ∈ A pontban P ∧ π ∧ t = t (q) (t0 = t (q)) igaz, amibýol (3) miatt következik, hogy q ∈ [lf (S, t < t (q))] ⇐⇒ q ∈ Dp(S) ∧ p (S) (q) ⊆ [(t < t (q))] Legyen b ∈ p (S) (q) tetszýoleges. Ekkor t (b) < t (q), ahonnan maxb∈g(q) t (b) < t (q). Hasonlóan igazoljuk, hogy ³ ´ tk+1 = max t eb < max t (b) = tk . eb∈g (k+1) (q) Minthogy b∈g (k) (q) ³ ´ eb ∈ g (k+1) (q) ⇐⇒ ∃z ∈ g (k) (q) : z, eb ∈ g és a z pontban P ∧ π ∧ t = tk igaz (mert g(k) (q) ⊆ [π], z ∈ [π]), azért z ∈ [[lf (S, t < tk )]] ⇐⇒ z ∈ Dp(S) ∧ p (S) (z) ⊆ [(t < tk )] . ³ ´ Minthogy eb ∈ p (S) (z), azért t eb < tk . Tehát tk+1 < tk és fennáll, hogy max

b∈g(t(q)+1) (q) t (b) < max b∈g (t(q)) (q) t (b) < . < max t (b) < t (q) b∈g(q) Minthogy itt t (q)+1 darab egymástól különbözýo és t (q)-nál kisebb egész számról van szó, szükségképpen max b∈g(t(q)+1) (q) t (b) < 0 következik. Ez ellentmond (1)-nek (t > 0) A két állítás után a tétel bizonyítása a következýo. Legyen q ∈ [P ] tetszýoleges Ekkor vagy q ∈ [P ∧qπ], vagy q ∈ [P ∧ π]. Ha q ∈ [P ∧qπ], akkor a ciklus deÞníciója alapján p (DO) (q) = {q} ⊆ [P ∧qπ]. Tehát q ∈ [lf (DO, P ∧qπ)] Ha q ∈ [P ∧ π], akkor a 2. állítás miatt ∃n ∈ N0 : g (n) (q) ⊆ [qπ] . Ez azt jelenti, hogy q ∈ Dp(DO) (n-nél rövidebb ”láncok” is indulhatnak q-ból, de azok is [qπ]-ben kell, hogy végzýodjenek). DeÞníció alapján p (DO) (q) ⊆ [qπ] . 27 Az 1. állítás miatt p (DO) (q) ⊆ [P ] . Tehát p (DO) (q) ⊆ [P ∧qπ] . Következésképpen q ∈ [lf (DO, P ∧qπ)] . Tehát P ⇒ lf

(DO, P ∧qπ). QED Vizsgáljunk meg néhány példát. A ciklust a következýo ”metanyelvi” leírással adjuk meg: while π S end A Q elýofeltételt, R utófeltételt, a P invariáns állítást és a t korlátozó függvényt belefoglaljuk a fenti leírásba: {Q} {P : az invariáns állítás} {t : korlátozó függvény} while π S end {R} A ciklus helyességét a következýok szerint kell ellenýorizni: 1. Igazoljuk, hogy P igaz a ciklus megkezdése elýott 2. Igazoljuk, hogy {P ∧ π} S {P }, azaz P tényleg invariáns 3. Igazoljuk, hogy P ∧qπ =⇒ R, azaz terminálás után az R utófeltétel bekövetkezik. 4. Igazoljuk, hogy P ∧ π =⇒ (t > 0) 5. Igazoljuk, hogy {P ∧ π} (t0 = t; S) {t < t0 } 7.1 Feladat: Formálisan igazoljuk a fenti öt pontot a következýo három példára! 7.1 Példa: Az algoritmus kiszámítja az i = 2p (i ≤ n < 2i) mennyiséget {n > 0} i := 1; {P : 0 < i ≤ n ∧ (∃p : i = 2p )} {t : n − i} while 2 ∗ i ≤ n i := 2

∗ i end {R : 0 < i ≤ n < 2 ∗ i ∧ (∃p : i = 2p )} 28 7.2 Példa: Az algoritmus kiszámítja az n-edik Fibonacci számot n > 0 esetén (f0 = 1, f1 = 1 és fn = fn−1 + fn−2 , ha n > 1). {n > 0} i, a, b := 1, 1, 1; {P : 1 ≤ i ≤ n ∧ a = fi ∧ b = fi−1 } {t : n − i} while i < n i, a, b := i + 1, a + b, a end {R : a = fn } 7.3 Példa: Az algoritmus kiszámítja a q hányadost és az r maradékot, amikor x-et y-al osztjuk. {x ≥ 0 ∧ y > 0} q, r := 0, x; {P : 0 ≤ r ∧ 0 < y ∧ q ∗ y + r = x} {t : r} while r ≥ y r, q := r − y, q + 1 end {R : 0 ≤ r < y ∧ q ∗ y + r = x} 3 Programszerkezetek analízise A programok szerkezetét irányított gráffal ábrázoljuk. Feltesszük, hogy minden program (és részprogram) determinisztikus (függvényreláció). 3.1 Gráfelméleti alapfogalmak 8.1 DeÞníció: A gráf pontokból és a pontokat összekötý o vonalakból álló alakzat. A gráf pontjait szögpontoknak, vagy

csúcsoknak nevezzük. A gráf két szögpontját összekötý o olyan vonalat, amely nem megy át más szögponton, élnek nevezzük. A szögpontok halmazát V (vertex), az élek halmazát E (edge) jelöli. A G gráfot a G = (V, E) pár adja meg. Egy e ∈ E élt a rendezetlen [u, v] pár ad meg, ahol u, v ∈ V . Az u és v csúcsok az e él végpontjai Az [u, u] ∈ E élt huroknak nevezzük. Az e, e0 ∈ E éleket többszörös éleknek nevezzük, ha ugyanazt a két pontot kötik össze, azaz e = [u, v] és e0 = [u, v]. A hurkot és többszös éleket nem tartalmazó gráfokat egyszerý u gráfoknak nevezzük egyébként pedig multigráfnak. 8.2 DeÞníció: Az u ∈ V csúcs φ (u) fokán az u csúcsot tartalmazó élek számát érjük. Ha φ (u) = 0, akkor az u csúcsot izoláltnak nevezzük 8.3 DeÞníció: A G gráf üres, ha E = ∅ Teljes a gráf, ha minden szögpontpár éllel van összekötve. 8.4 DeÞníció: Az u, v ∈ V csúcsokat összekötý o n hosszúságú

vonalnak nevezzük az egymáshoz csatlakozó {[vi−1 , vi ]}ni=1 élek sorozatát, ha v0 = u és vn = v. 29 A vonal zárt, ha v0 = vn . A vonalat útnak nevezzük, ha a v0 , v1 , , vn csúcsok a v0 = vn lehetý oség kivételével egymástól különböznek. A zárt utat körnek nevezzük. 8.5 DeÞníció: A gráf összefüggý o, ha bármely két szögpontját út köti össze. Következmény: Ha egy gráf nem összefüggý o, akkor van legalább egy olyan szögpontja, amelybý ol nem vezet út az összes többi szögpontba. 8.6 DeÞníció: Azok a szögpontok, amelyek egy adott szögpontból úttal elérhetý ok, a hozzájuk illeszkedý o élekkel együtt a gráf egy összefüggý o komponensét alkotják. 8.7 DeÞníció: Az olyan összefüggýo gráfot, amelyben nincsen kör, fának nevezzük Ha a fának n csúcsa van, akkor pontosan n − 1 éle van. 8.8 DeÞníció: A G gráfot cimkézettnek nevezzük, ha az éleihez adatokat rendelünk Ha minden e éléhez egy w (e) ≥

0 számot rendelünk, akkor súlyozott gráfról beszélünk. 8.9 DeÞníció: A G gráfot végesnek nevezzük, ha V és E véges halmazok 8.10 DeÞníció: A Gs = (Vs , Es ) gráf a G = (V, E) gráf részgráfja, ha Vs ⊆ V és Es ⊆ E. 8.11 DeÞníció: A gráf rangja, vagy ciklomatikus száma V (G) = e − n + p, ahol e az élek száma, n a szögpontok száma és p az összefüggý o komponensek száma. Megjegyzés: A ciklomatikus szám azonos a ”lineárisan független” körök maximális számával. Öszefüggý o gráf esetén V (G) = e − n + 1. 30 A E A D B C A D B B C C A E 3 3 B 2 2 3 4 D E C F 6 D Irányítatlan gráfok 8.12 DeÞníció: A G = (V, E) gráfot irányítottnak vagy digráfnak (directed graph) nevezzük, ha minden élét irányítjuk. Ekkor E rendezett párok halmaza. Az e = [u, v] ∈ E élnek u a kezdýopontja és v a végpontja. Egy u ∈ V csúcspont φbe (u) bemenýo foka, vagy be-foka az u szögpontban végzýodýo élek

száma. Az u csúcspont φki (u) kimenýo foka, vagy ki-foka az u pontból induló élek száma. Az u ∈ V csúcspontot forrásnak nevezzük, ha φki (u) > 0, de φbe (u) = 0. Az u ∈ V csúcspont nyelýo, ha φki (u) = 0, de φbe (u) > 0. Az irányított vonal, út és kör deÞníciója hasonló az eredeti defínícióhoz azzal az eltéréssel, hogy az út (és a kör) esetén az élek irányítása meg kell, hogy egyezzen az vonal irányításával. Az v csúcs elérhetýo az u csúcsból, ha létezik u-ból induló és v-ben végzýodýo irányított út. 8.13 DeÞníció: A G = (V, E) irányított gráf összefüggý o, ha az irányítások elhagyásával kapott gráf összefüggý o. 8.14 DeÞníció: A G = (V, E) irányított gráf erý osen összefüggý o, ha bármely u, v ∈ V csúcsot irányított él köt össze. 31 A D B C Irányított gráf A gráfok és relációk szoros kapcsolatban állnak egymással: 1. Legyen G = (V, E) irányított gráf Ez

megfeleltethetýo egy R ⊆ V × V relációnak: R = {(u, v) | e = [u, v] ∈ E} . 2. Legyen R ⊆ A × B reláció Ez megfeleltethetýo egy (V, E) gráfnak: V = A ∪ B, 3.2 E = {e = [u, v] | (u, v) ∈ R} . Vezérlési gráfok, blokkdiagramok A program utasításai egy irányított gráfra képezhetýok le, amelyben az utasításoknak a csomópontok felelnek meg, a gráf élei pedig az egyes utasítások után a következýo lépésben végrehajható utasításoknak megfeleltetett csomópontokat jelölik ki. A gráf csomópontjaihoz általában több bemenýo- és kimenýoél csatlakozik (1. ábra). 1. ábra 32 Az utasításoknak (csomópontoknak) kettýos funkciójuk lehet: - transzformációt hajtanak végre az adattéren - kijelölik a következýo végrehajtandó utasítást (kiválasztják azt a kimenýoélt, amelyen a vezérlés továbbhalad). A fenti gráfot célszerý uen kétféle tipusú gráfelemre bontjuk (2. ábra): 2. ábra A baloldali négyszög (deltoid)

vezérlési csomópont, az utasításnak mint elemi függvénynek azokat a funkcióit reprezentálja, melyek az adatteret (állapotteret) érintetlenül hagyják. Feladata kizárólag a következýo utasítás (csomópont) kijelölése. A fekvýo téglalap az adatteret transzformálja. Az ilyen tipusú csomópontból csak egy kimenýoél fut ki. Tehát a következýo utasítás egyértelmý uen meghatározott. Kikötjük, hogy a vezérlési csomópontokból kizárólag két él futhat ki. Ebben az esetben a vezérlési csomópontokat döntési (predikátum) csomópontoknak nevezzük. Ennek Þgyelembevételével az elýozýo gráfot (2. ábra) a következýoképpen helyettesíthetjük (3 ábra): 3. ábra A döntési csomópontok kétirányú elágazást reprezentálnak. Ennek analógiájára bevezetjük a gyý ujtýo csomópontot, melyen feladata kizárólag az, hogy a kétirányból érkezýo vezérlést egyesítse (4. ábra): 33 4. ábra Ez a csomópont nem hajt végre

transzformációt az állapottéren. Az új csomópont fogalom segítségével a 3. ábra gráfja átírható a következýo alakba (5 ábra): 5. ábra Ha eltekintünk attól, hogy a csomópontokban ténylegesen milyen döntés, vagy transzformáció játszódik le, tehát csak a gráf szerkezetét tekintjük, akkor az utóbbi tipusú gráfokat (a szý ukebb értelemben vett) vezérlési gráfoknak nevezzük. A programokat sok esetben blokkdiagram segítségével ábrázoljuk. A blokkdiagramot egy vezérlýográf és a gráf egyes csomópontjaihoz rendelt adattranszformációk, illetve lekérdezések (tesztek, predikátumok) határozzák meg Ezt a hozzárendelést a vezérlési gráf (egy adott programnak megfelelýo) interpretációjának nevezzük (6. ábra) f igaz P hamis g 6. ábra A 6. ábra az IF = (P : f, qP : g) elágazásnak felel meg (szöveges leírásban: if P then f else g). A blokkdiagramban csak adattranszformációs, döntési és gyý ujtýo csomópontokat engedünk

meg. 9.1 DeÞníció: A valódi program egy olyan összefüggý o irányított gráf, amelyre igazak a következý ok: 34 1. Véges számú nemzérus bemený oéllel és kimený oéllel rendelkezik; 2. Csomópontjait predikátumcsomópontok, függvénycsomópontok és gyüjtý ocsomópontok alkotják; 3. Minden csomóponton át vezet legalább egy bemený oéllel kezdý odý o és kimený oéllel végzý odý o útvonal. A programgráfot ki szokás egészíteni az indítási (START) és a befejezési (HALT, STOP) csomóponttal. Példa (nem valódi programra) a b P 7. ábra A P, a és b jelýu csomópontokon keresztül nem vezet útvonal a bemenýoéltýol a kimenýoélhez. 9.2 DeÞníció: Két programot (programgráfot) ekvivalensnek nevezünk, ha a programfüggvények megegyeznek. Példa (ekvivalens programgráfokra): 35 f hamis P igaz f a) hamis f hamis P igaz P igaz f b) 8. ábra Az a) esetben a programfüggvény: ha d ∈ [P ], akkor p (S) (d) = f (d),

egyébként ha f (d) ∈ [P ], akkor p (S) (d) = f (2) (d), . . / [P ] (i = azaz a programfüggvény p (S) (d) = f (n+1) (d) feltéve, hogy f (i) (d) ∈ 0, 1, . , n − 1) és f (n) (d) ∈ [P ] Itt ³ ´ f (n) (d) = f f (n−1) (d) , f (0) (d) = d, f (1) (d) = f (d) . A b) esetben a programfüggvény: ha d ∈ [P ], akkor p (Q) (d) = f (d), egyébként egy (utótesztelýo) iteráció kezdýodik, amelybýol akkor lépünk ki, ha (n) f (i) ∈ / [P ∈ [P ]. Ezután még végrehajtódik az ¡ (d) ¢ ] (i = 1, . , n − 1) és f (d) (n+1) (n) f f (d) leképezés. Tehát p (Q) (d) = f (d) feltéve, hogy f (i) (d) ∈ / [P ] (n) (i = 0, 1, . , n − 1) és f (d) ∈ [P ] Igazoltuk, hogy a két program ekvivalens. 36 3.3 A struktúrált programszerkezet Strukturáltnak, vagy D (Dijkstra) gráfnak nevezünk egy vezérlési gráfot, ha - meghatározott tipusú elemi részekbýol tevýodik össze, - és a részekbýol való összeállítás bizonyos szabályoknak tesz eleget. A

strukturált gráfok elemi részgráfjai a következýok: 1. Szekvencia (begin f 1, f 2, , fn end, vagy B (f 1, f 2, fn)): f1 f2 fn 9. ábra 2. Feltételes elágazás: if P then f , vagy IT (P ; f ) szerkezet: f igaz P hamis 10. ábra if P then f else g, vagy IT E (P ; f ; g) szerkezet: f igaz P hamis g 11. ábra 37 Az IT (P ; f) szerkezet az IT E (P ; f ; g) szerkezet speciális esete (g = id, vagy SKIP). 3. Iteráció, vagy ciklus (while P do f , vagy W D (P ; f )): hamis P igaz f 12. ábra A strukturált gráfokat az alábbi szabályrendszer alapján szerkeszthetjük: 1. Egyetlen csomópontból álló, egy input és egy output éllel rendelkezýo gráf struktúrált gráf; 2. A fenti elemi gráfok strukturált gráfok; 3. Strukturált gráf minden olyan vezérlési gráf, amelyben a komponens strukturált gráfokat egyetlen csomóponttá zsugorítva strukturált gráfot kapunk. Csakis a fentiek szerint szerkesztett gráfokat tekintjük strukturált, vagy D

gráfoknak. 9.3 DeÞníció: Egy vezérlý ográf lebontásának azt az eljárást nevezzük, amelynek során a gráfban elý oforduló három alapszerkezet valamelyikét egy csomóponttal helyettesítjük és ezt az eljárást mindaddig folytatjuk, amíg ilyen helyettesítés lehetséges. Ha a programgráf végül az egy csomópontot tartalmazó blokkra redukálódik, akkor ezt az önmagában álló éllel helyettesítjük 9.4 DeÞníció: Azt a programot, amelynek a vezérlý ográfja lebontható az önmagában álló irányított élre, strukturált programnak nevezzük. Megjegyzések: 1. A lebontás szempontjából az IT (P ; f ) és IT E (P ; f ; g) szerkezeteket azonosnak tekintjük. 2. A W D (P ; f) ciklus mellett szokták használni a Do f until P , vagy DU (P ; f ) utótesztelý o ciklust is (13. ábra) 38 f hamis P igaz 13. ábra Ez nem strukturált program, de a lebontáskor annak tekintjük. Feladat: Igazoljuk hogy a 13. ábra programja ekvivalens az alábbi

strukturált programmal: f hamis P igaz f 14. ábra Példa (strukturált program lebontása): Tekintsük az alábbi programgráfot. 15. ábra A gráf lebontásának lépései a következýok: 39 16. ábra Példa (nem strukturált valódi program) 17. ábra A program lebontása két lépés után elakad (18-19. ábra) 40 18. ábra 19. ábra Ez utóbbi már nem bontható tovább mert az alsó, if then else alakhoz hasonló szerkezet jobb alsó sarkában predikátum csomópont van. Kérdés: Hozzá lehet-e rendelni minden nem strukturált valódi programhoz egy strukturált programot? Feladat: Igazoljuk, hogy a 20. a) ábra nem strukturált programja ekvivalens a 20. b) ábra strukturált programjával! 41 h hamis Q hamis igaz P a) igaz f g h hamis Q hamis igaz P g igaz f b) g 20. ábra 9.1 Lemma: Ha egy programgráfban az élek száma e, a predikátumcsomópontok ujtý o csomópontok száma nc , száma np , a függvénycsomópontok száma nf és a

gyý akkor e = 3np + nf + 1 és np = nc . Bizonyítás: Számoljuk meg a csomópontokba befutó élek számát! függvény csomópont: nf predikátum csomópont: np gyýujtýo csomópont: 2nc összesen: nf + np + 2nc Ehhez hozzáadjuk a HALT csomóponthoz vezetýo 1 élt. Így a bemenýo élek száma: nf + np + 2nc + 1. A program csomópontjaiból kimutató élek száma: függvény csomópont: nf predikátum csomópont: 2np gyýujtýo csomópont: nc összesen: nf + 2np + nc Ehhez hozzáadjuk a START csomópontból kivezetýo 1 élt. Így a kimenýo élek száma: nf + 2np + nc + 1. Minthogy e = nf + np + 2nc + 1 = nf + 2np + nc + 1 kapjuk, hogy nc = np és e = 3np + nf + 1. QED 42 9.2 Lemma (Böhm-Jacopini): Egy S program akkor és csak akkor strukturált program, ha felírható B (g, h), vagy IT E (P ; g, h), vagy W D (P ; g) alakban, ahol P predikátum, g és h strukturált programok. Megjegyzések: 1. Az üres programot, amelynek vezérlési gráfja az önmagában álló

irányított él, is strukturáltnak tekintjük. 2. A lemma megadja a TOPDOWN programtervezési módszer hátterét is 9.1 Tétel (Corrado Böhm-Giuseppe Jacopini, 1966): Bármely valódi programhoz meg lehet konstruálni egy vele ekvivalens strukturált programot. 3.4 A struktúrálatlanság jellemzý oi A következýokben három fontos példát mutatunk nem strukturált programokra. Példa (Böhm-Jacopini Ω3 ) P1 P2 f1 P3 f2 21. ábra A példa vezérlési gráfja tkp. egy ciklus három kimenýoéllel Példa (két párhuzamos ciklus) 43 f3 A B 22. ábra A program két párhuzamos ciklusból áll, amelyek több kimenýoéllel rendelkeznek. Az A ciklus ezenkívül több belépýoéllel is rendelkezik A ciklusba történýo rendellenes belépések, ill. kilépések nem strukturáltsághoz vezetnek Példa (rendellenes elágazások) A 23. ábra A példa programja olyan két egymásbafésült elágazásból áll, amelyeknél rendellenes kilépések és belépések (A

rész) vannak. 9.2 Tétel: Egy program akkor és csak akkor nem strukturált, ha van olyan részgráfja, amely több ki-, ill. belépý o éllel rendelkezý o ciklus, vagy elágazás. Tekintsük az alábbi négy nemstrukturált programrészletet! 44 b) a) c) d) 24. ábra Az a) ábrán több kilépýo éllel, a b) ábrán pedig több belépýo éllel rendelkezýo ciklust látunk. A a c) ábrán több kilépýo éllel, a d) ábrán pedig több bemenýo éllel rendelkezýo döntést (elágazást) látunk. 9.3 Tétel: Egy nem strukturált programnak a 24 ábra gráfjai közül legalább kettý ot kell tartalmaznia. 3.5 Programok szerkezeti bonyolultsága Programok szerkezeti bonyolultságát többféleképpen mérjük. McCabe javasolta 1976-ban a vezérlýográf ciklomatikus számának használatát. Egy összefüggýo (G, V ) gráf ciklomatikus száma: V (G) = e − n + 1, ahol e az élek száma, n pedig a csomópontok száma. 9.5 DeÞníció: A P programgráf ciklikus

bonyolultságán az m (P ) = e − n számot értjük. Példa (strukturált elemi részgráfok) 45 P e=1, n=0, m(P)=1 e=6, n=4, m(P)=2 e=5, n=3, m(P)=2 e=5, n=3, m(P)=2 25. ábra 9.4 Tétel: Egy P programgráf ciklikus bonyolultságára fennáll, hogy m (P ) = np + 1, ahol np a program predikátum csomópontjainak száma. Bizonyítás: A 9.1 Lemma alapján e = 3np +nf +1 Másrészt n = np +nf +nc = 2np + nf . Ezért e − n = np + 1 QED 9.5 Tétel: Nem strukturált program ciklikus bonyolultsága legalább 3 Bizonyítás: A 9.3 Tétel alapján a program legalább két szerkezetét tartalmazza a 24. ábrának Ezért np ≥ 2 és m (P ) ≥ 3 QED A strukturált program lebontható egy ciklikus bonyolultságú programgráfra. Nemstrukturált program bonyolultságát lebontással csak bizonyos mértékig lehet csökkenteni. Példa: 46 26. ábra Az ábra nem strukturált programjában 5 predikátum csomópont van. Ezért a program ciklikus bonyolultsági száma 6. Ha a

programot lebontjuk, akkor a következýo gráfot kapjuk: 27. ábra Ennek ciklikus bonyolultsága: 4. Kézenfekvýo gondolat egy program bonyolultságát a lebontással elérhetýo ciklikus bonyolultsági számmal mérni. 9.6 DeÞníció: Jelölje k a P programgráf olyan részgráfjainak számát, amelyek az IT E, W D, DU formulák valamelyikével felírhatók. Ekkor a program lényeges bonyolultságán az M (P ) = m (P ) − k számot értjük. 47 Az elýozýo példa esetén M (P ) = 4, ami egyezik a lebontott gráf ciklikus bonyolultságával. Példa (strukturált program) 28. ábra A programgráf ciklikus bonyolultsága 4. Három strukturált részgráfja van, azaz k = 3. Ezért lényeges bonyolultsága M (P ) = 1 Nyilvánvaló a következýo állítás. 9.1 Állítás: A strukturált program lényeges bonyolultsága 1 Megjegyzés: A most tárgyalt program bonyolultsági fogalom csak egy a sok gráfelméleti bázisú programminý oségi mutató közül. 4 Adattípusok és

adatszerkezetek Egy program/algoritmus adatokat alakit át: - input adatok - közbülsýo adatok - output adatok. Az adatoknak bizonyos követelményeket kell kielégiteniük. Alapfogalom: elemi adattípus összetett adattipus, vagy adatszerkezet (bizonyos típusú adatok valamilyen összefüggéssel). A két alapfogalom között nincs éles határ (van amit ide-is, oda is sorolnak). Megjegyzések: 1. Számos axiomatikus felépítés létezik, de nincs általánosan elfogadott 2. Leginkább a program-, vagy metanyelvekhez kötý odý o leírásokat használjuk. Erý os hatása van N. Wirth munkásságának (Pascal, Modula): algoritmusok + adatstrukturák = programok Lásd még pl. ADA nyelv 3. Az adattípusok, adatszerkezetek géptý ol és programnyelvtý ol függnek (implementálásfüggý ok). 48 4. Az adattípusokhoz hozzá kell értenünk a velük végezhetý o mý uveleteket is. 5. Vannak alaptípusok és belý olük létrehozható bonyolultabb, un. strukturált, vagy

összetett típusok (Pascal nyelvvel kezdve). Ezek már adatszerkezeteknek tekinthetý ok. 6. A programozó által deÞniálható összetett adattípus és a vele végezhetý o mý uveletek voltak az objektumorientált programozás elý ofutárai. Legyen L egy programnyelv, D pedig a nyelvben deÞniálható adatok halmaza. Tetszýoleges d ∈ D adatnak pontosan egy meghatározott típusa van Ezért a D halmaz felbontható D = Dt1 ∪ Dt2 ∪ . alakban, ahol t 6= r esetén Dt ∩ Dr = ∅ és T = {t1 , t2 , . } az L nyelvben megengedett típusok azonosítóiból álló halmaz. Eszerint az L nyelv t típusú adatainak halmaza Dt = {d | d ∈ D, tṍpus (d) = t} . Legyen F az L programnyelv mý uveleteinek halmaza. Minden f ∈ F mý uvelet egy f : Dt1 × Dt2 × . × Dtn Dr1 × Dr2 × × Drm alakú leképezés. Formailag a programnyelvet a (D, F ) pár adja meg Adattipusok, adatszerkezetek megadására az alábbi közelítést választjuk: 1. Alap adattípusok 2. Strukturált,

vagy összetett adattípusok 3. Mutató típus A strukturált, vagy összetett típusokat az egyszerý u típusokból képezzük egy konstrukciós elvvel. Tehát a t ∈ T típust, amelyet a t1 , , tn típusokból képezünk, egy C : Dt1 × Dt2 × . × Dtn Dt konstrukciós függvény (konstruktor) és az Si : Dt Dti (i = 1, . , n) szelekciós függvények jellemzik. A C és Si függvények a következýo szabályoknak tesznek eleget: Si (C (d1 , . , dn )) = di (d1 ∈ Dt1 , . , dn ∈ Dtn ) és C (S1 (d) , . , Sn (d)) = d (d ∈ Dt ) . Az alábbiakban felsoroljuk a fýobb adattípusokat. 1. Elemei adattípusok: 49 Egyszerý u (v. skalár, v megszámozható) adattípus Részintervallum típus Szabványos elemi adattípusok (Pascal nyelvben) - logikai (Boolean) - karakter (char) - egész (integer) - valós (real) 2. Struktúrált adattípusok: tömb rekord egyesítés halmaz sorozat rekurzív típus (nem tárgyaljuk) 3. Mutató típus Az elemi adattipusokkat és

a mutató típust itt nem tárgyaljuk. 4.1 A tömb típus Legyen I a valós, vagy egész típust kivéve egy megszámozható, vagy részintervallum típus, T0 pedig tetszýoleges alaptípus. Az I indexhalmazú T0 típusú tömb Pascal deÞníciója: type T = array Iof T0 A T típusú A tömböt az A : DI DT0 leképezéssel, pontosabban ennek értékkészletével azonosítjuk. Tehát a T típus az DI DT0 leképezések halmazaként is felfogható. Legyen I = {i1 , i2 , , in } Ekkor az A leképezés értékkészlete {A [i1 ] , A [i2 ] , . , A [in ]}, ahol A [i] az A értéket jelöli az i ∈ I elemen. Az A tömböt az A [i1 ] i1 A [i2 ] i2 . A [in ] in alakban is ábrázolhatjuk. Tekintve, hogy I rendezett és megszámlálható, a T tömb típust azonosíthatjuk |I| az T0 halmazzal is. Példák: type A =array [1.20] of integer type alkalmazott = (T anaka, N akamura, Kato, Y amamoto) ; jovedelem =array [alkalmazott] of integer Legyen ak = A [ik ] (k = 1, . , n) Ekkor a T

típusú A tömböt az A = T (a1 , . , an ) = T (A [i1 ] , , A [in ]) = (A [i1 ] , , A [in ]) 50 formában írhatjuk fel. A T : DT0n DT függvényt tömbkonstruktornak nevezzük A konstruktor inverz mý uvelete a szelektor, amely a tömb egyes komponenseit választja ki: A [i] az i ∈ I komponensnek megfelelýo érték, [i] : DT DT0 indexfüggvény, T (a1 , . , an ) [i] = ai Az i index kifejezés kiértékelésével is megkapható. Adott i index esetén az i-edik komponens értékét megváltoztathatjuk: A [i] := a ahol a egy T0 típusú adat. Példa: A jovedelem típus esetén a Kato indexý u elem/komponens: A [Kato]. 4.11 Többdimenziós tömbök (mátrixok) Tömbtípusok összetevýoi maguk is lehetnek strukturáltak. Egy tömbváltozót, amelynek komponensei szintén tömbök, mátrixnak nevezünk. Legyen I1 , I2 , , In a valós, vagy egész típust kivéve egy megszámozható, vagy részintervallum típus, T0 pedig tetszýoleges alaptípus. Az n dimenziós

tömb típust a type T = array [I1 ] of array [I2 ] of . of array [In ] of T0 vagy az ekvivalens type T = array [I1 , I2 , . , In ] of T0 elýoírás deÞniálja. Ha A egy T típusú tömb, akkor az A : DI1 × DI2 × . × DIn DT0 leképezés értékkészletével azonosítjuk. Az A tömb egy elemét A [i1 , i2 , . , in ] formában adjuk meg, ahol i1 ∈ I1 , i2 ∈ I2 , . , in ∈ In Ez ugyanaz mint a szelektorok egymásután fý uzésével kapott alak: A [i1 ] [i2 ] . [in ] Példák: T =array [1.10] of array [15] of real T =array [1.10, 15] of real Az elnevezés eredete: A = [aij ]m,n i,j=1 mátrix szokásos alakja:   a11 a12 . a1n  a21 a22 . a2n    A= . , . .   . . . am1 am2 . amn u elem. Az A =array [1m, 1n] of T0 tömb ezzel analóg ahol aij az (i, j) indexý 51 4.2 A rekord típus Legyen T1 , T2 , . , Tn típusazonosító, s1 , s2 , , sn pedig névazonosítók T1 , . , Tn típusokból álló rekord típus

deÞníciója: A = record s1 : T1 ; s2 : T2 ; . sn : Tn end type T Az s1 , . , sn azonosítók a rekord komponensek (mezýok) nevei A T típusú rekordok halmaza DT = DT1 × DT2 × . × DTn Minden d ∈ DT felírható d = (d1 , . , dn ) alakban, ahol di ∈ DTi Ezt a tömbhöz hasonlóan ábrázolhatjuk: d1 s1 d2 s2 . dn sn Példák: type ido =record ora : 1.24 perc : 1.60 sec : 1.60 end Megjegyzés: Ti lehet összetett típusú is. Legyen di ∈ DTi (i = 1, . , n) Ekkor a megfelelýo T típusú d rekordot a d = T (d1 , d2 , . , dn ) = (d1 , d2 , , dn ) konstruktor függvény adja meg. A rekord egyes komponenseit ( mezýoit) az .si : DT DTi (i = 1, . , n) szelektorfüggvények adják meg: d.si = di Teljesülnek a következýo feltételek: T (d1 , d2 , . , dn ) si = di , T (d.s1 , ds2 , , dsn ) = d Az si mezýo értékadása: d.si := di Példák: x.ora = 11; 52 x.perc := 20; x. sec := 35 Megjegyzés: A tömb és rekord közötti azonosságok és

különbségek: 1. Tömbnél T1 = T2 = = TN = T0 2. (Fý okülönbség) A tömb indexei rendezett tipusúak és így adott sorrenben feldolgozható. A rekord komponensei rendezetlenek és nem formálnak egy adott típust. 4.3 Egyesítés típus Legyen A és B két nemüres halmaz. Az A és B halmazok diszjunkt egyesítése A ⊕ B = {(s, 1) | s ∈ A} ∪ {(s, 2) | s ∈ B} . Legyen T1 és T2 két adattípus, t1 és t2 a típusok azonosítói. A két típus T egyesítése a t1 : d1 és t2 : d2 (d1 ∈ DT1 , d2 ∈ DT2 ) párokból áll. Formális deklarációja: type T = union t1 : T1 ; t2 : T2 end Tehát DT = {t1 : d1 | d1 ∈ DT1 } ∪ {t2 : d2 | d2 ∈ DT2 } és a T egyesített típus egy elemét a következýoképpen ábrázolhatjuk: ti di Példa: type coordinate1 = record x, t : real end type coordinate2 = record r : real; θ : angle end type coordinate = union Cartesian : coordinate1; P olar : coordinate2 end 53 Az egyesítés egy lehetséges Pascal

megvalósítása: type ckind = (Cartesian, P olar) coordinate = record ckindof Cartesian : (x, y : real) ; P olar : (r : real; θ : angle) end Megjegyzés: Az egyesítés kettý onél több komponensre is kiterjeszthetý o. Az union szerkezet nem Pascal utasítás. A Pascalban a szerkezetet váltakozó rekordnak hívják (case utasítással valósítják meg) Legyen d ∈ DT . Két eset lehetséges: d vagy t1 : d1 (d1 ∈ DT1 ), vagy t2 : d2 (d2 ∈ DT2 ). Ennek megfelelýoen a T konstrukciós függvényt két részletben adhatjuk meg: T = t1 , vagy T = t2 , ahol ti : DTi DT (i = 1, 2). A di ∈ DTi értékhez a ti : di ∈ DT pár kerül hozzárendelésre. A .ti : DT DTi (i = 1, 2) szelektor függvényeket a következýoképpen adhatjuk meg: ½ ½ d1 , ha d = t1 : d1 deÞniálatlan egyébként d.t1 = d.t2 = deÞniálatlan egyébként d2 , ha d = t2 : d2 A fenti deÞníciókkal teljesülnek a d.ti = (ti : di ) ti = di ti : (d.ti ) = ti : di = d (di ∈ DTi ) (d ∈ DT , d.ti

deÞniált) feltételek. 4.4 Halmaztípus Jelölje [] az üres halmazt, [a.b] részintervallum típusú halmazt, [a, b, c, d, ] felsorolással megadott halmazt. A halmaz típus egy megadott T0 alaptípus részhalmazainak halmazát jelenti. Formális deÞníciója: type T = set of T0 . A T0 típus részhalmazai a DT = 2T0 = {S | S ⊂ DT0 } hatványhalmazt alkotják. Példa: type T =set of [1.3] esetén DT = {[] , [1] , [2] , [3] , [1, 2] , [1, 3] , [2, 3] , [1, 2, 3]} . 54 A halmaztípussal megengedett mý uveletek: 1. A + B (A + B = A ∪ B) 2. A ∗ B (A ∗ B = A ∩ B) 3. A − B (A − B = A B) A logikai relációk: 1. A = B 2. A 6= B 3. A ≤ B ⇐⇒ A ⊂ B 4. A ≥ B ⇐⇒ B ≤ A 5. a in B ½ true, ha a ∈ B ain B = f alse, ha a ∈ /B 4.5 Megjegyzések a tömb és rekord típusokról A tömb és rekord típusok deÞníciója (konstrukciója) igen egyszerý u. 1. Tömb: Legyen T0 egy már deÞniált típus. A T0n = T0 × T0 × . × T0 | {z } n direkt

szorzat elemeit (rendezett elem n-eseket) tekintjük n (hosszúságú) T0 tipusú tömböknek (vektoroknak). A konstrukciós függény: x1 , x2 , . , xn ∈ T0 (x1 , , xn ) ∈ T0n A selector: x[i] (x1 , . , xn ) ∈ T0n xi ∈ T0 A T0 alaptípus maga is lehet tömb. Pl kétdimenziós T0 tipusú tömböt (m×n mátrixot) a T0n tömb m szer önmagával vett direkt szorzatával képezhetünk: T0m×n = T0n × T0n × . × T0n | {z } m 2. rekord: Rekordoknak a T = T1 × T2 × . × Tn | {z } n direkt szorzat elemeit (rendezett elem n-eseket) tekintjük. A Ti típushalmazok között lehetnek azonosak is, de az egyes komponenseket (mezýoket) különbözýonek tekintjük. 55 A konstrukciós függény: x1 ∈ T1 , x2 ∈ T2 , . , xn ∈ Tn (x1 , , xn ) ∈ T A selector: x[i] (x1 , . , xn ) ∈ T xi ∈ Ti Hasonlóan a tömbhöz, képezhetjük a rekordok rekordjait is, és így tovább. A tömb és a rekord asszociatív adatszerkezetek. 4.6 Sorozat típusok

A sorozat típust felfoghatjuk úgy, mint egy T0 típusú adatokból álló változó hosszúságú tömbök (vektorok) halmazát: type T = sequence of T0 . Ennek megfelelýoen DT = ∪∞ n=0 DT0n , ahol T0n = T0 × . × T0 | {z } n Példák: type page =sequence of character type book =sequence of page =sequence of sequence of character Az e1 , e2 , . , en elemekbýol álló T típusú sorozatot T he1 , e2 , . , en i formában jelöljük. Ha n = 0, akkor ezt T hi jelöli, és üres sorozatnak nevezzük Az elemek kiválasztására a következýo függvényeket vezetjük be Legyen x sorozat. a) x [i] - az x sorozat i-edik eleme b) f irst (x) - az x sorozat elsýo eleme c) last (x) - az x sorozat utolsó eleme Ha x = T he1 , e2 , . , en i, akkor x [i] = ei (1 ≤ i ≤ n) , first (x) = e1 , last (x) = en . Tehát [i] , first, last : DT DT0 . Mý uveletek sorozatok elemeivel: a) tail (x) - az x sorozat elsýo elemének elhagyásával nyert sorozat b) initial (x) - az x

sorozat utolsó elemének elhagyásával nyert sorozat c) appendl (x, e) - az e elem x sorozat elé írásával nyert sorozat d) appendr (x, e) - az e elem x sorozat után írásával nyert sorozat. 56 Ha x = T he1 , e2 , . , en i, akkor tail (x) initial (x) appendl (x, e) appendr (x, e) = = = = T he2 , . , en i , T he1 , . , en−1 i , T he, e1 , e2 , . , en i , T he1 , e2 , . , en , ei Értelemszerý uen: tail, initial : DT DT , appendl, appendr : DT × DT0 DT . Teljesülnek a következýo összefüggések: f irst (appendl (x, e)) = e, tail (appendl (x, e)) = x, appendl (tail (x) , f irst (x)) = x, ha x 6= T hi , last (appendr (x, e)) = e, initial (appendr (x, e)) = x, appendr (initial (x) , last (x)) = x, ha x 6= T hi. Bevezetjük még a következýo függvényt: ½ true, ha x = T hi empty (x) = f alse, ha x 6= T hi Háromféle sorozat típust vizsgálunk: 1. Szekvenciális fájl 2. Verem 3. Sor 4.61 Szekvenciális fájl A szekvenciális fájl megadása: type

T = Þle of T0 Példa: type szoveg =Þle of char Az f szekvenciális fájl szerkezetet1 legegyszerý ubben egy mágnesszalagon egymásután elhelyezett adatokkal jeleníthetjük meg: 1A fájl tkp. a külsýo Þzikai tárolási formákból keletkezett 57 f e 1 . f R L . e i-1 e . i . e n író-olvasó fej f : puffer Olvasási helyzet A fájl elemeinek olvasása és írása egy író-olvasó fejen keresztül történik. Egyszerre csak egy adatot lehet olvasni, amelyet az ”író-olvasó fej” pozíciója határoz meg. Ha a pozíció az i-edik elemnél van, akkor a fájl tartalmát két halmazra bontja: fL = he1 , . , ei−1 i , fR = hei , . , en i Az egész fájl tartalma ekkor konkatenációval f = fL fR = he1 , . , ei−1 , ei , , en i Az írás-olvasás egy pufferen keresztül történik, amelynek tartalmát az f ↑ változó tartalmazza. Az f ↑ típusa azonos a fájl elemek típusával A szekvenciális fájloknál 4 mý uveletet (rewrite,

reset, write, read) és egy logikai függvényt (eof) engedünk meg. A szekvenciális fájlban nem lehet az egyes komponenseket felülírni. Az egyetlen lehetséges út a fájl törlése és újraírása. Ezt a rewrite (újraírás) utasítás végzi el. 58 f L =f R =f=< > író-olvasó fej f : puffer Az újraírás eredménye A rewrite (f ) mý uvelet az f := hi értékadást jelenti. Ekkor írhatjuk azt is, hogy rewrite (f) ⇐⇒ fL = hi , fR = hi . Vegyük észre, hogy a rewrite utasítással hozhatunk létre üres fájlt. A reset utasítással az író-olvasó fej a fájl elsýo pozíciójára helyezhetýo: f =< >, L e 1 . . f=f e i-1 R e . i . e n író-olvasó fej f : puffer A reset utasítás eredménye Az eof (f) (end of Þle) logikai függvény a fájl végét jelzi. DeÞníciója: eof (f ) ≡ fR ≡ hi . Tehát eof (f)=true, ha fR = hi, és eof (f ) = false, ha fR 6= hi . A fájlba új elemet írni csak az utolsó elem után

lehetséges a write (Pascalban put (f )) utasítással. 59 f e 1 . . f =< > R L e i-1 e f : . i . e n puffer írási helyzet Az írási pozicióban fR = hi, eof (f ) = true és write (f, e) ⇐⇒ fL = appendr (fL , e) , fR = hi . Figyeljük meg, hogy az írás után, újra írási pozicióba kerülünk. A fájlból olvasni csak az eof (f ) = hamis esetben lehetséges. A read (Pascalban get (f)) olvasási utasítás végrehajtása után az olvasó fej egy pozícióval jobbra mozdul: read (f, e) ⇐⇒ fL = appendr (fL , first (fR )) , fR = tail (fR ) , e = f irst (fR ) . Itt e azt az elemet jelöli, amelynél az író-olvasó fej aktuálisan áll. Megjegyzés: Különbözý o Pascal verziókban a fájl utasítások elnevezései mások is lehetnek. 4.62 Verem A verem olyan sorozattípus, ahol az írás és a törlés a sorozat ugyanazon végén történik (Last in First Out=LIFO): var: s : stack of T0 ; e : T0 Három müvelete van: 1. top - megadja a

sorozat utolsó elemét (verem tetejét): top (s) = last (s) . 2. pop 3. push - törli a sorozat utolsó elemét - új elemet ír a sorozat végére 60 A törlési mý uvelet: sn sn−1 . . pop (s) =⇒ sn−1 . . s2 s1 s2 s1 Képlettel kifejezve: pop (s) ⇐⇒ s = initial (s) . Az írási mý uvelet: sn . . push (s, x) =⇒ s2 s1 x sn . . s2 s1 Képlettel kifejezve: push (s, x) ⇐⇒ appendr (s, x) . 4.63 Sor A sor olyan sorozattípus, ahol az írás a sorozat elején (tkp. végén), a törlés a sorozat végén (tkp. elején) történik (First in First Out=FIFO): var: q : queue of T0 ; e : T0 Két mý uvelete van: 1. enter - új elem írása a sorozat végére 2. leave - a sorozat elsýo elemének törlése Az írási mý uvelet: appendl (q, e) qn . q2 q1 − =⇒ e qn . q2 Képlettel kifejezve: enter (q, e) ⇐⇒ q = appendl (q, e) . A törlési mý uvelet: qn . Képlettel kifejezve: q2 q1 inital (q) − leave (q) ⇐⇒ q = initial (q) . 61 qn

. q3 q2 q1 5 Programozási tételek Programozási feladatok megoldásakor a top-down (strukturált) programtervezés esetén három vezérlési szerkezetet használunk: - szekvencia - elágazás - ciklus Eddig megismertük az alábbi fogalmakat: - állapottér (A = A1 × . × An ) - változó (ai ∈ Ai ) - feladat (F ⊆ A × A) - program (S ⊆ A × A∗∗ ) - programfüggvény (a programfutás eredménye) (p (S) ⊆ A × A) Egy S program megoldja az F feladatot, ha DF ⊆ Dp(S) és ∀a ∈ DF : p (S) (a) ⊆ F (a). A ”megoldás” ellenýorzésére és a programhelyesség részleges bizonyítására bevezettük az elýo- és utófeltétel, valamint a leggyengébb elýofeltétel fogalmát: Legyen Q, R : A L két állítás, S program. A {Q} S {R} szimbólummal jelöltük azt, hogy ∀a ∈ [Q] esetén p (S) (a) ⊆ [R] A [Q] elýofeltétel halmazt felfoghatjuk az állapottér azon részeként, amelyre meg akarjuk a feladat megoldását kapni. Az elérendýo eredmény

megadására szolgál az [R] utófeltétel halmaz. A {Q} S {R} szimbólummal jelölt implikáció igazolása jelenti a parciális programhelyesség igazolását. Az lf (S, R) leggyengébb elýofeltétel a legbýovebb Q elýofeltételt jelenti. Egy feladat megadása (speciÞkációja) a következýoképpen történhet: - bemenýo (input) adatok - kimenýo (output) adatok - a feladatban használt fogalmak deÞníciója - az eredmény kiszámítási szabálya - a bemenýo adatokra kirótt feltételeket (elýofeltételek) - a kimenýo adatokra kirótt feltételek (utófeltételek). Lényeges észrevétel: a feladatok osztályokba sorolhatók a feladat jellege szerint és a feladatosztályokhoz a teljes feladatosztály megoldó algoritmusokat tudunk készíteni. Ezeket a tipus feladatokat programozási tételeknek nevezzük, mert igazolható, hogy megoldásaik a feladat garantáltan helyes megoldásai. A programozási tételek ismeretében a ”legtöbb” feladat megoldása során

”csak” a megfelelýo programozási tételt kell alkalmazni. Így elvileg helyes (de nem mindig optimális) megoldást kapunk. A feladatok olyanok, hogy egy, vagy több adatsokasághoz rendelünk valamilyen eredményt. Egyszerýuség kedvéért feltesszük, hogy ezek sorozatok, amelyeket tömbbel ábrázolhatunk Vizsgált feladatosztály típusok: - egy sorozathoz egy értéket rendelýo feladatok - egy sorozathoz egy sorozatot rendelýo feladatok - egy sorozathoz több sorozatot rendelýo feladatok - több sorozathoz egy sorozatot rendelýo feladatok. 62 5.1 Elemi programozási tételek A feladatok általános alakja: Input Output Q R : : : : n ∈ N0 , x ∈ H n , F : H ∗ G S∈G S = F (x1 , . , xn ) Egy bemenýo sorozattól függýo S értéket kell meghatároznunk. A feladatcsoporthoz több feladattípus tartozik 5.11 Sorozatszámítás Néhány példa: F1. Adjuk meg n alkalmazottból álló osztály bértömegét a bérek ismeretében! F2. Egy m elemý u betý

usorozat betý uit füzzük össze egyetlen szövegtipusú változóba! F3. A Balatonnál k madarász végez megÞgyeléseket Mindegyik megadta, hogy milyen madarakat látott. Készítsünk algoritmust, amely megadja a Balatonnál látott madarakat! F4. Adjuk meg az elsýo n természetes szám szorzatát! A feladatokban közös: adatok sorozatához rendelünk egy értéket, amelyet, egy az egész sorozaton értelmezett függvény ad meg (n szám összege, m betý u konkatenációja, k halmaz uniója, n szám szorzata). Az algoritmus: Változók: n : egész x : tömb(1.n:elemtipus) F0 : elemtipus1 S : elemtipus2 Input Output Q : : : R : {a feldolgozandó sorozat elemszáma} {a feldolgozandó sorozat elemei} {a mý uvelet nulleleme} {az eredmény} n ∈ N0 , x ∈ H n , F : H ∗ G S∈G ∃F0 ∈ G (nullelem) és ∃f : G × H G és F (x1 , . , xn ) = f (F (x1 , , xn−1 ) , xn ) és F () = F0 S = F (x1 , . , xn ) A feladat lehetséges variációi: X Y F = , , ∪, ∩,

∨, ∧, & (konkatenáció) F0 = 0, 1, [] , alaphalmaz, igaz, hamis, ””. A megoldás indukció segítségével: 63 - i = 0 esetre tudjuk az eredmény: F0 , - ha (i − 1)-re tudjuk az Fi−1 eredményt, akkor az i-re az eredményt Fi = f (Fi−1 , xi ) adja (i = 1, . , n) A feladatot megoldó algoritmus: sorozatszámítás(n, x, s) s := F0 for i = 1 : n s := f (s, x (i)) end eljárás vége Az F1. feladat esetén az eljárás: sorozatszámítás(n, x, s) s := 0 for i = 1 : n s := s + x (i) end eljárás vége Az F2. feladat esetén az eljárás: sorozatszámítás(m, x, sz) sz := ”” {üres szöveg} for i = 1 : m sz := sz&x (i) end eljárás vége Az F3. feladat esetén: unio(k, X, H) H := [] for i = 1 : k H := H ∪ X (i) end eljárás vége Végül az F4. feladat esetén: sorozatszámítás(n, x, p) p := 1 for i = 1 : n p := p ∗ x (i) end eljárás vége 64 5.12 Eldöntés A feladat annak eldöntése, hogy a) van-e a sorozatban adott tulajdonságú

elem b) a sorozat mindegyik eleme rendelkezik-e ezzel a tulajdonsággal. Az a) esetben a feladat alakja: Input Output Q R : : : : n ∈ N0 , x ∈ H n , T : H L V AN ∈ L V AN ≡ (∃i (1 ≤ i ≤ n) : T (xi )) Az algoritmus: Függvény: T : elemtṍpus L Változók: n : egész {a feldolgozandó sorozat elemszáma} x : tömb(1.n:elemtipus) {a feldolgozandó sorozat elemei} V AN : logikai {az eredmény} A feladattípus megoldására az elýozýo programozási tétel is alkalmas az F = ∨, f = ∨, F0 = hamis megfeleltetéssel: eldöntés(n, X, S) S := hamis for i = 1 : n S := S ∨ T (x (i)) end eljárás vége Vegyük észre, hogy ha egyszer S igaz lesz, akkor igaz is marad. Tehát nem kell a ciklust végig számolni. Eszerint az igazi megoldó algoritmus: eldöntés(n, x, V AN ) i := 1 while (i ≤ n) ∧ (qT (x (i))) i := i + 1 end V AN := (i ≤ n) eljárás vége A b) esetben a megoldást az adja, hogy átfogalmazzuk: ∀i : 1 ≤ i ≤ n : T (xi ) ≡ @i : 1 ≤ i ≤

n∧qT (xi ) . A sorozatszámítás itt az F = ∧, f = ∧, F0 = igaz értékekkel lehet alkalmazni. 65 A megoldó algoritmus: eldöntés(n, x, MIN D) i := 1 while (i ≤ n) ∧ (T (x (i))) i := i + 1 end M IN D := (i > n) eljárás vége Példa: Döntsük el, hogy egy adott sorozat monoton növekedýo-e! Esetünkben T (xi ) ≡ (xi ≤ xi+1 ) és ezért a ciklus csak (n − 1)-ig mehet. A megoldás: eldöntés(n, x, M ONOT ON) i := 1 while (i ≤ n − 1) ∧ (x (i) ≤ x (i + 1)) i := i + 1 end M ON OT ON := (i > n − 1) eljárás vége 5.13 Kiválasztás A feladat sorozat adott tulajdonságú elemének (indexének) megadása, amelynek létezését feltesszük: Input Output Q R : : : : n ∈ N, x ∈ H n , T : H L SORSZ ∈ N ∃i (1 ≤ i ≤ n) : T (xi ) (1 ≤ SORSZ ≤ n) ∧T (xSORSZ ) Az algoritmus: Függvény: T : elemtṍpus L Változók: n : egész {a feldolgozandó sorozat elemszáma} x : tömb(1.n:elemtipus) {a feldolgozandó sorozat elemei} SORSZ :

egész {az eredmény} A megoldás hasonlít az elýozýo feladattípushoz: kiválasztás(n, x, SORSZ) i := 1 while qT (x (i)) i := i + 1 end SORSZ := i eljárás vége 66 Feladat: A program az elsýo T tulajdonságú elemet adja meg. Hogyan kell módosítani, hogy az utolsó ilyet adja meg? 5.14 Lineáris keresés A feladat adott tulajdonságú elem megadása egy sorozatban, ha van ilyen. Ha nincs, akkor ezt a tényt kell megadni. Tehát az elýozýo két tétel mindegyikét tartalmazza: Input Output Q R n ∈ N , x ∈ H n, T : H L V AN ∈ L, SORSZ ∈ N V AN ≡ (∃i (1 ≤ i ≤ n) : T (xi )) ∧ ∧ (V AN =⇒ (1 ≤ SORSZ ≤ n) ∧ T (xSORSZ )) : : : : Az algoritmus: Függvény: T : elemtṍpus L Változók: n : egész {a feldolgozandó sorozat elemszáma} x : tömb(1.n:elemtipus) {a feldolgozandó sorozat elemei} V AN : logikai {az eredmény - van-e megfelelýo elem} SORSZ : egész {az eredmény -a megfelelýo elem sorszáma} A megoldó algoritmust az eldöntés

algoritmusa adja kiegészítve a kiválasztási algoritmus megfelelýo részével: keresés(n, x, V AN, SORSZ) i := 1 while (i ≤ n) ∧ (qT (x (i))) i := i + 1 end V AN := (i ≤ n) if V AN then SORSZ := i eljárás vége 5.15 Megszámolás A feladat annak meghatározása, hogy hány adott tulajdonságú elem van egy sorozatban: Input : Output Q R : : : Az algoritmus: n ∈ N0 , x ∈ H n , T : H L, χ : H {0, 1} χ (x) = 1, ha T (x) és χ (x) = 0, ha qT (x) DB ∈ N0 P DB = ni=1 χ (xi ) 67 Függvény: T : elemtṍpus L Változók: n : egész {a feldolgozandó sorozat elemszáma} x : tömb(1.n:elemtipus) {a feldolgozandó sorozat elemei} DB : egész {az eredmény -a megfelelýo elemek száma} A feladat egy sorozatszámítás (tkp. összegzés a χ függvény értékeire) A megoldó algoritmus: megszámolás(n, x, DB) DB := 0 for i = 1 : n if T (x (i)) then DB := DB + 1 end eljárás vége 5.16 Maximumkiválasztás A feladat az, hogy válasszuk ki egy sorozat

legnagyobb (legkisebb) elemét: Input Output Q R : : : : n ∈ N0 , x ∈ H n , H rendezett halmaz (∃ <, ≤ reláció) M AX ∈ N n≥1 1 ≤ M AX ≤ n ∧ ∀i (1 ≤ i ≤ n) : xMAX ≥ xi Az algoritmus: Változók: n : egész {a feldolgozandó sorozat elemszáma} x : tömb(1.n:elemtipus) {a feldolgozandó sorozat elemei} M AX : egész {a maximális értéký u elem sorszáma} A sorozatszámításnál F (x1 , . , xn ) = max (x1 , , xn ) és f (x, y) = max (x, y) függvényeket használjuk és az F0 = x1 választást (Nem neutrális elem, de az indexeléssel kompenzáljuk)! A megoldó algoritmus: maximumkiválasztás(n, x, MAX) MAX := 1 for i = 2 : n if x (MAX) < x (i) then MAX := i end eljárás vége 68 Ha a maximális értéket is akarjuk, akkor az algoritmus: maximumkiválasztás(n, x, MAX, M EXERT ) M AX, MAXERT := 1, x (1) for i = 2 : n if MAXERT < x (i) then M AX, MAXERT := i, x (i) end eljárás vége A legkisebb érték meghatározásához a ” <

” relációt át kell írni a ” > ” relációra (A változóneveket is célszerý u átírni a M IN, M IN ERT nevekre). 5.2 Összetett programozási tételek Sorozathoz sorozatot rendelýo feladatokkal foglalkozunk. 5.21 Másolás A bemenýo sorozatot le kell másolni, s közben az elemekre vonatkozó átalakításokat lehet végezni rajta: Input Output Q R : : : : n ∈ N0 , x ∈ H n , f : H G y ∈ Gn −− ∀i (1 ≤ i ≤ n) : yi = f (xi ) Az algoritmus: Függvény: f : H − elemtṍpus G − elemtṍpus Változók: n : egész {a feldolgozandó sorozat elemszáma} x : tömb(1.n:H-elemtipus) {a feldolgozandó sorozat elemei} y : tömb(1.n:G-elemtípus) {a feldolgozott sorozat} A megoldás: másolás(n, x, y) for i = 1 : n y (i) := f (x (i)) end eljárás vége Példa: Egy szöveg minden magánhangzóját cseréljük ki az e betý ure! 69 5.22 Kiválogatás Meg kell adni egy sorozat adott tulajdonságú elemeinek számát és indexeit: Input : Output

Q R : : : n ∈ N0 , x ∈ H n , T : H L, χ : H {0, 1} χ (x) = 1, ha T (x) és χ (x) = 0, ha qT (x) n DB ∈ N0 , y ∈ [1.n] P DB = ni=1 χ (xi ) ∧ y ⊂ [1.n] ∧ ∧ ∀i (1 ≤ i ≤ DB) : T (xyi ) Figyeljük meg, hogy az y tömb hossza elýore nem meghatározható, de legfeljebb n. Az algoritmus: Függvény: T : elemtṍpus L Változók: n : egész {a feldolgozandó sorozat elemszáma} x : tömb(1.n:elemtipus) {a feldolgozandó sorozat elemei} DB : egész {a megfelelýo elemek száma} y : tömb(1.n:egész) {a megfelelýo elemek sorszámai} A megoldás: kiválogatás(n, x, DB, y) DB := 0 for i = 1 : n if T (x (i)) then DB := DB + 1 Y (DB) = i end end eljárás vége Példa: Adjuk meg egy osztály jeles tanulóit! Feladat: Módosítsuk a feladatot és az algoritmust, hogy ne a sorszámokat, de magukat az elemeket gyüjtse ki. 5.23 Szétválogatás A feladat egy sorozat elemeinek szétválogatása két részsorozatba, ahol az egyik sorozatban adott tulajdonságú

elemek, míg a másikban az adott tulajdonsággal 70 nem rendelkezýo elemek vannak: Input : Output Q R : : : n ∈ N0 , x ∈ H n , T : H L, χ : H {0, 1} χ (x) = 1, ha T (x) és χ (x) = 0, ha qT (x) DBY, DBZ ∈ N0 , y, z ∈ H n P DBY = ni=1 χ (xi ) ∧ y ⊂ x ∧∀i (1 ≤ i ≤ DBY ) : T (yi ) ∧ ∧ DBZ = n − DBY ∧ z ⊂ x ∧∀i (1 ≤ i ≤ DBZ) :qT (zi ) Az algoritmus: Függvény: T : elemtṍpus L Változók: n : egész {a feldolgozandó sorozat elemszáma} x : tömb(1.n:elemtipus) {a feldolgozandó sorozat elemei} DBX, DBZ : egész {a megfelelýo sorozatok elemszámai} y, z : tömb(1.n:elemtípus) {a megfelelýo sorozatok elemei} A megoldás: szétválogatás(n, x, DBY, y, z, DBZ) DBY, DBZ := 0, 0 for i = 1 : n if T (x (i)) then DBY := DBY + 1 Y (DBY ) = x (i) else DBZ := DBZ + 1 Z (DBZ) = x (i) end end eljárás vége További változatok és idevágó tételek az irodalomban találhatók (pl. Wirth) 5.3 Rendezések Az alapfeladat egy n

elemszámú sorozat nagyság szerinti sorbarendezése. Ez feltételezi, hogy a sorozat elemeire létezik a ≤, < reláció. Számos megoldó algoritmus létezik és ezekkel külön terület (tantárgy) foglalkozik Input Output Q R : : : : n ∈ N0 , x ∈ H n x ∈ Hn xki rendezett és xki = permutáció (xbe ) Az algoritmus: 71 Változók: n : egész x : tömb(1.n:elemtipus) 5.31 {a feldolgozandó sorozat elemszáma} {a feldolgozandó sorozat elemei} Egyszerý u cserés rendezés: Alapötlete: Hasonlítsuk össze az elsýo elemet a sorozat összes többi mögötte levýo elemével, s ha valamelyik kisebb nála, akkor cseréljük meg ýoket. Ezzel elérhetjük, hogy a sorozat elsýo helyére a legkisebb elem kerül. Folytassuk ugyanígy a sorozat második elemével, stb., utoljára pedig az utolsó elýottivel rendezés(n, x) for i = 1 : n − 1 for j = i + 1 : n if x (i) > x (j) then csere (x (i) , x (j)) end end eljárás vége Az eljárás helyigénye: n + 1. Az

összehasonlítások száma: n (n − 1) /2 A cserék száma 0 és n (n − 1) /2 (Miért?). 5.32 Minimumkiválasztásos rendezés Az elýozýo rendezési eljárásban sok a felesleges csere. Ehelyett az aktuális elsýo elemet a mögötte lévýok közül egyedül a legkisebbel cseréljük ki. Ehhez a rendezýo ciklus belsejében egy minimumkeresést kell csinálni. rendezés(n, x) for i = 1 : n − 1 MIN := i for j = i + 1 : n if x (MIN ) > x (j) then M IN := j end csere(x (i) , x (M IN)) end eljárás vége Az eljárás helyigénye: n + 1. Az összehasonlítások száma: n (n − 1) /2 A cserék száma: n − 1 (Miért?). 5.4 Keresések Fontossága miatt szintén külön terület. Két esettel foglalkozunk 72 5.41 Lineáris keresés rendezett sorozatban Adott egy rendezett sorozat, amelyben egy adott értéký u elem sorszámát kell meghatározni, ha az benne ven a sorozatban: Input Output Q R : : : : n ∈ N, x ∈ H n , y ∈ H V AN ∈ L, SORSZ ∈ N0 rendezett

(x) V AN ≡ (∃i (1 ≤ i ≤ n) : xi = y) ∧ ∧V AN =⇒ (1 ≤ SORSZ ≤ n) ∧ xSORSZ = y Az algoritmus: Változók: n : egész x : tömb(1.n:elemtipus) y : elemtipus V AN : logikai SORSZ : egész A megoldó algoritmus: {a feldolgozandó sorozat elemszáma} {a feldolgozandó sorozat elemei} { a keresett elem} {az eredmény - van-e megfelelýo elem} {az eredmény -a megfelelýo elem sorszáma} keresés(n, x, y, V AN, SORSZ) i := 1 while (i ≤ n) ∧ (x (i) < y) i := i + 1 end V AN := (i ≤ n) ∧ (x (i) = y) if V AN then SORSZ := i eljárás vége Az algoritmus az y érték elsýo elýofordulását választja ki. Egy keresés minimum 1, maximum n, átlagosan pedig (n + 1) /2 összehasonlítással jár 5.42 Logaritmikus keresés rendezett sorozatban A sorozat rendezettségét a következýoképpen használhatjuk ki. Vizsgáljuk meg elsýo lépésben a sorozat középsýo elemét. Ha ez a keresett elem, akkor készen vagyunk. Ha a keresett elem ennél kisebb, akkor csak

az ezt megelýozýoek között lehet, tehát a keresést a továbbiakban a sorozat elsýo felére kell alkalmazni. Ha a keresett elem ennél nagyobb, akkor ugyanezen elv miatt a keresést a sorozat 73 második felére kell alkalmazni. keresés(n, x, y, V AN, SORSZ) e, u := 1, n do k := entier ((e + u) /2) if y < x (k) then u := k − 1 if y > x (k) then e := k + 1 until (e ≤ u) ∧ (x (k) 6= y) V AN := (e ≤ u) if V AN then SORSZ := k eljárás vége Az algoritmus az y érték valamelyik elýofordulását választja ki. Egy keresés minimum 1, maximum log2 n + 1, átlagosan pedig log2 n összehasonlítással jár. Innen az eljárás elnevezése. 5.5 Programozási tételek egymásra építése Ha programozási tételeket egymásután kell alkalmaznunk, akkor gyakran elýonyös a két megoldó algoritmus egybeépítése. Néhány esetet tárgyalunk 5.51 Másolással összeépítés A másolással bármelyik programozási tétel egybeépíthetýo: A programozási

tételben szereplýo xi hivatkozást kicseréljük g (xi )-re, ahol g a másolásnál szereplýo függvényt jelöli. 1. Példa: számsorozat elemeinek négyzetösszege=másolás (négyzetre emelés)+ sorozatszámítás (összegzés) Az általános feladat a következýo: Input Output Q : : : R : n ∈ N0 , x ∈ H n , F : G∗ G, g : H G S∈G ∃F0 ∈ G és ∃f : G × H G és F (y1 , . , yn ) = f (F (y1 , , yn−1 ) , yn ) és F () = F0 S = F (g (x1 ) , . , g (xn )) Az algoritmus: Függvény: g : H-elemtípus G-elemtípus Változók: n : egész {a feldolgozandó sorozat elemszáma} x : tömb(1.n:H−elemtipus) {a feldolgozandó elemek} F0 : G-elemtípus {a mý uvelet nulleleme} S : G-elemtípus {az eredmény} 74 A megoldás: Másolás sorozatszámítás(n, x, s) s := F0 for i = 1 : n s := f (s, g (x (i))) end eljárás vége 2. Példa: Másolás és maximumkiválasztás egybeépítése a maximális elem értékének és indexének meghatározásával. A feladat

leírása: Input Output Q R : : : : n ∈ N0 , x ∈ H n , H rendezett halmaz (∃ <, ≤ reláció), g : H G M AX ∈ N n≥1 1 ≤ MAX ≤ n ∧ ∀i (1 ≤ i ≤ n) : g (xMAX ) ≥ g (xi ) Az algoritmus: Függvény: g : H-elemtípus G-elemtípus Változók: n : egész {a feldolgozandó sorozat elemszáma} x : tömb(1.n:H-elemtipus) {a feldolgozandó sorozat elemei} M AX : egész {a maximális értéký u elem sorszáma} M AXERT :G-elemtípus {a maximális érték} Másolás maximumkiválasztás(n, x, MAX, M AXERT ) M AX, MAXERT := 1, g (x (1)) for i = 2 : n if MAXERT < g (x (i)) then M AX, MAXERT := i, g (x (i)) end eljárás vége 75 5.6 A gyorsrendezés Az alapfeladat egy n elemszámú sorozat nagyság szerinti sorbarendezése. Input Output Q R : : : : n ∈ N0 , a ∈ H n a ∈ Hn aki rendezett és aki = permutáció (abe ) Az algoritmus: Változók: n : egész {a feldolgozandó sorozat elemszáma} a : tömb(1.n:elemtipus) {a feldolgozandó sorozat elemei}

A gyorsrendezést C.AR Hoare alkotta 1962-ben Alapötlete: az a (1) , . , a (n) tömb felbontása két ”összefüggõ” résztömbre: {a (1) , . , a (loc)} , {a (loc + 1) , . , a (n)} úgy, hogy baloldali résztömb elemei kisebb, vagy kisebb-egyenlõk legyenek a jobboldali résztömb elemeinél. Ennek egy lehetséges módja a következõ: 1. Vegyük az elsõ elemet és legyen loc = 1 2. Hasonlítsuk össze az elemeket jobbról balra és álljunk meg az elsõ a (jobb) elemnél, amelyikre a (jobb) < a(1). 3. Cseréljük fel az a (1) és a (jobb) elemeket és legyen loc = jobb (Megjegyzés: a (loc) = a (1)-tõl jobbra csak nála nagyobb elemek vannak.) 4. Hasonlítsuk össze most az elemeket balról jobbra az [1jobb] intervallumban és álljunk meg az elsõ a (bal) elemnél, amelyre a (bal) > a(loc) 5. Cseréljük fel az a (bal) és a (loc) elemeket és legyen loc = bal (Megjegyzés: a (bal) = a (1)-tõl balra csak nála kisebb elemek vannak, a (jobb)-tól jobbra csak a

(1)-nél nagyobb.) 6. Ismételjük meg a 2-5 pont eljárását a [baljobb] intervallumon, amíg bal ≤ jobb. Az eljárás eredményeként a sorozat egy olyan felosztását kapjuk, amelyben baloldali rész sorozatban az eredeti a (1) − tõl kisebb, vagy kisebb-egyenlõ elemek vannak a, a jobboldali részsorozatban pedig a nála nagyobbak, vagy nagyobb egyenlõk. A loc változó az eredeti a (1) helyét mutatja az ”átrendezett” sorozatban. FONTOS: a részhalmazok általában NEM rendezettek!!! Megjegyezzük, hogy vannak más felosztási eljárások is, ahol egy tetszõleges x tömb elemmel történnek az összehasonlítások. 76 Példa: Tekintsük a következõ 12 elemû tömböt: 44∗ 33 11 55 77 90 40 60 99 22 88 66 Jobbról-balra pásztázva 22 az elsõ 44-nél kisebb elem. Csere után kapjuk, hogy 22♦ 33 11 55 77 90 40 60 99 44∗ 88 66 Balról-jobbra pásztázva az 55 az elsõ 44-nél nagyobb elem. Csere után a sorozat: 22 33 11 44∗ 77 90 40 60 99 55♦ 88

66 Jobbról (55-tõl) balra pásztázva 40 az elsõ 44-nél kisebb elem. A csere eredménye: 22 33 11 40♦ 77 90 44∗ 60 99 55♦ 88 66 Ismét balról-jobbra pásztázva 77 az elsõ 44-nél nagyobb szám. A felcserélés után kapjuk,hogy 22 33 11 40 44∗ 90 77♦ 60 99 55♦ 88 66 Jobbról-balra pásztázva kapjuk, hogy a maradék intervallumban minden elem (77, 90) nagyobb mint 44. Tehát kaptuk az eredeti sorozat következõ felosztását: {22, 33, 11, 40, 44} {90, 77, 60, 99, 55, 88, 66} . Az alábbi eljárás a fenti felosztó algoritmust valósítja meg egy tömb tetszõleges összefüggõ résztömbjén. 77 function [a,loc]=feloszt2(a,n,i1,j1) % feloszto algoritmus % Az a(1:n) tomb a(i1),.,a(j1) elemeit atrendezi,hogy % a(t)<=a(loc), i1<=t<loc % a(loc)<=a(j), loc<j<=j1 % % input valtozok: % a - n dimenzios tomb % n - a tomb merete % i1 - also index hatar % j1 - felso index hatar (i1<=j1) % output valtozo % a - a reszben

atrendezett/felosztott tomb % loc - az a(i1) elem helye % ========================= bal=i1; jobb=j1; loc=i1; while i1<=j1 % pasztazas jobbrol balra while a(loc)<=a(jobb) & loc~=jobb jobb=jobb-1; end if loc==jobb return end if a(loc)>a(jobb) temp=a(loc); a(loc)=a(jobb); a(jobb)=temp; loc=jobb; end % pasztazas balrol jobbra while a(bal)<=a(loc) & bal~=loc bal=bal+1; end if loc==bal return end if a(bal)>a(loc) temp=a(loc); a(loc)=a(bal); a(bal)=temp; loc=bal; end end 78 Ezután a Hoare-féle quicksort eljárás a következõ: Addig daraboljuk a sorozatot a fenti felosztó eljárással, amíg az összefüggõ részsorozatok hossza 2 alá nem csökken. Mivel egyszerre csak egy részsorozatot vizsgálhatunk, a többi részsorozatot valamilyen módon nyilván kell tartani Ehhez két verem szerkezet kell: verembal, veremjobb amelyek a részsorozatok bal és jobboldali indexhatárait tartalmazzák. Egy sorozat akkor kerül feldolgozásra, ha a bal és jobboldali

indexhatárát eltávolítjuk a verem tetejérõl. A felosztás után a legalább két tagot tartalmazó részsorozat bal és jobboldali indexhatárát a verembe visszahelyezzük. Az eljárást megvalósító program: function a=quicksort2(a,n) % Hoare quick sort algoritmusa % input valtozok: % a - n dimenzios tomb % n - tomb meret % output valtozok: % a - rendezett tomb % meghivott eljaras: % [a,loc]=feloszt2(a,n,i1,j1) %====================== top=0; if n>1 top=top+1; verembal(top)=1; veremjobb(top)=n; end while top>0 % resztomb kivetele a verembol bal=verembal(top); jobb=veremjobb(top); top=top-1; [a,loc]=feloszt2(a,n,bal,jobb); % a baloldali reszlista verembe rakasa, ha legalabb 2 eleme van if bal<loc-1 top=top+1; verembal(top)=bal; veremjobb(top)=loc-1; end % a jobboldali reszlista verembe rakasa ha legalabb 2 eleme van if loc+1<jobb top=top+1; verembal(top)=loc+1; veremjobb(top)=jobb; end end 79 Az eljárás legrosszabb esetben n (n + 1) /2 összehasonlítást

igényel. Ez akkor következik be, ha a sorozat már rendezett. Ekkor az 1 elem n összehasonlítás után marad a helyén Az elsõ részlista az {a (1)} elemet, a második az {a (2) , . , a (n)} elemeket fogja tartalmazni Itt az a (2) a helyén marad n − 1 összehasonlítás után. És így tovább Az összehasonlítások száma tehát n + (n − 1) + (n − 2) + . 2 + 1 = n (n + 1) n2 = + O (n) . 2 2 Az átlagos összehasonlítás szám azonban ≈ 1.4n log n, ami majdnem eléri az elvi, optimális értéket. A fenti programban a verem méretét nem kellett elõre megadni (dimenzionálni). Feladat: Mekkorára válasszuk a verem méretét, ha meg kell adni elõre? 5.7 Programhelyesség igazolása Egy un. blokkdiagram program helyességét igazoljuk teljes indukcióval Anderson könyve alapján Feladat: n X xj j=1 meghatározása. A feladat a sorozatszámítás programozási tétel speciális esete. Tekintsük az alábbi blokkdiagram sémát: 80 START 1 SUM=0 I=1 2

False 4 I<=N STOP True SUM=SUM+XI I=I+1 3 . , XN N -dimenziós valós tömb. Az 1. pontban, kiinduláskor, X1 , X2 , P P I−1 A 2. pontban 1 ≤ I ≤ N + 1, SU M = j=1 Xj ( 0j=1 Xj = 0). P A 4. pontban SUM = N j=1 Xj . A séma helyességét teljes indukcióval (kettõs indukció) igazoljuk. Jelölje n azt, hogy a 2. pontot hányadszorra értük el (0 ≤ n ≤ N + 1) Legyen ekkor In az I változó értéke, a SU Mn pedig a SU M változó értéke. 1. A 2 pont elsõ elõfordulásakor n = 1, I1 = 1, 1 = 0. PISUM P 1 −1 Minthogy 1 ≤ I1 < N + 1, SUM = SU M1 = j=1 Xj = 0j=1 Xj = 0, az elsõ elõforduláskor kapott eredmény helyes. 2. Tegyük fel, P hogy a 2. pontnál vagyunk, 1 ≤ In ≤ N + 1, In = n, In −1 Xj . SU M = SU Mn = j=1 Ha In ≤ N , akkor folytatjuk a ciklust, In+1 = In + 1 és SU Mn+1 = SU Mn + XIn = (X1 + . + XIn −1 ) + XIn = In X Xj . j=1 Továbbá 2 ≤ In+1 = In + 1 = n + 1 ≤ N + 1. Tehát I = n + 1 és SU M = SU Mn+1 = n X j=1 Xj = I X

Xj . j=1 Ha In = N +1, akkor kilépünk a ciklusból és ekkor I = N +1, SUM = Tehát a blokkséma program helyességét igazoltuk. 81 PN j=1 Xj . Feladat: Mit csinál az alábbi program? Igazoljuk a helyességét! START I=M J=0 True I=0 False STOP J=J+N I=I-1 6 Listák A láncolt lista egy olyan dinamikus adatszerkezet, amelyben az objektumok lineáris sorrendben követik egymást. A lista méretét felülrõl csak a rendelkezésre álló tároló helyek korlátozzák. Listák felhasználása számos helyen célszerû. Legegyszerûbb esetben egy listaelem két részbõl áll: ADAT MUTATÓ Az adat rész tartalmazza a tényleges információt, a mutató rész pedig hivatkozást a következõ listaelemre (a következõ listaelem címét). A létrehozható listaszerkezet elnevezése: Egyszerûen kapcsolt, vagy lineáris lista. 1 2 3 n-1 P n . A P változó (mutató) az elsõ listaelem címét tartalmazza. A ∅, vagy NIL jel a lista végét jelzi. A szimmetrikus

lista elemek az adatmezõn kívül két mutatót tartalmaznak: 82 BM ADAT JM a BM és a JM mutatót. A BM mutató az elõzõ (baloldali) szomszéd címét, a JM mutató pedig a következõ, jobboldali szomszéd címét tartalmazza. A szimmetrikus listaelemekbõl álló, szimmetrikus lista általános alakja: 1 2 3 n . B J Itt a B mutató az elsõ listaelem, a J mutató pedig az utolsó listaelem címét tartalmazza. Tömbök segítségével könnyen hozhatunk létre lineáris listákat. Kell két tömb: adat (N ) , mutató (N ) , ahol N a tárolandó adatok száma. Az {adat (i) , mutató (i)} páros képez egy listaelemet. A mutató (i) tartalma a következõ listaelem indexe A lista végén ∅ = NIL = 0. Példa: Tekintsük az alábbi két tömböt 1 2 P 9 3 O 6 4 T 0 6 11 7 X 10 5 8 9 N 3 10 I 4 11 E 7 12 A példán látható, hogy a két tömb hézagosan van kitöltve. Legalább két listát szokás létrehozni. A tényleges listán

túlmenõen létrehozzuk a rendelkezésre álló szabad tárolóhelyek listáját is Új adat listába való 83 elhelyezésekor a szabad tárolóhelyek listájából elveszünk, adat törlésekor pedig a szabad tárolóhelyek listájához hozzáteszünk. A lineáris lista szekvenciális feldolgozása: n o Legyen T a lista elem indexe, ADAT (T ) , M UT AT Ó (T ) pedig a T -ik listaelem. T ← P {Az elsõ listaelem címe} while T 6= ∅ W ← ADAT (T ) W feldolgozása T ← M U T AT Ó (T ) end Megjegyzés: Ha nincs feldolgozás, akkor csak bejárásról beszélünk. 6.1 Mûveletek listákban 1. Új adatelem beszúrása listába: A mûvelet sematikus képe a következõ: A k-ik és a (k + 1)-ik adatelem közé teszünk be új adatelemet. ez a kapcsolat törlésre kerül k-ik adatelem (k+1)-ik adatelem új adatelem A mûvelet megvalósítása (programrészlet): M U T AT Ó (T ) ← M U T AT Ó (k) M U T AT Ó (k) ← T 2. Lista elem törlése: A mûvelet sematikus képe a

következõ (a k-ik elemet töröljük): k-1 k k+1 A mûvelet lehetséges megvalósításai (programrészletek): 84 1. Változat (A (k + 1)-ik elem elõre ”csúszik” a k-ik helyére): T ← M U T AT Ó (k) if T = ∅ then hibajelzés és exit ADAT (k) ← ADAT (T ) M U T AT Ó (k) ← M UT AT Ó (T ) 2. Változat (minden elem a helyén marad): M U T AT Ó (k − 1) ← M UT AT Ó (k) Számos probléma merül fel az üres listák és a listák utolsó elemeinek kezelésével. A lehetséges megoldások a következõk. Listafej Az üres listákkal való problémák elkerülésére vezetjük be a listafejet: 1 P 0 listafej Így a lista hossza soha nem lesz zérus. A listafej tartalmazhat lista információkat (pl az elemek aktuális számát) Ciklikus lista A ciklikus, vagy cirkuláris lista az utolsó elemekkel való bajlódást kivánja csökkenteni. 1 2 n-1 n P A lista végén egy mutatót helyezünk el, amely az elsõ elemre mutat. Itt a listafej mutatója P a

jobb oldalon van. A problémát ennél a megoldásnál az jelenti, hogy nem tudjuk a lista végét. Ennek a megoldása a ciklikus lista listafejjel: listafej 1 2 n-1 n P A lista szekvenciális feldolgozásának végét a listafej elérése jelzi. Megjegyezzük, hogy a szimmetrikus listákat is el szokás listafejjel látni. 85 Verem ábrázolása listával: alsó elem felsõ elem V 0 A következõ lista mûveleteknél feltételezzük, hogy rendelkezésünkre áll a szabad helyek listája is, amelynek fejét az Ü változó jelzi. Új elem behelyezése a verembe: alsó elem felsõ elem V 0 Ü 0 új elem helye Az új elemet az üres helyek listájából elvett helyre tesszük és a mutatókat átirányítjuk mindkét listában. Felsõ elem törlése verembõl: alsó elem felsõ elem V 0 Ü 0 A verem felsõ elemét úgy töröljük, hogy a verem listafej mutatóját a következõ elemre irányítjuk, a törölt felsõ elemet pedig az üres helyek listájának

tetejére tessszük. 86 Sor ábrázolása lineáris listával fej 1 2 utolsó elem S 0 A listafej két mutatót tartalmaz. A bal mutató a sor utolsó elemére (a lista végére) mutat. Üres sor esetén a bal mutató sajátmagára (a listafejre) mutat: S 0 A sorból történõ olvasás, törlés ugyanaz mint a verem esetében. Beírás sorba utolsó elem után: 1 2 S Ü y 0 0 Az új y adatelem helyét elvesszük az üres helyek listájáról és mindkét listán a megfelelõ mutatókat átállítjuk. Vegyük észre, hogy az új elemhez kerül a NIL jelzés. 3. Keresés listában Két változatot nézünk meg. 1. Keresés rendezetlen listában: Legyen a keresett adat (tétel) X. Az X-et tartalmazó listaelem címe -LOCkell A megoldást a ”lineáris lista szekvenciális feldolgozása” algoritmus adja: 87 T ←P while T 6= ∅ if ADAT (T ) = X LOC ← MU T AT Ó (T ) exit endif T ← M U T AT Ó (T ) endwhile Legrosszabb esetben n összehasonlítás kell.

Általános esetben n/2 a várható összehasonlítás szám. 2. Keresés (növekvõen) rendezett listában: Itt nem alkalmazhatjuk a logaritmikus keresést, mert nem tudjuk indexelni a középsõ elemet. T ←P while T 6= ∅ if ADAT (T ) < X then T ← M U T AT Ó (T ) else if ADAT (T ) = X then LOC = M U T AT Ó (T ) exit else LOC = ∅ exit endif endwhile LOC = ∅ 4. Adatok rendezése lineáris listában A feladat: ADAT (1) ≤ ADAT (2) ≤ . ≤ ADAT (N) A megoldás alapötletei: 1. Az adatokat úgy szúrjuk be egy listába, hogy a rendezettség megmaradjon 2. Két mutatót használunk A rendezett lista feje legyen R. A beszúrás sémáját mutatja az alábbi ábra: 1 R i-1 i n MIN 0 T1 T2 W ADAT(T1)<=W<=ADAT(T2) 88 A M IN egy olyan adat, amelyik mindegyik rendezendõ adatnál kisebb. Ezért mindig a lista elsõ eleme marad. A W adatot a következõ program részlettel helyezzük el a listában a T1 és T2 elemek között: T1 ← R T2 ← M U T AT Ó

(R) while T2 6= ∅ and W · ADAT (T2 ) do T1 ← T2 T2 ← M U T AT Ó (T2 ) enddo endwhile Az általános rendezési algoritmus ezekután a következõ (feltételezve, hogy az adatokat egy fájlból olvassuk be): 1. Ü (üres helyek) lista létrehozása 2. Az R (rendezõ) lista (fejének) levágása az Ü üres helyek listájáról 3. ADAT (R) ← MIN , MU T AT Ó (R) ← ∅ 4. W beolvasása: while W 6= eof W elhelyezése a listában end 6.2 Megjegyzések 1. A listáknak még más változatai is léteznek 2. A listaelem általánosítható (multilista), amely segítségével a hierarchikus és hálós adatszerkezeteket tudjuk megvalósítani. 3. Speciális hierarchikus szerkezetben, a bináris fa esetén, amikor egy csomópontból legfeljebb két él indul (vagy két részfa tartozik hozzá), akkor kétszeresen láncolt listával könnyen ábrázolhatjuk, ahol a balmutató a baloldali részfa gyökerére, a jobbmutató a jobboldali részfa gyökerére mutat. Példa:

Tekintsük a következýo bináris fát: a c b d e bináris fa 89 f A megfelelýo lista ábrázolás: gyökér a b c . d e f a bináris fa listás ábrázolása 90 7 Irodalom S. Alagić, MA Arbib: The Design of Well-Structured and Correct Programs, Springer, 1978 R. B Anderson: Proving Programs Correct, Wiley, New York, 1979 Andrásfai Béla: Gráfelmélet, Polygon, Szeged, 1997 Bárdos Attila: A programbizonyítás alapjai, SZÁMOK, Budapest, 1979 J.L Bentley: A programozás gyöngyszemei T.H Cormen-CE Leiserson-RL Rivest: Algoritmusok, Mûszaki Könyvkiadó, 1998 O.J Dahl, EW Dijkstra-CAR Hoare: Strukturált programozás, Mý uszaki Könyvkiadó, 1978 E.W Dijkstra: A Discipline of Programming, Prentice-Hall, Inc, Englewood Cliffs, N.J, 1976 Fóthi Ákos: Bevezetés a programozáshoz, ELTE jegyzet, Tankönyvkiadó, Budapest, 1984 Fóthi Ákos, Steingart Ferenc: Programozási módszertan, kézirat, ELTE, 1999 D. Gries: The Science of Programming, Springer,

1981 Hajnal Péter: Gráfelmélet, Polygon, Szeged, 1997 Dr. Hetényi Pálné (szerk): Programozási feladatok 2000-ig I-II, OMIKK B.W Kernighan-B Plauger: A programozás magasiskolája, Mý uszaki Könyvkiadó D. Knuth: A számítógép programozás mý uvészete I-III, Mý uszaki Könyvkiadó, 1988 S. Lipschutz: Data Structures, MacGraw-Hill, 1986 (van magyar fordítás is) Z. Manna: Lectures on the Logic of Computer Programming, SIAM, Philadelphia, 1980 Z. Manna: Programozáselmélet, Mý uszaki Könyvkiadó, J.G Sanders: A Relational Theory of Computing, Lecture Notes in Computer Science, Vol 82, Springer, 1980 Szlávi Péter, Zsakó László: Módszeres programozás: Programozási tételek, µlógia 19, ELTE TTK, 1999 Varga László: Programok analízise és szintézise, Akadémiai Kiadó, Budapest, 1981 N. Wirth: Algoritmusok+adatstruktúrák=programok, Mý uszaki Könyvkiadó, 1982 91