ProgramozásMódszertan
2. előadás’2004
(vázlat)

1. Specifikáció

1.1. Alapvető matematikai jelölések

Lásd http://izzo.inf.elte.hu/szlavi honlapon a „Prtetel.doc”-ban (vagy a Prtetel.pdf-ben)!

H halmaz	•	tetszőleges (véges) halmaz a szokásos halmaz műveletekkel és konstansokkal (Î,Ï,Ì,Í,È,Ç,\,Æ, Számosság)
L	•	logikai értékek halmaza: {Igaz,Hamis} a szokásos műveletekkel (Ø,Ù,Ú,Û,Þ), kvantorokkal (",$) és individuumváltozókkal, halmazokkal [1]
N	•	természetes számok halmaza {0, 1, ...} a szokásos műveletekkel (+,-,*,Div,Mod)
Z	•	egész számok halmaza {.., -1, 0, 1, ...} a szokásos műveletekkel (+,-,*,Div,Mod)
R	•	valós számok halmaza a szokásos műveletekkel (+,-,*,/, ^)
C	•	karakterek halmaza {…, ’ ’,…, ’A’,…,’z’, …}
S	•	szövegek halmaza
H-Sorozat	•	H-beli elem N-esek (NÎN), amelyen alapműveletként értelmezzük az i. elem (iÎ{1..N}) kiválasztását: si:= az S sorozat i. eleme, valamint az eleme relációt: xÎS, ha $i: x=si, és a sorozathossz függvényt, ekkor Hossz(S)=N
H^N halmaz NÎN	•	H-beli N-elemű sorozatok halmaza
H^* halmaz	•	H-beli véges sorozatok halmaza, azaz H^*= È(i=0..¥) H^i
()ÎH^* üres sorozat	•	S=() Û Hossz(S)
[x..y][2] index-intervallum x,yÎN	•	[x..y]:={x,x+1,...,y-1,y}
I[x..y] index-sorozat	•	I[x..y]:=(x,x+1,...,y-1,y)ÎN^y-x, ha y³x I[x..y]:=(), egyébként
F(H,S) függvényhalmaz	•	F(H,S):={ f : f:H®S }
£HÎF(HxH,L) rendezés rendezési reláció (infix jelölésű bináris függ.) ha lehet: £H helyett £	•	ha "aÎH: a£a (reflexív), "a,b,cÎH: a£b és b£c Þ a£c (tranzitív), "a,bÎH: a£b és b£a Þ a=b (antiszimmetrikus) "a,bÎH: a£b vagy b£a (teljes)
H halmaz RendezettHalmaz£(H)	•	ha "h,jÎH: h£j vagy h³j (ha H véges Þ $max, min eleme)
SÎH^* sorozat RendezettSorozat£(S)	•	ha RendezettHalmaz(H) és "iÎ[1..N): si£si+1
SÎH^* sorozat HalmazFölsorolás(S)	•	ha "i,jÎ[1..N]: i¹j Þ si¹sj
X&Y konkatenációja X és Y sorozatoknak	•	X&Y:=(x1,...,xN,y1,...,yM), ahol N=Hossz(X) és M=Hossz(Y)
XÍY X részsorozata Y-nak	•	"yÎY: $xÎX: y=x és i,jÎ[1..Hossz(Y)]: i<j: yi,yjÎY Þ $k,lÎ[1..Hossz(X)]: k<l: (yi=xk és yj=xl)
R\r sorozat rÎH, RÎH^N: HalmazFölsorolás(R)	•	ha rÎR Þ R\rÎH^N-1 és R=R1&(r)&R2 Þ R\r=R1&R2 ha rÏR Þ R\r=R
P(R) az RÎH^N Permutációhalmaza	•	P(R):={SÎH^N : N=1 Þ S=R, N>1 Þ S=s&S, és sÎR és S,ÎP(R\s)}
X,Y a Z felbontása (X,Y,Z sorozatok)	•	ha Z=X&Y
Ti:H®L iÎ[1..K] H-partícionálása	•	"xÎH: Ú(i=1..K) Ti(x)=Igaz és (Ti(x)ÙTj(x)=Hamis (i¹j))

Definíció: Az F:H^*®S^* feladat elemenként feldolgozható, "ZÎH^* " X,Y Z-felbontásra igaz, hogy F(X)&F(Y)=F(Z).

Lemma: Ha az F:H^*®S^* feladat elemenként feldolgozható, akkor $f:H®S függvény, hogy f(hi)=si iÎ[1..N].

1.2. Egy példa

Feladat:

Egy egyetem hallgatóinak adatai (név, szak, évfolyam) alapján adjuk meg, van-e első éves informatika szakos hallgató!

Specifikáció:

Bemenet: NÎN, HallgatókÎ(Név´Szak´Évfolyam)^*,
Név=S, Szak={Info, Mat, Fiz, …[3]}, Évfolyam=N

Kimenet: VaneÎL

Előfeltétel: Hossz(Hallgatók)=N Ù
"iÎ[1..N]: Hallgatók_i.Név¹’’ Ù Hallgatók_i.ÉvfolyamÎ[1..5]

Utófeltétel: Vane = $iÎ[1..N]: Hallgatók_i.Szak=Info Ù Hallgatók_i.Évfolyam=1

1.3. Specifikáció és programmodell

Állapottér: (bemenő és kimenő, valamint belső) adatok absztrakt halmaza, amelynek egy-egy vetületét („dimenzióját”) alkotják a változók.

Feladat: egy binér reláció az állapottér (-kettős) felett. Értve ez alatt: a bemeneti és a hozzá rendelt kimeneti állapot kettősének halmazát. Az állapottér kezdetben (bemenetként) elfogadható elemeinek halmazát jelöli ki az előfeltétel. (Amelyek kielégítik az előfeltételt, azok tartoznak a tényleges bemeneti halmazba.) Az elérendő végállapotot az utófeltétel rögzíti az állapothalmazban (a bemeneti állapot függvényében).

Specifikáció: a feladat formális meghatározása.

A program egy kiszámítási sorozatot definiál, amely meghatározza, hogy a számítás milyen állapottér „útvonalon” haladva jusson el a végeredményhez. Vagyis a program mint függvény (programfüggvény) egy állapottér-transzformátor.

Feladat- és programspecifikáció kapcsolata: a programspecifikációt úgy kapjuk a feladatspecifikációból, hogy gyengítjük az előfeltételt („többet engedünk meg”) és szigorítjuk az utófeltételt („egyértelműsítve az esetlegesen meglévő nemegyértelműségeket”).

2. Algoritmus és adat – ’Struktúraszerinti feldolgozás’ elv

2.1. Az elv

Absztraktadat	Algoritmikus nyelvi adatfogalom	Þ	Algoritmus
Elemi	Skalár	Þ	Értékadás (függvénnyel), eljárás
Direktszorzat	Rekord	Þ	Rekord-mező szerinti utasítás-szekvencia
Iteráció	Sorozatfélék (pl. tömb)	Þ	Ciklus, rekurzió
Unió	Alternatív rekord	Þ	Elágazás az alternatíva feltételei szerint

A fenti példában: az N és a Vane elemi (skalár), a Hallgatók iteráció (pl. tömb), mégpedig a Név, a Szak és az Évfolyam halmazok direktszorzataként adódó rekord.

2.2. Hogyan használható az elv föl?

Az 1.2.-beli példa „vezérlő” (azaz legbonyolultabb lévén, a legtöbb „gondot okozó”) adatszerkezete a Hallgatók. Ez iteráció, tehát sejthető, hogy a feldolgozás legbonyolultabb része egy ciklus lesz.

3. A strukturált programozás elvei

3.1. Felülről-lefelé tervezés és lépésenkénti finomítás

A feladat egészét tekintjük először, s így bontjuk föl néhány (3-7) részfeladatra. A részfeladatok megengedett programstruktúrák komponenseiként alkotják a feladat egészének megoldását. A dekomponáláskor a részfeladatokat a szokásos elő- és utófeltételekkel specifikáljuk. (Ezek az elő- és utófeltételek természetesen „kellően” illeszkednek egymáshoz.)

Az egyes részfeladatokat külön-külön oldjuk meg az előbbi szerint.

3.2. Megengedett programstruktúrák

Transzformáció (értékadás jobboldalán függvénnyel; eljárás)

Elágazások (Ha…akkor...különben…; Ha…akkor…)

Ciklus (Ciklus amíg …)

3.3. Példa

Az 1.2.-beli példa lebontásának vázlata:

Program = Beolvasás(N,Hallgatók)
Vane:=Számítás(N,Hallgatók)
Kiírás(Vane)

Beolvasás(…) = …

Számítás(…) =
Ciklus … N-re
HallgatóFeldolgozás(Hallgatók(i))
Ciklus vége

Kiirás(…) = …

4. Algoritmikus nyelv részletei

4.1. A program legfelsőbb szintje

Program PrNév:
Globális adatok definíciója, deklarációja
(Típusdefiníciók, konstans- és változó-deklarációk)
A végrehajtás legfelsőbb szintje
Program vége.[4]

Természetesen a végrehajtórészben szerepelnek azoknak az eljárásoknak és függvényeknek a hívásai, amelyeket a lépésenkénti finomítás során a tervezéskor kaptunk.

4.2. Az alprogramok definiálása

A felülről-lefelé haladva finomodó tevékenységek definiálása:

Eljárás EljNév(form.param.):

lokális adatok definíciója, deklarációja
A végrehajtás utasításai
Eljárás vége.

Függvény FvNév(form.param.): ÉrtékTípus

lokális adatok definíciója, deklarációja
A végrehajtás utasításai
FvNév:=kifejezés
Függvény vége.

Be: NÎN, HallgatókÎ(Név´Szak´Évfolyam)^*,
Név=S, Szak={Info,Mat,Fiz,…}, Évfolyam=N

Ki: VaneÎL

4.3. Példa

Program Egyetem:
Típus
TNév=Szöveg
TSzak=(Info, Mat, Fiz, …)
TÉvfolyam=Egész
THallgató=Rekord(
Név:TNév
Szak:TSzak
Évfolyam:TÉvfolyam)
Konstans
MaxN:Egész(1000)
Típus
THallgatók=Tömb(1..MaxN:THallgató)
Változó
N:Egész
Hallgató:THallgatók
Vane:Logikai

Beolvasás(N,Hallgatók)
Vane:=Feldolgozás(N,Hallgatók)
Kiírás(Vane)
Program vége.

Ef: Hossz(Hallgatók)=N Ù
"iÎ[1..N]: Hallgatók_i.Név¹’’ Ù Hallgatók_i.ÉvfolyamÎ[1..5]

Eljárás Beolvasás(Változó n:Egész, h:THallgatók):
Be: n [0£n£MaxN]
Be: h(1..N) [h(1..N).Név¹’’ és
h(1..N).ÉvfolyamÎ[1..5]]
Eljárás vége.

Függvény Feldolgozás(Konstans n:Egész
h:THallgatók):Logikai
Változó
i:Egész

Uf: Vane=$iÎ[1..N]: Hallgatók_i.Szak=Info Ù Hallgatók_i.Évfolyam=1

i:=1
Ciklus amíg i£N és
nem (h(i).Szak=Info és h(i).Évfolyam=1)
i:+1
Ciklus vége
Feldolgozás:=i£N
Függvény vége.

Eljárás Kiírás(Konstans v:Logikai):
Ki: v
Eljárás vége.

Megjegyzések:

· Érdemes megfigyelni a specifikáció és az algoritmus formális kapcsolatait, továbbá az alkalmazott névkonvenciókat.

· Mivel a specifikációban felbukkanó adatok a „főprogram” minden résztevékenysége számára elérhető (ún. globális adatok), ezért eltekinthetünk a résztevékenységeket megvalósító eljárások, ill. függvények paraméterezésétől.

· Bevezettük a programozási nyelvekben is gyakorta meglevő „inkrementálás” (növelés) műveletet. Értelmezését az alábbi: példa érzékelteti:

x:+y ugyanaz, mintha x:=x+y

(Persze kitalálható a jelentése a dekrement és társai műveleteknek: x:-y, x:*y, x:/x .)

5. Programozási tételek

5.1. A céljuk, lényegük

Gondolati mankóul szolgál a program algoritmusának felderítésében és formalizálásában. (A hatékonyság egyelőre nem szempont!)

Tételek szerkezete:

· Feladat/program-specifikáció

1) Bemenet

