Algoritmusleíró módszerek

AZ ALGORITMUS

Különböző feladatokat megvizsgálva azt tapasztalhatjuk, hogy azok két csoportra bonthatók:

Vannak olyan feladatok, problémák, melyek megoldásához adható több-kevesebb iránymutatás, de mindenképpen problémamegoldó gondolkodást, önálló ötleteket kívánnak meg.

Ugyanakkor vannak olyan feladatok, problémák, amelyek megoldására fel tudunk készülni, és a megoldás több hasonló probléma megoldására is használható. A megoldás felbontható meghatározott lépésekre. Ezeket az eljárásokat algoritmusoknak nevezzük.

Az algoritmus: több (gyakran végtelen sok) azonos jellegű, egymástól különböző feladat megoldására használható eljárás, amelynek során utasításszerűen, előre meghatározott számolási lépéseket és döntéseket (utasítás) kell adott sorrendben végrehajtani.

Az algoritmussal szembeni követelmények:

Véges: véges számú lépés után meg kell tudnia határozni a kiindulási feladat megoldását (ez a szám lehet nagyon nagy is), vagy meg kell mutatnia a feladat nem megoldható voltát.

Meghatározott (determinisztikus): a megoldáshoz vezető lépéssorozat tisztán, egyértelműen van megadva és szigorúan követhető.

Input (bemenet): az algoritmus vagy igényel, vagy nem olyan adatokat, amelyeket a kezdetkor (elindulás előtt) meg kell adni. A feladathoz szükséges információ mindig bizonyos meghatározott halmazokból kerül ki.

Output (kimenet): az algoritmushoz egy vagy több output (válaszok vagy eredmények) tartozhat, de legalább egy biztosan van. Ezek meghatározott kapcsolatban állnak az input-tal.

Elvégezhetőség: elvárjuk, hogy az algoritmust végre lehessen hajtani.

Az algoritmusok alapelemei az utasítások.

Az utasítások lehetnek:

Informatív utasítások: amelyek a gépi környezetre, az adatok típusára, a szerkezetre vonatkoznak.

Végrehajtási utasítások: valamilyen művelet végzését írják elő;

Értékadó utasítások: valamely változó értékét definiálják aritmetikai- vagy más függvénykifejezés formájában. Definíciós utasításnak is nevezik.

Feltételes utasítások: végrehajtásuk egy vagy több feltétel teljesülésétől függ.

Vezérlő utasítások: azok, melyek az utasítások eredeti sorrendjének megváltoztatását irányítják.

Input/output utasítások:

– az input utasítás információ-bevitelt hajt végre valamelyik periférikus egységről a központi tárba,

– az output utasítás információátvitel a központi tárból perifériára.

Egyéb utasítások: minden, az előbbiekhez nem sorolható utasítás, pl. az ún. állománykezelők.

Az algoritmusok a bennük előforduló utasítások, valamint azok jellege és tulajdonságai alapján lehetnek:

1. Elemi algoritmusok:

1.1. Soros v. szekvenciális algoritmusok

1.2. Feltételes és elágazásos algoritmusok

1.3. Ciklusok

1.4. Eljárások, szubrutinok

2. Alapvető algoritmusok:

2.1. Egy sorozathoz egy érték rendelése; az összegzés-, az eldöntés-, a kiválasztás-, a lineáris és a bináris keresés-, a megszámlálás- és a maximum-kiválasztás tételei;

2.2. Egy sorozathoz egy sorozat hozzárendelése; a kiválogatás és rendezési tételek;

2.3. Több sorozathoz egy sorozat hozzárendelése; metszetképzés, egyesítés, az összefuttatás és a visszaléptetéses (backtrace) keresés tételei. (Az egyes típusok részletes kifejtésére majd az algoritmusleíró eszközrendszer megismerése után térünk vissza.)

AZ ALGORITMUSLEÍRÓ ESZKÖZÖK

Az algoritmusleíró eszközök használatának célja, hogy a feladatmegoldás menetét világosan bemutassa. Gyakorlatilag géptől független, szemléletes, logikai gondolatmenet. Ez jól jön, ha például többen dolgoznak egy adott feladaton, projekten, könnyebb átlátni ki miért felelős, mit készít el. Saját magunknak is hasznos, ha dokumentáljuk, egy adott feladatot hogyan oldunk meg, milyen változókat mire használunk stb…

Előnyei:

szemléletes algoritmusleírás könnyen áttekinthető és követhető bárki számára,

a világos algoritmusszerkezet gyakran sugall korábban nem is sejtett egyszerűsítő megoldásokat, esetleg egy adott probléma valamilyen irányba történő továbbfejlesztésének lehetőségeit is.

A FOLYAMATÁBRA

A folyamatábra a feladatmegoldás lépéseinek sorrendjét – utasítástípusonként különböző geometriai alakzatok felhasználásával – szemlélteti.

folyamatabra

A jeleket a folyamatábra elkészítése során meghatározott szabályok szerint lehet felhasználni. A legfontosabb szabályokat az alábbiakban foglalhatjuk össze:

