Vissza az előzőleg látogatott oldalra (nem elérhető funkció)Vissza a modul kezdőlapjáraUgrás a tananyag előző oldaláraUgrás a tananyag következő oldaláraFogalom megjelenítés (nem elérhető funckió)Fogalmak listája (nem elérhető funkció)Oldal nyomtatása (nem elérhető funkció)Oldaltérkép megtekintéseSúgó megtekintése

Tanulási útmutató

Összefoglalás

A programkészítési folyamat legelsőjével fogunk foglalkozni, a specifikációval.

Követelmény

Önállóan megoldható feladatok

A specifikáció

A programkészítés menetének első lépése a feladat meghatározása, precíz újrafogalmazása”. Milyen is legyen, mit várjunk el tőle? Nézzünk meg néhány jónak tűnő követelményt egyelőre címszavakban! (A továbbiakban a specifikáció szűkebb értelmezéséről lesz szó.) A specifikáció legyen:

Miből álljon a fenti feltételeknek megfelelő specifikáció, és milyen eszközökkel írhatjuk le? A kérdés megválaszolásához tekintsünk három példát! (Ezeket fogjuk végig használni ebben a fejezetben, és a sorszámukkal hivatkozunk rájuk.)

Feladat

1. feladat (1. változat): Adjuk meg egy másodfokú egyenlet megoldását!

2. feladat (1. változat): Adjuk meg N ember közül a legmagasabbat!

3. feladat (1. változat): Adjuk meg N ember közül a második legmagasabbat!

A specifikáció első közelítésben lehetne a feladatok szövege. Ez azonban több problémát vethet fel:

A/1. probléma: A másodfokú egyenletet többféle alakban is megadhatjuk, például:

ax2+bx+c=0 vagy (x-a)(x-b)=0.

Melyiket kell a feladat megoldásában használnunk?

A/2. probléma: A legmagasabb ember megadása mit jelent? Adjuk meg a sorszámát, vagy a nevét, vagy a személyi számát, vagy a magasságát, esetleg ezek közül mindegyiket?

Megjegyzés

A 3. feladat problémái sokáig azonosak lesznek a 2. feladatéval, emiatt csak akkor foglalkozunk vele külön is, amikor újdonsággal találkozunk.

Tanulságként megállapíthatjuk, hogy a specifikációnak tartalmaznia kell a bemenő és a kimenő adatok leírását. Pontosítsuk ezek alapján az előbbi feladatokat!

Feladat

1. feladat (2. változat): Adjuk meg egy másodfokú egyenlet megoldását! Az egyenlet ax2+bx+c=0 formában adott.

Bemenet:

a,b,c együtthatók.

Kimenet:

x1,x2 az egyenlet megoldásai.

Feladat

2. feladat (2. változat): Adjuk meg N ember közül a legmagasabbat!

Bemenet:

N az emberek száma,

A a magasságukat tartalmazó sorozat.

Kimenet:

MAX a legmagasabb ember sorszáma.

Feladat

3. feladat (2. változat): Adjuk meg N ember közül a második legmagasabbat!

Bemenet:

N az emberek száma,

A a magasságukat tartalmazó sorozat.

Kimenet:

MAX2 – a második legmagasabb ember sorszáma;

MAG2 – a második legmagasabb ember magassága.

Egy olyan problémával folytatjuk, amely a fenti három példában a feladatszövegek alapján majdnem mindig egyértelműen megoldható, mégis érdemes kitérni rá. Tudjuk-e, hogy a bemenő, illetve a kimenő változók milyen értéket vehetnek fel?

B/1. probléma: Megengedjük-e az a=0 esetet? Ha azt megengedjük, akkor lehet-e ebben az esetben b = 0? És ilyenkor c milyen értékeket vehet fel?

B/2. probléma: Az emberek magasságát milyen mértékegységben kell megadni? Az eredményül kapott sorszám milyen érték lehet: 1-től sorszámozunk, vagy 0-tól?

Megállapíthatjuk tehát, hogy a specifikációban a bemeneti és a kimeneti változók értékhalmazát is meg kell adnunk.

Feladat

