A problémamegoldás lépései

Programozás kapcsán úgy tűnik, kétféle tevékenységről beszélhetünk. Egyrészt léteznek programkészítő szakemberek, akiknek ez a szakmájuk. Ők rendelkeznek mindazzal a módszertani ismerettel, programkészítést támogató eszközök ismeretével, amelyek akár tetszőlegesen nagyméretű, bonyolult rendszerek elkészítéséhez szükségesek.

Sok olyan célfeladat van azonban, amelyekhez nincs szükség egy szakember teljes szakmai fegyvertárára. (Gondoljunk arra, hogy az autónkat elvisszük-e szerelőhöz, ha kereket kell cserélni, lámpát kell cserélni, ... Kicsit hozzáértőbbek még néhány egyszerű javítást is maguk végeznek.) A programkészítés terén is sok olyan célprogram van, amelyet tanult emberek maguk is el tudnak (és kívánatos is, hogy el tudjanak) készíteni, szakember segítsége nélkül.

Ugyanígy természetesnek mondható az is, hogy az algoritmizálás, adatmodellezés ma már az általános kultúra részének tekinthető, így az iskolákban ilyen típusú ismeretekre (ezek tanítására) mindenképpen szükség van.

Van tehát kétféle, a programozással kapcsolatos „kultúrkör”. Az egyik az átlag ember fejében meglévő ismereteken alapul, a másik a „profik piacközéppontú tudományán” nyugszik. Érdemes tehát mindenekelőtt összeszedni, összevetni: melyek is azok a szempontok, amelyek megkülönböztetik e kétféle programozási kultúrát? Az egyes szempontok nem különítik el élesen egymástól a kettőt, inkább utalások a különbözőségre.

A számítógép programozása – hétköznapi algoritmusok

Miből is áll egy feladat megoldása? Kiindulásul tegyük föl, hogy ismerjük a feladatot. „Csúnya” szakzsargonnal élve: elkészítettük a feladat specifikációját. Ezt a természetesnek ható dolgot azért kellett külön említeni, mert tapasztalat szerint éppen természetessége miatt sokszor ez a lépés, a specifikálás lépése marad végiggondolatlan, esetleges: sok-sok kérdést hagy nyitva, amelyek hiánya pillanatnyilag föl sem tűnik. A későbbi lépések során e hiányosságok halmozottan, ismételten föl-föl bukkannak, s emiatt kell több lépést többször is újra megtennünk.

A feladat biztos ismeretében már érdemben dönthetünk arról, hogy a feladat megoldásához milyen eszközöket, módszereket fogunk igénybe venni.

Ha ez megvan, meg kell terveznünk a feladat megoldását, számítógépes feladatmegoldás esetén meg kell alkotnunk a feladatot megoldó algoritmust. Ezt az algoritmust meg kell fogalmaznunk a számítógép számára is érthető nyelven, s valamilyen módon be kell juttatnunk a számítógépbe.

A számítógép ezek alapján már meg tudná adni a feladat megoldását, ha nem lennénk hajlamosak arra, hogy hibázzunk, elfelejtsünk valamit, azaz a számítógép nagyon gyakran nem azt a feladatot oldja meg az általunk megadott utasítássor kapcsán, mint amit mi vártunk tőle. Következő lépésben tehát meg kell győződnünk a megoldás helyességéről, s ha hibáztunk, akkor ki kell javítanunk.

Ahogyan a mindennapi életben, úgy a programokkal kapcsolatban is felmerülhetnek minőségi, gazdaságossági problémák, s nekünk ezekkel is foglalkozni kell.

A program egy termék, s mint minden termék, ő sem eladható értelmes használati utasítás nélkül, tehát még ilyet is írnunk kell.

A programkészítés során tehát több, különböző nehézségű és különböző kvalitásunkat próbáratevő tevékenységgel kell megbirkóznunk. Az egyik legnehezebbnek, legkreatívabbnak, az algoritmuskészítésnek az alapjaival ismerkedhetünk meg e fejezetben, sok hétköznapi példán keresztül.

1. Szörpautomata használati algoritmusa