2) Kimenet

3) Előfeltétel

4) Utófeltétel

5) Definíciók (opcionális)

· Absztrakt algoritmus

· Állítás: a specifikációt az absztrakt algoritmus kielégíti.

· Bizonyítás

5.2. A formalizmus és célja

Megállapodások:

· A tételeket mint függvényeket is megadjuk (a „fejsorban”, az ún. szignatúrában), amelynek argumentuma tartalmazza azokat a „kellékeket”, amelyek a szükséges bemenetei, ill. az értékét, amely halmazba képez. E jelölés célja, hogy pusztán ilyen „szintaktikai” természetű dolog is segítségünkre legyen majd a tételek összeépítésénél.

· Szívesebben adunk meg egy sorozatot H^*-beliként (H^N helyett), mivel a specifikációban legkevésbé így köti meg a kezünket (nem utal a leírás tömbre vagy más, fixhosszúságú szerkezetre). A „tétel-függvényben” éppen e megfontolásból nem tüntetjük föl a sorozatok elemszámát szimbolizáló paramétereket.

· Az absztrakt algoritmust komplett eljárásként fogalmazzuk meg, amelyet megelőz a szükséges típusok definíciója.

5.3. A programozási tételek

5.3.1. Másolás tétel

Másolás(H^*,F(H,S)):S^*