1. feladat (3. változat): Adjuk meg egy másodfokú egyenlet megoldását! Az egyenlet ax2+bx+c=0 formában adott.

Bemenet:

a,b,c együtthatók, tetszőleges valós számok.

Kimenet:

x1,x2 az egyenlet megoldásai, tetszőleges valós számok.

Feladat

2. feladat (3. változat): Adjuk meg N ember közül a legmagasabbat!

Bemenet:

N az emberek száma, természetes szám;

A a magasságukat tartalmazó sorozat, egész számok,

amelyek a magasságot centiméterben fejezik ki (a sorozatot 1-től N-ig indexeljük).

Kimenet:

MAX a legmagasabb ember sorszáma, 1 és N közötti természetes szám.

Feladat

3. feladat (3. változat): Adjuk meg N ember közül a második legmagasabbat!

Bemenet:

N az emberek száma, természetes szám,

A a magasságukat tartalmazó sorozat, egész számok,

amelyek a magasságot centiméterben tartalmazzák (a sorozatot 1-től N-ig indexeljük).

Kimenet:

MAX2 a második legmagasabb ember sorszáma, 1 és N közötti természetes szám,

MAG2 a második legmagasabb ember magassága, valós szám, amely a magasságot méterben adja meg.

Most már a bemenő és a kimenő változók értékhalmazát pontosan meghatároztuk, csupán az a probléma, hogy a feladatban használt fogalmakat és az eredmények kiszámítási szabályát nem definiáltuk.

C/1. probléma: Mit jelent az, hogy megoldás? Van-e tetszőleges a-ra, b-re és c-re megoldás? Ugyanúgy kell-e ezeket kiszámolni?

C/3. probléma: Mit jelent az, hogy második legnagyobb? A legnagyobbat kizárva: a maradék közül a legnagyobb vagy pedig a legnagyobbnál alacsonyabbak közül a legnagyobb? (Ha a legmagasabbal egyforma magasságú ember létezik, akkor e két megfogalmazás nem ugyanazt jelenti!) Bár naiv kérdésnek tűnik, de azért feltesszük: hogyan kell a centimétert méterbe átszámítani? (Nem hangzik ennyire magától értetődőnek – legalábbis a mi számunkra, nem „tősgyökeres” angolok számára ha például a kiinduló adatok hüvelykben lennének megadva és az eredményt lábban kellene előállítani.)

A specifikációnak tehát tartalmaznia kell a feladatban használt fogalmak definícióját, valamint az eredmény kiszámítási szabályát. Itt lehetne megadni a bemenő adatokra vonatkozó összefüggéseket is. A bemenő, illetve a kimenő adatokra kirótt feltételeket nevezzük előfeltételnek, illetve utófeltételnek. Az előfeltétel nagyon sokszor egy azonosan igaz állítás, azaz a bemenő adatok értékhalmazát semmilyen „külön” feltétellel nem szorítjuk meg.

Feladat

1. feladat (4. változat): Adjuk meg egy másodfokú egyenlet megoldását! Az egyenlet ax2+bx+c=0 formában adott.

Bemenet:

a,b,c együtthatók, tetszőleges valós számok.

Kimenet:

sz a megoldás „milyenségére utaló” szöveg

x1,x2 az egyenlet megoldásai, tetszőleges valós számok.

Előfeltétel:

a=0 és b=0, akkor c=0.

Utófeltétel:

ha a=0 és b=0 és c=0, akkor sz="nulladfokú az egyenlet, végtelen sok megoldása van"

ha a=0, akkor x1=-c/b, sz="elsőfokú az egyenlet, egy megoldása van"

ha a≠0 és b2<4*a*c, akkor sz="nincs valós megoldás"

ha a≠0 és b2=4*a*c, akkor x1=-b/(2*a), sz="egy kétszeres valós megoldás van"

ha a≠0 és b2>4*a*c, akkor x1=-b+Négyzetgyök(b2-4*a*c)/(2*a), x2=-b-Négyzetgyök(b2-4*a*c)/(2*a),

sz="két különböző valós megoldás van".

Megjegyzés

Itt egy igen ritka utófeltételt látunk, amelyben explicite fejeződik ki a kimenet és a bemenet közötti kapcsolat.

