Bevezetés
Algoritmusok leírása¶
Az algoritmusnak, mint műveletnek a legfontosabb része tehát az, hogy megadjuk annak vezérlését, azaz azt az előírást, amely az algoritmus minden lépésére kijelöli, hogy a lépés végrehajtása során melyik lépés végrehajtása következik.
Az algoritmusok leírására többféle módszer használható.
- A legegyszerűbb a természetes nyelvi leírás, ami szövegesen, mondatokba foglalva írja le az algoritmust. Ez a leírás nagyon távol állhat a "gép" megvalósításától.
- A következő lehetőség, amikor az algoritmust pszeudó kóddal adjuk meg. Ez egy programozás nyelv szerű strukturált nyelv, de sokkal szabadabb, mint egy valódi programozási nyelv, hiszen ebben nem kell minden részletet definiálni.
- A folyamatábra egy grafikus, kevésbé strukturált gráf reprezentációja a végrehajtásnak, amely a működési folyamatra koncentrál.
- A szerkezeti ábra egy szintén grafikus, strukturált leírása az algoritmus felépítésének leírására, amely leírja a működési folyamatot is.
Folyamatábra¶
Ha csak a kész algoritmus működését szeretnénk leírni, és a szerkezete kevésbé fontos, akkor használhatjuk a folyamatábrát, mint leíró nyelvezetet. Ez egy olyan ábra, amelyben az algoritmus egyes lépéseit a gráf csúcspontjaiban definiáljuk, amely pontokat irányított nyilakkal kötjük össze, ezzel kijelölve a végrehajtás irányát. A folyamatábra által leírt algoritmus nagyon közel áll az alacsony szintű programozáshoz, az assembly nyelvhez.
Mint minden nyelvnek, így a folyamatábrának is megadhatjuk a szintaxisát. Legyenek M={M1, ..., Mk} műveletek és F={F1, ..., Fl} feltételek. Az (M,F) feletti folyamatábrán olyan irányított gráfot értünk, amelyre teljesül a következő 5 feltétel:
- Van egy olyan pontja, ami a Start művelettel van címkézve, és ebbe a pontba nem vezet él.
- Van egy olyan pontja, ami a Stop művelettel van címkézve, és ebből nem indul ki él.
- Minden pontja vagy egy M-beli művelet, vagy egy F-beli feltétel a Start és Stop pontokon kívül.
- Ha egy pont
- M-beli művelettel van címkézve, akkor belőle egy él indul ki
- F-beli feltétellel van címkézve, akkor belőle két él indul ki, és ezek az i (igen), illetve n (nem) címkéket viselik.
- A gráf minden pontja elérhető a Start címkéjű pontból.
A szintaktika megadása után folyamatábra szemantikáját, azaz jelentését is meg kell adjuk. A folyamatábra a következő összetett vezérlési előírást jelenti, azaz a következőképpen kell értelmezni:
- A végrehajtást a Start pontból kell kezdeni.
- Az összetett utasítás akkor ér véget, ha elértük a Stop pontot, azaz a vezérlést megkapja a Stop pont.
- A gráf egy pontjának a végrehajtását attól függően definiáljuk, hogy az M-beli utasítással, vagy F-beli címkével van címkézve.
- Ha a pontban M-beli művelet van, akkor a művelet végrehajtódik és a vezérlés a gráf azon pontjára kerül, amelybe a pontból kiinduló él vezet.
- Ha a pont F-beli feltétellel van címkézve, akkor kiértékelődik a feltétel. Ha az értéke igaz, akkor az a pont kap vezérlést. amelybe az i (igen) címkéjű él vezet, egyébként az a pont kapja meg a vezérlést, amelybe az n (nem) címkéjű él vezet.
Egyszerű példa folyamatábrára:
Amikor ennek a folyamatábrának a végrehajtását megkezdjük, a Start pontból a vezérlés rákerül az M1 utasítást tartalmazó blokkra. Ezt az utasítást végre kell hajtani, majd ezután az F1 feltétel kiértékelése történik meg. Ha ez a felétel igaz, akkor végrehajtjuk az M2 utasítást is, és eljutva a Stop csomópontig az összetett utasítás végrehajtása befejeződik, vagy rögtön befejezzük az összetett utasítás végrehajtását az F1 pontból rögtön a Stop csomópontba jutva.
Kicsit nagyobb összetettebb esetet ír le a következő folyamat ábra:
A Startból a Stop pontba vezető összes lehetséges útvonal kijelöli az algoritmus potenciális végrehajtási lehetőségeit. Látható, hogy az algoritmus újra és újra visszatérhet az M1 vagy M3 utasításhoz több átfedő ciklust is kialakítva, amely ciklusokból akkor tudunk csak kilépni, ha a megfelelő feltételek ezt megengedik.
Szerkezeti ábra¶
Az algoritmus tervezése során szerkezeti ábrával (structure diagram, struktúradiagram) (is) le tudjuk írni, hogy a problémát milyen részproblémákra bontottuk, és a megoldásukat milyen módon raktuk össze. A szerkezeti ábra egyszerre fejezi ki az algoritmustervezés folyamatát és a kifejlesztett algoritmust is.
Egy részprobléma megoldását leíró szerkezeti ábrarész különálló ábrával is kifejezhető, amelynek gyökerében a részprobléma megnevezése áll. Minden vezérlési módhoz bevezetünk egy szerkezeti ábra jelölést. Az egyes vezérlések szerkezeti ábra jelöléseit a vezérléseknél mutatjuk be.