Be: NÎN, XÎH^*

Ki: YÎS^*

Ef: F elemenként feldolgozható az f:H®S függvénnyel Ù Hossz(X)=N

Uf: "iÎ[1..N]: yi=f(xi)

Alg:

Konstans MaxN:Egész(???)
Típus THk=Tömb(1..MaxN:TH)
TSk=Tömb(1..MaxN:TS)

Eljárás Másolás(Konstans N:Egész, X:THk
Változó Y:TSk):
Változó
i:Egész

Ciklus i=1-től N-ig
Y(i):=f(X(i))
Ciklus vége
Eljárás vége.

5.3.2. Sorozatszámítás tétel

Sorozatszámítás(H^*,F(H^*,H)):H lehetne még Sorozatszámítás(H^*,H,F(H,S)):S

Be: NÎN, XÎH^*, F:H^*®H

Ki: SÎH

Ef: Hossz(X)=N Ù $f:HxH®H Ù f₀ÎH : F((x₁..x_N))=f(F(x₂..x_N),x₁,), F(())=f₀ Ù f₀ f-neutrális[5]

Uf: S=F(X)

Alg:

Konstans MaxN:Egész(???)
Típus THk=Tömb(1..MaxN:TH)

Eljárás Sorozatszámítás(Konstans N:Egész, X:THk
Változó S:TH):
Változó
i:Egész

