Algoritmus-modellezés folyamatábrákkal

Szerz®

Témavezet®

Bernád Kinga

Lect. Dr. Darvay Zsolt

Babe³-Bolyai Tudományegyetem

Babe³-Bolyai Tudományegyetem

Matematika és Informatika Kar

Matematika és Informatika Kar

Informatika szak, 3. évfolyam

Programozási Nyelvek és Módszerek Tanszék

Algoritmus-modellezés folyamatábrákkal

XI. Erdélyi Tudományos Diákköri Konferencia

Kolozsvár 2008. Május 23-24.

Kivonat Napjainkban a programok tervezése igen fontos szerepet játszik a jó projektek elkészítésében. Az algoritmusok modellezése viszont nem fejl®dött a kell® mértékben. Ennek oka az, hogy nem áll rendelkezésünkre megfelel® technológia a folyamatábrák készítéséhez, amely jelent®s mértékben megkönnyíthetné a fejleszt®k feladatát.

Azért választottam

ezt a témát, mert úgy látom, hogy egy megfelel® algoritmus modellez® alkalmas lenne a középiskolások oktatására is, és a tapasztalattal rendelkez® fejleszok számára is. Az alkalmazás algoritmus modellezésre és kódgenerálásra használható, de egy UML modellez®eszközbe integrálás is megvalósítható.

Tartalomjegyzék

1. Bevezetés

4

1.1.

A folyamatábrák

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.2.

Az UML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.2.1.

Az UML nézetei [8] . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.2.2.

A diagramok

9

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2. Az algoritmus-modell

11

2.1.

A modellez® részei

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.

A modellez® felépítése

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

2.3.

Használt programozási eszközök . . . . . . . . . . . . . . . . . . . . . . . .

15

2.4.

A modellez® m¶ködése és további tervek

16

3

. . . . . . . . . . . . . . . . . . .

11

1. fejezet Bevezetés

Napjainkban egyre inkább nélküközhetetlenné válnak a számítógépek és a számítógépes szoftverek használata.

Egyre többen döntenek a programfejlesztés mellett, mert látják

annak fontosságát, jöv®jét. Egy jó program elkészítéséhez nem elég ismerni a megfelel® programozási nyelvet, a környezetet, amelyben futtatni szeretnénk, többr®l van itt szó, a tervezésr®l. Egy jól megtervezett program felgyorsítja a fejleszt® munkáját. Az algoritmusok modellezése viszont nem fejl®dött a kell® mértékben. A programozók nem látták értelméte módszernek hiszen megkétszerezte munkájukat. Ennek oka az, hogy nem áll rendelkezésünkre megfelel® technológia a folyamatábrák készítéséhez, amely jelent®s mértékben megkönnyíthetné a fejleszt®k feladatát. E dolgozat ráébreszt a program tervezésének fontosságára, eszközöket, ötleteket tár eléd a fejlesztéssel kapcsolatban, valamint egy olyan programot mutatbe, amely el®segítheti az algoritmusok fejlesztését. Olyan tanárokna ajánlom, akik készek egy új módon oktatni, és megszerettetni tanítványaikkal az algoritmusok helyes tervezését folyamatábrák segítségével. A fejeleszt®k és szoftvertervez®k gyelmébe is ajánlom, hiszen beépítve egy UML modellez®be, még eredményesebbé tehetik munkájukat. A továbbiakban tárgyalom az alkalmazást és a vele kapcsolatos továbbfejlesztési terveimet. Megtudhatod, milyen f®bb elemeket használtam az elkészítéséhez. Majd a metamodell bemutatja, milyen fontosabb osztályokat használtam a folyamatábra elkészítéséhez. El®bb azonban lássuk a folyamatába készítés és az UML modellezési eszköz fontosabb részeit.

4

1. FEJEZET. BEVEZETÉS

5

1.1. A folyamatábrák A folyamatábra-készítés egy olyan modellezési módszer, amely lehet®séget biztosít egy folyamat eseményeinek, tevékenységeinek, lépéseinek vizuális tervezésére, szemléltetésére valamint megértésére. Áttekinthet®bbé teszi a folyamatok kapcsolódását, és ezáltal nagyobb lehet®ségünk lesz a hibamentes m¶ködés megvalósítására. A folyamatábrák elemeit szimbólumokkal -, az elemek közötti kapcsolatot (a folytamat irányát) nyilakkal jelöljük.

