Induljunk ki egy ismert tételből:
Megszámolás(H*,F(H,L)):N |
Szignatúra Milyen absztrakt paraméterei vannak (értelmezési tartomány); milyen absztrakt eredményt állít elő (értékkészlet). Csak az alaphalmazt jelöljük; anonim módon. |
Be: NÎN, XÎH*, T:H®L Ki: DbÎN Ef: … ez most nem érdekes … Uf: ... ez most nem érdekes … Def: … ez most
nem érdekes … |
Specifikáció |
Alg: ... ez most nem érdekes ... |
Algoritmus |
A tételekről ezt a szignatúra-adta „kevés” információt arra használhatjuk föl, hogy „megsaccoljuk” egy adott feladat megoldására mely tételek valamilyen kombinációja képzelhető el.
A „megsaccolni” ige arra utal, hogy ha azt nem is tudjuk előre garantálni: valóban mely tételek lesznek nyerők, az biztos, hogy milyenek zárhatók ki eleve.
A legjellegzetesebb szempont a csoportosításra: a benne szereplő sorozatok száma.
Értelmezési tartománybeli
sorozatok száma |
® |
Értékkészletbeli sorozatok
száma |
Tétel |
® |
0 [az érték egy skalár] |
||
1 |
® |
1 |
Rendezés(ek) |
1 |
® |
sok |
|
sok |
® |
1 |
Egy egyetem hallgatóinak adatai (név, szak, évfolyam, átlag) alapján adjuk meg a hallgatók közül kik voltak a legjobbak az egyes évfolyamokban!
A feladat specifikációjában egy sorozatból kell kiindulni, s egy sorozatot/5-elemű skalárt[1] kell előállítani.
’Egy sorozat ® egy sorozat’ esetén szóba jöhető tételek:
· másolás |
|
· rendezés |
Hossz(Spec.Be)¹Hossz(Spec.Ki) ÞD |
· kiválogatás |
C |
Akkor legyen a ’Kiválogatás’?!?
Döntésünk még nem tűnik véglegesnek, hiszen nem létezik egyértelmű (univerzális) T tulajdonság. (Pontosabban 5 hasonló tulajdonság van: x-évfolyambeli, x=1..5) Arra viszont rávilágít, hogy az eredménysorozat minden elemét „azonos logika” szerint kell előállítani.
Figyeljünk most erre a „logikára”! Minden „legjobb” a bemenő sorozat egy adott részsorozatára: az adott évfolyamhoz tartozó hallgatókra vonatkozik. Tehát ha tudnánk is „mennyi a legjobb”, hogyan korlátozzuk a megfelelő részsorozatra? Tehát, hogy szűrjük ki a bemenő sorozat megfelelő részét? Az előbbi tételcsoportos okoskodást újból végig víve már bizonyosra vehető konzekvenciaként fogalmazhatjuk meg a tételt: kiválogatás. A „legjobbság” valami maximumkiválasztás-félére utal, amit éppen valamelyik évfolyambelire kell alkalmazni.
Azaz, jelöljük
az egyetemi hallgatók sorozatát: E-vel (melynek van pl. E.Átlag-gal jelölt komponense),
a legjobbak sorozatát:
L-lel,
így az algoritmus tételfüggvényekkel kifejezve:
Li:=Maximumkiválasztás(Kiválogatás(E,Évfolyambeli(.,i)[2]),£Átlag) (i=1..5)
Évfolyambeli: N´N ® L Évfolyambeli(x,e):=(x=e)
[3] |
Elképzelhető lenne így is: |
|
£Átlag : N´N ® L |
vagy |
£Átlag : R´R ® L |
Konkretizáljunk, s közben ellenőrizzük a minimális elfogadhatóságot: az összeilleszthetőséget!
Kiválogatás(H*,F(H,L)):N* vagy H* |
Maximumkiválasztás(H*,F(H´H,L)):N vagy H |
H*=(Név´Szak´Évfolyam´Átlag)*'E
A továbbiakban jelöljük a struktúrát
így: HallgatóiAdat |
|
F(H,L)'Évfolyambeli(.,e) függvények |
|
N* vagy HallgatóiAdat* |
H*=N* vagy HallgatóiAdat* |
|
F(H´H,L)=F(N´N,L)'£Átlag
rendezési
reláció vagy |
|
N vagy HallgatóiAdat |
Egy egyetem hallgatóinak adatai (név, szak, évfolyam, átlag) alapján adjuk meg a hallgatók közül kik voltak a legjobbak!
Az előző feladathoz képest az eltérés az, hogy az összes legjobbat (ha több azonos átlagú van) kell évfolyamtól függetlenül kikeresni.
A feladat specifikációjában egy sorozatból kell kiindulni, s egy sorozatot kell előállítani. A számba jövő tételek közül megint a kiválogatás marad fenn, amely egymagában megint nem jelentheti a megoldást. Miért nem?
A legjobbságról (megint) a maximumkiválasztásra (mégpedig annak elemértékű, 2. variánsára) asszociálhatunk, hogy végül is az alábbi megoldásvázlatot kapjuk:
L:=Kiválogatás(E,Legjobb)
ahol
Legjobb: R ® L
Legjobb(x):=( x=Maximumkiválasztás(E,£Átlag) )[5]
A formális ellenőrzést most nem részletezem.
Végezetül
hangsúlyozni szeretném, hogy a fenti gondolatmenetnek semmi köze a formális
levezetéshez, csupán azt illusztrálja, hogy miképpen lehet ötletekhez jutni
pusztán a tételek szignatúrájából a megfelelő megoldás megsejtéséhez!
Szétválogatás(H*,Fi(H,L)(i=1..K)):(H*)K
Be: NÎN , XÎH*, KÎN, Ti:H®L (i=1..K)
Ki: DbiÎN , YiÎH* (i=1..K)
Ef: N=Hossz(X) Ù K³2 Ù Ti H-partícionálása
(i=1..K)
Uf: Ù YiÎHDbi Ù YiÍX Ù "jÎ[1..Dbi]: Ti(yij) (i=1..K)
Alg:
Konstans MaxN:Egész(???)
Típus THk=Tömb(1..MaxN:TH)
Konstans K:Egész(???)
Függvény T(Konstans i:1..K, x:TH):Logikai
... feladatfüggő
számítás: x Ti tulajdonságú-e? ...
Függvény Vége.
Típus TDbk=Tömb(1..MaxN:Egész)
THkk=Tömb(1..MaxN:THk) [sorozatok
sorozata]
Eljárás Szétválogatás(Konstans N:Egész,X:THk, K:Egész
Változó Db:TDbk,Y:THkk):
Változó
i:Egész
Db(1..K):=0
Ciklus i=1-től N-ig
j:=MelyikTIgaz(X(i),K)
Db(j):+1; Y(j,Db(j)):=X(i)
Ciklus vége
Eljárás vége.
Függvény MelyikTIgaz(Konstans e:TH, K:Egész): Egész
Változó
i:Egész
i:=1
Ciklus amíg i£K és
nem T(i,e)
i:+1
Ciklus vége
MelyikTIgaz:=i
Függvény vége.
Megjegyzések:
1. Természetesen értelmes változat: a szétválogatás indexsorozatokra vonatkozó is.
2. Egyszerűsíthető némileg a kétfelé szétválogatás (K=2) algoritmusa (hisz a T2=ØT1). Érdekes alesetei:
a. Két sorozatba,
b. Egy sorozatba (elől a T-, hátul a nem-T-tulajdonságúak),
c. Helyben.
Ez utóbbi eset gyakran előfordul, emiatt foglalkozunk részletesen.
SzétválogatásHelyben(H*,F(H,L)):(H*)
)-: Vegyük észre: a „helybenség”-et a függvényszerű leírás nem
támogatja! :-(
Be: NÎN , XÎH*, T:H®L
Ki: DbÎN [XÎH* nem
jelenik meg explicite, helyette X’ÎH*-t
fogunk írni]
Ef: N=Hossz(X)
Uf: Ù X’ÎP(X) Ù "iÎ[1..Db]: T(x’i)
Megjegyzés:
P(X) az X permutációhalmazát jelöli; továbbiakban is alkalmazandó megállapodás lesz, hogy a „helybenség” (azaz, ha ugyanazon adat a bemeneten is és a kimeneten is megjelenik) kifejezésére használjuk az aposztróf jelet.
Alg:
Konstans MaxN:Egész(???)
Típus THk=Tömb(1..MaxN:TH)
Eljárás SzétválogatásHelyben(Konstans N:Egész ,
X:THk
Változó
Db:Egész, X:THk):
Változó
i:Egész
h:TH
Db:=0
e:=1; u:=N; h:=X(e)
Ciklus amíg e<u
Ciklus amíg e<u és nem T(X(u))
[T-tulajdonságú keresése hátul]
u:-1
Ciklus vége
Ha e<u akkor
X(e):=X(u); e:+1
Ciklus amíg e<u és T(X(e)) [nem
T-tulajdonságú keresése elöl]
e:+1
Ciklus vége
Ha e<u akkor
X(u):=X(e); u:-1
Ciklus vége
X(e):=h
Ha T(X(e)) akkor Db:=e különben
Db:=e-1
Eljárás vége.
Megjegyzés:
1. spórolhatnánk 2 felesleges feltételvizsgálatot, ha a második belső ciklust és az őt követő elágazást az első feltételes utasítás akkor-ágához illesztenénk.
2. Érdemes meggondolni a programspecifikáció utófeltételét!
Egyesítés(H*,H*):H*
Be: NÎN , XÎH*, MÎN, YÎH*
Ki: DbÎN , ZÎH*
Ef: N=Hossz(X) Ù HalmazFölsorolás(X) Ù M=Hossz(Y) Ù HalmazFölsorolás(Y)
Uf: Ù ZÎHDb Ù HalmazFölsorolás(Z) Ù "iÎ[1..Db]:( ziÎX Ú ziÎY)
Alg:
Konstans MaxN:Egész(???)
Típus THk=Tömb(1..MaxN:TH)
Eljárás Egyesítés(Konstans N:Egész,X:THk,
M:Egész,Y:THk
Változó Db:Egész,Z:THk):
Változó
i:Egész
Z:=X; Db:=N [feltöltés X elemeivel]
Ciklus j=1-től M-ig
i:=1
Ciklus amíg i£N és Y(j)¹X(i)
i:+1
Ciklus vége
Ha i>N
akkor Db:+1; Z(Db):=Y(j)
Ciklus vége
Eljárás vége.
Megjegyzések:
1. Észre vehető, hogy a belső ciklus (és „környéke”) egy Eldöntés tételt formál, míg a külső ciklus (és környéke) egy Kiválogatás tételt; ill. a törzs első sora egy triviális másolás tételalkalmazás.
2. Gondolja ezt meg úgy, hogy megpróbálja a fenti algoritmust a korábbiakban taglalt tételfüggvényes leírási móddal újrafogalmazni!
3.
Könnyen belátható az alábbi állítás: helyes végállapotban
ZÍX&Y is teljesül.
(Akár a programspecifikáció részeként is fölfoghatnánk.)
4. Miért nem lenne helyes a specifikáció kimeneti részében a „DbÎN, ZÎHN+M”?
Metszet(H*,H*):H*
Be: NÎN , XÎH*, MÎN , YÎH*
Ki: DbÎN , ZÎH*
Ef: N=Hossz(X) Ù HalmazFölsorolás(X) Ù M=Hossz(Y) Ù HalmazFölsorolás(Y)
Uf: Ù ZÍX Ù "iÎ[1..Db]: ziÎY
Állítás: helyes végállapotban Z-re teljesülni fog:
HalmazFölsorolás(Z)
Biz.: (indirekt)[SzP1]
Tfh. Ø HalmazFölsorolás(Z) Þ $k,l: k<l Ù zk=zl. (1)
Helyes
végállapotban: ZÍX Þ "i: $j:
zi=xj,
Þ k: $j: zk=xj, l: $j’: zl=xj’ Ù
k<l Þ j<j’ (2)
(1) Ù (2) Þ
j¹j’
Ù
xj=xj’
Ez
ellentmond az Ef-beli elvárással: HalmazFelsorolás(X).
¨
Alg:
Konstans MaxN:Egész(???)
Típus THk=Tömb(1..MaxN:TH)
Eljárás Metszet(Konstans N:Egész,X:THk,
M:Egész,Y:THk
Változó Db:Egész,Z:THk):
Változó
i:Egész
Db:=0
Ciklus i=1-től N-ig
j:=1
Ciklus amíg j£M és X(i)¹Y(j)
j:+1
Ciklus vége
Ha j£M akkor Db:+1; Z(Db):=X(i)
Ciklus vége
Eljárás vége.
1. Észre vehető, hogy a belső ciklus (és „környéke”) egy Eldöntés tételt formál, míg a külső ciklus (és környéke) egy Kiválogatás tételt.
2. Gondolja ezt meg úgy, hogy megpróbálja a fenti algoritmust a korábbiakban taglalt tételfüggvényes leírási móddal újrafogalmazni!
3. Miért nem lenne helyes a specifikáció kimeneti részében a „DbÎN, ZÎHMin(N,M)”?
Összefuttatás(H*,H*,F(H´H,L)):H*
Be: NÎN , XÎH*, MÎN, YÎH* (£:H´H®L rendezés)
Ki: DbÎN , ZÎH*
Ef: N=Hossz(X) Ù M=Hossz(Y) Ù
HalmazFölsorolás(X) Ù HalmazFölsorolás(Y) Ù RendezettSorozat£(X)
Ù RendezettSorozat£(Y)[6]
Uf: Ù ZÎHDb Ù HalmazFölsorolás (Z) Ù RendezettSorozat£(Z)
Ù
"iÎ[1..Db]:( ziÎX Ú ziÎY)
Alg:
Konstans MaxN:Egész(???)
Típus THk=Tömb(1..MaxN:TH)
Eljárás Összefuttatás(Konstans
N:Egész,X:THk,M:Egész,Y:THk
Változó Db:Egész,Z:THk):
Változó
i:Egész
Db:=0
i:=1; j:=1
Ciklus amíg i£N és
j£M
Db:+1
Elágazás
X(i)<Y(j) esetén Z(Db):=X(i);
i:+1
X(i)=Y(j) esetén Z(Db):=X(i);
i:+1; j:+1
X(i)>Y(j) esetén Z(Db):=Y(j);
j:+1
Elágazás vége
Ciklus vége
Ciklus amíg i£
Db
Ciklus vége
Ciklus amíg j£M
Db:+1; Z(Db):=Y(j); j:+1
Ciklus vége
Eljárás vége.
Megjegyzések:
1. Észre vehető a specifikáció alapján, hogy ez nem más, mint egyesítés rendezett sorozatokra.
2. Az elágazás teljes eseményt ír le, így nyilván a 3. feltétel helyettesíthető az „egyébként” kulcs-szóval (amivel kevesebb vizsgálatot írunk elő).
3. Érdemes eltűnődni azon, hogy mennyi nyereséggel jár az „eredeti” egyesítéshez képest a rendezettség figyelembe vétele.
|
||||
Minimálisan |
Max(N,M) |
(M+1)*M/2[7] |
Max(N,M) |
Min(N,M) |
Átlagosan |
N+M/2 |
O(M*N)[8] |
O(N+M) |
2*Min(N,M) |
Maximálisan |
N+M |
M*N |
N+M |
3*Min(N,M) |
|
Másolásszám |
Hasonlításszám |
Másolásszám |
Hasonlításszám |
A táblázat értelmezéséhez tudnia kell, hogy milyen feltételek húzódnak meg az egyes értékek mögött. Többször előfordul, hogy valójában nem ilyen „egyszerű” érték a pontos érték. Például függhet attól, hogy N, M közül melyik a nagyobb. Nos ilyenkor önkényes feltétellel éltem. De mivel? Gondolja meg, melyik értékhez milyen előfeltétel teljesülése szükséges!
4. Az előbbi megoldás „szépséghibája”, hogy két szemet bántó másolással kellett kiegészíteni, mert a „fő” ciklus idejekorán véget ért, s így nem tudta elvégezni a kitűzött feladatot. Ezt kiküszöbölhetjük, ha a sorozatok végéhez illesztünk két azonos (eddig nem bennlevő) maximális értéket: +¥[9] (Ef: … Ù +¥ÏX Ù +¥ÏY).
Alg:
Konstans MaxN:Egész(???)
Típus THk=Tömb(1..MaxN:TH)
Eljárás Összefuttatás(Konstans
N:Egész,X:THk,M:Egész,Y:THk
Változó Db:Egész,Z:THk):
Változó
i:Egész
N:+1; X(N):=+¥; M:+1; Y(M):=+¥;
Db:=0
i:=1; j:=1
Ciklus amíg i<N vagy j<M
Db:+1
Elágazás
X(i)<Y(j) esetén Z(Db):=X(i);
i:+1
X(i)=Y(j) esetén Z(Db):=X(i);
i:+1; j:+1
X(i)>Y(j) esetén Z(Db):=Y(j);
j:+1
Elágazás vége
Ciklus vége
Eljárás vége.
ProgramozásMódszertan
4. előadás’2001 (vázlat)
1.2.
A tételek csoportjai és a szignatúra
1.3.
A tételek összeépítéséről előzetesen
2. További Programozási tételek
[1] Mert, hogy előre ismert és kicsiny számú az eredmény. Így nagy a kísértés, hogy „egységnek” érezzük.
[2] Évfolyambeli(.,e) azt hangsúlyozza, hogy ebben a szituációban a kétváltozós függvény valójában csak az első változójától függ, a második rögzített: 1 vagy 2 vagy … vagy 5 (e) értékű.
[3] Az x helyébe valamely Ei.Évfolyam-t képzelhetjük.
[4] Egy lehetséges hívása: Ei.Átlag£Ej.Átlag, azaz ái helyébe Ei.Átlag és áj helyébe Ej.Átlag helyettesítendő.
[5] Világos, hogy x helyébe az Ei.Átlag-k kerülnek.
[6] A rendezettség „irányáról” feltesszük a növekvőséget.
[7] N=M esetén.
[8] Ordó függvény. L. a hatékonyságról szóló előadásban a 32. dián.
[9] Később bevezetjük a rendezett típusok esetére alkalmazható típusfüggvényt a hozzá tartozó legnagyobb érték jelölésre. Ez a TH típusra így néz ki: Max’TH.
[SzP1]Meg kell gondolni