Mit is nevezünk algoritmusnak, milyen jellemzői vannak, s hogyan kell ilyet csinálni? Vizsgáljunk meg egy egyszerű, mindenki által ismert, nap mint nap megoldott feladatot: hogyan is kell a szörpautomatát használni?

Ez egy algoritmus, szemben a szörpautomata formai leírásával (ami szintén az „szörpautomatáról szól”), amely semmiképpen sem az. Ez alapján az algoritmus jellemzői a következők:

1. végrehajtható,

2. lépésekre bontva hajtható végre,

3. minden lépés vagy elemi utasítás vagy további algoritmus,

4. pontosnak kell lennie meghatározott végrehajtási sorrenddel,

5. véges a leírás (bár a végrehajtása korántsem mindig véges).

Értelmezzük az egyes vonásait az algoritmusnak:

1. Lehet hozzá végrehajtót (egy valakit, egy gépet, egy processzort, egy LOGO-teknőcöt stb.) találni, neki, az „Ő nyelvén” szól.

2. Világos a végrehajtó számára, hogy mit tekintsen lépésnek (a neki szóló „mondat” egy szavának).

3. Elemi az, ami értelme felöl nincs kétsége a végrehajtónak, „magáért beszél”, és persze képes is ennek „szellemében” cselekedni. Ha egy lépés önmagában nem egyértelmű (azaz számára új „fogalom”), akkor azt részletezni, értelmezni kell. Más szóval: meg kell adni a lépés (az új fogalom) részletes (további) részlépésekből összeálló algoritmusát. És ezt mindaddig kell folytatni, amíg a végrehajtásban már csak alapszavakkal kell megbirkóznia a végrehajtónak. Például a „Tárcsázzon!” felbontható 6-7-... számjegy egymásutáni tárcsázására, sőt egy számjegy tárcsázása különböző típusú telefonkészülékeken mást és mást jelenthet.

4. Nemcsak az egyes lépések önálló jelentése kell, hogy tiszta legyen, hanem az is, hogy melyiket mikor kell, lehet elvégezni; ez által lesz az egész algoritmus teljes, pontos. (Ahogy pl. a következő két nyelvtanilag helyes magyar mondat is azonos szavakból áll, de teljesen más értelemmel rendelkezik: „az úr ír”, ill. „az ír úr”, ugyanígy döntő az algoritmus lépéseinek sorrendje is.)

5. Ez azt jelenti, hogy előadódhatnak olyan helyzetek, amikor ez a végesen megfogalmazott parancs-sorozat precíz végrehajtása esetén soha sem ér véget. Gondoljunk csak arra, hogy ha a fenti algoritmust nem egy értelmes ember hajtaná végre, akkor a „Várja meg a tárcsahangot!” utasítás hatására rossz telefonkészülék esetén akár végtelen sokáig is várakozhatna.

A példában egy olyan algoritmust láttunk, ahol elemi tevékenységeket kellett végrehajtani, mindegyiket végre kellett hajtani, s adtunk hozzá egy egyértelmű végrehajtási sorrendet. A szörpautomata használatának menetén keresztül most azt vizsgáljuk, hogy elemi lépéseket hogyan, milyen sorrendben lehet végrehajtani.

Itt megjelent egy újdonság: elemi tevékenység többszöri végrehajtása. A végrehajtás számát egy feltételtől tettük függővé: addig kell várni, amíg megtelik a pohár. Az egymás után végrehajtandó elemi tevékenységek is különbözőek. Például a 'Vedd ki a poharat!' és az 'Idd meg a szörpöt!' nevű tevékenységet csak ilyen sorrendben lehet elvégezni, fordítva nem, s egyszerre sem. Ugyanakkor a 'Válaszd ki a megfelelő szörpöt!' és a 'Dobj be egy 100 Ft-ost!' tevékenységek sorrendje tetszőleges lehet, sőt akár egyszerre is végezhetjük őket.