a szimbólumok nagysága változhat a beírt szövegnek megfelelően, de a méretek arányait a felismerhetőség korlátozza;

a szimbólumok állását megváltoztatni, azokat elforgatni tilos, mert ezzel a felismerhetőség csökken;

a folyamatok iránya, ha nincs külön megjelölve, mindig balról jobbra és felülről lefelé értelmezendő. Eltérő esetekben nyílhegyeket alkalmazunk az új irány megjelölésére;

a szimbólumok funkciójával kapcsolatos információkat, utasításokat a rajzjelek belsejében helyezzük el;

a folyamatvonalak kapcsolódhatnak egymásba, ilyenkor a becsatlakozó vonalak végére nyílhegyet teszünk. A kapcsolódó folyamatvonalak mindig merőlegesek egymásra,

a folyamatvonalak kereszteződhetnek, de csak merőlegesen. A kereszteződés nem jelent logikai kapcsolatot. (Alkalmazott jelölése (→)

Nézzünk egy egyszerű példát. Adott egy osztály, x darab tanulóval. Számoljuk meg, hányan lettek kitűnőek. Bekérjük az osztály létszámát, majd minden diák átlagát. Azt, hogy hány darab kitűnő van a DB változó fogja tárolni, aminek az értéke kezdetben 0. Ha egy átlag nagyobb, mint 4.5, akkor ennek a DB változónak az értékét növeljük eggyel.  Ha elfogytak a diákok, akkor a végén kiíratjuk, hányan vannak a kitűnők, azaz mennyi a DB értéke.

folyamatabra2

A MONDATSZERŰ LEÍRÁS

Az algoritmus egymást követő lépéseit mondatokkal vagy mondatszerű szerkezetek egymásutánjával próbáljuk leírni. Két fajtája különböztethető meg:

Mondatok sorozata írja le a feladat megoldását. Ezeket a mondatokat sorszámmal látjuk el. Erre azért van szükség, mert a programok legnagyobb részénél el kell térni a soros (szekvenciális) végrehajtástól feltétel nélkül vagy feltételtől függően, és ilyenkor hivatkozhatunk a megfelelő sorszámra.

Szemléletesebb az, amikor mondatok helyett csak ún. mondatszerű szerkezetek egymásutánjával írjuk le a feladat megoldását. Ennél a leírási módnál az algoritmus szerkezeti egységeit bekezdéses struktúra segítségével szemléltetjük.

folyamatabra3

A STRUKTOGRAM

Az algoritmus elemeit egy téglalapba írjuk. A feladatmegoldás struktúrájának (szerkezetének) megfelelően ebbe a téglalapba további téglalapokat illesztünk, és a végrehajtási utasításokat ezekbe írjuk bele. Egymás utáni végrehajtás esetén a téglalapot két vagy több téglalapra osztjuk.

folyamatabra4

 

Háromféle algoritmusleíró módszer terjedt el Magyarországon. Az első leírási módszert még a második generációs gépek idején találták ki, ma is sokan használják. Ez a folyamatábra. A folyamatábrát elsősorban az egyszerűbb rendszerek futtatási folyamatainak ábrázolására találták ki. Előnye az, hogy vizuálisan megmutatja a programok futásának menetét. Az oktatásban, az egyszerűbb folyamatok ábrázolásában nagy szerepe van. Ahogy a programozás egyre inkább tudománnyá vált a folyamatábra már nem felelt meg az egzakt és absztrakt ábrázolásnak, a programozók kitalálták a struktogram-ot. A struktogram precízen ábrázolja a folyamatokat, ugyanakkor olvasása esetenként nehézkes, a valódi programozástól kicsit elrugaszkodott. Formalizmusa precíz, de nehezen értékelhető vizuális ábrákat eredményez. A programozás oktatásában vezették be a mondatszerű leírást vagy pszeudo-kódot. A mondatszerű leírás nagy tért hódított, mivel nagyon jól illeszkedik a Pascal programozási nyelv szintaktikájához, kellően szabadon definiálhatók az egyes programozási elemek, ugyanakkor nem vizuális. A mondatszerű leírás használata esetén a kódolás esetenként a magyar nyelvről az angol nyelvre való fordításra egyszerűsödik. A felsorolt három algoritmus-leíró módszer egyenrangú, mind a három alkalmas arra, hogy kisebb-nagyobb rendszerek algoritmusait megfogalmazzuk segítségükkel. Itt nem tárgyaljuk, de a bonyolult rendszerek leírásához a fenti módszerek egyike sem elegendő ma már, ezért az objektum-orientált programok leírásához az UML (=Universal Modelling Language) az egyik legígéretesebb leírónyelv, amit a jegyzet későbbi részében részletesen tárgyalunk 3.1.1 Folyamatábra A folyamatábrák használatakor grafikai jelekkel jelöljük az egyes programozási egységeket. A grafikai jeleket nyilakkal kötjük össze, a program futásának megfelelő módon. Általában egy program vagy egy eljárás fentről lefelé vagy balról jobbra hajtódik végre, legalábbis a folyamatábra rajzolásánál erre kell törekedni. A szokásos feldolgozási lépéseket az alábbi módon szimbólumokkal jelöljük:

Struktogram A struktogram algoritmus leíró módszer elsősorban a professzionális programozás oktatása során használandó. Ennek a leíró módszernek az előnye rendkívül egzakt módjában és tömörségében van. Talán kezdők számára nem annyira áttekinthető, mint a folyamatábra, de annak hibáit kiküszöböli. A lényeg az, hogy egy programot egymásba ágyazott dobozokkal szemléltetek és minden doboz egyúttal további programszerkezetek tárolója is.

Mondatszerű leírás A mondatszerű leírásnak akkor van értelme, ha a programozó valamennyire tisztában van egy számítógépes program működésével, érti az utasítások egymásutániságát, az értékadás, az elágazások, a ciklusok fogalmát. Érti azt, hogy mit jelent egy eljárás hívása és mit jelent egy függvény hívása. Mint látjuk majd, az algoritmus-leíró nyelv egyfajta magyar nyelvű programozási nyelv. A magyarországi programozás-oktatásban középszinten és egyetemi szinten is több területeken preferálják ezt a módszert, ráadásul az érettségi és az OKJ-s vizsga is tartalmazhat ilyen módon megfogalmazott feladatokat, ezért ezt egy kicsit részletesebben tárgyaljuk. A mondatszerű leírás a következő szintaktikai (=helyesírási) szabályokat tartalmazza:

Egy sorba egy utasítást írunk 2. Változó nevének, típusának és értelmezési tartományának megadása Byte i Egész szám Tomb A[N] szövegekből álló tömb Egy változó típusát nem kell mindig külön deklarálnunk, ha az értékadáskor kiderül a típus. j := 23 3. Beviteli és kiviteli utasítások Ki: Kiíró utasítás Be: Adatbeviteli utasítás 4. Program struktúrák Program jelzése Program Név …… Program vége Eljárás jelzése Eljárás Név(paraméterlista) …… Eljárás vége Függvény jelzése Függvény Név(paraméterlista) …… Nev := visszatérési érték Függvény vége Az eljárásokat és függvényeket az alábbi módon hívhatjuk meg a programból: Név( paraméterlista ) vagy Érték := Név( paraméterlista ) 5. Egy változó értékadása B := érték Pl. B := 65 A két oldalon azonos típusú értékek vannak 6. Vezérlési szerkezetek Feltételes elágazás Ha feltétel igaz akkor Utasítás vagy Ha feltétel igaz akkor Utasítások … Elágazás vége vagy Ha feltétel igaz akkor Utasítások … Különben Utasítások … Elágazás vége Ciklusok Definíció: Megszámlálásos ciklus Olyan ciklus Ciklus cv :=kezdőértéktől végértékig lépésközzel …… Ciklus vége vagy Ciklus amíg feltétel igaz …… Ciklus vége vagy Ciklus …… amíg feltétel Ciklus vége 3.2 Program vagy algoritmus specifikáció Amikor egy programot vagy algoritmus készítünk meg kell határozni, hogy milyen típusú és értéktartományú adatokat kap a program és milyen kimeneti adatokat várunk a programtól. Definíció: Programspecifikáció (algoritmus specifikáció) A program bemeneti és kimeneti adatainak a meghatározása. Meghatározzuk a program bemenő és kimenő adatainak a • Nevét, • Értelmét • Típusát, • Értéktartományát Meg kell határoznunk, hogy a bemenő adatok ismeretében milyen kimenő adatokat tekintünk helyesnek és melyeket helytelennek, azaz meg kell határoznunk az összefüggést a bemenő és kimenő adatok között. 3.3 Algoritmusok dokumentálása Bármelyik algoritmusleíró módszert is használjuk, fontos a program részletes dokumentálása. Az absztrakt módszerek használata esetén (folyamatábra, struktogram) ez fokozottabban érvényes. Az eljáráshívások helyén le kell írni a nem magától értetődő eljárások szerepét, az átadott paramétereket és a visszakapott értékeket. Az eljárás kifejtésekor le kell leírni az eljárás fejlécénél, az átvett értékek és visszaadott értékeket, név és típus szerint. Röviden le kell írni a függvény vagy eljárás szerepét. A programhoz vagy algoritmushoz akkor kell megjegyzéseket fűzni, ha a kód nem teljesen triviális az átlagos fejlesztő számára. Figyelembe kell venni, hogy a programozók egy-két hónap után elfelejtik a saját kódjukat is, tehát inkább több megjegyzést, mint kevesebbet célszerű használni. Az algoritmusok leírásánál mindig törekedjünk a világos áttekinthető leírásra, inkább több helyet hagyjunk egy-egy programrésznek, mint kevesebbet. Használjuk a bekezdéses írásmódot. Ez azt jelenti, hogy az elágazások és ciklusok belseje kezdődjön a médián (papíron, a szövegszerkesztőben) beljebb, mint az elágazás vagy ciklus fejléce. Ugyanígy az eljárások eljárás magja is kezdődjön beljebb az eljárás fejlécénél.