Készítésének három f® típusa létezik, amelyeket bármilyen

esetben használhatunk[4]:

•

makró folyamatábrák (magas szint¶ folyamatábrák)

•

részletezett folyamatábrák

•

struktúrált részletezett folyamatábrák

1.1. ábra. A makró folyamatábrák: csak annyi információt tartalmaznak, amennyi a feladat általános megértéséhez szükséges. Nincsenek benne döntési pontok.

A folyamatábra készítésének több el®nye is van: áttekinthet®bbé, tisztábbá teszi számunkra az algoritmusokat, könnyebben megérthetjük m¶ködésüket, a középiskolásoknak nagy el®nyt jelent, különösen amikor bevezetik ®ket az algoritmusok világában, el®re megtervezhetjük a kívánt algoritmust. A legf®bb el®nyét a programozásban látom: már a tervezés közben olyan hibákat vehetünk észre, amelyek esetleg több plusszórai munkát jelentettek volna számunkra. Hátrányokból sem szenved hiányt: ha túl bonyolult az algoritmus esetleg megnehezítheti a kódolást, amivel szintén hátrányba kerülhetünk, de ha megfelel®en struktúráljuk az algoritmust, akkor ezt a problémát elkerülhetjük.


6

1.2. ábra. A részletezett folyamatábrák a feladat minden tevékenységét és döntési pontját tartalmazza (algoritmusok megjelenítésére a legalkalmasabb).

1.3. ábra. A struktúrált részletezett folyamatábrák:

úgy struktúráljuk a folyamatábra

elemeit, hogy a képzeletbeli oszlopok egy-egy szervezeti egységet, vagy felel®st mutatnak.


7

1.2. Az UML Talán mondhatjuk azt, hogy a folyamatábra készítése volt az els® modellezési eszköz, az els® számítógép megjelenése el®tt használták már az e fajta modellezést.

De sajnos

a feladatok elbonyolódása és az alkalmazások megnövekedése miatt új modellezési módszerekre lett szükség. Olyan eszközökre, amelyek lehet®vé teszik a fejleszt® számára a feladatok kidolgozását, valamint a már meglév® feladatok újrafelhasználását. Ezen igények felismerése eredményezte az UML-t, mint modellezési eszközt, amely jóval kés®bb jelent meg, mit a folyamatábrák, az 1990-es évek végén. Az UML egy szabványos egységesített

modellez®nyelv, amely az alkalmazások inkre-

mentális és architektúra szemlélet¶ fejlesztésére, valamint a különböz® fejlesztési modellek rendkívül jó szemléltetésére alkalmas. Ezáltal a modellez® által a tervezés, a specikáció, a dokumentálás mind grakus formában, mind beszédes ábrák, diagramok, táblázatok segítségével könnyedén végezhet®.

1.2.1. Az UML nézetei [8] Mivel a fejlesztésben résztvev® szakemberek különböz® módon látják a rendszert, ezért olyan módszert kell alkalmazni, mely képes kezelni a

sokrét¶séget, valamint elég egyszer¶

mindenki számára. Ez alapján UML öt nézetre osztható:

•

Használati eset nézet (Use case view) A rendszer viselkedését, funkcionalitását írja le a szerepl®k és a feladatok megjelölésével, a felhasználó szemszögéb®l nézve. (A szerepl® (actor) olyan személy vagy elem, amely kapcsolatban áll a rendszerrel, és aktívan kommunikál azzal, funkciókat indít el, vagy hajt végre.)

A használati esetek jól meghatározott funkciók, ame-

lyek végrehajtása üzenetváltást kíván. Meghatározó szerepet játszanak a fejlesztési folyamatban, hiszen a m¶ködés leírása a többi nézetet is jelent®sen befolyásolja.

•

Komponens/implementációs nézet (Component view) A rendszer struktúráját, a programkomponensek, állományok kapcsolatát írja le. Els®sorban a programfejleszt®k használják, hiszen az elemek, kódkomponensek egyetlen m¶köd®képes rendszerré integrálását valósítja meg.


