Programozás | Programozás-elmélet » Dr. Strauber Györgyi - Programozás módszertan

-1- Dr. Strauber Györgyi PROGRAMOZÁS MÓDSZERTAN -2- A modul tartalma - matematikai ismétlés (gráfelmélet) - a program matematikai fogalma, a programgráf - valódi program, struktúrált program, struktúrált programozás - absztrakt adatszerkezetek analízise, az O.OP elméleti alapjai - fastruktúra, fabejárási algoritmusok, alapvető műveletek fákon - programhelyesség-bizonyítás Kapcsolódó modul Gyakorlat ! Követelmények, értékelés 45/16-os modul. Felmérés: 6. héten: felmérő teszt: 50 pont / javítás nincs / 9. héten: vizsgadolgozat: 50 pont / teszt + feladat / Értékelés: Pont 0-50 51-60 61-70 71-80 81-100 jeles Érdemjegy elégtelen elégséges közepes jó (5) (1) (2) (3) (4) Irodalom Demetrovics-Denev-Pavlov: A számítástudomány matematikai alapjai Lipschutz: Adatszerkezetek, Számítástechnika középfokon Varga László: A programozási módszertan elmélete I., II kötet Aszalós-Erki: Bevezetés a struktúrált programozásba

-3- Bevezetés. A szükséges matematikai alapfogalmak átismétlése GRÁFELMÉLET A leggyakrabban használt jelölések: ∈ : eleme ( x∈V) ⊂ : részhalmaza (V 1 ⊂ V 2 ) ∩ : metszete ∪ : uniója ∀ : minden ( ∀ x ∈V) (univerzális kvantum) ∃ : létezik ( ∃ x ∈V) (egzisztenciális kvantum) ∃ ! : egyértelműen létezik ( ∃ ! x ∈V) ∃ : nem létezik : olyan hogy ( ∃ ! x ∈V 1 x ∉V 2 ) x : Descartes-szorzat t.fh : tegyük fel, hogy GRÁF: - IRÁNYÍTOTT - IRÁNYÍTATLAN Irányítatlan gráfok Definíció: G irányítatlan gráf, ha G = (V,E) kettős, ahol V a csúcsok, E az élek halmaza, továbbá E ⊂ V x V (rendezetlen párok) Definíció: G 1 részgráfja G-nek, ha G 1 = (V 1 , E 1 ), ahol V 1 ⊂ V és E 1 ⊂ E . Definíció: G 1 feszítő részgráfja G-nek, ha V 1 = V Példa G G1 1 2 feszítő részgráf 1 4 2 4 3 3 Definíció: G 1 telített részgráfja G-nek, ha E 1 = V 1 x V 1 ∩ E. Példa G G 1 telített 1 2 1 4 3 G 2

nem telített 2 1 2 3 3 -4- Definíció: Egyszerű gráf: ∃ hurok, ∃ többszörös él. hurok többszörös él 1 1 2 Definíció: Gráfok metszete, uniója: G 1 ∩ G 2 = (V 1 ∩ V 2 , E 1 ∩ E 2 ) G 1 ∪ G 2 = (V 1 ∪ V 2 , E 1 ∪ E 2 ) Definíció: Csúcsok fokszáma: d(x), x∈ V csúcs fokszáma a belőle induló élek száma. Definíció: Izolált pont: Az a csúcs, melyre d(x)=0. Példa d(1)=2 , d(2)=d(3)=1 , d(4)=0 ( izolált pont ) 1 2 3 4 Definíció: Élsorozat: [x 1 ,x 2 ] [x 2 ,x 3 ] [x 3 ,x 4 ]. [x n-1 ,x n ] tetszőleges élek sorozata, ahol [x i ,x i+1 ]∈E ; i=1,.,n-1 Vonal: Olyan élsorozat, melyben ∀ él különböző. Út: Olyan nyílt élsorozat (x 1 ≠x n ) , melyben ∀ csúcs különböző. Kör: Olyan zárt élsorozat (x 1 ≠x n ) , melyben ∀ csúcs különböző. Példa [3,1] [1,2] [2,3] [3,4] [4,2] [2,1] 1 élsorozat, de nem vonal [1,2] [2,3] [3,1] [1,4 ] vonal, de nem út 2 3 4 1 2 3 4 -5- [1,4] [4,3] [3,1] Kör

1 2 3 4 Tétel: Ha x 1 és x n között ∃ élsorozat, akkor ∃ út is. Definíció: G összefüggő (öf.), ha ∀ két csúcs között ∃ út Példa nem öf. nem öf. öf. 1 2 1 2 1 2 3 4 3 4 3 4 H H C C H H Állítás: |V| = n esetén |E| ≥ n-1, ha G öf. Bizonyítás: Teljes indukció. 1., n=2 esetén igaz. U i: (legalább 1 él kell az öf.-séghez) 2., T.fh |V| = n esetén igaz 3., Lássuk be |V| = n+1 esetében is. 1 2 n csúcsú öf. gráf |E| ≥ n-1 az ind. felt miatt n+1 csúcs. Legalább 1 él kell, hogy ne legyen izolált pont ⇒ |E| ≥ n-1+1=n Definíció: Fa: Összefüggő, körmentes gráf. Állítás: n csúcsú fa éleinek száma = n-1. Példa Telített szénhidrogének: metán etán H H C H H H H -6- Definíció: Feszítőfa: Ha F feszítőrészgráfja G-nak és F fa, akkor F-t G feszítőfájának nevezzük. F2 Példa G F1 1 2 1 2 1 2 3 4 3 4 3 4 Állítás: ∃ G-nek feszítőfája ⇔ G öf. Bizonyítás:

⇒ triviális ( fa eleve öf. ) ⇐ : konstruktív Ha öf. és ∃ kör ⇒ fa Ha öf. és ∃ kör ⇒ elhagyunk a körből egy élt, ez öf marad - ha fa ⇒ kész - ha nem ⇒ folytatom Megjegyzés: Legyen |V| = n ; |E| = m Az eljárás során m-(n-1) élt hagyok el. Definíció: Ciklikus szám ( ciklometrikus szám, nullitás ) ν(G):= m-n+1 Megjegyzés: G öf esetén: Ha ν(G)=0 ⇒ G fa ν(G)=1 ⇒ 1 kör van ν(G)≥1 ⇒ legalább ν(G) kör van ν(G)=5-4+1=2 körök száma =3 1 2 3 4 Irányított gráfok Definíció: Egyszerű irányított gráf a G = (V,E) kettős, ahol V a csúcsok, E az élek halmaza, E = {<x,y>, x≠y, rendezett párok, x ,y ∈ V } ; ( <x,y> és <y,x> megengedett, de hurok és többszörös él nem ) Megjegyzés: G-hoz hozzárendelhető egy G irányítatlan gráf az alábbi módon: Ha G = (V,E), akkor G=(V,E) V(G)=V(G), E = { [x,y] | <x,y> ∈ E vagy <y,x> ∈ E } Példa G G 1 2 1 2 -7- 3 4 3 4 Definíció:

Csúcsok fokszáma: d be (x) : e= <y,x> élek száma d ki (x) : e= <x,y> élek száma d(x)= d be (x) + d ki (x) Megjegyzés: ∑ d be (x) = x ∑ d ki (x) = |E| x Példa d be (1)=1 ; d be (3)=2 ; d ki (1)=2 ; d ki (3)=0 ; d(1)=3 ; d(3)=2; 1 3 2 4 Definíció: Irányított élsorozat: <x 0 ,x 1 ><x 1 ,x 2 > . <x k-1 ,x k > <x i ,x i+1 > ∈ E Irányított vonal, út, kör: hasonlóan az irányítatlan gráfhoz. Példa kör nem kör 1 2 1 2 3 4 3 4 Definíció: Gyenge összefüggőség: G gyengén öf., ha G öf Definíció: Erős összefüggőség: G erősen öf., ha ∀ két x és y ∈ V csúcs esetén ∃ x y út és ∃ yx út Példa G G G gyengén öf., de erősen nem ( Pl: ∃ 13 út ) 1 2 1 2 3 4 3 4 1 2 G gyengén és erősen öf. 3 4 Megjegyzés: G erősen öf. ⇒ G gyengén öf -8- Definíció: Irányított fa (rekurzív definíció) 1., 1 csúcspontú gráf: fa gyökere, levele az az 1 pont. 2.,