Tehát, ha elemi tevékenységek mindegyikét végre kell hajtani, akkor a végrehajtás sorrendjére három szabály is alkalmazható: Adott sorrendben egymás után kell végrehajtani, tetszőleges sorrendben lehet egymás után végrehajtani, lehet párhuzamosan, egyszerre végrehajtani őket.

A bevezetőben arról volt szó, hogy az algoritmus végrehajtása nem feltétlenül véges. Ez persze a legtöbb esetben (mint most is) hiba. Ezért, amikor elemi tevékenységek ismétlését írjuk le, akkor mindig meg kell gondolni, hogy az ismétlés befejeződik-e. Most például elképzelhető a végtelenség, ha az automata csak félig adja a poharat. Módosítsuk az ismétlés feltételét!

Persze elképzelhető, hogy a pohár megtelik, s a szörp tovább folyik ..., érdemes ezen is elgondolkodni, de most mi más úton fogunk továbbhaladni.

Nézzünk egy másik problémát! Mit tehetünk, ha nincs 100 Ft-osunk és az automata elfogad 20 Ft-osokat is?

Újdonság itt az, hogy most megadtunk két tevékenységet ('Dobj be 5 db 20 Ft-ost!', valamint 'Dobj be egy 100 Ft-ost!'), de közülük csak az egyiket kell elvégezni, azaz választani kell közülük.

A megoldás nem tartalmazza azt a lehetőséget, amikor nincs sem 20, sem 100 Ft-osunk. Ugyanakkor, ha van 5 db 20 Ft-os és van 100 Ft-os is, akkor a fenti két lehetőségből bármelyiket választhatjuk.

Tehát újdonságként megjelent a több lehetőségből való választás, amelyben ráadásul a választás nem is egyértelmű.

Nézzük meg, mit tehetünk, ha egyáltalán nem folyik szörp!

Most egy olyan utasítást is be kellett vezetnünk, amely azt „szervezi meg”, hogy valamit vagy végre kell hajtani, vagy nem. Fölbukkant egy újabb fajta ismétlés is, ebben csak azután nézzük meg, hogy kell-e még ismételni, miután az ismétlődő utasítás(oka)t egyszer már végrehajtottuk.

A 20 Ft-osokat persze egyenként kell bedobni, s nem egyszerre. Ezért a megoldás kicsit precízebben így fogalmazható meg:

Harmadik fajta ismétlést láthatunk ebben a megoldásban: megmondtuk pontosan, hogy hányszor kell az ismétlendőt megismételni.

Nézzük meg, hogy az összetett algoritmusainkat milyen módon bontottuk elemibbekre!

1. Az összetett algoritmus több elemibb algoritmusból áll, és mindegyiket végre kell hajtani.

a) A végrehajtási sorrend adott, s egyszerre csak egyet lehet végrehajtani.

b) A végrehajtási sorrend tetszőleges, s egyszerre csak egyet lehet végrehajtani.

c) A végrehajtási sorrend tetszőleges, akár egyszerre is végre lehet hajtani az összeset.

2. Az összetett algoritmus egy vagy több elemi algoritmusból áll, és ezek közül csak legfeljebb az egyiket kell végrehajtani.

a) 1 elemi algoritmust vagy végrehajtunk, vagy nem.

b) 2 elemi algoritmus közül egyértelműen választanunk kell az egyiket.

c) Sok elemi algoritmus közül egyértelműen választanunk kell az egyiket.

d) Sok elemi algoritmusok közül választanunk kell az egyiket, de a választás nem egyértelműen definiált.

3. Az összetett algoritmus 1 elemi algoritmus ismétléséből áll.

a) Tudjuk, hogy pontosan hányszor kell végrehajtani.

b) Tudunk mondani egy feltételt, aminek teljesülése esetén még végre kell hajtani.

c) Tudunk mondani egy feltételt, aminek teljesülése esetén még végre kell hajtani, de a feltétel vizsgálatához az ismétlendőt egyszer már végre kellett hajtani, azaz legalább egyszer „lefut” az ismétlendő.

Az 1/b és az 1/c megvalósítható az 1/a segítségével, a 2/d pedig a többi 2-es valamelyikével, így ezekkel külön nem foglalkozunk.