8

1.4. ábra. Az UML nézetei

•

Folyamat nézet (Process view) A rendszert folyamataira, végrehajtható egységeire bontva ábrázolja. Célja a párhuzamosítható m¶veletek felismerése, az aszinkron események megfelel® kezelése, ezáltal hatékony er®forrás-gazdálkodás elérése.

•

A telepítési/m¶ködési nézet (Deployment view) A rendszer zikai felépítését rögzíti, a hardvertopológiát, az adott szoftverkomponensek által igényelt er®forrásokat írja le.

•

Logikai/tervezési nézet (Design view) Azokat az elemeket, feltételeket határozza meg, amelyek a megfelel® m¶ködéshez kellenek. Els®sorban a tervez®k és fejleszt®k számára fontos, hiszen a rendszer statikus struktúráját, az együttm¶ködést, az objektumok közötti kommunikációt írja le. Itt kell pontosan meghatározni a bels® struktúrát és interfészeket is.

A különböz® nézetek sajátosságait különböz® diagramokkal fejezhetjük ki.

A dia-

gramok a rendszer különböz® elemeit ábrázolják, melyek között kapcsolatokat(relációkat) írhatunk fel.


9

1.5. ábra. A relációk UML szimbólumai

1.2.2. A diagramok A

diagram ok [8] olyan gráfok, amelyek csomópontjai elemeket, élei az elemek közötti

kapcsolatokat képviselik. A diagramokat két részre oszthatjuk: statikus diagramok és a dinamikus (viselkedés) diagramok. Statiskus diagram családhoz öt diagram tartozik [8]:

•

Osztály diagram (class diagram): Az osztályok, interfészek, ezek együttm¶ködésének és kapcsolataiknak ábrázolására szolgál.

•

Obejktum diagram (object diagram): Az osztály-diagram elemeinek pillanatnyilag létez® példányait, azok kapcsolatait szemléleti.

•

Komponens diagram (component diagram):

A komponensek egymáshoz való vi-

szonyát fejezi ki.

•

Telepítési/m¶ködési diagram (deployment diagram): A futás közben igényelt er®forrásigényt, és a csomópontokon m¶köd® komponenseket ábrázolja.

•

Használati eset diagram (use case diagram): A valós rendszer szerepl®it, ezek kapcsolatát és tevékenységeit mutatja be.

Dinamikus diagramok fontosabb típusai:

•

Szekvencia diagram (sequence diagram): Az üzenetek küldésének és fogadásának id®rendi sorrendjét határozza meg, a használati esetekb®l kiindulva.


•

10

Együttm¶ködési diagram (collaboration diagram): Az üzeneteket váltó objektumok kapcsolatát, és az üzenetváltás struktúráját ábrázolja.

A szekvenciadiagramból

egyszer¶ algoritmus alapján megkapható.

•

Állapot diagram (state-chart): A diagram csomópontjai állapotok, az irányított élek az állapotok közötti átmeneteket reprezentálják. Rendkívül fontos az eseményorientált viselkedés vizsgálatánál.

•

Aktivitás diagram (activity diagram): Speciális állapotdiagram, amely a végrehajtandó tevékenységek folyamatát mutatja. Jelent®sége az objektumok vezérlési folyamatainak tervezésénél a legnagyobb.

Az UML modellezési eszköz megkönnyíti a programozó munkáját. Segítségével a feladatokat könnyedén különálló részekre bonthatjuk, pontosan deniálhatjuk a fejlesztend® terméket, lehet®vé teszi az egyéni és csoportos feladatok egységes kezelését. Az általános gyengeségekr®l [7] sem feletkezhetünk meg az UML modellezéssel kapcsolatban: nincs világosan meghatározva a diagramok implementálási szabályai, nehéz meghatározni, melyik modellek kombinációja a legalkalmasabb egy adott projekt esetén, a diagramok között átfedések vannak, ezért a modell tesztelése nehézkessé válhat.

2. fejezet Az algoritmus-modell