G=(V,E) |V| = k-1 gyökér: r , levelek: l 1 , . ,l m 3., ! b új csúcs (b ∉ V) és ! a ∈ V Új él: ab Az új gráf: G=(V,E) , V=V ∪ b , E=E ∪ <a,b> r a l1 . lm b Fa az, ami ezzel a konstrukcióval előállítható. Példa 1., 2., 3., vagy r r r b1 b1 r b2 b1 Megjegyzés: Új gyökér: r Ha a levél volt (e j ) ⇒ levelek: l 1 ,., l j-1 ,b, l j+1 ,, l m Különben: ⇒ levelek: l 1 ,., l m ,b Állítás: Gyökértől ∀ csúcsba pontosan 1 út vezet. Programozás módszertan Bevezetés: Régen: Cél: monolitikus programozás tárigény, futásidő csökkentése (pr.sorok) Pr. módsz kezdete: 60-as évek vége: "szoftver-krízis" - hardver eszközök egyre hatékonyabbak, olcsóbbak - nőnek a programozási igények - DE: pr. készítés nem elég termelékeny - nem tudjuk pontosan az előállításhoz szükséges időt - pr.-ok nem megbízhatóak - üzemeltetés, karbantartás költséges MIÉRT ? b2 -9- - fiatal tudomány - a

problémák bonyolultak - a pr.-ok, prrsz-ek bonyolultak A programozás módszertan célja: Olyan technológia kidolgozása, mely megbízható pr. termék előállítását eredményezi előre meghatározott időn és költségen belül. Eszközök: - analitikus út: matematikai verifikációs módszerek kidolgozása adott specifikáció szerint helyes pr.-ok kidolgozására ( pr helyesség biz) - mérnöki út: hatékony módszerek kidolgozása a pr.-hoz szükséges erőforrások becslésére ; szabványok kidolgozása a pr. készítés különböző fázisai számára, hatékony szoftvereszközök ( struktúrált programozás, adatszerkezetek analízise, O.OP) A programok szerkezetének analízise A pr. matematikai fogalma: Definíció: Specifikáció: a pr. által megvalósítandó leképezés Definíció: Program: a specifikáció megvalósítására egy kiszámítási szabályt rögzít. Cél: Olyan pr. előállítása, mely egy előre adott specifikációnak felel meg

Matematika függvény kiszámítási szabály ⇔ Szám.tech specifikáció ⇔ program Matematika: Egy fv. leírása a következő módon történik: D(f): értelmezési tartomány R(f): értékkészlet f = { (x,y) | F(x,y) ∧ x ∈ D(f) ∧ y ∈ R(f) } ; ( F predikátum ) Kiszámítási szabály lehet többféle: y=x2-1 y=(x+1)(x-1) Programozás: Pr. nyelv utasításai - függvények F:= { f 0 , f 1 ,. } Ezeknek ugyan az az értelmezési tartományuk: a pr. adatmezeje - 10 - D(f i ):= D := { d 0 , d 1 ,.} A pr. s i =( d i , f i ) i=0,1, állapotok sorozata, ahol s i+1 = f i ( d i ) Azaz: R(f i )=s:=D x F (értékkészlet) Megjegyzés: ∀ utasítás végrehajtása tehát egy új d i+1 adatot és egy új f i+1 végrehajtandó utasítást eredményez. Megjegyzés: s a pr. állapottere Definíció: Ha a pr. véges lépésben befejeződik, akkor adott u kezdőértékhez a pr végrehajtásának eredménye v, ha az állapotok sorozata: u:= s 0 , s 1 ,. ,s n :=v Megjegyzés:

Tehát a pr. az { (u 1 , v 1 ); (u 2 , v 2 ); } fv előállítására egy kiszámítási szabályt ad meg. Definíció: A pr. végrehajtása befejeződik ( a pr terminál ) az i lépés után, ha f i (d i ) ∉ s A pr. szemléltetése gráffal 1., Példa Csomópontban: utasítások Éleken (f i , f j ) vektor: azon adatmezők halmaza, melyekbe tartozó eredmény esetén f i utasítást f j utasítás követi. Dk Di f: Dj fk Dl Dm 2., Példa fl fm Prédikátum-csp. bevezetése: f i (d i )=( d i+1 , f i+1 ) Különválasztjuk f i+1 és d i+1 előállítását. Prédikátum-csp.: Vizsgálat, mely a bemenő adatok alapján meghatározza, hogy milyen irányú elágazásokra van szükség, kijelöli a megfelelő f i végrehajtását. Függvény-csp.: Végrehajtja a kijelölt f i utasítást Dk Di Dj fi D f Dl Dm fk fl fm - 11 - 3., Átírjuk két elágazásra (adott feltétel - prédikátum - ↑ vagy ↓): Dk fk Di D fi Dj Dm p2 p1 Dm | ↑ d ∈ Dm p 1 (d)= |

|↓ d ∉ D m Példa Di Dj fl fm | ↑ d ∈ Dl p 2 (d)= | | ↓ d ∉ Dl o o D =D k  D l  D m 4., Dl o  - diszjunkt  Gyűjtő-csp.: 2 bemenet, 1 kimenet Kimenethez rendeljük a 2 bemenethez tartózó adathalmazok egyesítését. D fm D Definíció: Valódi program: olyan gyengén öf. irányított gráf, amely: 1., véges számú nem zérus bemenő éllel és kijövő éllel rendelkezik 2., csp.-jai prédikátum csp-ok és fvcsp-ok és gyűjtő csp-ok 3., ∀ csp.-on át vezet legalább egy bemenő éllel kezdődő és kijövő éllel végződő út Példa Nem valódi pr.: Definíció: Pr. végrehajtása adott bemenő adat mellett: Végigjárunk egy bemenő éltől egy kijövő élig vezető utat, melyet az úton levő pred.-ok jelölnek ki és végrehajtjuk az úton levő utasításokat. Megjegyzés: Pr. gráfot kiegészíthetjük egy indítási és egy állomás csp-tal Struktúrált programozás - 12 - 1., if p then f else g - I-T-E (p,f,g) p ↑ f

g ↓ p g f ha p akkor f kül. g ha vége 2., while p do f - W-D(p,f) p p f f ciklus amíg p f ciklus vége 3., begin f g end - B(f,g) f f g g f g Definíció: Egy pr. gráf lebontása az az eljárás, melynek során a f enti 3 alapszerkezet valamelyikét egy fv.csp-tal helyettesítjük, és ezt addig folytatjuk, amíg lehetséges Egy fv.csp-ot tartalmazó gráf önmagában álló ir él Példa p2 1., f2 p1 f1 2., W-D(p2, f2) p1 f1 3., I-T-E(p1, f1, 4., W-D(p2, f2)) - 13 - Definíció: Azt a pr.-ot, melynek gráfja lebontható az önmagában álló ir élre, struktúrált prnak nevezzük Megjegyzés: Lehet a do f while p - DU(p,f) formát is struktúrált alapformának tekinteni. f p f p ciklus f amíg p Példa nem strukt. f strukt. h q h q p g p f g f Alapvető struktúrált pr.-ok: g 1., Összegképzés: n s:= ∑ a i a ∈ Rn i =1 s:=0 s:=0 i:=1 i≤n s=0 i=0 ciklus amíg i ≤ n s=s+a i i=i+1 ciklus vége s:=s+a i i:=i+1 2.,

Maximumkeresés mé:= max a i 1≤i≤n i:=1 i≤n s:=s+ai i:=i+1 a ∈ Rn mé:= - ∞ mh:= 0 i:=1 i≤n a i ≥mé a i ≥mé ↑ mé:= a i mh:=i mé:= - ∞ mh:=0 i:=1 i≤n mé=- ∞ mh=0 ↓ i=1 ciklus amíg i ≤ n ha a i ≥mé akkor mé:= ai - 14 - mé=a i mh=i ha vége i:=i+1 ciklus vége i:=i+1 mh:=i i:=i+1 3., Lineáris keresés K:= { min i | 1 ≤ i ≤ n , β(a i )=↑} ↑ i=n+1 ∃ megfelelő ai i ≤ n Λ ¬ β(a i ) i:=1 i:=1 i ≤ n Λ ¬ β(a i ) i:=i+1 i:=i+1 i=1 ciklus amíg i ≤ n és β(a i )=↓ i:=i+1 ciklus vége ↓ k:=1 Tétel: (Bölm-Jacopini) ∀ valódi pr.-hoz ∃ vele ekvivalens struktúrált program Bizonyítás: (vázlat) 1. Lemma: Adott egy pr gráf: élek száma: n pred.csp: π gyűjtő csp.: γ fv.csp: ϕ Ekkor: n = 3π + ϕ + 1 és π = γ Ui.: Csp-ba mutató élek száma: fv.csp-ba: ϕ Összesen: pred.csp-ba: π ϕ + π + 2γ +1 = n gyűjtő csp.-ba:2γ kimenő él Csoportból kimutató élek: fv.csp-ba: ϕ