Az 1. megvalósítását a programozásban egymás utáni végrehajtásnak, szekvenciának nevezzük, a 2.-at választásnak vagy elágazásnak, a 3.-at pedig ismétlésnek vagy ciklusnak.

Az 1/b és a 2/d hozná be a programozásba az ún. nemdeterminisztikusságot, az 1/c pedig a párhuzamosságot.

2. Jegyárusító automata

Újabb példánkkal egy vasútállomáson használható jegyárusító automata működését írjuk le. A korábbiakban már megállapítottuk, hogy a túlságosan nagy „szabadság” az algoritmusírásban felesleges bonyodalmakat okoz, célszerű lenne az algoritmusok leírására használatos nyelvünket egységesíteni, rögzíteni, s a leírás mögötti tartalomban megegyezni. Ezt majd a következő fejezetekben tesszük meg, de már ebben a példában is használjuk ezen – általunk javasolt – „szabványos” nyelvet.

A szabványos algoritmikus elemeket vastag betűkkel jelöljük a továbbiakban. Ez a kiemelés hasznunkra lesz, mivel első pillantásra is áttekinthetővé teszi a tevékenység(nek legalább a) szerkezetét.

Elképzeljük a megoldást: az automatán – általános szokás szerint – látszanak azok az állomások, amelyekre jegyet képes adni. Olvasható az is, hogy mennyibe kerülnek az egyes jegyek. Például az alábbi képet társíthatjuk az automatához.

Kezdjük ismét a kellékekkel! Szükség lesz:

• bedobott pénzre,
• visszajáró pénzre,
• jegyre,
• állomás(sorszám)ra.

Jegyárusító automata.

Az algoritmus legfelső szintjét nevezzük programnak. A megoldás tehát első közelítésben:

Elágazásoknak algoritmusleíró nyelvünkben nemcsak az elejét, hanem a végét is jelezni fogjuk, kivéve, ha e nélkül is egyértelmű. A bekezdések mindig utalnak a struktúrára, azaz utasítások együvé tartozó csoportját jelzik. Bekezdés vége a struktúra végét is jelöli.

Megjegyzés

1. A visszajáró pénzről juthat eszünkbe, hogy egységesíteni lehetne a pénz visszaadást, ha az 'Adj vissza' tevékenység mindig a visszajáróban találja a neki megfelelő mennyiséget. Így az elágazás akkor-ága (azaz az akkor kulcs-szóval bevezetett struktúra) a következőképpen módosul:

visszajáró:=bedobott
Adj vissza [Ki: visszajáró]

2. Ennél „igazibb” megoldás, ha –a már korábban körvonalazott– paraméterezett eljárással oldjuk meg a visszaadást; az alábbi módon:

Az "Adj vissza" paraméterezett eljárás.

Jegyezzük meg, hogy a résztevékenységeket algoritmizáló programrészeket eljárásoknak nevezzük! Az eljárás mindig azzal a névvel kezdődik, amellyel korábban hivatkoztunk rá. Vagyis erre utalunk a programunk fent tisztázott szintjén két helyen is:

Folytassuk a részletezést az egyes résztevékenységekkel! A 'Várd az állomást'-ban megjelenik a felhasználóval való kommunikáció másik utasítása (a Ki: párja), a beolvasás.

Mint minden, ami fix, rögzített, ami eleve „kiírattatott” az automata dobozára, úgy az algoritmusbeli táblázat is „eleve megvan”, s nem fog a használat által változni. Az ilyen adatféleséget korábban konstansnak neveztük. Itt persze az eddig megszokott „triviális” konstansoktól (5, 10, ..., 3.1415, ...) több szempontból is eltérő valamivel találkozunk. Első újdonság: általunk adott neve van (táblázat), második: „bonyolult” szerkezetű. Egy fontos fogalompárral érdemes megismerkednünk ezzel kapcsolatban: adataink lehetnek strukturálatlanok (mint a max, vagy a bedobott stb.), s lehet szerkezetük (amilyen a táblázat).

A pénz számlálására alapesetben elég egy beolvasó utasítást írni.