A fentiekben láthattuk, hogy egy modellezési eszköz milyen el®nyöket és milyen hátrányokat jelenthet a fejleszt® számára. Bár két különböz® modellezési eszközr®l beszéltünk, a céljuk mégis ugyanaz: tegye egyszer¶bbé, attekinthet®bbé az informatikus munkáját. Még napjainkban is a lehet®ségeink az algoritmusok modellezése szintjén meglehet®sen korlátozottak. A fejleszt®k körében is az algoritmusok tervezése háttérbe szorul. Senki sem akar kétszeres munkát vállalni: tervezés és aztán kódolás. Az UML sem tartalmaz olyan modellezési eszközt, amely lehet®vé teszi az algoritmusok tervezését és modellezését. Az osztálydiagram modellez®je is csak az attribútumok és az üres metódusok generálását teszi lehet®vé. Szükség van egy olyan modellezési eszközre, amely támogatja az algoritmusok megtervezését (algoritmus szintjén), és ezen modell alapján egy függvény kódjának generálását. Ez a

megtervezem és felhasználom módszer nemcsak a középiskolások fej®désében játszana

nagy szerepet, hanem a fejleszt®ket is ösztönözné jól megtervezett programok, algoritmusok készítésére.

Ebb®l született az ötlet, hogy készítsünk osztály-diagramhoz hasonló

módon folyamatábrákat is.

2.1. A modellez® részei Az elképzelés megvalósítása nem a legegyszer¶bb dolog. A folyamatábrák készítésére nincs egy standard jelölési rendszer. A modellelemek mindenhol másképp jelennek meg,

11

2. FEJEZET. AZ ALGORITMUS-MODELL

annak függvényében, hogy milyen iskolából vagy térségb®l származnak.

12

A jelölésrend-

szer sehol sem teljes, egy-egy helyen több újdonsággal is szembe találhatjuk magunkat, míg máshol le van sz¶kítve.

Én ezeket az elemeket tettem egységessé, az adott célnak

megfefel®en [5] [4]:

1. Az élek a rendszer legfontosabb elemei. Ezek kötik össze a különböz® m¶veleteket, utasításokat, ciklusokat. Az éleknek mindíg van egy irányuk, amely irány meg kell egyezzen az algoritmus irányával.

2.

Az algoritmus kezdetét és végét jelöl® szimbólumok csak egyszer fordulhatnak el® a modellünkön, viszont jelenlétük kötelez®.

Beolvasáskor kötelez® módo egy változót kell megadni, amelyikbe

3.

a beolvasandó adat kerül, kiíratáskor viszont egy egyszer¶ szöveg is megadható. Meg lehet adni, hogy konzolról, vagy fájlból szeretnénk beolvasni.

Ezt a trapéz

fels® részén lehet kiválasztani.

4. A feltételek megadása többféle parancsban is megjelenthet.

(a)

Az egyszer¶ if utasítás esetén a rombuszba beleírjuk a feltételünket. A két ágat az algoritmusunk alapján kitölthetjük.

(b)

A while ciklust az if utasításhoz hasonlóan egy rombusz jelöli. A while ciklus esetén a rombusz elé vissza kanyarodó él jelzi, hogy itt nem egy if utasításról beszélünk.

A ciklusban lev® utasításokat viszont az adott élre

helyezhetjük.

(c)

A for ciklus esetén egy kicsit nagyobb a komplikáció.

Itt is

egy él fog bekanyarodni a rombusz elé, viszont itt az utolsó téglalapba beírt értékadás mindg a léptetés kell legyen. A kezdeti értéket mindíg a ciklus el®tt kell fet¶ntetni.


13

Az értékadáskor a téglalapba be kell írni egyszer¶en az értékadást.

5.

Egy

értékadás jobb oldalán szerepelhet akár m¶velet is.

6.

A függvényhívások ábrázolására egy ellipszist használunk, amelynek tartalmaznia kell a függvény nevét, és a paramétereket.

Vigyázat, csak azokat a függ-

vényeket találja meg, melyek az adott állományban szerepelnek.

7.

Sajnos ezzel a programmal sem lehet majd elvégeztetni mindent.

Sokszor

megjelennek különböz® programokban olyan elemek, melyek már a megjelenítéshez vagy esetleg a komplexebb m¶veletekhez kapcsolódnak. Ilyen esetben használható a