S:=f₀
Ciklus i=1-től N-ig
S:=f(S,X(i))
Ciklus vége
Eljárás vége.

5.3.3. Eldöntés tétel

Eldöntés(H^*,F(H,L)):L

Be: NÎN, XÎH^*, T:H®L

Ki: VaneÎL

Ef: Hossz(X)=N

Uf: Vane º $iÎ[1..N] : T(xi)

Alg:

Konstans MaxN:Egész(???)
Típus THk=Tömb(1..MaxN:TH)

Eljárás Eldöntés(Konstans N:Egész, X:THk
Változó Vane:Logikai):
Változó
i:Egész

i:=1
Ciklus amíg i£N és nem T(X(i))
i:+1
Ciklus vége
Vane:=i£N
Eljárás vége.

Megjegyzés: Hogyan származtatható e tételből az, amely utófeltétele az alábbi:

Uf: Minde º "iÎ[1..N] : T(xi)

azaz, hogy „minden X-elem T-tulajdonságú-e”?

Válasz:

Uf: Minde º Ø$iÎ[1..N] :ØT(xi)

És algoritmikus folyamánya:

…
Eljárás Eldöntés(Konstans N:Egész, X:THk
Változó Minde:Logikai):
Változó
i:Egész

i:=1
Ciklus amíg i£N és nem T(X(i))
i:+1
Ciklus vége
Minde:=i>N
Eljárás vége.