Feladat

2. feladat (4. változat): Adjuk meg N ember közül a legmagasabbat!

Bemenet:

N az emberek száma, természetes szám,

A a magasságukat tartalmazó sorozat, egész számok,

amelyek a magasságot centiméterben tartalmazzák (a sorozatot 1-től N-ig indexeljük).

Kimenet:

MAX a legmagasabb ember sorszáma, 1 és N közötti természetes szám.

Előfeltétel:

Ai-k pozitívak.

Utófeltétel:

MAX olyan 1 és N közötti szám, amelyre AMAX nagyobb vagy egyenlő,

mint a sorozat bármely eleme (az 1. és az N. között).

Feladat

3. feladat (4. változat): Adjuk meg N ember közül a második legmagasabbat!

Bemenet:

N az emberek száma, természetes szám,

A a magasságukat tartalmazó sorozat, egész számok,

amelyek a magasságot centiméterben fejezik ki (a sorozatot 1-től N-ig indexeljük).

Kimenet:

MAX2 a második legmagasabb ember sorszáma, 1 és N közötti természetes szám.

MAG2 a második legmagasabb ember magassága, valós szám,

amely a magasságot méterben adja meg (1 méter=100 centiméter).

Előfeltétel:

N legalább 2, és van a legmagasabbtól különböző magasságú az A sorozatban és Ai-k pozitívak.

Utófeltétel:

MAX2 olyan 1 és N közötti szám, amelyre AMAX2 kisebb, mint a sorozat legnagyobb eleme,

a többinél pedig nagyobb vagy egyenlő (a második legmagasabb ember a legmagasabbnál alacsonyabbak közül a legnagyobb), és

MAG2 éppen egyenlő AMAX2-vel átváltva cm-ről m-re.

Újabb probléma merülhet fel bármelyik feladattal kapcsolatban: az eddigiek alapján a „várttól” lényegesen különböző nyugodtan állíthatjuk: „banális” , az elő- és utófeltételnek megfelelő megoldást is tudunk készíteni.

D/1. probléma: Az x1:=0; a:=0; b:=1; c:=0; sz:="elsőfokú..." utasítássorozat végrehajtása egy olyan állapotot eredményez, amely megfelel az utófeltételnek, de nyilvánvalóan nem helyes megoldás tetszőleges a,b,c-re.

Itt persze arról a hallgatólagos (tehát még meg nem fogalmazott, ki nem mondott) feltételezésről van szó, hogy a bemeneti változók értéke nem változik meg. Ez sajnos, mint láttuk, nem feltétlenül igaz. A probléma megoldására kétféle utat követhetünk (a későbbiekben mindkettőt alkalmazni fogjuk):

A második megoldásból az következik, hogy meg kell különböztetnünk egymástól a feladat és a program elő, illetve utófeltételét! Ez hosszadalmasabbá bár precízebbé – teszi a feladat megfogalmazását, emiatt ritkábban fogjuk alkalmazni.

Előfordulhat, hogy a feladat megfogalmazása alapján nem lehet egyértelműen meghatározni az eredményt, ugyanis az utófeltételnek megfelelő több megoldás is létezik.

E/2. probléma: Ha több, a legmagasabbal azonos magasságú ember van, akkor melyiket kell megadni eredményként?

Ez a jelenség a feladat ún. nemdeterminisztikussága. Az első fejezetben beszéltünk nemdeterminisztikus algoritmusokról is, de rögtön megállapítottuk, hogy ilyenekkel egyelőre nem foglalkozunk. Ehhez a nemdeterminisztikus feladathoz tehát determinisztikus programot kell írnunk, aminek az utófeltétele már nem engedheti meg a nem egyértelműséget, a nemdeterminisztikusságot. E probléma miatt tehát mindenképpen meg kell különböztetnünk egymástól a feladat és a program elő, illetve utófeltételét!

Feladat

2. feladat (5. változat): Adjuk meg N ember közül a legmagasabbat!

Bemenet:

N az emberek száma, természetes szám;

A a magasságukat tartalmazó sorozat, egész számok,