megjegyzés.

A teend®:

a kis téglalapba bele írhatod a megjegyzéseidet, és ez

kommentként fogod látni a generált kódodban.

2.2. A modellez® felépítése Amint láthattuk, a modellünk több elemb®l tev®dik össze. Hogy az alkalmazás megfelel®en m¶ködjön a modell minden elemének megfeleltetek egy objektumot, amint az alábbi diagram is mutatja. A redundáns adatok egyszeri eltárolása valamint az áttekinthet®ség el®segítése érdekében absztrakt osztályokat használok. Az els®dleges absztrakt osztály a gram fontosabb tulajdonságait tartalmazza. Tehát

ModelElement, a dia-

a Star, a Stop, a Fleck, az Operation

egyaránt model elemek. Az él (Edge) két modell elemet köt össze, ezért a sajátos tulajdonsága, hogy tartalmazza azt a két m¶veletet, amit összeköt. Az Operation szintén egy absztrakt osztály. Ez tartalmazza a m¶veleteket, utasításokat, amelyek objektumok, és csoportosíthatjuk ®ket típusaik szerint. A ciklusok (ForCycle, WhileCycle) egy

Cycle absztrakt osztálytól származnak.

A kimeneti-bemeneti

m¶veletek (InputOutput), az értékadás (SetValue), a függvényhívás (FunctionCall), a megjegyzés (Comment) egy

Command absztratkt osztálytól származnak.

Az algoritmusoknál láthattuk, hogy vannak olyan m¶veletek, amelyek blokkokat tartalmaznak. A blokkok belsejében még több utasítás is szerepelhet. Ilyen m¶veletek az utasítás (mindkét ágában szerepelhetnek blokkok), a

for illetve a while ciklus.

if


2.1. ábra. A folyamatábra objektum-orientált szerkezete

14


15

E probléma megoldására egy "bennefoglalás" kapcsolatot használtam: egy ilyen m¶velet tartalmazhatja az összes többi m¶veletet akár többször is. A f® objektumunk a

Diagram objektum. Ebben található az összes elem, amely a

modellben megjelenhet. A diagramunkban csak egyetlen Start és Stop objektum jelenhet meg, ezért a kapcsolat is így van felépítve.

Az alkalmazás végeredménye ezt fogja

megjeleníteni.

2.3. Használt programozási eszközök Egy jó program elkészítéséhez a terv elkészítése nem elég. Olyan eszközöket kell választanunk, amelyeket megfelel®en ismerünk, és megfelel® segítséget nyújthatnak számunkra. Én a Java-t, Eclipse-t, EMF-et [6], GEF-et [6], JET-et, UML szerkeszt®t választottam, hogy ezen eszközök által készüljön el a végs® termék. 1. A

Java egy objektum-orientált programozási nyelv. A szintaktikája nagyon egy-

szer¶, érthet®, könnyedén megírható benne szinte bármilyen garkus felület.

El-

s®sorban azért választottam ezt a programozási nyelvet, mert az egyetemi évek alatt nagyon megkedveltem, rengeteg programozási eszköz alapja, valamint ingyen letölthet® az Internetr®l. Igaz a memória-kezelése miatt lassíthatja az alkalmazást, viszont ellensúlyozza a platformfüggetlensége.

2. Az

Eclpise egy Javan alapuló fejleszt®i környezet.

Rengeteg olyan komponens

található benne, amely megkönnyíti a fejleszt® munkáját, áttekinthet®bbé teszi kódunkat. Napjainkban a programozók körében igen elterjedt.

3. Az

EMF (Eclipse Modelling Framework) [1] egy modellezési és kódgenetrálási keret-

rendszer.

Segítségével strukturált adatmodellen alapuló alkalmazások, eszközök

keszithet®ek.

A strukturált adatmodell az EMF esetében egy osztálydiagramhoz

hasonlóan meghatározza a modellobjektumokat és az azok közötti kapcsolatokat. Ezt a diagramot az EMF egy .ecore kiterjesztés¶ fájlba menti el (tartalma XML felépítés¶). A jól eltervezett objektummodellb®l generálhatunk egy szerkeszt®t. A szerkeszt®t megfefel®en használva készíthetünk ábrákat fa struktúrában. Az EMF hátránya, hiányosak a metódusainak a dokumentálása.