5.3.4. Kiválasztás tétel

Kiválasztás(H^*,F(H,L)):N

Be: NÎN, XÎH^*, T:H®L

Ki: SorszÎN

Ef: Hossz(X)=N Ù $iÎ[1..N] : T(xi)

Uf: SorszÎ[1..N] Ù T(x_Sorsz)

Alg:

Konstans MaxN:Egész(???)
Típus THk=Tömb(1..MaxN:TH)

Eljárás Kiválasztás(Konstans N:Egész, X:THk
Változó Sorsz:Egész):
Változó
i:Egész

i:=1
Ciklus amíg nem T(X(i))
i:+1
Ciklus vége
Sorsz:=i
Eljárás vége.

5.3.5. Keresés tétel

(Lineáris) keresés(H^*,F(H,L)):L ÈLxN

Be: NÎN, XÎH^*, T:H®L

Ki: VaneÎL, SorszÎN

Ef: Hossz(X)=N

Uf: Vane º $iÎ[1..N] : T(xi) Ù Vane Þ SorszÎ[1..N] Ù T(x_Sorsz)

Alg:

Konstans MaxN:Egész(???)
Típus THk=Tömb(1..MaxN:TH)

Eljárás LinKeresés(Konstans N:Egész, X:THk
Változó Vane:Logikai, Sorsz:Egész):

Változó
i:Egész

i:=1
Ciklus amíg i£N és nem T(X(i))
i:+1
Ciklus vége
Vane:=i£N
Ha Vane akkor Sorsz:=i
Eljárás vége.

6. Specifikáció – algoritmus –kód

A specifikáció kapcsolata az algoritmussal, és a kóddal kérdéskörhöz érdemes a http://izzo.inf.elte.hu/szlavi honlapon a HTML-publikációk 2. hivatkozását (Specification, algorithm and program code.) fellapozni.

Tartalom

1. Specifikáció. 1

1.1. Alapvető matematikai jelölések. 1

1.2. Egy példa. 2

1.3. Specifikáció és programmodell 3

2. Algoritmus és adat – ’Struktúraszerinti feldolgozás’ elv. 3

2.1. Az elv. 3

2.2. Hogyan haszálható az elv föl?. 3

3. A strukturált programozás elvei 4

3.1. Felülről-lefelé tervezés és lépésenkénti finomítás. 4

3.2. Megengedett programstruktúrák. 4

3.3. Példa. 4

4. Algoritmikus nyelv részletei 4

4.1. A program legfelsőbb szintje. 4

4.2. Az alprogramok definiálása. 4

4.3. Példa. 5

5. Programozási tételek. 6

5.1. A céljuk, lényegük. 6

5.2. A formalizmus és célja. 6

5.3. A programozási tételek. 7

5.3.1. Másolás tétel 7

5.3.2. Sorozatszámítás tétel 7

5.3.3. Eldöntés tétel 8

5.3.4. Kiválasztás tétel 9

5.3.5. Keresés tétel 9

6. Specifikáció – algoritmus –kód. 10

---

[1] Pl. „$iÎH: T(i)” logikai kifejezésben az i – individuumváltozó, a H – az individuumhalmaz. A kifejezést így értjük: „létezik olyan H-beli i elem, amelyre teljesül a T predikátum”.

[2] Helyenként ugyanilyen értelemben használjuk a [x,y] rövidebb jelölést. A balról/jobbról nyíltságra a hagyományos matematikai zárójeleket használjuk.

[3] A „…” jelentése: itt egy felsorolás lenne, amit most nem folytatunk (formálisan persze kellene, mivel ki nem található)! Figyelem: így csak egy szak rendelhető a hallgatóhoz! Nagy baj ez?

[4] Az algoritmus (és majd a kód) szerkezetet meghatározó kulcs-szavait vastagítva kiemeljük.

[5] Azaz "xÎH: f(f₀,x)=f(x,f₀)=x