Programozási tételek – mint láttuk – magasszintű absztrakciós műveletek bázisai. Ebben a fejezetben bemutatunk egy gondolatmenetet, amellyel az absztrakció gondolkodási eszközt felhasználva hozunk létre további programozási tételeket. Tehát az absztrakció egy további szintjének létezésére mutatunk ezzel rá.
Hasznos általánosítás révén juthatunk el a keresési módszerek nevezetes osztályaihoz. Kiindulunk a lineáris keresés jól ismert algoritmusából, nem nehéz a következő meglehetősen általános keresési algoritmushoz jutni. [SzP3/5-7]
Új fogalom | Magyarázat |
|---|---|
L∈H* lehetségesek sorozata | az eredeti X egy alkalmasan választott részsorozata (L⊆X) |
||.||: H*→N hossz | sorozat hossza (elemszáma) |
σ: H*→H* sorozatszűkítés | ∀L∈H*: σ (L)=L1 L⊃L1 (⇒ ||L||>||L1||) |
ε: H*→N elemindex-kiválasztás | ∀L∈H*: ε (L)∈[1..||L||] |
Ezen fogalmakkal az általánosított keresés tétel megfogalmazása:
L:=X
Ciklus amíg ||L||>0 és nem T(X(ε(L)))
L:=σ(L)
Ciklus vége
Van:=||L||>0
Ha Van akkor Sorsz:=ε(L)
Nézzük a ’lineáris keresés’ tétel újrafogalmazását!
(L1) L:=(xi: i∈[e..N]) – elejétől végig, e : ahol tartunk=1..N+1
Látható, hogy L azonosítható, sőt helyettesíthető is az első elemének indexével:
(L1’) L:=L(e) → e
(L2) ε(L(e)):=e – első elem
(L3) σ(L(e)):=(xi: i∈[e+1..N])⊆(xi: i∈[e..N]) – maradék, szűkített sorozat
(L4) (L1)⇒ ||L(e)||:=N–e+1
(L5) (L4)⇒ ||L(e)||>0 ⇔ N–e+1>0 ⇔ N+1>e ∧ e∈N ⇔ N≥e
A fogalmak „aktualizálás” után nézzük az általánosból származó „alap” algoritmust, kommentálva:
Általánosított keresés | Lineáris keresés | |
|---|---|---|
L:=X | (L1’) | i:=1 [1.-nél kezdődik a sorozat] |
Érdemes tudnunk, hogy a közismert keresésekben milyen ε- és σ-függvények fordulnak elő. Ezek értelmezését adjuk meg a következő táblázatban:
Definíció | Megjegyzés | |
|---|---|---|
1. | ε1((xi,...,xj)):=i | első elem |
2. | εu((xi,...,xj)):=j | utolsó elem |
3. | εk((xi,...,xj)):=(i+j) DIV 2 | középső elem |
4. | σ1((xi,...,xj)):=(xi+1,...,xj) | első elem nélkül |
5. | σu((xi,...,xj)):= (xi,...,xj-1) | utolsó elem nélkül |
6’. | σk<((xi,...,xj)):= (xi,...,xm), ahol m=(i+j DIV 2)-1 | középső előttiek |
6’’. | σk>((xi,...,xj)):=(xl,...,xj), ahol l=(i+j DIV 2)+1 | középső mögöttiek |
7. | σ<((xi,...,xj)):=(x’l,...,x’k)⊆(xi,...,xj) ∀x’m<xi m∈[l..k] | első elemnél kisebbek |
Ezek után könnyen levezethető az általános keresés algoritmusából a lineáris keresés rendezett sorozatban, a logaritmikus, sőt a backtrack-alapú keresés is.
A ’lineáris keresés rendezettben’ algoritmusához a fogalmi megfeleltetések:
(Lr1) L:=(xi: i∈[e..N]) – elejétől végig, e : ahol tartunk=1..N+1
Az e a sorozat elejét jelöli, amelyben még lehet a keresett. Figyelem: az L sorozat még annak előtte, hogy az N. eleméhez érnénk, véget érhet! (Ha x>y bekövetkezett.)
L azonosítható, sőt helyettesíthető is az első elemének indexével:
(Lr1’) L:=L(e) → e
(Lr2) ε(L(e)):=ε1(L(e)):=e – a mindenkori első elem
(Lr3) σ(L(e)):=(xi: i∈[e+1..N]), ha xe≤y
(Lr4) σ(L(e)):=(xi: i∈[N+1..N]), ha xe>y
(Lr5) (Lr3)&(Lr4)⇒ σ(L(e))⊆(xi: i∈[e..N])
(Lr6) (Lr1)⇒ ||L(e)||:=N–e+1
(Lr7) (Lr6)⇒ ||L(e)||>0 ⇔ N≥e
A mechanikusan származtatott algoritmus 1. változata (most már hivatkozások nélkül):
e:=1
Ciklus amíg N≥e és X(e)≠y
Elágazás
X(e)<y esetén e:=e+1
X(e)>y esetén e:=N+1
Elágazás vége
Ciklus vége
Van:=N≥e
Ha Van akkor SORSZ:=e
Az alábbi észrevételeket tehetjük:
(1) a ciklusból kilépünk, ha N<e vagy X(e)=y teljesül;
N<e ⇔
X(e)>y – találunk nagyobbat (⇐ σ-definíció (2))
vagy
N+1=e – egyszerűen a sorozat végére érünk
(2) Így a ciklusfeltételre a következő teljesül:
N≥e és X(e)≠y ⇔ nem (X(e)>y vagy N+1=e) és X(e)≠y ⇔
X(e)≥y és N+1>e és X(e)≠y ⇔
N+1>e és X(e)<y ⇔ N≥e és X(e)<y
(3) Ezen átalakítás után a ciklusmagban fölöslegessé vált az elágazás, hiszen az első ág triviálisan igaz, a másik meg sohasem teljesülhet.
(4) Ezzel viszont a kilépés okát már nem jelzi egyértelműen az N≥e feltétel (hiszen az L sorozat üresre állítását nem végzi el senki): egybemosódott a sikeres és az értelmetlen keresést meggátoló kilépés. A sikerességet viszont egyértelműen jelzi az N≥e és X(e)=y feltétel teljesülése. Vagyis a módosult algoritmus:
e:=1
Ciklus amíg N≥e és X(e)<y
e:=e+1
Ciklus vége
Van:=N≥e és X(e)=y
Ha Van akkor SORSZ:=e
(5) Tovább egyszerűsödik az algoritmus, ha sikerül egyszerűsíteni e szétválás érzékelése. A „trükk” mindössze annyi, hogy az utolsó elem előtt kilépünk, s ennek vizsgálatára redukáljuk a problémát:
e:=1
Ciklus amíg N>e és X(e)<y
e:=e+1
Ciklus vége
Van:=X(e)=y
Ha Van akkor SORSZ:=e
Ez a gondolatsor egyben példázza a programtranszformálás mint tipikus programgyártási eszköz működését is, amely lényege, hogy egy algoritmust (programot) ellenőrzött transzformációs lépéseken keresztül módosítunk – általában – a bonyolultság csökkentése céljából.
Hasonló gondolatmenettel juthatunk a logaritmikus keresés ismert algoritmusához, amelynek most csak elindulását és a célhoz érését mutatjuk be.
A ’logaritmikus keresés’ algoritmusához a fogalmi megfeleltetések:
(Lg1) L:=(xi: i∈[e..v]) – a mindenkori eleje-vége; kezdetben:(1..N)
L azonosítható, sőt helyettesíthető is az első és az utolsó elemének indexével:
(Lg1’) L:=L(e,v) → (e,v)
(Lg2) ε(L(e,v)):=εk(L(e,v)):=(e+v) DIV 2 – középső elem
(Lg3) σ(L(e,v)):=σk≤(L(e,v)), ha xL(e,v)<y
(Lg4) σ(L(e,v)):=sk≥(L(e,v)), ha xL(e,v)>y
(Lg5) (Lg1)⇒ ||L(e,v)||:=v–e+1
(Lg6) (Lg5)⇒ ||L(e,v)||>0 ⇔ v–e+1>0 ∧ e,v∈N ⇔ v≥e
A közvetlen származtatás után kapható algoritmus:
(e,v):=(1,N)
Ciklus amíg v≥e és X((e+v) DIV 2)≠y
Elágazás
X((e+v) DIV 2))>y esetén (e,v):=(e,((e+v) DIV 2)-1)
X((e+v) DIV 2))<y esetén (e,v):=(((e+v) DIV 2)+1,v)
Elágazás vége
Ciklus vége
Van:=v≥e
Ha Van akkor SORSZ:=(e+v) DIV 2
Az egyszerűbb leírhatóság érdekében tároljuk az ε(L(e,v))-dik (=(e+v) DIV 2) elem indexrészét a k változóban, e leválasztás viszont a külön kiszámolást jelenti! Másrészt az ’X(k)≠y’ feltétel kétirányúra egyszerűsíti a ciklusmagot. Így az alábbi, „szokásos” algoritmus marad:
(e,v):=(1,N); k:=(e+v) DIV 2
Ciklus amíg v≥e és X((e+v) DIV 2)≠y
Ha X(k)>y akkor v:=k-1
különben e:=k+1
Ciklus vége
Van:=v≥e
Ha Van akkor SORSZ:=(e+v) DIV 2
A backtrack-alapú keresés annyival bonyolultabban származtatható az általános keresés fenti algoritmusából, amennyivel bonyolultabb a „backtrack-logika” szerinti keresési tér. A részletek megtalálhatók a [SzP3/8-9] irodalomban.
Az absztrakcióra vonatkozó eddig részletezett gondolatmenethez az [SzPZsL2/64-65] irodalomban ehhez további érdekes adalékok találhatók. Azt a kérdést vizsgáljuk ott, hogy miként lehet az korábbi, „új fogalom” táblázatban felsorolt absztrakt fogalmakból fölépíteni a backtrack-logika szerint működő más programozási tételeket (megszámlálás, maximum kiválasztás, kiválogatás stb.). Vagyis egy újabb gyümölcsöző következményét tapasztalhatjuk meg e fejezetben bemutatott az absztrakt hozzáállásnak: a keresés – egyfajta – általánosításának. Persze lehet más irányú általánosítás is, például amely az adatszerkezet variálásán alapul: tömb helyett más sorozat féle (lista, szekvenciális input/output fájl stb.), esetleg más sokaság féle (pl. halmaz, gráf)
A programozás során számos lexikális ismeretet kell mozgósítani. Ilyen néhány kis szókincsű, bár nagy variabilitású nyelv: specifikációs nyelv, algoritmikus nyelv, valamely programozási nyelv. A módszeres programozás a kódolást is szabályozza. Így ezekhez társul néhány kódolási szabály is. A programozás elemi szintje fölött lexikális ismeretként említhetők a programozási tételek is, amelyeket a programtranszformációk halmaza tesz teljessé (a programozás már felsőfokú szintjén). Fölvetődik a kérdés: nem súlyosbítjuk a programozás ezen elképzelés szerinti erőltetésével a tanulók képességfejlődés terén tapasztalt, és – többek közt – a PISA-jelentés által feltárt negatív helyzetet? Csupa lexikális ismeret, hol a kreativitás?!?
Világos, hogy a kódolási szabályok célja éppen az, hogy leegyszerűsítse a megcélzott programozási nyelv megismerését. Koncentrálja az ismeretet, ami lerövidíti azt az időt, amely szükséges ahhoz, hogy a kódolás elkezdődhessen. De mi van a többi lexikális ismerettel.
Had idézzünk mindenekelőtt egy szakembert: William James pszichológus-filozófus [KGy/62]:
... az egész nevelés szempontjából döntő jelentőségű, hogy idegrendszerünket szövetségesünkké tegyük, és ne ellenségünkké. El kell érnünk, hogy gyümölcsözően befektethessük és tökéletesíthessük megszerzett tudásunkat, hogy azután kényelmesen élhessünk e tőke kamataiból. Éppen ezért minél előbb automatikussá és megszokottá kell tennünk annyi hasznos cselekvést, amennyit csak lehet. Minél több hétköznapi tennivalónkat bonyolítjuk le automatikusan, megerőltetés nélkül, annál több magasabb szellemi képességet lehet a csak ezek segítségével elvégezhető tevékenységek számára felszabadítani.
Azaz a programozáshoz kapcsolódó ismeretek „bemagolása” olyan instrumentumokat ad a programozó tanulók kezébe, amelyek segítségével kreativitásukat nem apró-cseprő megfogalmazási vagy algoritmikus részletkérdésekre kell elfecsérelniük, hanem az igazi problémák megoldására összpontosíthatják. Vagyis ezen alapokra támaszkodva a kreativitás magasabb fokon, a problémamegoldás felsőbb színterén tud kibontakozni.
Persze veszélyt jelenthet az ún. beállítódás, a „sablonok megcsontosodása”, amelyről Lábos Elemér az alábbiakat írja [LE/61]:
A beállítódás azért különösen érdekes belső mechanizmus, mert két, a gondolkodási folyamatban szerepet játszó dologra utal. A gondolkodás során ismételt feladatokra kész programok kerülnek aktív állapotba, és gyorsítják a megoldást, de ugyanakkor más programok előhívását gátolják.
  |
 |
 |
A tananyag az ELTESCORM keretrendszerrel készült