pred.csp-ba: 2π gyűjtő csp.-ba: γ Összesen: ϕ + 2π + γ +1 = n bemenő él ⇒ ϕ + π + 2γ +1 = ϕ + 2π + γ +1 γ = π n=3π+ϕ+1 2. Lemma: Egy pr struktúrált ⇔ felírható B(g,h) , vagy I-T-E(p,g,h) , vagy W-D(p,g) alakban, ahol p predikátum, g,h struktúrált pr., vagy fv, vagy üres pr Ui.: Egyszerű meggondolással látható a pr lebontásánál mutatott módszerrel - 15 - Bizonyítás: (tétel) Konstruktív Belátjuk: ∀ valódi pr. felírható B(g,h), I-T-E(p,g,h), W-D(p,g) alakban, ahol g,h valódi pr-ok és gráfjukban az élek száma kisebb, mint ez eredeti pr. éleinek száma Nem strukturáltság jellemzői Tétel: Egy pr. nem struktúrált ⇔ részgráfjaként előfordul nem struktúrált alapforma Tétel: A nem struktúrált pr. a nem struktúrált alapformák közül legalább 2-t tartalmaz Nem struktúrált alapformák: több kilépő élű ciklus több belépő élű ciklus - 16 - több kilépő élű döntés több belépő élű

döntés Struktúrált programozás mint módszertan Programok bonyolultsága Struktúrált programozás: a pr. felülről lefelé történő kifejtése 1. szint: pr-ot a 3 alapegység valamelyikével valósítjuk meg - argumentumokban makroutasítások 2. szint: makroutasításokat szintén a 3 alapegység valamelyikével valósítjuk meg . : addig folyatatjuk, míg az argumentumokban a pr nyelv utasításai nem állnak Megvalósítás: eljárásokban Cél: bonyolultság csökkentése Programok bonyolultsága Cél: - pr. komplexitás fogalmának tisztázása - pr. komplexitás mértékszámának kidolgozása - mértékszám felhasználása a programozói munka minőségének javítására. Pr. komplexitás összetett fogalom ∃ egyértelmű mérőszám Program komplexitása kiszámítási kompl. - műveleti igény - tárigény ( ??? ) pszichológiai kompl. (mennyire nehéz egy programozónak egy eddig nem látott pr.-ot megérteni és módosítani.) pr. szerkezetének

bonyolultsága - pl. ciklusok száma adatok szerkezeti bony. Komplexitás csökkentése: - Dekomponálással: Pr. szerkezet bonyolultságának csökkentése Egymástól függetlenül kezelhető pr. részek létrehozása, melynek komplexitása már kezelhető. - 17 - - Absztrakcióval: Adatszerkezetek bonyolultságának csökkentése. Egy adott programozási szinten szétválasztjuk az ott lényeges tulajdonságokat a lényegtelenektől. - Szabványosítással: - formátumban - nevekben ( deklarációs unit ) - kommentárokban, stb. Adatszerkezetek absztrakt analízise Eddig volt: struktúrált programozás, mint módszertan. Napjainkban: objektum orientált programozás (O.OP) Struktúrált programozás - adatok egyszerű (integer, real.) összetett (array,set record.) - eljárások, fv.-ek O.OP - objektum, mint komplex egész. Definiáljuk a - szerkezetét és - azokat az eljárásokat, melyek leírják a viselkedését. Ezek között nincs szoros összefüggés.

Történelmi összefüggés: O.OP elméleti alapjainak lerakása a 70-es években kezdődött az adatszerkezetek absztrakt analízisének vizsgálatával. Gyakorlati megvalósítás: Smalltalk, Lisp, Simula, Modula-2, ADA, később: C++, majd Turbo Pascal 5.5 (1989) Adatok elemi összetett (relatív, pl.: lebegőpontos szám) Definíció: Absztrakt elemi adat: Olyan adategység, mellyel a programozás adott szintjén végezhetők műveletek, de annak részeivel nem. Definíció: Elemi adattípus (objektum): egy (A,M) kettős, ahol A az adattípusba tartozó absztrakt adatok nem üres halmaza, M pedig az m: AxAx.xA A alakú műveletek véges halmaza. Példa - 18 - 1., 2., Egész típus absztrakciója: A:={.,-1,0,1,} ( egész számok ) M:={+,-, ¬ } Szintaktika: + : AxA A - : AxA A ¬ :AA Boolean típus: A:= { ↑,↓ } M:= {∧, ∨, ¬ } Szintaktika: ∧ : AxA A ∨ : AxA A ¬: A A Definíció: Összetett adattípus absztrakciója egy (V,F) kettős, ahol V={V 1 , V 2 ,.,V

m }, m ≥ 2 és V 1 az összetett adatok (vagy adatszerkezetek) nem üres halmaza, V 2 az összetett adatokat alkotó elemi adatok nem üres halmaza V 3 . V m segédhalmazok F a következő f i műveletek véges halmaza: f i : V i1 x V i2 x . x V ik V in (k≥0) és az f i műveletek között ∃ az f j : V j1 x V j2 x . x V jm V 1 (m≥0) alakú műveleteknek egy olyan részhalmaza, melyek egymás utáni alkalmazásával a V 1 halmaz ∀ eleme előállítható. Példa Halmaz (set) V = { H, HE, B } ↑ ↑ ↑ V1 V2 V3 H: halmazok halmaza HE: halmaz elemei (elemi adatok, pl. egész számok) B: {↑, ↓} F= { empty, insert, has, delete } ↑ ↑ ↑ ↑ f1 f2 f3 f4 Szintaktika: empty: H : f1 : V1 insert: H x HE H : f2 : V1 x V2 V1 has: H x HE B : f3 : V1 x V2 V3 delete: H x HE H : f4 : V1 x V2 V1 Definíció: Ha f j : V j1 x V j2 x . x V jn V 1 (n≥0), ahol ( ∀ i, 1 ≤ i ≤ n ) (j i ≠ 1), akkor a v=f j (v j1 , v j2 ,.,v jm ) v ji ∈ V j1 i=1,.,n

adatszerkezeteket generátor elemnek nevezzük. - 19 - Megjegyzés: Általában egy generátor elem van, melyet a f: V 1 konstans fv. állít elő Példa Halmaz: empty: H generátor fv., mely az üres halmazt (generátorelem) hozza létre Definíció: Tekintsük az f j : V j1 x V j2 x . x V jn V 1 (n≥0), alakú műveleteket. Ezek közül a min számít, melyek egymás utáni alkalmazásával V 1 ∀ eleme előállítható, konstrukciós műveleteknek nevezzük. A többi művelet: szelekciós műveletek. Példa Halmaz: empty konstrukciós has szelekciós insert delete Példa 2., Zsák (bag) V = { B, BE, I } B: bag ( nem az előbbi B(oolean) ) BE: elem F={ bempty, binsert, bmany (bhas), bdelete } Szintaxis: bempty: B binsert: B x BE B bmany: B x BE I (bhas: B x BE Bool) bdelete: B x BE B Konstrukciós: bempty, binsert Szelekciós: bmany, bdelete Példa 3., Verem (LIFO) V = { verem, elem } F = { create, push, top, pop } Szintaxis: create: push: pop: top: Konstrukciós:

create, push Szelekciós: pop, top verem verem x elem verem verem verem verem elem Vermek felhasználása 1., Rekurzív algoritmusok Veremben tároljuk a - paramétereket, - a lokális változókat, - a visszatérési címeket Példa rekurzív algoritmus: Hanoi tornyai I: egész (bool.) - 20 - A Hanoi tornyai néven ismert feladat kiinduló helyzete n=6 korong esetén A B C 1. 2. 3. Az A rúd legfelső n-1 darab korongjának áthelyezése B rúdra. Az A rúd legfelső korongjának áthelyezése C rúdra: A C A B rúd legfelső n-1 darab korongjának áthelyezése a C rúdra. n: kez: seg: cél: korongok száma (itt: 6) kezdőrúd (itt: A) segédrúd (itt: B) célrúd (itt: C) TORONY(n,kez,seg,cél): eljárás, mely n korongot áttesz kez-ről cél-ra seg segítségével. TORONY(1,kez,seg,cél) : kez cél 1., TORONY (n-1,A,C,B) TORONY(n,A,B,C) 2., TORONY (1,A,B,C) 3., TORONY (n-1,B,A,C) ↑ n=1 ↓ TORONY(n-1,A,C,B) AC AC TORONY(n-1,B,A,C) 2., Kifejezések