Mivel az a megoldás nagyon elüt a valóságtól, ezért ezt a későbbiekben „részletesebbel”, egy reálisabbal helyettesítjük:

Hogy mi a megengedett, attól először –legalábbis a kódolásnál– célszerű eltekinteni. Kiemelendő az eljárásban a Van még pénz függvényszerű beépítése, amelynek a kérdésre adott válasz logikai értékét kell előállítania. (Ennek a tevékenységnek –ti. összegzés– visszatérő voltáról esik még szó: sorozatszámítás tétel első előbukkanásának tekinthető.)

A pénz visszaadása első esetben szintén egyetlen kiírásból állhat.

Ezt az eljárást átalakíthatjuk olyanná, amely megmondja, hogy melyik pénzérméből mennyit kell visszaadni.

A pénzvisszaadáshoz nem az egyetlen lehetséges elképzelést valósítottuk meg, hogy ti. a legkevesebb számú pénzben történjék. Ha a beolvasásnál ellenőriztük az érmék helyességét, akkor már abban az eljárásban kellett az érme vektort deklarálnunk. (És íme egy újabb visszaköszönő algoritmusfajta prototípusa: a kiválasztás tétel első előfordulása.)

Tanulságként hívhatjuk föl a figyelmet arra, hogy „bonyolult” szerkezetű adatok egészére (jegy), vagy annak még nem feltétlenül elemi részére (táblázat egy sorára) is lehet (illetve így lehet) hivatkozni.

A eljárásfüggvénynek egyetlen érdekessége van: hogyan kell a függvény értékének megadásáról gondoskodni.

Az 'Írj tájékoztatót' eljárás tisztázását, mint algoritmikusan nem problematikust, a kódolásra hagyjuk (azaz csak a konkrét programozási nyelven megfogalmazandónak vesszük).

3. Metróvezető algoritmusa

A párhuzamossággal a továbbiakban ritkán fogunk foglalkozni. Hogy ne maradjon ki teljesen ennek jellegzetes „problémavilága”, az alábbiakban egy tanulságos példán keresztül vizsgálódunk. Nézzük meg, mit kell tennie egy metróvezetőnek a metróállomáson!

Ebben a példában tehát kimondottan párhuzamosan elvégzendő tevékenységeket adtunk meg, amelyeket az ÉS KÖZBEN szópár köt össze.

Párhuzamosan zajló „események” algoritmizálása közben (röviden: „párhuzamos környezetben”) szükség lehet egyes folyamatok várakoztatására a részfolyamatok szinkronizálódása érdekében. Ezt láthatjuk a következő algoritmusvariációban.

Nemcsak elemi tevékenységek végezhetők párhuzamosan, hanem tetszőleges összetett (több utasítást tartalmazó) programstruktúrák is:

Vissza a tartalomjegyzékhez

A programkészítés folyamata

A bevezető ismeretek után pontosítsuk a programkészítés folyamatát, annak egyes lépéseit. Talán most már senkit sem fog meglepni, hogy ez a szorosan vett programozási nyelven történő ún. kódoláson túl jó néhány más tevékenységet is tartalmazni fog.

Az első teendő a feladat pontos meghatározása, a specifikáció. Ez a feladat szöveges és formalizált, matematikai leírásán (a specifikáció ún. szűkebb értelmezésén) túl tartalmazza a megoldással szemben támasztott követelményeket, környezeti igényeket is (ami a specifikáció ún. tágabb értelmezése).

A specifikáció alapján meg lehet tervezni a programot, elkészülhet a megoldás algoritmusa és az algoritmus által használt adatok leírása. Az algoritmus és az adatszerkezet finomítása egymással párhuzamosan halad, egészen addig a szintig, amelyet a programozó ismeretei alapján már könnyen, hibamentesen képes kódolni. Gyakran előfordul, hogy a tervezés során derül fény a specifikáció hiányosságaira, így itt visszalépésekre számíthatunk.

Az algoritmusírás után következhet a kódolás. Ha a feladat kitűzője nem rögzítette, akkor ez előtt választhatunk a megoldáshoz programozási nyelvet. A kódolás eredménye a programozási nyelven leírt program.

