Programozási tételek szerepe a gyakorlati programozásban
Gondolatok egy feladat megoldása kapcsán
Egy konkrét feladat megoldása közben arról töprengünk, hogy miként tehető mechanikussá a programkészítés tevékenysége a biztonságosság, helyesség megőrzése mellett. Más oldalról megközelítve a kérdést: mi a szerepe a lexikális ismereteknek a programozásban? Megint másként: rutinszerű tevékenység vagy alkotás (már amennyire szembeállíthatók ezek egymással) a programírás?
Három lépésen (gondolatsoron) keresztül jutunk el a feladatból a megoldó program kódjáig. Azt vizsgáljuk, hogy a három lépés: a feladatspecifikáció, az algoritmizálás és a kódolás hogyan kapcsolódnak egymáshoz. Igyekszünk beláttatni, hogy az első lépés a leginkább „kreatív” lépés, amelynek jó vagy rossz döntései tükröződnek az algoritmuson és a kódon is. Mind az algoritmizálás, mind a kódolás nagyban mechanizálható lépések láncolatából tehető össze.
Az első gondolatsor „mottója” ez lehet: mi a tételek szerepe a specifikáció elkészítésekor? A másodiké: hogyan kapcsolódnak össze a specifikáció egyes részei az algoritmus egyes részleteivel? S végül a harmadiké: milyen információk használhatók föl kódolás során az algoritmusból és az algoritmusból?
0. Bevezetés
Írásomban egy programozási feladat megoldása kapcsán hangosan gondolkodom ilyesfajta kérdéseken, mint „Mennyire tehető mechanikussá a programkészítés?”, vagy „Mi a szerepe a lexikális ismereteknek a programozásban?”, ill. „Rutin vagy alkotás a programírás?”
Azt gondolom, ezek a kérdések nagyban befolyásolják a programozás oktatás „filozófiáját”. Hisz egy tevékenység rutinszerűen elvégezhető lépéseit lehet/kell gyakoroltatni, egy ismeretnek lexikális részei „bemagoltatható” még a legbigottabb számítógép-kerülő tanulóval is; mindezt persze azért, hogy mindenki birtokába juthasson azoknak az eszközöknek, amelyekkel azután szárnyalni, alkotni képes.
Nos, az alábbiakból –remélem– kiolvasható lesz, hogy igen nagy részben mechanizálható lépések sorozatából áll a programozás, amelyek –megfelelően leegyszerűsített formalizmus esetén– korán taníthatók minden, „számítógéppel nem fertőzött gondolkodású” gyermekkel.
Tudom, hogy e gondolatokat megfogalmazni mai, túlracionalizált „felfedezés orientált” felfogású világunkban szinte szentségtörés, de mivel szentül meg vagyok győződve igazamról, leírom.
Előzetesen jeleznem kell, hogy az ELTE Informatika Tanár Szakán szokásosnak mondható felfogást követem, sok dolgot nem magyarázok meg, hanem utalásokkal intézem el. Például nem magyarázom a specifikáció részeit, mit jelentenek a formalizmusok, ugyancsak magyarázatlanul maradnak az algoritmikus nyelv elemei, ill. a célnyelvnek tekintett Turbo Pascal szintaxisa, szemantikája, ismertnek tételezem föl a programozási tételek fogalmát, sőt magukat a tételeket is. Ezen ismereteket az ajánlott irodalmakból össze lehet szedni. A függelékben összegyűjtöttük a feladat megoldása során „alapvetőként” fölhasznált ismereteket. (Tételspecifikációkat, -algoritmusokat stb.)
1. A feladat
Adott egy repülőgépről fölvett
magassági méréssorozat. A repülő Európából indult, ahol az első mérést
megtette, és Amerikában szállt le, ahol szintén egy szárazföldi méréssel
fejezte be útját. Tudjuk, hogy legalább egy mérést a tenger felett végzett. Ott,
ahol tenger van (s csak ott) a mérés 0-nak adódott. Gyűjtsük ki, azon
mérés-sorszámokat, ahol sziget kezdődött, ill. ahol sziget fejeződött be.
A feladat „eredeti” szövege ennyi. Mint általában e leírás titkokat rejt, nem egyértelmű. De hát az Élet is ilyen. A feladatmegoldó első dolga ezeket az „információs hézagokat/ disszonanciákat” betömni/feltárni. Ezt végezzük el a specifikáció elkészítése során.
a feladat és a feladatspecifikáció
Tisztázandó tehát, milyen információk állnak rendelkezésünkre, amikből ki lehet indulni (Bemenet), ill. miféle információk, amiket a programnak szolgáltatnia kell (Kimenet). Ennek megfogalmazása során érdemes csak néhány alaphalmazt fölhasználni, mégpedig olynéhányat, amelyeknek könnyen megfeleltethetünk egy, az algoritmikus nyelvben előforduló típust.[1] Ezek lehetnek: Z (egész számok), N (természetes számok), R (valós számok), Szöveg, Karakter, L (logikai értékek).
A rendelkezésre álló információk nemcsak adatok lehetnek, hanem valami, a feladat szempontjából kulcsfontosságú „adatosztályozó” elv: tulajdonság. Így célszerű a bemeneti részben megemlíteni az ilyen információkat hordozó logikai értékű függvényeket.
Az előrelátható, hogy az adatok és a függvények a leírás további részeiben is szerepelnek majd, ezért nevet kell hozzájuk rendelni.
Tehát a konkrét esetben:
Bemenet: NÎN,
MagÎRN,
Eleje:N®L,
Eleje(z):=Magz-1=0
és Magz>0, Vége:N®L, Vége(z):=Magz>0
és Magz+1=0
Magyarázatra talán csak a két tulajdonság függvénye szorul. Ez is egy ábrával kellően illusztrálható. (L. 1. ábrát.)
1. ábra
Az eredmény miféle? A feladat szerint egy adatpárokból álló sorozatot várunk, ami „rossz” esetben nullahosszúságú. A leírásban nehézséget legfeljebb a „párság” okozhat. A „tisztességes” megoldás megkapható a halmazok között alkalmazható direktszorzat segítségével; bár –most– megkerülhető: önálló sorozatokként való föltüntetésével. Azaz
Kimenet: DbÎN, SzigetÎ(Első x Utolsó)Db, Első,Utolsó=N
vagy
Kimenet: DbÎN, Első,UtolsóÎNDb
A két leírás szemlélete más, ami a későbbi lépésekben (algoritmus és kód) is tükröződni fog.
Ez az a pillanat, amikor már érdemes kacsingatnunk a megoldás során felhasználható tételek garnitúrája felé.[2] Ugyanis, ha megsejtjük, hogy mely tétel alkalmazható a feladatra, akkor ezt az információt fölhasználhatjuk fogódzóként a specifikáció további részeinek elkészítéséhez, és természetesen az algoritmizálást már –úgy’szólván– mechanikusan végezhetjük el.
A leggyakrabban használt tételeinket az alábbi kategóriákba csoportosíthatjuk. A csoportosítás alapja, hogy –mint egy leképezésnek tekintve– mi az „értelmezési tartománya” (bemenet) és mi az „értékkészlete” (kimenet). Eszerint a csoportok:
a. sorozat[3] ¾® érték
b. sorozat ¾® sorozat
c. sorozat ¾® sorozatok
d. sorozatok ¾® sorozat
Látszik, hogy ez az osztályozás „ránézésre” elvégezhető, s eredményeként a közel 20 tétel helyett már csak 4-6 tételt kell alaposabban szemügyre venni. (Például az a. esetben az „érték” mifélesége teljesen egyértelműen eligazít.) Esetünkben a b. csoport jön szóba, illetve az alternatív kimenetet vizsgálva a c. csoportra gondolhatunk. Az elsőt vizsgáljuk az alábbi A.-val jelölt részben, az utóbbit a B.-vel jelöltben.
A. esetben:
A szóba jöhető tételek: másolás, kiválogatás, rendezés(ek). Pusztán formális meggondolással kizárható a másolás és a rendezés (hisz a kimeneti sorozatok hossza ezeknél a bemenetiével feltétlenül megegyező, ami most nem igaz). A megmaradt egyetlen kiválogatás tétellel egy aprócska probléma van: az eredetiben egy tulajdonság helyett itt kettő is van. Ebből arra következhetünk, hogy a feladat valójában nem egy, hanem kettő kiválogatás tételt rejt. De azt már is konstatálnunk kell, hogy a két kiválogatás eredmény sorozatai azonos (Db) hosszúságúak.
A kiválogatás tétel specifikációját mintaként használjuk az előfeltétel és utófeltétel összeállításához. Az előfeltétel írja le (logikai formulaként[4]), hogy milyen szűkítő feltételek érvényesek a feladat szerint a bemeneti adatokra az előzőkben definiálthoz képest; jelen esetben N-re (N-hez képest), Mag-ra (RN-hez képest). A sablonként alkalmazott tétel előfeltétele „üres” (azaz azonosan igaz), a feladat ezen szűkít: N³3, hiszen azt állítja, hogy az első és az utolsó mérés pozitív, sőt legalább egy a tengerbeli; következésképpen legalább ennyi mérés volt. Az RN helyett R+È{0} az alkalmazandó. Vagyis:
Előfeltétel: N³3 és "iÎ[1,N]: Magi³0 és Mag1,MagN>0 és $iÎ[2,N]: Magi=0
Az utófeltétel összeállításánál jelentősebb segítséget ad a tétel. A sablon szerint Db-re kell mondanunk valamit: „éppen akkora ..., ahány olyan ...”, és az eredmény sorozat elemeiről: „éppen azok indexei, amelyek olyanok ...”. Ahogy azt előbb megsejtettük, itt két kiválogatás van, amelyek egyikéhez az Eleje-tulajdonság és a Mag sorozat tartozik, a másikhoz a Vége-tulajdonság és az Utolsó komponens.
Ebből arra gondolunk, hogy az utófeltételnek két hasonló része lesz: az egyikben az egyik kiválogatás, a másikban a másik „mondanivalója”. Így kapjuk:
Utófeltétel: Db=S(i=2..N) cEleje(i) [5]
és
("iÎ[2,N]:
Eleje(Sziget.Elsői) [6]
és HalmazFölsorolás(Sziget.Első) [7]
és
("iÎ[2,N]:
Vége(Sziget.Utolsói) és HalmazFölsorolás(Sziget.Utolsó)
A feladathoz egy „átlagos” állapotot tükröző ábrát készítve némi rossz sejtelmünk ébredhet az utófeltételt illetően. (L. 2. ábrát!)
2. ábra
Az utófeltétel szerint olyan mérés, amely teljesíti az Eleje predikátumot három van, jól lehet sziget csak kettő. Hol a hiba? Válasz: az Eleje predikátumot leegyszerűsítettük két pont vizsgálatára, s nem foglalkoztunk azzal, hogy ezek sziget pontjai valójában vagy sem. A probléma megoldása lehet: 1) kiegészíteni a hiányolt vizsgálattal, de ez –előreláthatólag– meglehetősen hosszadalmassá tenné az eldöntést, vagy 2) a predikátumot korlátozzuk csak olyan szakaszra, ahol nem keveredhet a szigetek közé kontinens. Azaz, ahol az index a [2,N]-ben „fut” (a S-ban, illetve a "iÎ[2,N] hatáskörben) az utófeltételben cseréljük ki az alábbira: [e,u]-ra, ahol
(*) e,uÎ[1,N]: "iÎ[1,e-1]È[u+1,N]: Magi>0
Ezzel a kiegészítéssel a végső változat így alakul:
Utófeltétel: e,uÎ[1,N]:
"iÎ[1,e-1]È[u+1,N]:
Magi>0 és
Db=S(i=e..u) cEleje(i) [8]
és
("iÎ[e,u]:
Eleje(Sziget.Elsői) [9]
és HalmazFölsorolás(Sziget.Első) [10]
és
("iÎ[e,u]:
Vége(Sziget.Utolsói) és HalmazFölsorolás(Sziget.Utolsó)
B. esetben:
A szóba hozható tétel mindössze egy: a szétválogatás. Az elő- és utófeltétel összeszedését már nem részletezzük. Az előfeltétel ugyanaz lesz, mint az előbbi. Az utófeltétel is azonos, a különbség a „levezetésben” lesz, ui. most nem kell rájönni arra, hogy két tétel bújik meg benne.
3. A második gondolatsor
a specifikáció és az algoritmus
Túlvagyunk a dolog legkreatívabb lépésén. Az elkövetkezőkben a specifikációból és a megsejtett tételből kiindulva a megoldó algoritmust „generáljuk”. Az algoritmuskészítés során csak a lényegi részre koncentrálunk; s nem foglalkozunk pl. az adatok beolvasásával és az eredmény megjelenítésével (amik természetesen nélkülözhetetlenek lennének a megoldó programhoz, de ezeket majd a kódolás során fogjuk meggondolni).
A be- és a kimenet figyelembevétele
A be- és kimeneti részből származtatjuk a leendő programunk globális deklarációs részét. Alkalmazzuk a következő „halmaz ® típus” egymáshozrendelési konvenciót: N, Z®Egész; L®Logikai; R®Valós; ...
A halmazokon végzett műveletekkel képzett összetett adathalmazokhoz egy-egy új típust rendelünk, ahogy ezt az alábbi példa mutatója:
valamiÎAxB, ahol A=C, B=D ® Típus ABTip=Rekord(A:CTip, B:DTip)
Értelemszerűen a CTip, DTip a C, D halmazok típusmegfelelőit jelölik[11]. Egy másik típikus példa:
valamiÎAN ® Típus ANTömbTip=Tömb(1..N:ATip) [12]
Abból indulunk ki, hogy a bemenő adatok értékeit „meg kell szerezni” – mégha ezt nem is algoritmizáljuk–, ezért a bemeneti adatobjektumokat változóként deklaráljuk az algoritmusban. Így:
Változó N:Egész
Típus ValósNTömb=Tömb(1..N:Valós)
Változó Mag:ValósNTömb
A specifikációban szereplő függvények definícióját is itt helyezzük el az algoritmikus nyelvi szabályok szerint, amihez minden definíciós „kellék” megvan:
Függvény
Eleje(z:Egész):Logikai
Eleje:=Mag(z-1)=0 és Mag(z)>0
Függvény vége.
Függvény
Vége(z:Egész):Logikai
Vége:=Mag(z)>0 és Mag(z+1)=0
Függvény vége.
Majd a kimenet megfelelője következik:
Típus ElsőUtolsóTip=Rekord(Első:Egész,Utolsó:Egész)
ElsőUtolsóNTömb=Tömb(1..N:ElsoUtolsóTip)
[13]
Változó Db:Egész
Sziget:ElsőUtolsóNTömb
Az elő- és az utófeltétel figyelembevétele
Az előfeltételnek most nincs szerepe. Ott használjuk föl a benne levő információt, ahol a bemenő adatok „születnek”, vagyis –a majdan meggondolandó– beolvasó eljárás kódolásánál.
Talán a legizgalmasabb részhez értünk. Most jön létre a
megoldás lényegi része, amelyet egy –feladatra utaló nevű– eljárásba foglaljuk
(most: Szigetek). Két utófeltétel-variánsunk is van, mivel a második egyetlen
tételhez (szétválogatás) kapcsolódik, így egyszerűbbnek ígérkezik, ezért
válasszuk azt. (Az első változatra is vissza fogunk térni.)
A szétválogatás tétel algoritmusát, mint sablont fölhasználva, a konkrétumok behelyettesítés után az alábbi algoritmusdarabhoz jutunk:
Db:=0
Ciklus i=e-től u-ig
Elágazás
Eleje(i) esetén Db:=Db+1; Sziget(Db).Első:=i
Vége(i) esetén Sziget(Db).Utolsó:=i
Elgázás vége
Ciklus vége
Be kell vallani, két, egymással összefüggő problémát kellett áthidalni az átírás közben. Az első mindjárt az, hogy a tétel szerint két eredménysorozathoz külön-külön tartozik egy-egy számláló, márpedig erről „nem tud” a specifikáció. Mivel itt a két sorozat elemei párt alkotnak –éppen ezt fejezi ki a specifikáció A-változata–, ezek hossza szükségképpen megegyezik. Továbbá a feldolgozás során mindig az „Első” sorozatbeli jön, amelyet a párja (egy „Utolsó”-beli) követ, így egyetlen számláló elegendő.
A másik probléma: az elágazás második ágánál –a sablon szerint– épp az előbbiekben kiselejtezett számlálót kellene növelni. Innen a számlálónövelés most már nyilvánvalóan okok miatt minden gond nélkül elhagyható.
Az algoritmusban használtunk két deklarálatlan, sőt értéket sem kapott e-t és u-t. Szerepükre világít rá az utófeltételben szereplő és eddig fel sem használt (a korábban (*)-gal jelölt) többlet-információ.
Az e és u meghatározására ismét valamilyen tételt kell alkalmaznunk. Ha a (*)-állítást utófeltételként értelmezzük, csak olyan tétel jöhet szóba, amely egy sorozatból egy valamilyen tulajdonságú (Magi>0) elem indexét állítja elő. Egyetlen ilyen van: a kiválasztás, amelynek előfeltételeként viszontláthatjuk a mostani előfeltételünk egy részletét: Magi=0. Azaz minden kétséget kizáróan erről van szó. Így a hiányzó algoritmusdarabbal kiegészített megoldó eljárás az alábbi:
Eljárás Szigetek:
Változó i,e,u:Egész
|
i:=2 |
az „újdonság” |
Db:=0
Ciklus i=e-tõl u-ig
Elágazás
Eleje(i) esetén Db:=Db+1; Sziget(Db).Első:=i
Vége(i) esetén Sziget(Db).Utolsó:=i
Elgázás vége
Ciklus vége
Vegyük észre, hogy a specifikációbeli feltételek „futó” (a kvantorok mellett szereplő individuum) változói az eljárás lokális változóiként bukkannak elő.
Ami az A-változatot illeti: két független kiválogatással operáló algoritmushoz jutunk első lépésben. Szemet kell, szúrjon, hogy ezek nagyban azonosak (mindössze a cikusmagbeli feltételek különböznek). S józan megfontolásokkal[14] a fenti algoritmusokhoz jutunk.
az algoritmus + a specifikáció és a kódolás
Eljutottunk a programozás legmechanikusabban[15] elvégezhető lépéséhez: a kódoláshoz. Ennél a lépésnél pontosan ismernünk kell a célnyelv szintaktikáját, szemantikáját és más természetű „korlátait”. Ezek tudatában elkészíthető jó előre az előzőekben használt algoritmikus nyelv és a célnyelv közötti ún. kódolási szabályok. Ilyeneket alkalmazunk most a Turbo Pascal nyelv esetére, néhány általánosabb megjegyzéssel kísérve.
A Pascal programnak van néhány olyan jellemzője, amely alaposan rányomja bélyegét a kódolási lépésünkre. Ezek:
1. A program felülről lefelé tervezéssel szemben a Pascal programban a használatot mindig meg kell, előzze a definiálásnak, azaz alulról felfelé építkezés jellemzi.
2. A tömbök méretének ismertnek kell lennie már fordításkor, azaz statikus tömbfogalmat ismer a Pascal.
Kódolásnál követni fogjuk azt az elvet, hogy a programban három funkció: a beolvasás, a kiszámítás és az eredménymegjelenítés önálló eljárások formájában ölt testet. Azaz a program szerkezete nagy vonalakban:
Program ProgNév;
... definíciós és deklarációs rész ...
Procedure Beolvas;
Begin
... eljárástörzs ...
End;
Procedure
Kiszámol{valami lényegre utaló név};
Begin
... eljárástörzs ...
End;
Procedure
EredménytMegjelenít;
Begin
... eljárástörzs ...
End;
Begin
Beolvas;
Kiszámol{valami lényegre utaló név};
EredménytMegjelenít
End.
Ezután a kódolásban a legkreatívabb feladat: a Beolvas, illetve az EredménytMegjelenít eljárások megalkotása. Ehhez szükséges ismereteket az algoritmikus deklarációból származó globális adatleíró, illetve a specifikáció előfeltétel része szolgáltatja.
A globális definíciós és deklarációs részhez –most– mindössze egy többlet konstans bevezetéséről kell gondoskodnunk a 2. Pascal jellemző miatt.[16] Így ez a része a programunknak így alakul:
Var N:Integer;
Const MaxN=100; {ide írandó az elvileg
előforduló
legnagyobb elemszám}
Type ValosNTomb=Array[1..MaxN] of Real;
Var Mag:ValoNTomb;
Function Eleje...;
...
Var Db:Integer;
Type ElsoUtolsTip=Record
Els,Utolso:Integer End;
ElsoUtolsNTomb=Array[1..MaxN] of
ElsoUtolsoTip;
Var Sziget:ElsoUtolsNTomb;
Szándékosan megtartottuk az algoritmusbeli sorrendet, bár más ott is és természetesen itt is átcsoportosíthatók az egyes deklarációs részek (figyelembe véve persze a korábban említett Pascal korlátozásokat).
Az utolsó (részletesebb) megemlítésre érdemes gondolat a beolvasás kódolása. A vezérgondolat itt az, hogy az adatok értékeinek beolvasásánál garantálnunk kell az előfeltételben előírtakat. Ez „többféle igényességgel” is elvégezhető. Mi most csak jelzésszerűen, vázlatosan oldjuk meg a beolvasás ellenőrzését: feltételezzük, hogy a felhasználó típussértést nem, „legfeljebb” értékhatár-átlépést követ el. Így kapjuk meg a Beolvas eljárást:
Procedure Beolvas;
Var i,beI:Integer;
beR:Real;
jo,van:Boolean;
Begin
Repeat
Write('N:'); Readln(beI);
Until (beI>=3) and (beI<=MaxN);
az elõfeltételbõl a Pascal kódolási elvbõl
N:=beI;
Van:=False;
Repeat
For i:=1 to N do
Begin
Repeat
Write(i,'. mérés:');
Readln(beR);
Case i of
1,N: jo:=beR>0;
else jo:=beR>=0;
End;
Van:=Van or (beR=0);
Until jo;
Mag[i]:=beR;
End;
Until Van;
End;
Megjegyzések:
1. A beolvasott értékek ellenőrzésére –most– a célváltozóval azonos típusú segéd változókat vezettünk be. Minden elem beolvasása egy ciklus, aminek feltétele: az előfeltételben rögzített, illetve a tömb maximális méretéből adódó értékek közé esés.
2. Ha a segéd változó típusát „bővebbre” változtatnánk, akkor nagyobb teret engednénk a felhasználói hibázásnak. (Pl. Integer helyett Real vagy String.)
3. A tömbbeolvasás relatíve nagy bonyolultságának[17] az az oka, hogy van az aktuális tömbnek egy olyan jellemzője is, ami „globális” jellegű, azaz a tömb teljes beolvasása után derül csak ki ennek teljesülése vagy nem teljesülése.
4. Most a „küllemre” egyáltalán nem ügyelünk. Ez természetesen fontos lenne, de mostani témánk: a specifikáció-algoritmus-kódolás hármas kapcsolata szempontjából nem érdekes.
5. Következtetések
Függelék - „alapismeretek”
F1. Néhány programozási tétel
Másolás(N,H*,H®G):G*
Be: NÎN, XÎH*, f:H®G
Ki: YÎG*
Ef: -
Uf: "i(1£i£N): yi=f(xi)
Az algoritmus:
Eljárás Másolás(Konstans
N:PozEgész,X:Tömb(1..N:H_elemTíp),
Változó Y:Tömb(1..N:G_elemTíp)):
Ciklus I=1-től N-ig
Y(I):=f(X(I))
Ciklus vége
Eljárás vége.
Kiválogatás(N,H*,H®L):(N,N *)
Be: NÎN, XÎH*, T:H®L
Ki: DBÎN, YÎN*
Ef: -
Uf: 
Ù
YÎ[1..N]DB
Ù
HalmazFölsorolás(Y)
Ù "iÎ[1..DB]:
T(xyi)
Az algoritmus:
Eljárás Kiválogatás(Konstans
N:PozEgész,
X:Tömb(1..N:H_elemTip),
Változó M:PozEgész,
Y:Tömb(1..M:NemNegEgész)):
M:=0
Ciklus I=1-től N-ig
Ha T(X(I)) akkor M:+1;
Y(M):=I
Ciklus vége
Eljárás vége.
F2. Példák a kódolási szabály-gyűjteményből
Az alábbi kiragadott kódolási példáknál a
deklarációknak csupán információ-nyújtás szerepe van, nem tekinthető
teljesnek.
Skaláradat (pl. Integer, Real, ...) beolvasása:
|
Változó X:Egész ... |
Var X:Integer; beX:Real; ... ... |
Tömb (pl. Integer, Real, ...) beolvasása:
|
Változó X:Tömb(1..N:Egész) ... |
Const MaxN=1000; ... |
Irodalom
[]
[]
[]
[]
[]