kiértékelése: Lengyel-formula A+B, ( A + B ) * C +AB,*+ABC AB+, AB+C* infix jelölés prefix jelölés postfix jelölés - 21 - Postfix kifejezések kiértékelése veremmel: 1., Operandus Verem 2., ⊗ operátor: - verem két felső elemének (pl.: A,B) kiemelése - B ⊗ A elvégzése - eredmény verem Példa 5, 6, 2, +, *, 12, 4, /, - ( 5(6+2)-12/4 ) 1., 2., 3., 4., 5., 5 6 5 2 6 5 8 5 40 6., 7., 8., 9., 12 40 4 12 40 3 40 37 Infix kifejezések átalakítása postfix kifejezéssé veremmel 1., Operandus P (postfix kif) 2., ( verem 3., ⊗ operátor: - veremből P-be helyezi sorban az összes olyan operátort, melynek precedenciája ≥, mint ⊗-é. - ⊗ verem 4., ): - veremből P-be helyezi ∀ -t, míg ( nem jön - ( eltávolítása 5., Végén ∀ maradékot veremből P Példa ( A + B ) * C - D/E C ( A + ( A + ( AB AB+ * - - / - / - AB+C AB+C* AB+C*D Példa Sor (FIFO) V = { sor, elem } F = { new, add, front, remove } AB+C*D * AB+

AB+C*DE AB+CDE/- - 22 - Szintaxis: new: add: front: remove: Konstrukciós: new, add Szelekciós: front, remove sor sor x elem sor sor elem sor sor Adatszerkezetek szemantikája Definíció: Szemantika: a műveletek jelentését adja meg. Megadás: Matematikában: Itt: Példa 1., Halmaz: axiómák segítségével Megadjuk a szelekciós műveleteknek a konstrukciós műveletekkel előállított adatszerkezetekre gyakorolt hatását. h∈H e 1 , e 2 , e 3 ∈ HE delete ( empty,e ) = empty delete ( insert(h, e 1 ), e 1 ) = ha e 1 = e 2 , akkor delete(h, e 1 ) különben insert(delete(h, e 2 ), e 1 ) e:= e 1 = e 2 ha e ∈ h , akkor insert(h,e)=h ha e ∉ h , akkor delete(h,e)=h másrészt delete(insert(h,e),e)=h delete(insert(h,e),e)=delete(h,e) has(empty,e)=↓ has(insert(h, e 1 ), e 2 )= ha e 1 = e 2 , akkor ↑ különben: has(h, e 2 ) Példa 2., Zsák: bdelete(bempty,e)=bempty bdelete(binsert(b, e 1 ), e 2 )= ha e 1 = e 2 , akkor b különben: binsert(bdelete(b, e 2 ), e

1 ) bhas(bempty,e)=↓ bhas(binsert(b, e 1 ), e 2 )= ha e 1 = e 2 , akkor ↑ különben: bhas (b, e 2 ) Példa 3., Verem: v ∈ verem e ∈ elem - 23 - pop(push(v,e))=v top(push(v,e))=e pop(create)=create top(create=error Példa 4., Sor: ←e v s ∈ sor push (v,e) e ∈ elem remove(add(s,e))= ha s=new, akkor new különben: add(remove(s),e) front(add(s,e))= ha s=new, akkor e kül önben: front(s) add(s,e) s remove(s) e add(s,e) s e remove(new)=new front(new)=error Kérdés: az axiómarendszerrel kapcsolatban: - teljes-e ? - konzisztens-e ? Adatszerkezetek tulajdonságai Kérdés: mikor nevezünk két adatszerkezetet egyenlőnek? Ha a megfelelő részeik egyenlőek. Megadás: szelekciós műveletek segítségével. Példa 1., Verem T.fh "elem" halmaz elemei ismert tulajdonságúak, itt az egyenlőség eldönthető ! v 1 , v 2 ∈ verem Szelekciós műveletek: pop, top v 1 = v 2 ≡ ( pop(v 1 )=pop(v 2 ) ∧ top(v 1 )=top(v 2 ) ) ez az egyenlőség

axiómája. Példa 2., Halmaz ! h 1 , h 2 ∈ halmaz Az egyenlőség axiómája: h1= h2 ≡ ( ∀ e, e ∈ elem )( has(h 1 ,e)=has(h 2 ,e) ∧ delete(h 1 ,e)=delete(h 2 ,e) ) ∨ (h 1 =empty ∧ h 2 =empty) - 24 - De: Általunk képzelt halmaz esetén két halmaz egyenlő, ha az elemei egyenlőek. Azaz: h 1 = h 2 ≡ ( ∀ e, e ∈ elem )( has(h 1 ,e)=has(h 2 ,e)) ∨ (h 1 =empty ∧ h 2 =empty) Állítás: ( ∀ e, e ∈ elem )( has(h 1 ,e)=has(h 2 ,e)) ⇒ delete(h 1 ,e)=delete(h 2 ,e) Bizonyítás: Teljes indukció a konstrukciós műveletek alapján. Adatszerkezetek tulajdonságainak analizálása: Tételek, melyek a műveletek közötti azon kapcsolatokat írják le, melyeket az axiómák nem rögzítenek. Példa Halmazok esetén: 1., insert(insert(h,e 1 ),e 2 )= insert(insert(h,e 2 ),e 1 ) 2., delete(delete(h,e 1 ),e 2 )= delete(delete(h,e 2 ),e 1 ) 3., has(delete(h,e 1 ),e 2 )= ha e 1= e 2 , akkor ↓ különben: has(h,e 2 ) 4., insert(delete(h,e 1 ),e 2 )= ha e 1= e 2 ,

akkor insert(h, e 2 ) különben: delete(insert(h, e 2 ), e 1 ) 5., has(h, e) ⇒ insert(h,e)=h ¬ has(h, e) ⇒ delete(h,e)=h 6., Tételek bizonyítása 1. módszer: az egyenlőség mindkét oldalát behelyettesítjük az egyenlőség axiómájába Példa Fenti 1. állítás ! e tetszőleges has(insert(insert(h,e 1 ), e 2 ), e)= | h* | szemantika axiómája miatt ha e 2 =e , akkor ↑ különben: has(h*,e)=has(insert(h,e 1 ),e) has(h*,e)=has(insert(h,e 1 ),e)= ha e 2 =e , akkor ↑ különben: has(h,e) Tehát összefoglalva has(insert(insert(h,e 1 ), e 2 ), e)= | h1 | ha e= e 1 ∨ e= e 2 , akkor ↑ kül.: has(h,e) Mivel a végeredmény független az indextől, így azok felcserélésével ugyan ez kapható: has(insert(insert(h,e 1 ), e 2 ), e)= | h2 | - 25 - ha e= e 1 ∨ e= e 2 , akkor ↑ kül.: has(h,e) Tehát h 1 és h 2 halmaz ugyan az. 2. módszer: A konstrukciós műveletek száma szerinti teljes indukció. Példa Fenti 2. állítás: 1., ! h=empty Ekkor

delete(delete(empty,e 1 ), e 2 ) = delete(empty, e 2 )=empty ↑ szemantika ↑ Az indexek felcserélésével ugyan ez kapható. 2., Tfh h-re igaz az állítás 3., Belátjuk: igaz h=insert(h,e)-re is Az egyenlet bal oldala: delete(delete(insert(h,e), e 1 ), e 2 )= ha e= e 1 , akkor delete(h, e 1 ) kül.: insert(delete(h, e 1 ),e) = ha e= e 1 , akkor delete(delete(h, e 1 ), e 2 ) kül.: delete(insert(delete(h, e 1 ),e), e 2 ) | h* | delete(insert(h*,e), e 2 )= ha e= e 2 , akkor delete(h*,e 2 )= delete(delete(h, e 1 ), e 2 ) kül.: insert(delete(h*, e 2 ),e)=insert(delete(delete(h, e 1 ), e 2 ),e) Tehát összefoglalva: delete(delete(h, e 1 ), e 2 )= ha e= e 1 ∨ e= e 2 , akkor delete(delete(h, e 1 ), e 2 ) kül.: insert(delete(delete(h, e 1 ), e 2 ),e) Az indexek felcserélésével kapható: Az egyenlet jobb oldala delete(delete(h, e 2 ), e 1 ) = ha e= e 1 ∨ e= e 2 , akkor delete(delete(h,e 2 ), e 1 ) kül.: insert(delete(delete(h, e 2 ), e 1 ),e) Tehát h-re vonatkoztatott teljes

indukciós feltevésből következik, hogy az egyenlet két oldala azonos. A fa adatszerkezet Bináris fa: minden csomópontnak 0,1 vagy 2 rákövetkezője (gyereke) lehet. Példa Bal oldali gyerek A B gyökér(szülő) C Jobb oldali gyerek 0. szint 1. szint - 26 - D E F G H J Bal oldali részfa K Jobb oldali részfa ág 2. szint levél 3. szint A fa mélysége: 4 Példa Kétoperandusos műveleteket tartalmazó algebrai kifejezés: E=(a-b)/((c*d)+e) / a + b e * c d Teljes bináris fa: az utolsó szintet kivéve minden szinten a csomópontok száma maximális, az utolsó szinten baloldalról helyezkednek el a csomópontok. Példa 1 2 3 4 8 5 9 6 7 10 T 10 teljes fa Megjegyzés: K csomópont bal rákövetkezője: 2*K K csomópont jobb rákövetkezője: 2*K+1 K csomópont szülője: K/2 Kiterjesztett bináris fa (kettes fa): minden csomópontnak 0 vagy 2 gyereke van. 2 gyerekes csomópont: belső csomópont (O) 0 gyerekes csomópont: külső

csomópont ( ) Példa O O O O O O O O O 2. példa Kétoperandusos műveletek szemléltetése: operandus: külső csomópont operátor: belső csomópont O O O - 27 - Bináris fák megvalósítása 1. módszer: láncolt listákkal gyökérmutató balmutató jobbmutató A B ∅ D C E ∅ ∅ F G ∅ ∅ J ∅ ∅ ∅ ∅ K H ∅ J K ∅ 2. módszer: vektorban (szekvenciális ábrázolás) A B C D E G H ∅ ∅ F ∅ ∅ ∅ Megjegyzés: Szekvenciális ábrázolás hatékony, ha a fa teljes vagy csaknem teljes. Bináris fák bejárása I. Preorder bejárás (R gyökerű fáé) 1. gyökér feldolgozása 2. R bal oldali részfájának preorder bejárása 3. R jobb oldali részfájának preorder bejárása Preorder (R) R levél I R feldolgozása I I Példa H R feldolgozása Bal (R) = NIL Preorder (Left(R)) Jobb (R) = NIL Preorder (Right(R)) A H H Rekurzív algoritmus az R gyökerű fa prorder bejárásához - 28 - B D C E F G

Preorder bejárás: H J ABDEFCGHJK K II. Inorder bejárás 1. R bal oldali részfájának inorder bejárása 2. R gyökér feldolgozása 3. R jobb oldali részfájának inorder bejárása Példa A fenti ábra inorder bejárása: DBFEAGCJHK III. Posztorder bejárás 1. R bal oldali részfájának posztorder bejárása 2. R jobb oldali részfájának posztorder bejárása 3. R gyökér feldolgozása Példa A fenti ábra posztorder bejárása: DFEBGJKHCA - 29 - 2. példa E=(a-b)/((c*d)+e / Preorder bejárás: - /-ab+*cde prefix jelölés a + b Posztorder bejárás: e ab-cd*e+/ posztfix jelölés * c d Preorder bejárás megvalósítása verem segítségével: MUT: a feldolgozandó csomópontra mutat VEREM: még feldolgozandó jobb csomópontokat tárolja Preorder (R) PUSH(verem,nil) Mut:=R Mut≠nil Mut feldolgozása Jobb(Mut)=Nil I H PUSH(verem,jobb(Mut)) Bal(Mut)=Nil I H Mut:= Mut:= Top(verem) Bal(Mut) Pop(verem) Példa A 1. B 4. H C ∅ Mut: G 3. C C ∅

∅ ∅ Mut: A Mut:B Mut: D C D G 2. E F H K 5. C ∅ Mut: H 6. K C ∅ Mut: 7. 8. C ∅ Mut: K ∅ Mut: C - 30 - 9. 10. F ∅ ∅ Mut: E 11. Mut: F Mut: ∅ ← eljárás vége Halom, halomrendezés Halom(piramis): Olyan teljes bináris fa, melynek minden csomópontjára igaz, hogy a csomópont értéke nagyobb, mint a csomópont gyermekeinek értéke. Példa 97 Piramis 88 95 66 66 18 55 35 40 30 95 48 28 55 48 62 77 25 38 24 Megjegyzés: Szekvenciálisan tároljuk. Beszúrás halomba 1.lépés: Új elemet a halom végéhez csatoljuk, hogy a teljes fa szerkezet megmaradjon (halom nem feltétlenül). 2.lépés: Visszaállítjuk a halom szerkezetet Példa Az előbbi halomba beszúrjuk a 70-es elemet. 97 97 97 88 88 88 55 55 70 48 70 55 70 48 48 1. - halom végére tétel 2., 3- beemelés a halom megfelelő helyére Megjegyzés: Sorozatból halmot építeni beszúrások sorozatával. Példa 44,30,50,22,60 1. 2. 3. 4. 5. 6. 7. 8. 44

44 44 50 50 50 50 60 30 30 50 30 44 30 22 44 30 22 44 60 60 22 44 30 50 22 44 30 - 31 - Halom gyökerének törlése 1. lépés: R gyökeret töröljük (értékül adjuk egy változónak) 2. lépés: gyökér helyére tesszük az utolsó elemet (megmarad a teljes fa szerkezet, halom nem feltétlenül) 3. lépés: az új gyökeret a megfelelő helyre illesztjük a fában Példa 95 15 85 55 70 33 15 30 65 55 33 30 2. 85 85 70 33 70 1., 15 55 85 3., 30 55 65 15 65 70 33 4., 30 65 Halomrendezés Rendezzük A tömb elemeit! 1. lépés: H halom felépítése A elemeiből 2. lépés: H gyökerének ismételt törlése (Más vektorba, vagy A vektor végére) (n=104 13,29∗104) (n=104 108) Műveleti igény: O(n log 2 n) Megjegyzés: Buborék rendezés: O(n2) Programhelyesség - bizonyítás Szemantika: program tartalmára utal. "A program azt csinálja-e, amit elvárunk tőle?" Volt: specifikáció - bemenő és kimenő adatok

egymáshoz rendelése program - kiszámítási szabály. Ezt leírja a P(x) program függvény Kérdés: P(x) valóban az adott specifikációt valósítja-e meg? Szemantika megadás módszerei: 1. Program függvény felírása bonyolult! Struktúrált program esetén: g(x) p(x) ln(x) h(x) g(x) f(x)=h(g(x)) f(x)= g(x), ha p(x)=↑ h(x), ha p(x)=↓ - 32 - p(x) f(x)= g(x) x, ha p(x)= ↓ f(g(x)), ha p(x)= ↑ 2. Predikátumos szemantika megadás Programot részekre bontjuk és lépésenként a részekre bizonyítjuk, hogy a program megfelel a specifikációnak. programhelyesség bizonyítás Alapfogalmak Specifikáció - Rögzíti a bemenő adatok halmazát:{ x | ϕ (x)} - ϕ(x) feltétel (predikátum) pl. x! számításakor x > 0, x egész ϕ(x)= ↑, ha x > 0 és x egész és ϕ(x)= ↓ különben - Rögzíti az x, z adatok egymáshoz rendelését, ahol z az x elem bemenő adathoz tartozó eredmény: : {(x,z) | ψ(x,z)} - ψ(x,z) prédikátum pl. z:=x!

ψ(x,z)=↑, ha z=x és ψ(x,z)=↓ különben. Definíció: Egy P program végrehajtása a bemenő adatok ϕ(x) specifikációja mellett befejeződik, ha a program végrehajtása során kiindulva az indítási pontból elér az álláspontig. Definíció: Legyen P program, mely a p(x) kiszámítási szabályt definiálja és legyen ϕ(x), ψ(x,z) a program specifikációja. A P program parciálisan helyes az adott specifikáció mellett, ha - feltéve, hogy a program végrehajtása minden x-re, melyre ϕ(x)= ↑ befejeződik - a p(x) eredményre: ψ(x,p(x))= ↑. Definíció: P program a ϕ(x), ψ(x,z)specifikáció mellett teljesen helyes, ha parciálisan helyes és minden x bemenő adatra, melyre ϕ(x)= ↑ a program végrehajtása befejeződik. Programhelyesség - bizonyító módszerek Floyd, Manna-féle részcél módszer, Hoare - féle deduktív módszer, Burstall módszer - Először kézzel történő bizonyítás - Első interaktív rsz. : 1973 Cél: Program parciális

helyességének bizonyítása Példa (n,m) legnagyobb közös osztó(lnko) számítása n:= 60 =2*235 m= 42 =7*32 lnko(60,42)=6 Állítás: n>m ⇒ lnko(n,m) = lnko(n-m,m) lnko(60,42)=lnko(18,42)=lnko(18,24)=lnko(18,6)=lnko(12,6)=lnko(6,6)=6 - 33 - - 34 - Program: ( i,k) ← (n,m) ↑ i=k ↓ ↓ i>k k ← k-i konstans egész n,m változó egész i,k (i,k) ← (n,m) ciklus amíg i≠k addig ha i>k akkor i ← i-k különben k ←k-i (ha) vége ↑ (ciklus) vége i←i-k A specifikáció: ϕ(n,m) = n > 0 és m > 0 ψ(i,k) = k = lnko(n,m) A módszer: 1. A program indítási pontjához rendeljük hozzá a ϕ(x), a végállapot ponthoz a ψ(x,z) predikátumot.(Mint a változókra vonatkozó állítást) 2. Bontsuk a programot részprogramokra úgy, hogy a részprogramok ne tartalmazzanak kört. (Azaz minden cikluson belül helyezzünk el egy metszéspontot.) Ebben a pontban helyezzünk el egy P i (x) állítást, mely a változók invariáns tulajdonságait

specifikálja ezen a ponton. Invariáns állítás: Az a tulajdonság, amivel a változók ebben a pontban konkrét értéküktől függetlenül mindig rendelkeznek. ϕ(n,m) : n > 0 és m > 0 ( i,k) ← (n,m) i=k ↓ k ← k-i ↓ i>k P(i,k,n,m): i>0, k>0, lnko(i,k), ↑ lnko(n,m) ψ(i,k,n,m): k=lnko(n,m) ↑ i←i-k 3. Tekintsük azokat az utakat, melyek "állítástól állításig" vezetnek úgy, hogy közben nincs elhelyezett állítás. Minden ilyen útszakasz helyettesíthető egy y - 35 - =r(x) leképezéssel (a függvénycsomópontokban elhelyezett leképezések összessége az út mentén) és egy R(x) feltétele. (Ez a feltétel egy állítás, ami azokra és csak azokra a változóértékekre teljesül, melyekkel mint kezdő értékkel az útszakasz végrehajtásra kerül.) Négy út a példában: Emlékeztető: ϕ(n,m), n > 0 és m > 0 P(i,k,n,m): i > 0 és k > 0 és lnko(i,k) = lnko(n,m) ; ψ(i,k,n,m): k=lnko(n,m) U1: R 1

(i,k)=↑ ϕ ( i,k) ← (n,m) U3: R 3 (i,k) : i = k P i=k r 1 (i,k) : (n,m) P r 3 (i,k) : (i,k) ψ U2: P U4: P R 2 (i,k): i < k r 2 (i,k) : (i,k-i) i=k ↓ i>k ↓ k ← k-i P R 4 (i,k): i > k r 4 (i,k) : (i-k,k) i =k ↓ i>k ↑ i ← i-k P 4. Minden U útszakaszra felírjuk a következő bizonyítandó állítást: (∀x) (P i (x) és R u (x) ⇒ P j (r u (x)), ahol P i az útszakasz végén elhelyezett állítás. (Ideértve ϕ-t és ψ-t is.) 5. Minden útszakaszra bebizonyítjuk a felírt állítások helyességét A példában: U 1 : ϕ(n,m) és R 1 (i,k) ⇒ P(n,m) n > 0 és m > 0 és nő ⇒ n > 0 és m > 0 és lnko(n,m) = lnko(n,) U 2 : P(i,k) és R 2 (i,k) ⇒ P(i,k-i) i > 0 és k > 0 és lnko(i,k) = lnko(n,m) és i < k ⇒ i > 0 és k-i > 0 és lnko(i,k-i) = lnko(n,m) i < k ⇒ lnko(i,k) = lnko(i,k-i)-ból és lnko(i,k)=lnko(n,m) - ból: lnko(i,k-i) = lnko(n,m) U 3 : P(i,k) és R 3 (i,k) ⇒ ψ(i,k) i > 0 és k

> 0 és lnko(i,k) = lnko(n,m) és i = k ⇒ k = lnko(n,m) i = k ⇒ lnko(i,k) = i = k-ból és lnko(i,k) = lnko(n,m)-ból: lnko(n,m) = k U 4 : P(i,k) és R 4 (i,k) ⇒ P(i-k,k) i > 0 és k > 0 és lnko(i,k) = lnko(n,m) és i > k ⇒ i-k > 0 és k > 0 és lnko(i-k,k) = lnko(n,m) - 36 - i >k ⇒ lnko(i,k)=lnko(i-k,k)-ból és lnko(i,k)=lnko(n,m) ⇒ lnko(ik,k)=lnko(n,m) Floyd-tétel Adott P program, ϕ(x), ψ(x,z) specifikációk. Ha egymás után végrehajtva az 1 5 l épéseket azt kapjuk, hogy minden állandóan növekedik, akkor a P program parciálisan helyes az adott specifikáció mellett. 2. példa s:= n ∑ aj, a ∈ R j =1 ϕ(n) : n > 0 i:=1 s:=0 A P(i,s,n) : s = i −1 ∑ a j és i ≤ n+1 j =1 i ≤n ψ(i,s,n) : s = n ∑ aj j =1 ↑ s:=s+a i i:=i+1 U1: r 1 (i,s) : (1,0) R 1 (i,s) : növekvő U2: r 2 (i,s) : (i+1,s+a i ) R 2 (i,s) : i ≤ n ϕ i:=1 U3: r 3 (i,s) : (i,s) R 3 (i,s) : i > n P i≤n s:=0 ↓ P ψ i≤n

↑ s:=s+a i - 37 - i:=i+1 A bizonyítandó állítások: 0 n > 0 és növekvő ⇒ 0= ∑ a j és 1 ≤ n+1 U 1 : ϕ(n) és R 1 (i,s) ⇒ P(1,0) j =1 U 2 : P(i,s) és R 2 (i,s) ⇒ P(i+1,s+ai) i −1 i ≤ n+1 és s = ∑ a j és i ≤ n ⇒ s+ai = j =1 U 3 : P(i,s) és R 3 (i,s) ⇒ ψ(i,s,n) i ∑ a j és i+1 ≤ n+1 j =1 i ≤ n+1 és s = i −1 ∑ a j és i > n ⇒ s = j =1 i ∑ aj j =1 (i ≤ n-ből és i > n- ből következik, hogy i-1 = n) 3. példa max:= max aj; a∈R, 1 ≤ j ≤ n ϕ(n) : n > 0 i:= 2 max:=a 1 A i≤n ↑ a i > max ↑ P(i,max,n) : i ≤ n+1 és max = max a j (1 ≤ j ≤ i-1) ↓ ψ(max,n) : max = max a j (1 ≤ j ≤ n) ↓ max:=a i i:=i+1 U1: ϕ i:= 2 max:=a 1 P U3: r 1 (i,max) : (2,a 1 ) R 1 (i,max) : ↑ P i≤n ↑ ai > max ↓ i:=i+1 P r 3 (i,max) : (i+1,max) R 3 (i,max) : i ≤ n és a i ≤ max - 38 - U2: P i≤n ↑ a i > max ↑ max:=a i U4: r 2 (i,max) : (i+1,a i ) P i≤n R 2

(i,max) : i ≤ n és a i >max ψ r 4 (i,max) : (i,max) R 4 (i,max) : i >n i:=i+1 P A bizonyítandó állítások: U1: ϕ(n) és R 1 (i,max) ⇒ P(2,a 1 ) n > 0 és növekvő ⇒ a 1 = max a j (1 ≤ j ≤ 1) és 2 ≤ n+1 U2: P(i,max) és R 2 (i,max) ⇒ P(i+1,a i ) max = max a j (1 ≤ j ≤ i-1) és i ≤ n+1 és i ≤ n és ai > max ⇒ a i = max a j (1 ≤ j ≤ i) és i+1 ≤ n+1 U3: P(i,max) és R 3 (i,max) ⇒ P(i+1,max) max=max a j (1 ≤ j ≤ i+1) és i ≤ n+1 és i ≤ n és a i ≤ max ⇒ max=max a j (1 ≤ j ≤ i) és i+1 ≤ n+1 U4: P(i,max) és R 4 (i,max) = ψ(i,max) max = max a j (1 ≤ j ≤ i-1) és i ≤ n+1 és i>n ⇒ max = max a j (1 ≤ j ≤ n) i ≤ n+1 -ből és i>n -ből következik: i-1=n Teljes helyesség bizonyítása Teljes helyesség: parciális helyesség és befejeződés Program befejeződésének kimutatása (parciális helyességtől függetlenül): Minden ciklushoz hozzárendelünk egy nemnegatív értékű függvényt,

melynek értéke a ciklus minden végrehajtása után csökken. Legyen adott a P program és a bemenő adatok ϕ(x) specifikációja. 1. A P program minden ciklusának egy alkalmas pontjához rendeljünk hozzá egy q(x) állítást, mely ott a program változóinak a program befejeződése szempontjából szignifikáns, invariáns tulajdonságát specifikálja. - 39 - Példa (i,k) ← (n,m) A ↑ i=k ϕ(n,m) : n > 0 és m > 0 q(i,k) : i > 0 és k > 0 i>k k←k-i i←i-k 2. Bizonyítsuk be, hogy q(x) helyessége következik a bemenő adatok ϕ(x) specifikációjából és a program szövegéből. (Parciális helyességhez hasonlóan) Példa U1: R 1 (i,k) : ↑ ϕ (i,k) ← (n,m) r 1 (i,k) : (n,m) q U2: q i=k R 2 (i,k) : i < k ↓ r 2 (i,k) : (i,k-i) i>k ↓ k←k-i q ϕ(n,m) és R 1 (i,k) ⇒ q(n,m) n > 0 és m > 0 és növekvő ⇒ n > 0 és m > 0 U3: q i=k R 3 (i,k) : i > k ↓ r 3 (i,k) : (i,k-i) q(i,k) és R 2 (i,k) ⇒ q (i,k-i)

i>0 és k>0 és i<k ⇒ i>0 és k-i>0 i>k ↑ q(i,k) és R 3 (i,k) ⇒ q(i-k,k) i>0 és k>0 és i>k ⇒ i-k>0 és k>0 i←i-k q U 4 : Ezt itt nem kell vizsgálni, mert csak q(x) helyességét bizonyítjuk. 3. Rendeljünk hozzá a P program minden ciklusához egy olyan E(x) egész értékű függvényt, melyre igaz, hogy: (∀x) (q(x) ⇒ E(x) ≥ 0). Példában: E(i,k) := i+k Beláthatjuk, hogy (∀i,k) (q(i,k) ⇒ E(i,k) ≥ 0). i >0 és k>0 ⇒ i+k ≥ 0 4. Mutassuk ki a ciklus minden útjára nézve, hogy (∀x) (q(x) és R(x) ⇒ E(x) > E(r(x)), ahol R(x) és r(x) az adott úthoz tartozó feltétel illetve leképezés. (Azaz belátjuk, hogy E értéke a ciklus minden útja mentén csökken.) Példában (Cikluson belüli utakat kell vizsgálni: U2, U3.) U2: q(i,k) és R2(i,k) ⇒ E(i,k) > E(i,k-i) i>0 és k>0 és i<k ⇒ i+k > i+(k-i) i+(k-i)=k - 40 - U3: q(i,k) és R3(i,k) ⇒ E(i,k) > E(i-k,k) i>0 és k>0

és k<i ⇒ i+k > (i-k)+k (i-k)+k=i Tétel Ha az 1.- 4 lépések végrehajthatóak, akkor a P program végrehajtása a bemenő adatok ϕ(x) specifikációja mellett befejeződik. Megjegyzés: Gyakran q(x) céljára választható a parciális helyesség vizsgálatánál alkalmazott P(x) invariáns, ekkor 1.-t és 2-t nem kell újra belátni (Példában is: q(x) részállítása P(x)-nek.) 2. példa i:=1 s:=0 ϕ(n) : n > 0 1. lépés q(i) : i ≤ n+1 Emlékeztető: i≤n r 1 (i,s) : (1,0) R 1 (i,s) : növekvő r 2 (i,s) : (i+1,s+a i ) R 2 (i,s) : i ≤ n s:= s+ai i:= i+1 2. lépés U 1 : ϕ(n) és R 1 (i,s) ⇒ q(1) U 2 : q(i) és R 2 (i,s) ⇒ q(i+1) n > 0 és növekedő ⇒ 1≤n+1 i ≤ n+1 és i ≤ n ⇒ i+1 ≤ n+1 3. lépés E(i) : (n+1)-1 q(i) ⇒ E(i) ≥ 0 i ≤ n+1 ⇒ (n+1)-i ≥ 0 4. lépés q(i) és R 2 (i,s) ⇒ E(i) > E(i+1) i ≤ n+1 és i ≤ n ⇒ (n+1)-i [=(n-i)+1)] >(n+1)-(i+1) [=n-i]) - 41 - 3. példa ϕ(n) : n > 0 i:=2 1.

lépés max:=a1 A i≤n ↑ ↑ ai > max max:=ai i:=i+1 q(i) : i≤n+1 ↓ Emlékeztető: ↓ r 1 (i,max) : (2,a 1 ) R 1 (i,max) : növekvő r 2 (i,max) : (i+1,a i ) R 2 (i,max) : i ≤ n és a i > max r 3 (i,max) : (i+1,max) R 3 (i,max) : i ≤ n és a i ≤ max 2. lépés U 1 : ϕ(n) és R 1 (i,max) ⇒ q(2) n > 0 és növekvő ⇒ 2≤n+1 U 2 : q(i) és R 2 (i,max) ⇒ q(i+1) i ≤ n+1 és i ≤ n és a i > max ⇒ i+1 ≤ n+1 i ≤ n+1 és i ≤ n és a i ≤ max ⇒ i+1 ≤ n+1 U 3 : q(i) és R 3 (i,max) ⇒ q(i+1) Megjegyzés: U 2 és U 3 a befejezés szempontjából összevonható. 3. lépés E(i) := (n+1)-i q(i) ⇒ E(i) ≥ 0 i ≤ n+1 ⇒ (n+1)-i ≥ 0 4. lépés U 2 : q(i) és R 2 (i,max) ⇒ E(i) > E(i+1) i ≤ n+1 és i ≤ n és a i > max ⇒ (n+1)-i [=(n-i)+1 !!!] > (n+1)-(i-1) [=n-i !!!!] U 3 : q(i) és R 3 (i,max) ⇒ E(i) > E(i+1) i ≤ n+1 és i ≤ n és a i ≤ max ⇒ (n+1)-i [=(n-i)+1 !!!] > (n+1)-(i-1) [=n-i !!!!] - 42 -

Gráfok és alkalmazásaik G=(V,E) egyszerű gráf (irányított), |V| = m A csomópontok rendezettek: v 1 ,v 2 ,v 3 , . ,v m Szomszédsági mátrix: A=(a ij ) szomszédsági mátrixa G-nek, ha a ij =0, ha minden v i v j él és a ij =0 különben. Példa v1• 0111 A= 0 0 0 0 0001 v2• •v 4 0010 Tétel A a G gráf szomszédsági mátrixa. A2:= A*A, A3:=AAA ., A k :=(a k (i,j)) Ekkor a k (i,j) egyenlő a v i -ből v j -be vezető k hosszúságú utak számával. Példa A2= 0 0 0 0 0 0 0 0 •v 3 1 0 1 0 1 0 0 1 v 1 v 4 v 3 Útmátrix: P=(p ij ) mátrix a G irányított gráf útmátrixa, ha p ij =1, ha minden v i -ből v j -be út és p ij =0 különben. Tétel: Példa v1• p ij =1 ⇔ ha B m =A+A2+A3+.+Am mátrix (i,j)-ik eleme ≠ 0, ahol A a G gráf szomszédsági mátrixa, m a csúcsok száma. •v 2 •v 3 012 B 2 =A+A2+A3= 0 0 1 000 011 A= 0 0 1 000 001 A = 000 000 000 A = 000 000 2 Összesen kétféle módon juthatok el v 1 -ből v 3 -ba! 3 0 1 1 Nem minden

elem P= 0 0 1 egyenlő 1-gyel ⇒ 0 0 0 nem szorosan összefüggő! Warshall - algoritmus Cél: G mátrix esetén P útmátrix meghatározása. Az algoritmus: 1. P:=A 2. FOR K=1 TO M 3. FOR I=1 TO M 4. FOR J=1 TO M P(i,j) := P(i,j) vagy (P(i,k) és P(k,j)) - 43 - Példa Előző 011 P:= 0 0 1 =A 000 011 P1= 0 0 1 000 011 P2= 0 0 1 000 011 P3= 0 0 1 000 Legrövidebb út algoritmus (Ez az algoritmus egy módosított Warshall-algoritmus) G súlyozott irányított gráf, W:=(w ij ) súlymátrix [w ij = 0, ha nem létezik v i v j él] Cél: Q=(q ij ) mátrix megkeresése, ahol q(i,j) az v i v j legrövidebb út hossza. Jelölés: P k (i,j):=1, ha létezik v i v j út csak v 1 , v 2 , . ,v k csúcsokat tartalmazza, és P k (i,j):=0 különben. Megjegyzés: P 0 (i,j)=1, ha létezik v i v j él, azaz P 0 =A szomszédsági mátrix. Továbbá P m =P útmátrix. Állítás: P k (i,j) = 1, ha - vagy P k-1 (i,j) = 1 vk - vagy P k-1 (i,j) = 1 és P k-1 (k,j) = 1 - vagy vagy • vi• •v

j vi• v 1 , . ,v k-1 csúcsokat tartalmazó út Azaz P k (i,j) = P k-1 (i,j) vagy (P k-1 (i,k) és P k-1 (k,j)), ahol: és 0 1 vagy 0 1 0 0 0 0 0 1 1 0 1 1 1 1 Jelölés: Q k (i,j) := min(Q k-1 (i,j));Q k-1 (i,k)+Q k-1 (k,j)) v 1 ,.,v k-1 csúcsokat felhasználó legrövidebb út hossza Az algoritmus: 1. Q(i,j):=W(i,j), ha W(i,j) ≠ 0 és Q(i,j):= ∞ különben 2. For K:=1 to M 3. For I:=1 to M 4. For J:=1 to M Q(i,j):= min(Q(i,j);Q(i,k)+Q(k,j)) Példa v1• 1 4 ∞ 1 2. ∞ ∞ ∞ ∞ v1 •v 2 2 •v 3 4 2 ∞ 014 W= 0 0 2 000 ∞ 1 3 3. ∞ ∞ 2 ∞ ∞ ∞ v1, v2 ∞ 1 4 1. Q= ∞ ∞ 2 ∞ ∞ ∞ ∞ 1 3 4. ∞ ∞ 2 ∞ ∞ ∞ v1, v2, v3 •v j - 44 - Gráfok megvalósítása kapcsolt adatszerkezettel Példa v2 • v1• Csúcs v1 v2 v3 v4 •v 3 •v 4 A kapcsolt adatszerkezet: Start • Csúcslista v1 • • Szomszédsági lista v2, v3, v4 v3 v4 Éllista • • v2 • • • ∅ v3 • • • ∅ • • • ∅ v4 ∅ ∅ Gráfok

bejárása Keresztirányú keresés: 1. A kiindulópontot vizsgáljuk 2. A szomszédjait vizsgáljuk 3. A szomszédok szomszédjait, stb Megvalósítás: sor segítségével. Jelölés: Egy csomópont státusza (ST) lehet  1 - készenléti állapot (még nem vizsgált)  2 - várakozó állapot (a sorban van)  3 - feldolgozott állapot Az algoritmus: 1. Minden pont státusza legyen 1 2. A kiindulópont (A) elhelyezése a sorban ST(A):=2 3. Ismétlés, amíg a sor üres nem lesz: 4. A sor első elemének (N) eltávolítása, N feldolgozása, ST(N):=3 5. N készenléti állapotú szomszédainak hozzácsatolása a sorhoz, státuszuk 2-re változtatása. Megjegyzés: Ha maradnak feldolgozandó pontok, melyek A-ból nem érhetők el, egy ilyen ponttal újra kell kezdeni az algoritmust. - 45 - Példa A sor alakulása: ST(v 1 , v 2 , v 3 ):= • v2 v1• v4 • • v3 ← ← v1 ← ST(v 1 ):=2 v2 v3 ← ST(v 1 ):=3 ST(v 2 ,v 3 ):=2 ← v3 ← ST(v 2 ):=3 ←

v4 ← ST(v 3 ):=3 ← ST(v 4 ):=3 ← Hosszirányú keresés: 1. A kiindulópont feldolgozása 2. A-ból kiinduló egy P út teljes feldolgozása 3. Visszalépés P-n (Hasonlít a bináris fa inorder bejárásához.) Megvalósítás: veremmel Az algoritmus: 1. Minden csomópont státusza legyen 1 2. A kiindulópont (A) ráhelyezése a veremre, ST(A) :=2 3. Ismétlés, amíg a verem ki nem ürül 4. A verem felső elemének (N) leemelése, N feldolgozása, ST(N):=3 5. N készenléti állapotú szomszédainak ráhelyezése a veremre, státuszuk legyen 2 Példa • v5 v1• 3. v2• • v3 v 4 ST(v 5 ):=3 v3 1. ST(v 1 , . ,v 5 ):=1 v1 ST(v 1 ) :=2 2. • v4 4. v3 ST(v 4 ):=3 5. v2 v5 v4 v3 ST(v 3 ):=3 Gráfok topológiai rendezése T.fh G gráf nem tartalmaz kört Definiáljuk az alábbi α relációt: u < v, ha létezik uv út. Állítás: α részleges rendezési reláció: ST(v 1 ):=3 ST(v 3 ,v 4 ,v 5 ):=2 6. ST(v 2 ):=3 - 46 - Ui.: 1. Minden v

csomópontra v ≥ v (nem reflexív) 2. Ha u<v, akkor v ≥ u (assszimetrikus) 3. Ha u<v és v<w, akkor u<w (tranzitív) Def.: G gráf topológiai rendezése G csúcsainak olyan lineáris sorbarendezése, melyre, ha létezik vu út G-ben azaz v<u, akkor v megelőzi u-t a sorban. Példa A • G• E• •F B• •C • D Két topológiai rendezése a gráfnak: BDGAFEC vagy EGBADFC Tétel: G véges irányított gráf, mely nem tartalmaz köröket. Ekkor G-nek létezik topológiai rendezése. Jelölés: BE(N) : N csúcs éppen aktuális be-fokának tárolása. Cél: G topológiai rendezése. Megvalósítás: sor segítségével. 1. Zérus be-fokú pont megkeresése 2. N és a hozzá tartozó élek törlése a gráfból Az algoritmus: 1. A G gráf minden pontjának be-fokának meghatározása 2. A zérus be-fokú pontok elhelyezése a sorban 3. Ismétlés, míg a sor üres nem lesz 4. Sor első elemének eltávolítása (N) 5. Az N pont minden M szomszédjára:

BE(M):=BE(M)-1 Ha BE(M)=0, M hozzácsatlakozik a sorhoz. Példa A sor alakulása: BE(A):=0 BE(B):=1 BE(C):=1 BE(D):=2 •B A• •C •D A AB 1., ← A 2., ← 3., ← B C 4., ← C ← ← BE(B):=1-1=0 BE(C):=1-1=0 ← ← BE(D):=2-1=1 - 47 - ABC ABCD 5., ← 6., ← 7., ← a topológiai rendezés ← D ← ← BE(D):=1-1=0