amelyek a magasságot centiméterben tartalmazzák (a sorozatot 1-től N-ig indexeljük).

Kimenet:

MAX a legmagasabb ember sorszáma, 1 és N közötti természetes szám.

Előfeltétel:

Ai-k pozitívak.

Utófeltétel:

MAX olyan 1 és N közötti szám, amelyre AMAX nagyobb vagy egyenlő,

mint a sorozat bármely eleme (az 1. és az N. között).

Program Utófeltétel:

MAX olyan 1 és N közötti szám, amelyre AMAX nagyobb vagy egyenlő,

mint a sorozat bármely eleme (az 1. és az N. között), és előtte nincs vele egyenlő.

Megállapíthatjuk ebből, hogy a program utófeltétele lehet szigorúbb, mint a feladaté, emellett az előfeltétele pedig lehet gyengébb.

Visszatekintve a specifikáció eddig „bejárt pályájára” egy szemléletes modellje körvonalazódik a feladatmegoldásnak. Nevezetesen: nyugodtan mondhatjuk azt, hogy a feladatot megoldó program egy olyan automatát határoz meg, amelynek pillanatnyi állapota a feladat paraméterei (a program változói) által „kifeszített” halmaz egy eleme. (E halmaz annyi dimenziós, ahány paraméterváltozója van a programnak; minden dimenzió egyik változó értékhalmaza. Tehát egy konkrét időpillanatban e „gép” állapota: a változóinak abban a pillanatban érvényes értékeinek együttese.) Ezt a halmazt nevezzük a program állapotterének. Amikor megfogalmazzuk az előfeltételt, akkor tulajdonképpen kihasítjuk ebből az állapottérből azt a részt (azt az altért), amelyből indítva elvárhatjuk az automatánktól (amit a megoldó program vezérel), hogy a helyes eredményt előállítja egy végállapotában. A végállapotot jelöltük ki az utófeltétellel.

Ezt a modellt elfogadva adódik még egy további megoldásra váró kérdés. Akkor ugyanis, amikor a programot írjuk, lépten-nyomon a részeredmények tárolására újabb és újabb változókat vezetünk be. Fölvetődik a kérdés: hogyan egyeztethető össze az imént elképzelt modellel? A válasz egyszerű: minden egyes újabb változó egy újabb dimenziót illeszt az eddig létrejött állapottérhez. Tehát a programozás folyamata leegyszerűsítve a dolgot nem áll másból, mint annak pontosításából, hogy hogyan is nézzen ki a megoldó automata állapottere (és persze: hogyan kell az egyik állapotból a másik állapotba jutnia). A feladatban szereplő paraméterek meghatározta „embrionális” állapotteret hívhatjuk paramétertérnek, ami csak altere a program valódi állapotterének. Ez is azt sugallja, hogy az feladat előfeltétele gyengébb (azaz az általa kijelölt állapothalmaz bővebb) lehet, mint a program előfeltétele. Például:

F/1. probléma: A másodfokú egyenlet kiszámításánál érdemes a diszkriminánst (b2-4ac kifejezés) értékét csak egyszer kiszámítani, és az összes helyen, ahol szerepel, egy segédváltozót helyettesíteni. Ez azt jelenti, hogy a segédváltozóval bővítjük az állapotteret, és figyelembe véve ezt az új „dimenziót”, átalakítjuk az „állapotátmeneti szabályokat” (a kiszámítás utasításait) úgy, hogy

1. legelőször is kapjon értelmes értéket ez a komponens is (a ’D:=b2-4ac’ értékadás bevezetésével),

2. azokat a számításokat, ahol a diszkrimináns előfordult, módosítjuk azzal, hogy számítás helyett erre a komponensre (a D dimenzióra) történjék a hivatkozás.

Látható, hogy a szemléletes szöveges leírás a pontosság érdekében nagyon hosszúvá, akár áttekinthetetlenné is válhat. Szükségünk lenne egy eszközre, amellyel mindezt sokkal rövidebben is leírhatnánk, persze az egyértelműség megtartása mellett. Ezzel későbbi leckékben fogunk foglalkozni.

Összefoglalás