4. A

16

JET [3] az EMF keretrendszeren belül kimondottan "kódgeneráló" implemen-

tálásra fejlesztették ki. A kódgeneráló egy fontos komponense az MDD-nek (Model Driven Development).

5. A

GEF (Graphical Editing Framework) [2] lehet®séget nyújt a fejleszt®knek, hogy

egy modell alapján gyorsan keszítsenek egy grakus szerkeszt®t. Számomra lehet®séget biztosít egy EMF által elkészített szerkeszt®nek a továbbfejlesztésére.

Ezen szer-

keszt® segítségével fog elkészülni a grakus szerkeszt®, amelyben már szimbólumok fogják jelölni a különböz® m¶veleteket.

6. Az

UML szerkeszt®t csak a projekt legvégén veszem igényben, amikor ebbe a szer-

keszt®be integrálom. Egy olyan szerkeszt®be, amelyik nyílt forráskódú és legalább egy osztálydiagram-készít®t tartalmaz.

2.4. A modellez® m¶ködése és további tervek A folyamatábra objektum-orientált szerkezetének meghatározásával egy lépéssel közelebb kerültük a célunkhoz. Az EMF szerkeszt® segítségével egy olyan modellez®t hoztam létre, amely képes fa struktúrában ábrázolni egy folyamatábrát. Kezdetben van egy Diagram, amelyhez hozzá lehet adni gyerekeket. A gyerekek az algoritmus részei lesznek. A fa struktúrájú folyamatábráknak az a hátránya, hogy kevésbé átlátható, ezért megnehezítheti a dolgunkat. A fa struktúrás szerkesztés nem bizonyult megfelel®nek.

A továbbiakban az eddig

készített munkámat kiegészítve készítek egy grakus szerkeszt®t, amely lehet®séget biztosít általunk készített algoritmusok elmentésére, és már helyes algoritmusok generálására. A szerkeszt® majd lehet®vé teszi a folyamatábra képpé exportálását valamint a folyamatábrából való kódgenerálást. A könnyed ellen®rzés és áttekinthet®ség érdekében lehet®ség nyílik az algoritmus lépésenkénti lefuttatására (debugg). A végs® mozzanat a tervünk befejezéséhez egy UML szerkeszt®be való integrálás. Ezen lépés fontossága a kódgeneráláshoz kapcsolódik. Az UML osztálydiagram szerkeszt®jében is találkozhatunk kódgenerálással, viszont azzal csak az adott osztály attributumait valamint


17

2.2. ábra. A Diagram, és a lehetséges gyerekei amely által felépíthetünk egy folyamatábrát

2.3. ábra. Egy egyszer¶ algoritmus elkészítése fa struktúra segítségével


18

az üres metódusait generálhatjuk ki, ami nagy el®ny számunkra, viszont hiányos. Az UML szerkeszt®be való integrálás lehet®vé teszi a két (osztály diagram és a folyamatábra) kódgenerálás egyesítését.

Módosíthatjuk az osztálydiagramból való generálást, úgy hogy a

megfelel® függvényeket is belegenerálja az adott osztályba. Így kiteljesíhetjük az osztálydiagram kóddá alakítását.

Irodalomjegyzék

[1]

Eclipse Modeling Framework (EMF). http://www.eclipse.org/modeling/emf/.

[2]

GEF. http://www.eclipse.org/gef/overview.html.

[3]

Model To Text (M2T). http://www.eclipse.org/modeling/m2t/?project=jet.

[4] A problémafeltárás és hibaelemzés technikái.

[5] Flowchart diagrams, 2005.

[6] Anna Gerber Gunnar Wagenknecht Philippe Vanderheyden Bill Moore, David Dean.

Eclipse Development. IBM International Technical Support Organization. [7] Molnár Ágnes. Az uml2 és a modell-vezérelt alkalmazásfejlesztés.

[8] Molnár Ágnes. Az uml, 2003.

19

Algoritmus-modellezés folyamatábrákkal

Recommend Documents