A program első változatban általában sohasem hibátlan, a helyességéről csak akkor beszélhetünk, ha meggyőződtünk róla. A helyesség vizsgálatának egyik lehetséges módszere a tesztelés. Ennek során próbaadatokkal próbáljuk ki a programot, s az ezekre adott eredményből következtetünk a helyességre. (Ne legyenek illúzióink afelől, hogy teszteléssel eldönthető egy program helyessége. Hisz hogy valójában helyes-e a program –sajnos– nem következik abból, hogy nem találtunk hibát.)

Ha a tesztelés során hibajelenséggel találkozunk, akkor következhet a hibakeresés, a hibajelenséget okozó utasítás megtalálása, majd pedig a hibajavítás. A hiba kijavítása több fázisba is visszanyúlhat. Elképzelhető, hogy kódolási hibát kell javítanunk, de az is lehet, hogy a hibát már a tervezésnél követtük el. Javítás után újra tesztelni kell, hiszen –legyünk őszinték magunkhoz!– nem kizárt, hogy hibásan javítunk, illetőleg –enyhe optimizmussal állítjuk:– a javítás újabb hibákat fed fel, ...

E folyamat végeredménye a helyes program. Ezzel azonban még korántsem fejeződik be a programkészítés. Most következnek a minőségi követelmények. Egyrészt a hatékonyságot kell vizsgálnunk (végrehajtási idő, helyfoglalás), másrészt a kényelmes használhatóságot. Itt újra visszaléphetünk a kódolási, illetve a tervezési fázisba is. Ezzel elérkeztünk a jó programhoz.

Egyetlen program –általánosabban fogalmazva: termék– sem használható megfelelő leírások, ún. dokumentáció nélkül, így még ez a teendő van hátra. Bár ezt a folyamat végén említjük, de korántsem jelenti azt, hogy időben is a végén kell elvégezni. A dokumentálást már a feladat-meghatározásnál el kell kezdeni, s folyamatosan, a befejezésig kell készíteni. (Az előbbi mondatban szereplő 'kell' szót senki se tekintse valami kellemetlen, kívülről ránk erőszakolt kényszernek, hisz nekünk, magunknak is támaszt jelenthet a dokumentáció „torzója” abban, hogy vissza-visszanyúljunk korábbi döntéseinkhez, megállapodásokhoz, és nem kell rettegnünk emlékezetünk korlátai miatt.

„Hosszú életű”, professzionális programoknál még ezután kezdődik egy igen nagy fontosságú munka, a karbantartás. (Erről részletesebben azért nem szólunk, mert könyvecskénknek csak a kezdők bevezetése volt célja, tehát ez most még nem lesz igazán érdekes számunkra.)

A programkészítés folyamata.

Programkészítési folyamat lépése	Mire keresi a választ	Mi a végterméke?
Feladatmegfogalmazás	Miből? Mit? Mi a kapcsolat?	Specifikáció
Tervezés	Hogyan ábrázoljam? Hogyan végezzem el?	Adatleírás + algoritmus
Kódolás	A számítógép hogyan ábrázol­ja, és hogyan végezze el?	Kód
Tesztelés	Helyes-e?	Tesztesetek
Hibakeresés	Hol a hiba?	Hibahely-lista
Hibajavítás	Mi a hiba oka, hogyan küszö­bölhető ki?	Hiba-ok és javítási javaslat
Hatékonysági tesztelés	Hogyan függ a paraméterektől az időbeli működése és a hely­foglalása? Kielégítő-e?	Hatékonysági tesztesetek
Rossz hatékonyságú pontok keresése	Mely kódrész felelős a nem várt idő- / helyfelhasználásért?	Problematikus helyek listája
Hatékonyságnövelés	Hogyan gyorsítható, hogyan tehető kisebb helyigényűvé?	Probléma-ok és módosítási ja­vaslat
Dokumentálás	Hogyan telepíthető, használ­ható, hangolható?	Dokumentáció

Vissza a tartalomjegyzékhez