Foglaljuk most össze, hogy melyek a specifikáció részei! Ezek az eddigiek, valamint a programra vonatkozó további megkötések lesznek.

1. A feladat specifikálása:

  • a feladat szövege,
  • a bemenő és a kimenő adatok elnevezése, értékhalmazának leírása,
  • a feladat szövegében használt fogalmak definíciói (a fogalmak fölhasználásával),
  • a bemenő adatokra felírt előfeltétel (a fogalmak fölhasználásával),
  • a kimenő adatokra felírt utófeltétel.

2. A program specifikálása:

  • a bemenő és a kimenő adatok elnevezése, értékhalmazának leírása,
  • (a feladat elő-, illetve utófeltételétől esetleg különböző) program elő- és utófeltétel,
  • a feladat megfogalmazásában használt fogalmak definíciói.

Ezek az absztrakt specifikáció elemei. Az alábbiak másodlagos, mondhatjuk: technikai specifikáció részei:

  • a program környezetének leírása (számítógép, memória- és perifériaigény, programozási nyelv és annak esetleges változata, szükséges fájlok stb.),
  • a programmal szembeni egyéb követelmények (minőség, hatékonyság, hordozhatóság stb.).

A technikai specifikáció nélküli leírást a program szűkebb specifikációjának nevezik.

Egy utolsó gondolattal zárjuk a specifikációval kapcsolatos kérdéskört. A specifikáció precíz elkészítése azzal jár, hogy komolyan belegondolunk a feladatba. Ez önmagában is jó, de ha ehhez hozzátehetjük azt is, hogy a specifikáció által már a megoldó algoritmus szerkezetéről is sokat kimondtunk, az külön öröm. Nézzük meg ezt, hogy is lehetséges ez!

A specifikáció, mint láttuk, egy olyan leképezést határoz meg, amely a bemenő értékekhez hozzárendeli a jó eredmény értékét. (Itt tehát azt az automatát, amelyhez a programot megírjuk, egy leképezést megvalósító gépnek tüntetjük föl. Ez a leképzés az ún. programfüggvény.) A függvények konstruálásánál az alábbi eszközöket szokás igénybe venni:

Az eszköz

A magyarázat

két függvény kompozíciója:

A rekurzív függvény globális formulája.

ami ugyanaz, mint f(g(x)).

alternatívával definiálás:

Az alternatív függvény formalizálása.

ami hosszasabban úgy fogalmazható meg, hogy p(x) legyen f(x)-szel egyenlő, ha T(x) igaz, különben pedig g(x)-szel.

rekurzióval definiálás:

A rekurzív függvény formalizálása.

vagyis feltételtől függően vagy egyszerűen f(x), vagy egy rekurzívan számolható g°f°h(x).

Ha tehát a specifikációban „hagyományos” függvénymanipulációkat alkalmazunk, akkor a következő kapcsolatot fedezhetjük föl ezen manipulációk és az algoritmikus szerkezetek között:

A függvénymanipuláció

Az algoritmikus párja

A rekurzív függvény globális formulája.

g és f kiszámításának szekvenciája:

p(x)

y:=g(x); p:=f(y)

Az alternatív függvény globális formulája.

T-től függő elágazás:

p(x)

Ha T(x) akkor p:=f(x)

különben p:=g(x)

A rekurzív függvény globális formulája.

ciklus vagy rekurzió:

p(x)

Ha T(x) akkor p:=f(x)

különben y:=h(x); z:=p(y); p:=g(z)

Fejezzük be ezt a fejezetet egy jövőbe mutató megjegyzéssel! Kapcsolat létesíthető a specifikáció és egyes részei és az algoritmus egyes részei között. A kapcsolatról röviden:

Specifikáció

Algoritmus

Bemenet, kimenet

Típusdefiníció, típusdeklaráció

Előfeltétel

Beolvasás ellenőrzéssel

Utófeltétel

A finomítások (eljárások, függvények…) törzse

Fogalomdefiníció

Finomítások definíciói

Vissza a tartalomjegyzékhez

Fel a lap tetejére
Új Széchenyi terv
A projekt az Európai Unió támogatásával, az Európai Szociális Alap társfinanszirozásával valósul meg.