Programozási módszertan Galántai Aurél 2004-02-23
Contents 1 Bevezetés
3
2 Motívációk
5
3 Program fejlesztési eszközök és technikák
6
4 Top-down programozás lépésenkénti Þnomítással 4.1 Zárómegjegyzések . . . . . . . . . . . . . . . . . . . . . . . . .
8 26
5 Programok helyességének bizonyítása 5.1 Parciális helyesség . . . . . . . . . . . 5.1.1 Az invariáns módszer . . . . . . 5.1.2 A részcél módszer . . . . . . . 5.1.3 A módszerek összehasonlítása . 5.2 Terminálás . . . . . . . . . . . . . . .
28 32 33 36 38 40
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
6 Programok transzformálása és optimálása 7 Programok tesztelése 7.1 Bottom-up tesztelés . . . . . . . . . . . . . . . . . . . 7.2 Tesztelési egységek, formázott hibakeresýo eszközök és driverek . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 A tesztelés gráf modelljei és technikái . . . . . . . . . . 7.4 Integritás tesztelés . . . . . . . . . . . . . . . . . . . . 7.5 Elfogadási tesztelés és regressziós tesztelés . . . . . . . 7.6 Top-down tesztelés és ”stub”-ok . . . . . . . . . . . . . 7.7 Tesztelési tervek . . . . . . . . . . . . . . . . . . . . . 7.8 A tesztelés és a veriÞkálás összehasonlítása . . . . . . .
1
42
. . . . teszt . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45 46 48 49 51 51 52 54 55
8 Mérés és tuningolás
55
9 Szoftverek újrahasznosítása és bottom-up programozás
58
10 Programok struktúrálása és dokumentálása
59
2
1
Bevezetés Programozási módszertan ≈ software engineering
Célja/tárgya: A szoftverfejlesztés, szoftver tesztelés, szoftver megbízhatóság, szoftver minýoség, szoftver karbantartás és üzemeltetés kérdéseinek szisztematikus vizsgálata, hatékony módszerek kifejlesztése és alkalmazása. Különféle felfogásban és kiméretben szokás tárgyalni. Egyes idetartozó területeket önálló diszciplinaként is szokás tárgyalni. Pl. szoftver metrika.
3
Példák: A) ”A programozás gondolkodási formái - Egy programozási módszertan” felépítése a következýo: I. Programozási modell 1. Alapfogalmak 2. SpeciÞkáció (leggyengébb elýofeltétel, speciÞkáció tétele, stb.) 3. Programszerkezetek II. Procedurális programtervezés 4. Levezetés 5. Visszavonás 6. Moduláris programtervezés III. Tipus-orientált programtervezés 7. Az absztrakció eszköze: a típus 8. Típus átalakítás 9. Állapottér alakítás IV. Függelék Kiterjesztési tételek Programozási tételek B) Egy ”Objektum orientált felfogás” 1. Bevezetés 1. Top-down programozás lépésenkénti Þnomítással 2. Programok helyességének bizonyítása 3. Programok transzformálása és optimálása 4. Programok tesztelése 5. Programok Þnomításának és mérésének ÞlozóÞája 6. Szoftverek újra felhasználása és bottom-up programming 7. Programok felépítése és struktúrálása 8. Szoftverek életciklusa 9. Szoftverek hatékonysága (software productivity) 10. Szoftver üzemeltetsi modellek C) Egy ”Klasszikus felfogás” 1. Bevezetés 2. Program fejlesztési eszközök és technikák 3. A bonyolultság, a memória igény és futási idýo elemzése 4. Programok tesztelése 5. Szoftverek megbízhatósága 6. Programok menedzselése
4
2
Motívációk
A) Kisméretý u (small-scale) programozás: programming-in-the-small: Kisméretý u, néhány soros, vagy oldalas programok írására koncentrál. A nehézséget itt az okozza, hogy a kisméretý u programok logikailag igen bonyolultak is lehetnek. Az itt alkalmazott programozási technikák célja a tiszta és világos programozói stílus kialakítása. B) Nagyméretu ý (large-scale) programozás: programming-in-the-large: Nagyméretu ý, több százezer, vagy hosszabb programok/program rendszerek fejlesztési és módosítási technikáira koncentrál. Idetartozik a nagy erýoforrásokat használó, nagylétszámú fejlesztýo csoportok munkájának szervezése és koordinálása is. C) Programhelyesség bizonyítása: matematikai eszközökkel tipikusan kisméretý u programokra. D) Programok tesztelése: Programhibák szisztematikus keresése. Korlátozott erejý u, de szükséges. Mottó: ”Testing can reveal the presence of bugs, but it can never prove their absence” E) Top-down programozás lépésenkénti Þnomítással: kisméretu ý programozás hatékony eszköze, de nagyméretýu programozásnál is meg vannak a változatai (Miért?) F) Programok speciÞkációja: elýofeltétel, utófeltétel, csomóponti állítások, stb. G) Programok transzformálása és optimálása: pl. rekurzió eltávolítása, stb. H) Mérés és Þnomítás: A program (és részei) hatékonyságának mérése, a mérés alapján a program (részek) Þnomítása. I) Újra felhasználható szoftver komponensek: modularitás, könyvtárak, stb. További szempontok: - Számítógépek és programok elterjedése - Szoftverek magas (fejlesztési) költsége - Szoftverhibák hatása Nagy rendszerek fejlesztésének fýobb lépései: 1. Kezdeti elképzelés 2. Követelmények meghatározása 3. SpeciÞkáció 4. Kezdeti rendszer terv 5. A kezdeti rendszerterv veriÞkációja és tesztelése 5
6. Újra tervezés 7. Prototípus elýoállítása 8. Összeállítás és rendszer integráció tesztje 9. Elfogadási teszt (a terv validációja) 10. Gyártás (ha több rendszer kell) 11. Helyszíni próba és hibakeresés 12. Helyszíni karbantartás 13. További kiegészítések tervezése és hozzáadása 14. A rendszer kivonása (halála), vagy teljes újratervezés
3
Program fejlesztési eszközök és technikák
Számos technika, eszköz létezik, volt, van, lesz. Ok: világos Fontos tervezési és implementálási technikák: - top-down - bottom-up - struktúrált - moduláris - stb. Nincs igazán tiszta tervezési eljárás, mert minden tervezésben van/kell egy iteratív korrekciós fázis. Adott tervezési eljáráshoz számos leíró/megjelenítýo eszközt lehet találni. Ezek gyorsan változnak, de valamilyen formában megtalálhatók a következýok: - blokk diagramszeru ý leírások - folyamat gráfszeru ý leírások - stb. A top-down tervezés ÞlozóÞája és elvei: 1. dekompozíciós eljárás, amely a program vezérlési szerkezetére fokuszál. 2. A tervezés elsýo lépcsýojében a feladat átfogó aspektusaira koncentrál és felbontja a feladatot egymástól független részfeladatokra (modulokra) (3-10 részfeladat) 3. A folyamat ismétlýodik addig, amig a részfeladatok eléggé egyszerý uek, hogy direktben megoldhatók legyenek (programming in the small, sýot smaller). Megjegyzések: 1. A modulok fa struktúrában vannak. 2. A top-down tervezés lehetýové teszi, hogy döntéseket a végsýokig elhalasszunk. Ez elýonyös, de lehet hátrányos is.
6
A bottom-up tervezés ÞlozóÞája: 1. A tervezés elsýo lépcsýojében egy tipikus (vázlatos) rendszerterv készül, amelyben valaki kiemeli a legkényesebb/legkritikusabb részeket. 2. Ezt a legkritikusabb részek speciÞkációja követi. 3. A kritikus részek után megtervezésre kerül a többi rész is Megjegyzések: 1. Mekk Elek házat épít. 2. Van azért elýonye is. Mi? 3. A két tervezési ÞlozóÞa idýonként keveredik. Tekintsük a következýo példát, amely az Ax3 + Bx2 + Cx + D = 0 harmadfokú egyenlet megoldására vonatkozik. A top-down tervezés elsýo szintje: harm adfokú egyenlet gyökei
Input: A, B, C, D együtthatók
Szinguláris esetek tesztelése
gyökök m eghatározás a
top-down tervezés, első dekom pozíciós szint
A bottom-up tervezés:
7
gyökök osztályozása
Output: gyökök és osztályozásuk
O utput: gyökök és osztályozásuk
gyökök osztályozása
kvadratikus oldóképlet használata
a valós gyök leválasztása Newton-m óds zerrel
Input: A, B, C, D együtthatók
bottom -up tervezés
Feladat: Adjunk részletes folyamatábrát mindkét közelítésben!
4
Top-down programozás lépésenkénti Þnomítással
Tekintsük az alábbi szerencsejátékot (USA): 1$ árú kaparós sorsjegy 6 számot tartalmaz. A fedýoréteg lekaparása után a sorsjegy a következýoképpen néz ki:
8
The Big Scratch-O ff Gam e
L
$10 $5
$5 $50
$2 $5
A szerencsejáték szabályai a következýok: 1. A legnagyobb legalább háromszor megismétlýodýo összeget nyerjük. 2. Ha egyetlen szám sem ismétlýodik legalább háromszor, akkor nem nyerünk semmit. FELADAT: Irjunk egy Pascal programot, amely beolvassa a lekapart szelvényen lévýo hat számot és kinyomtatja a nyeremény értékét! Ha nincs nyeremény, akkor 0$ összeget nyomtasson! 1. A feladat egyszerý u és az idevágó elvek illusztrálására szolgál. A topdown tervezés fontos sajátossága, hogy az algoritmusokat és az adatstruktúrákat párhuzamosan választjuk meg. 2. Több lehetséges megoldás van. 1. megoldás: ”készitsünk egy táblázatot és keressük benne a megoldást”
9
Enter
Input: 6 szám a usertől
Készítsük el a szám ok és ism étléseik táblázatát
Output: a legalább három szor előforduló legnagyobb szám
Exit
A konkrét lottószelvény esetében ez a következýoképpen nézne ki: 10 5 2 5 50 5
Sorszám 1 2 3 4
Összeg 10 5 2 50
Ismétlések száma 1 3 1 1
Nyer: 5$
2. megoldás: ”rendezzük az input adatokat csökkenýo sorrendbe és találjuk meg az elsýo három ismétlýodést” Enter
Input: 6 szám a usertől
Rendezzük az input adatokat csökkenő sorrendben
Keressünk három ism étlést és nyom tassuk ki az eredm ényt
Exit
10
A konkrét lottószelvény esetében ez a következýoképpen néz ki: 10 5 2 5 50 5
50 10 5 5 5 2
Nyer: 5$
1. megoldási stratégia: Tekintsük az elsýo megoldási stratégia top-down kifejtését Pascal környezetben!
5
10
procedure FindWinningAmount; | begin | | {Get six input amounts from user} | | {Make a table of amounts and repetitions} | | {Print largest amount repeated at least three times} | end{FindWinningAmount}; (5.4) 1. program stratégia, top-level célok
A fenti ”programvázlat” a top-level (elsõ) szintû célokat tartalmazza. A következõ lépés a célok Þnomítása: 1. Írjunk programot, amely a 6 számot beolvassa és egy tömbben tárolja. Ebben az elsõ Þnomító lépésben az adat megjelenési formáját és az algoritmust egyidejûleg választjuk meg. Legyen A a tömb, amelyben az input adatokat tároljuk. A program végrehajtásakor jelenjen meg egy üzenet, amelyre a felhasználó a 6 input adatot a következõ formában adja meg: Give six dollar amounts separated by spaces: 10 5 2 5 50 5
11
A következõ (5.5) program ezt valósítja meg type var
5
10
InputArray=array [1..6] of Integer; A: InputArray
procedure GetSixInputs(var A: InputArray); {Get six dollar amounts} | var {and put them in array A} | i: Integer; begin | | Write(’Give six dollar amounts separated by spaces: ’); | | for i:=1 to 6 do begin | | Read(A[i]); {read in six dollar amounts} | end{for} | | ReadLn; {read past end of input line to next line} | end{GetSixInputs}; (5.5) Input program
2. Finomítsuk a ”számok és ismétlõdéseik táblázata” célt. Két lehetõség van: a) elõbb megválasztjuk az adatszerkezetet és aztán az algoritmust; b) elõbb algoritmus, aztán adatszerkezet (postponing the choice of data representations). Válasszuk az utóbbit és tervezzük meg az algoritmust anélkül, hogy kötelezettséget vállalnánk az adat reprezentációra. Az alábbi program ezt teszi.
12
5
10
procedure MakeTable(var A: InputArray); {Create a Table of amounts} | var {and their repetitions} | i: integer; begin | | {Initialize the Table to be empty} | | {Insert each of the six amounts to the Table} | for i:=1 to 6 do begin | | {Insert the amount A[i] into the Table} | | InsertAmount(A[i]) | end{for}; | end{MakeTable}; (5.6) Táblázatkészítõ program
A programban hivatkozunk egy még megíratlan ”InsertAmount” eljárásra. Ez a top-down tervezésnél általában is így van. Amikor megírtuk egy szint algoritmusait, akkor lépünk tovább a jelzett algoritmusok megírására, vagy esetleg további bontására (stepwise reÞnement). A bottom-up programozásnál ez éppen fordítva van. A legalsó szintýu eljárásokból építjük fel a magasabb szinteket (ha tudjuk, remember not Alamo but modularity). Esetünkben az ”InsertAmount” eljárás a következýo lehet:
13
5
10
15
procedure InsertAmount(AmountToInsert: Integer); {Insert and amount} | {in the Table} begin | | {If one of the rows in the Table already contains the amount to insert,} | {then increase the number of repetitions in the row and exit the procedure} | for {each row in the Table} do begin | | if {the row amount}=AmountToInsert then begin | | | {increase the row’s repetition count by one} | | | {Table update completed. Set ßag to exit from search loop} | | end{if }; | end{for}; | | {If no row’s amount matched the amount to insert, then add a new row to} | {the table containing the amount to insert and repetition count of one} | end{InsertAmount}; (5.7) Beszúrás program
A következýo program szintén az 5.4 program stratégia Þnomítása:
14
5
10
15
procedure FindAndPrintWinner; {Search the Table for a row having} | var {the largest amount repeated three} | AmountWon: Integer {or more times and print it} begin | | {Initially establish the AmountWon to be zero.} | {It will remain 0 unless a higher amount is discovered during the search.} | | {Search the Table to Þnd the largest amount won among the rows} | {having three or more repetitions} | for {each row in the Table} do begin | | if {the row’s number of repetitions>=3} and | | {the row’s amount}>AmountWon then begin | | AmountWon:={the row’s amount} | | end{if }; | end{for}; | | {Print AmountWon} | end{FindAndPrintWinner}; (5.8) A nyeremény megállapítása és kinyomtatása program
A fenti programok a felsýo szint Þnomításai. Nem ismert azonban a táblázat reprezentációja (típusa). Jelen pillanatban ismert a következýo. Két táblázat mý uveletünk van: beszúrás és a legalább háromszor ismétlýodýo legnagyobb szám keresése. Ha meghatározzuk beszúrási és keresési mý uveleteket (algoritmusokat), akkor már lehetýoségünk van az adat típus jó megválasztására is. A táblázat adat reprezentációjának megválasztása Lehetýoségek: 1. a sorokat reprezentáló rekordok tömbje, 2. két dimenziós egész típusú tömbök, 3. listák 4. bináris adat reprezentációk. Jelen esetben az adatméret olyan kicsi, hogy bármi megteszi. Tehát a következýot választjuk:
15
type
RowRecord= record Amount: Integer; {the dollar amount} Repetitions: Integer {how many times it is repeated} end
var
Table: array [1..6] of RowRecord;
Felhasználunk még egy pointer változót: LastRowUsed, amelyik Table tömb utoljára tárolt sorát mondja meg. Ezután a ”MakeTable” program konkretizálása a következýo:
5
10
procedure MakeTable(var A: InputArray); {Create a Table of amounts} | var {and their repetitions} | i: integer; begin | | {Initialize the Table to be empty, we initialize} | {a pointer to the last row used in theTable} | LastRowUsed:=0; | | {Insert each of the six amounts to the Table} | for i:=1 to 6 do begin | | InsertAmount(A[i]) {Insert the amount A[i] into the Table} | end{for}; | end{MakeTable}; (5.9) Táblázatkészítõ program
Az adattípus megfelelýo ismeretében megírhatjuk az beszúrási eljárást is:
16
5
10
15
20
25
30
procedure InsertAmount(AmountToInsert: Integer); {Insert and amount} | var {in the Table} | row: Integer; | UpdateCompleted: Boolean; begin | | {Initializations} | row:=1; {start at Þrst row of Table} | UpdateCompleted:=false; {the table update isn’t Þnished yet} | | {If one of the rows in the Table already contains the amount to insert,} | {then increase the number of repetitions in the row and exit the procedure} | while (row<=LastRowUsed) and (not UpdateCompleted) do begin | | if Table[row].Amount=AmountToInsert then | | | begin | | | Table[row].Repetitions:=Table[row].Repetitions+1; | | | UpdateCompleted:=true; | | | end | | else begin | | | row:=row+1; {search further in next row of Table} | | end{if }; | end{while}; | | {If no row’s amount matched the amount to insert, then add a new row to} | {the table containing the amount to insert and repetition count of one} | if not UpdateCompleted then begin | | LastRowUsed:=LastRowUsed+1; | | Table[LastRowUsed].Amount:=AmountToInsert; | | Table[LastRowUsed].Repetitions:=1; || end{if }; | end{InsertAmount}; (5.10) Beszúrás program
Ugyanez a helyzet a nyeremény megállapítása és kinyomtatása (FindandPrintWinner) programmal is:
17
5
10
15
20
procedure FindAndPrintWinner; {Search the Table for a row having} | var {the largest amount repeated three} | AmountWon: Integer {or more times and print it} begin | | {Initially establish the AmountWon to be zero.} | {It will remain 0 unless a higher amount is discovered during the search.} | AmountWon:=0; | | {Search the Table to Þnd the largest amount won among the rows} | {having three or more repetitions} | for row:=1 to LastRowUsed do begin | | if (Table[row].Repetitions>=3} and | | | (Table[row].Amount>AmountWon) then begin | | | AmountWon:=Table[row].Amount | | end{if }; | end{for}; | | {Print the amount won} | WriteLn(’You won $’,AmountWon); | end{FindAndPrintWinner}; (5.11) A nyeremény megállapítása és kinyomtatása program
Az (5.4) sémában megadott felsýo szintý u célokat beleÞnomíthatók az alábbi programba:
5
procedure FindWinningAmount; begin | GetSixInputs(A); {Get six input amounts from user} | MakeTable(A); {Make a table of amounts and repetitions} | FindAndPrintWinner; {Print largest amount repeated 3 or more times} end{FindWinningAmount}; (5.12) Nyeremény megállapítása program A fenti programokat az alábbi komplett program rakhatjuk össze: 18
5
10
15
20
25
program LotteryProgram; | | type | InputArray=array [1..6] of Integer; | | RowRecord= record | Amount: Integer; | Repetitions: Integer; | end{record}; | | var A : InputArray; | Table : array [1..6] of RowRecord; | LastRowUsed : integer; | | {Here, insert the declarations of the procedures:} | { GetSixInputs - 5.5 Program} | { InsertAmount - 5.10 Program} | { MakeTable - 5.9 Program} | { FindAndPrintWinner - 5.11 Program} | { FindWinningAmount - 5.12 Program} | begin {main program} | | FindWinningAmount {Get inputs and print winning amounts} | end{LotteryProgram} (5.13) Teljes program (1. stratégia)
Megjegyzés: A program kicsisége miatt vannak globális változók. Nagy program esetén ez nem megengedett (modularitás, objektum orientált programozás). 2. megoldási stratégia: Tekintsük most a második megoldási stratégia kifejtését. Itt a feladat megoldása az, hogy az input adatokat csökkenõ nagyságrendben sorba rendezzük és az elsõ három egymásután következõ azonos számot keressük (ha van ilyen). Az alábbi ”programvázlat” a top-level (elsõ) szintû célokat tartalmazza:
19
5
10
procedure FindWinningAmount2; | begin | | {Get six input amounts from user} | | {Sort the amounts into descending order} | | {Search for three in a row and print it} | end{FindWinningAmount2}; (5.14) 2. program stratégia, top-level célok
Az adatok csökkenõ sorba rendezésére számos lehetõség van. Egyelõre tegyük fel, hogy a SelectionSort eljárás, a SelectionSort(A,1,6) hívással ezt teszi. (Feltesszük, hogy a rendezés problémáját ”megoldottuk” és tovább megyünk a következõ megoldatlan feladatrész Þnomítási feladatára). A nyeremény keresése és nyomtatása a következõ programmal történhet:
20
5
10
15
20
25
procedure FindAndPrintWinner2; | var | AmountWon, i: Integer; Found: Boolean; begin | | {Initially establish the AmountWon to be zero,} | {and initialize the starting position, i, to 1 and the ßag, Found, to false} | AmountWon:=0; | i:=1; | Found:=false; | | {For each possible starting position i=1,2,3, & 4, where a run of} | {three identical values could start in the sorted InputArray, A, check} | {to see, if a run of three identical values exists, and exit, if it does.} | repeat | | if (A[i]=A[i+1]) and (A[i+1]=A[i+2]) then | | | begin | | | AmountWon:=A[i]; {a winning amount A[i] was found} | | | Found:=true {set Found ßag in order to exit the loop} | | | end | | else begin | | | i:=i+1; | | end{if }; | until Found or (i>4); | | {Print the amount won} | WriteLn(’You won $’,AmountWon); | end{FindAndPrintWinner2}; (5.15) A nyeremény megállapítása és kinyomtatása program
Az (5.14) sémában megadott felsýo szintu ý célokat beleÞnomíthatók az alábbi programba:
21
procedure FindWinningAmount2; begin | GetSixInputs(A); {Get six input amounts from user} | SelectionSort(A,1,6); {Sort the amounts into descending order} | FindAndPrintWinner2; {Search for three in a row and print it} end{FindWinningAmount};
5
(5.16) Nyeremény megállapítása program Ha még feltesszük, hogy a rendezõ eljárás (amely a maximumkiválasztásos rendezés) meghív egy FindMax(A,m,n) függvényt is, amely az A[m..n] résztömb legnagyobb elemének pozícióját megadja, akkor a teljes program így nézne ki:
5
10
15 25
program LotteryProgram2; | | type | InputArray=array [1..6] of Integer; | var A : InputArray; | | {Here, insert the declarations of the procedures:} | { GetSixInputs - 5.5 Program} | { FindMax - 5.20 Program, késõbb} | { SelectionSort - 5.19 Program, késõbb} | { FindAndPrintWinner2 - 5.15 Program} | { FindWinningAmount2 - 5.16 Program} | begin {main program} | | FindWinningAmount {Get inputs and print winning amounts} | end{LotteryProgram2} (5.17) Teljes program (2. stratégia)
Eddig késleltettük a sorbarendezési algoritmust. A programozásra kerülõ algoritmus a maximum (minimum) kiválasztásos rendezés, amelynek elve a következõ: 22
Megkeressük a legnagyobb számot az A[m], A[m+1],...,A[n] elemek között, majd ezt a számot kicseréljük az A[m] elemmel. Ekkor A[m] lesz a legnagyobb elem az A[m..n] résztömbben. Ezt megismételjük az A[m+1..n] résztömbben és így tovább.
5
10
procedure SelectionSort(var A:SortingArray; m,n:Integer); | begin | | if {there is more than one numer to sort} then begin | | | | {Let MaxPosition be the index of the largest element in A[m..n]} | | | | {Exchange A[m]<—>A[MaxPosition]} | | | | {SelectionSort the subarray A[m+1..n]} | | | end {if }; | end{SelectionSort} (5.18) Maximumkiválasztásos rendezés
Az eljárásban feltesszük, hogy meghív egy FindMax(A,m,n) függvényt is, amely az A[m..n] résztömb legnagyobb elemének pozícióját megadja. Ezután
23
az eljárás kódja a következõ lehet:
5
10
15
20
procedure SelectionSort(var A:InputArray; m,n:Integer); | | var MaxPosition, Temp: Integer; | begin | | if m
A[MaxPosition]} | | Temp:=A[m]; | | A[m]:=A[MaxPosition]; | | A[MaxPosition]:=Temp; | | | | {SelectionSort the subarray A[m+1..n]} | | SelectionSort(A,m+1,n); | | | end {if }; | end{SelectionSort} (5.19) Maximumkiválasztásos rendezés programja
24
A Findmax eljárás kódja a következõ lehet:
5
function FindMax(var A:InputArray; m,n:Integer):Integer; {assume mA[j] then j:=i; {if A[i]>largest previous A[j], then j:=i} | until (i=n); {stop when all i in m..n have been tested} | | FindMax:=j; {return j=position of the largest number A[j] in A[m..n]} | end{FindMax} (5.20) Maximumkeresõ program
Ezzel a második közelítés top-down tervezése is kész. Megjegyzések: 1. Az elsõ közelítés a keresésen alapult, a második pedig a rendezésen. 2. Más adatszerkezetek esetén a megoldás is eltérõ lehet. Feladatok: 1. Mutassuk meg, hogy az 5.15 program hatékonyabb lesz, ha a 16-ik sor utasítását kicseréljük az if A[i]=A[i+2] then utasítással. Mennyivel lesz jobb?
25
2. Vizsgáljuk meg a következõ programot!
5
10
15
program ShortLotterySolution; | | var i, AmountWon: Integer; array [1..6] of Integer | | function Repeated3orMore(Amt:Integer): Boolean; | | var k,j: Integer; | begin | | k:=0; | | for j:=1 to 6 do if A[j]=Amt then k:=k+1; | | Repeated3orMore:=(k>=3); | end{Repeated3orMore}; | begin | Write(’Give 6 Amounts:’); for i:=1 to 6 do Read(A[i]); ReadLn; | AmountWon:=0; | for i:=1 to 4 do | if (A[i]>AmountWon) and (Repeated3orMore(A[i])) then | AmountWon:=A[i]; | Writeln(’You win $’,AmountWon) end{ShortLotterySolution}
Helyes-e a fenti program? Hasonlítsuk össze a három megoldás hatékonyságát! Tudna-e az utolsó program hatékonyságán javítani? Ha igen, akkor mennyiben különbözne ez az elsõ két programtól?
4.1
Zárómegjegyzések
A módszeres programozást és a feladat naív (frontális) közelítését az alábbiakban szokás összehasonlítani: 1. A feladat elleni frontális támadás módszere: a) A fejlesztés visszalépésekkel sûrûn tagolt (vissza-visszafordulás a dzsungelben). b) Visszakozás helyett további útkeresés a dzsungelben. c) A hibakeresés megfelelõ tájékozódási pontok nélkül nehézkes. d) A hibakeresésnek nincs vége. Hiba hibát szül. e) A hibajavításnak nincs vége. Nem tudjuk, hogy mikor van vége. f) A program módosíthatatlan. g) A program áttekinthetõség hiányában használhatatlan mások számára. Egy idõ után az irójának is az lesz. 26
2. A módszeresen írt program kényelmetlen vonásai: a) A felhasználónak fogalma sincs a program mikéntjérõl, hacsak a program maga nem igazítja el ebben. b) Ha a felhasználó elront valamit, akkor ez egy nem eléggé felkészült program számára probléma lehet. c) A felhasználó pánikba eshet, ha nem tudja nyomon követni a program futását. Megjegyzés: A 2. pontban foglaltak minden bonyolultabb program esetén fennállnak. Tehát értékük ??? A strukturált (top-down) programozás általános elvei: 1. Oszd meg és uralkodj. 2. Lépésenkénti Þnomítás elve. 3. A feladat lebontása részekre az ”utasítások” szintjéig (piramis elv) Taktikai elvek: 1. Párhuzamos Þnomítás elve (Az egyes ágakon párhuzamosan kell végezni a Þnomítást). 2. A döntések elhalasztásának elve (egyszerre csak kevés dologról, de következetesen kell rendelkezni. Az a jó döntés, amelyik a legkevésbé dönti meg a kezünket). 3. Vissza az õsökhöz elv (vissza kell lépni az elõzõ szinthez, ha zsákutcába kerültünk). 4. A nyílt rendszerû programfelépítés elve (nemcsak a konkrét feladatra, hanem a feladatot is tartalmazó feladatkörre alkalmazható programot érdemes deÞniálni). 5. A döntések el nem halasztásának elve (a ki nem mondott, de hallgatólagosan meghozott döntések problémákat okozhatnak). 6. Az adatok elszigetelésének elve (Az egyes programegységek a megtervezett illesztéseken kívül egymással nem érintkezhetnek. Az adatok célszerû csoportosítása a programegységben betöltött szerepük alapján javasolt: közös (globális) adatok, input és output adatok, lokális adatok, munkaadatok, stb.). Technológiai elvek: 1. Kevés, de egyértelmû szabályt kell kialakítani az algoritmusok leírására. 2. Könnyû olvashatóság a bekezdéses leírás és az összetett utasítások zárójelezésének felhasználásával. 3. A beszédes azonosítók elve.
27
A programozás folyamata az algoritmus készítésére és a kódolásra bontható. Ezt készíti elõ a feladatmeghatározás (speciÞkáció) és ezt ”zárja le” a program tesztelése. Technikai elvek: 1. Udvarias program. 2. Bolondbiztos (biztonságos) program. 3. Jól olvasható program. 4. Jól dokumentált program Emberközelség: 1. Lapkezelési technika. 2. Menûtechnika. 3. Input/output adatoknál mértékegység, értéktartomány. 4. Fontos adatok kiemelése. 5. Szövegek tördelése a helyesírás szabályainak megfelelõen. 6. Következetes beolvasási szokások. 7. A hiba megfontolt kijelzése (és képi környezete).
5
Programok helyességének bizonyítása
A programok elemzése, megértése a programozó számára lényeges kérdés, különösen a következýo esetekben: 1. Az algoritmus megalkotásakor 2. Hibakereséskor. 3. A program hatékonyságának növelésekor. 4. A program veriÞkációjakor (korrekt mu ý ködés ellenýorzésekor. Három fogalom lényeges programok helyességének igazolásakor: elýofeltétel (P), utófeltétel (R), ciklusinvariáns (Q). A (parciális) programhelyesség igazolásakor lényegében azt mutatjuk meg, hogy ha a program kezdýoadataira az elýofeltétel teljesül, akkor a program eredményére az utófeltétel teljesül. Jelölés: {P }program{R}, vagy {P } program {R}
28
Példaként igazoljuk a SelectionSort algoritmus helyességét! {m ≤ n} {Az A tömbnek legalább egy eleme van} SelectionSort(A,m,n) {A rendezýoprogram} {A [m] ≥ A [m + 1] ≥ . . . ≥ A [n]} {Elemek csökkenýo sorrendben vannak} A bizonyításhoz a) állításokat (logikai feltételeket) helyezünk el a programban (a programgráf pontjaiban), b) A felhasznált szubrutinok helyességét szintén igazoljuk. Esetünkben ez a FindMax rutin és a bizonyítandó konstrukció: {m < n} {A [m..n] legalább két eleme van} j:=FindMax(A,m,n) {A maximum keresýo program} {A[j] ≥ A [m..n]} {A [j] az A [m..n] tömb legnagyobb eleme} Megjegyzés: A [j] ≥ A [m..n] azt jelöli, hogy A [j] ≥ A [i] (∀m ≤ i ≤ n). Tekintsük most a FindMax programot a megfelelýo állításokkal ellátva!
29
5
10
15
20
25
function FindMax(var A:InputArray; m,n:Integer):Integer; | | {Precondition: mA[j] then j:=i; | | | {♦loop invariant: A [j] ≥ A [m..i] ∧ (i ≤ n) ♦} | | until (i=n); | | | {♦Final assertion: A [j] ≥ A [m..n] ♦} | | FindMax:=j; {return j=position of the largest number A[j] in A[m..n]} | end{FindMax};
A bizonyítás lépései: 1. Tegyük fel, hogy m < n (elýofeltétel). 2. Ekkor i = j = m és (i = m) ∧ (j = m) ∧ (m < n) teljesül. 3. A ciklus elsýo iterációjában: i := i + 1 = m + 1 ≤ n. Ha A [i] = A [m + 1] > A [j] = A [m], akkor j 0 := m + 1 lesz és teljesül a ciklusinvariáns: £ ¤ £ ¤ A j 0 ≥ A [m] ∧ A j 0 ≥ A [m + 1] . 30
Ha A [i] = A [m + 1] ≤ A [j] = A [m], akkor j = m marad és szintén teljesül a ciklusinvariáns. 4. Tegyük fel, hogy az i indexre teljesül a ciklusinvariáns és vizsgáljuk az (i + 1)-edik iterációt! Ekkor i < n. Ha A [i + 1] > A [j], akkor j 0 := i + 1 lesz, i + 1 ≤ n és £ ¤ A j 0 := A [i + 1] > A [j] ≥ A [m..i] .
Tehát A [j] ≥ A [m..i + 1] . Ha A [i + 1] ≤ A [j], akkor j változatlan marad, (A [i + 1] ≤ A [j]) ∧ (A [j] ≥ A [m..i]) ⇒ (A [j] ≥ A [m..i + 1]). 5. Kilépéskor i = n. Ide az i = n − 1 ciklusérték után jutunk és az elýozýo okfejtés érvényes rá. Tehát kilépéskor teljesül, hogy A [j] ≥ A [m..n] , ami éppen az igazolni kívánt utófeltétel. Tehát a FindMax program (parciális) helyességét igazoltuk. Tekintsük most a SelectionSort programot!
31
5
10
15
20
25
procedure SelectionSort(var A:InputArray; m,n:Integer); | | {Precondition: m ≤ n} | {Postcondition: A [m..n] is sorted such that A [m] ≥ A [m + 1] ≥ . . . ≥ A [n]} | | var MaxPosition, Temp: Integer; | begin | | if mA[MaxPosition]} | | Temp:=A[m]; A[m]:=A[MaxPosition]; A[MaxPosition]:=Temp; | | | | {♦A[m] ≥ A [m..n] ♦} | | | | SelectionSort(A,m+1,n); | | | | {♦A[m] ≥ A [m + 1] ≥ . . . A [n] ♦} | | | end {if }; | | {♦Final assertion: A[m] ≥ A [m + 1] ≥ . . . A [n] ♦} | end{SelectionSort}
Házi feladat: Igazoljuk a fenti program helyességét a megelýozýo minta alapján! Néhány logikai alapú programhelyesség vizsgálati módszert ismertetünk.
5.1
Parciális helyesség
A következõ jelöléseket használjuk: P - program x - a P program összes változójának összessége (vektora) x0 - az x változók kezdeti értéke (a programfutás kezdetekor) 32
xh - az x változók végsõ értéke (a programfutás befejezésekor, v. termináláskor). Legyenek L0 , L1 , . . . , Lh a program kijelölt cimkéi (a programgráf csomópontjai), ahol L0 a belépési pont és Lh a kilépési pont. Az Li és Lj csomópontok (cimkék) közti α útvonal alapvetõ, ha nincs kijelölt cimke Li és Lj között. L
Li α
j
Legyen tα (x) az α útvonalra lépés feltétele, gα (x) pedig egy függvény, amely az értékek megváltozását fejezi ki az α útvonal bejárása után. Legyen az Li cimkénél (csomópontban) x = a. Ha tehát tα (a) igaz, akkor az α útvonal végrehajtódik, eljutunk az Lj csomópontba, ahol a változók új értéke x = gα (a) lesz. Legyen Φ (x0 ) egy input speciÞkáció, amely megadja a legális kezdeti értékeket. Hasonlóképpen legyen Ψ (x0 , xh ) egy output speciÞkáció, amely megadja a kezdõ- és végértékek közt megkövetelt összefüggéseket. A következõ deÞníciókat használjuk: DeÞníció: A P program parciálisan helyes a Φ és Ψ szerint, ha minden olyan x0 értékre, amelyre Φ (x0 ) igaz és a program eléri az Lh kimenetet, Ψ (x0 , xh ) igaz. DeÞníció: A P program terminál Φ szerint, ha minden olyan x0 értékre, amelyre Φ (x0 ) igaz, a program eléri az Lh kimenetet. DeÞníció: A P program teljesen helyes a Φ és Ψ szerint, ha P parciális helyes Φ és Ψ szerint és P terminál φ szerint. 5.1.1
Az invariáns módszer
A módszer Floyd (1967) és Hoare (1969) nevéhez fûzõdik. A Φ és Ψ szerinti parciális programhelyesség igazolásához olyan, az L0 , L1 , . . . , Lh cimkéknek megfelelõ q0 (x0 , x) , q1 (x0 , x) , . . . , qh (x0 , x) predikátumokat keresünk, amelyekre a következõ ellenõrzõ feltételek teljesülnek minden x, x0 és xh esetén: (I1) Φ (x0 ) ⇒ q0 (x0 , x0 ), (I2) qh (x0 , xh ) ⇒ Ψ (x0 , xh ), (I3) Minden Li és Lj közti alapvetõ útvonalra fennáll, hogy tα (x) ∧ qi (x0 , x) ⇒ qj (x0 , gα (x)) . 33
Az (I1) feltétel jelentése: az input speciÞkációból a kezdõ predikátum következik. Az (I2) feltétel jelentése: az utolsó predikátumból az output speciÞkáció következik. Az (I3) feltétel jelentése: az útvonal elõtti predikátumból következik az útvonal bejárása utáni predikátum, feltéve, hogy az útvonal bejárható. Az (I1) és (I3) ellenõrzõ feltételekbõl következik, hogy minden i-re, qi (x0 , x) egy invariáns állítás az Li cimkénél (csomópontban). Minden alkalommal, amikor Li -n keresztülmegyünk, qi (x0 , x) igaz az x0 kezdeti értékre és az x aktuális értékre. Ennek megfelelõen a qh (x0 , x) predikátum is invariáns az Lh kilépési pontban. Ezért az (I2) feltétel miatt a P program parciálisan helyes. Tétel (Floyd): Az (I1)-(I3) feltételek fennállása esetén a P program parciálisan helyes a Φ és Ψ speciÞkáció szerint. A gyakorlatban Φ (x0 ) gyanánt a q0 (x0 , x0 ), Ψ (x0 , x) gyanánt pedig a qh (x0 , x) predikátumokat szokás venni. Ekkor az (I1) és (I2) ellenõrzõ feltételek automatikusan teljesülnek. √ Példa (négyzetgyök egészrésze program): A program a b = [ a] értéket számolja ki tetszõleges nemnegatív a egész számra. A b végsõ értéke az a √ legnagyobb k egész szám, amelyre a k ≤ a feltétel teljesül, azaz b2 ≤ a < (b + 1)2 . Tekintsük a következõ programot: input (a) L0 : (b, c, d) ← (0, 1, 1) L1 : if c > a then Lh : output (b) else (b, d) ← (b + 1, d + 2) c←c+d goto L1 A program mûködésének megértéséhez táblázatoljuk a változók iterációnkénti értékeit néhány esetre. Az i-edik iterációban a b ← b + 1, d ← d + 2 és c ← c + d + 2 értékadás történik: i 0 1 2 3
b 0 1 2 3
d 1 3 5 7
c 1 4 9 16
Tulajdonképpen b = i, d = 2i + 1 és c = (i + 1)2 . Ezért az (i + 1)-edik lépésben (ha végrehajtható) c = (i + 1)2 +(2i + 1)+2 = i2 +4i+4 = (i + 2)2 . 34
A parciális helyesség igazolásához legyen Φ (a0 ) : a0 ≥ 0 és Ψ (a0 , bh ) : b2h ≤ a < (bh + 1)2 . Tegyük fel, hogy q0 (a0 , a0 ) ≡ Φ (a0 ) és qh (a0 , bh ) ≡ Ψ (a0 , bh ). Olyan q1 (a0 , a, b, c, d) predikátumot kell keresnünk, amelyre a következõ (I3) ellenõrzõ feltételek fennállnak: Φ (a0 ) ⇒ q1 (a0 , a0 , 0, 1, 1) ; c > 0 ∧ q1 (a0 , a, b, c, d) ⇒ Ψ (a0 , b) ; c ≤ a ∧ q1 (a0 , a, b, c, d) ⇒ q1 (a0 , a, b + 1, c + d + 2, d + 2) . A következõ q1 (a0 , a, b, c, d) : a = a0 ∧ b2 ≤ a ∧ c = (b + 1)2 ∧ d = 2b + 1 invariáns feltétel ezt kielégíti. Feladat: Csináljunk egy olyan programot a fenti feladatra, amelyben a ciklusváltozó értékét emeljük négyzetre, amíg lehet. Igazoljuk a program helyességét a fenti módszerrel! Hasonlítsuk össze a két programot! A program helyességének adott input-output speciÞkációk szerinti ellenõrzése három fázisból áll: - alkalmas invariáns állítások keresése, - a megfelelõ ellenõrzõ feltételek elõállítása, - az ellenõrzõ feltételek igazolása. Az invariáns állítások megtalálásához a program elveinek mély ismerete és megértése szükséges, amelyrõl feltesszük (?), hogy a programozó azokat a program leírásában megadja. A program helyesség ellenõrzésének lépéseit a következõképpen foglalhatjuk össze: program + input/output speciÞkációk + invariáns feltételek ↓ ellenõrzõ feltételek generálása ellenõrzõ feltételek ↓ tétel bizonyítás igen, nem, vagy nem tudjuk 35
5.1.2
A részcél módszer
A módszer Manna (1971), Morris és Wegbreit (1977) munkásságának köszönhetõ. Az invariáns módszertõl két alapvetõ dologban tér el: (1) A qi (x0 , x) invariáns állítás az x aktuális értéket összekapcsolja az x0 kezdeti értékkel. A részcélok módszerében a qi∗ (x, xh ) állítás az x aktuális értéket az xh végsõ értékhez kapcsolja. Azt is mondhatjuk, hogy qi (x0 , x) azt írja le, hogy mi volt eddig, míg qi∗ (x, xh ) azt írja lesz, hogy mit kell tenni ezután. (2) Az invariáns módszer elõretartó indukciót használ L0 -tól Lh -ig: q0 (x0 , x0 ) qi (x0 , x) ⇒ qj (x0 , gα (x)) . Ugyanakkor a részcél módszer hátratartó indukciót használ Lh -tól L0 -ig: qh∗ (xh , xh ) qj∗ (gα (x) , xh ) ⇒ qi∗ (x, xh ) . A Φ és Ψ szerinti parciális programhelyesség részgól módszer szerinti igazolásához olyan, az L0 , L1 , . . . , Lh cimkéknek megfelelõ q0∗ (x, xh ) , q1∗ (x, xh ) , . . . , qh∗ (x, xh ) predikátumokat kell keresnünk, amelyekre a következõ ellenõrzõ feltételek teljesülnek minden x, x0 és xh esetén: (S1) qh∗ (xh , xh ), (S2) Φ (x0 ) ∧ q0∗ (x0 , xh ) ⇒ Ψ (x0 , xh ), (S3) Minden Li és Lj közti alapvetõ útvonalra fennáll, hogy tα (x) ∧ qj∗ (gα (x) , xh ) ⇒ qi∗ (x, xh ) . Az (S1) feltétel jelentése: Az utolsó predikátum mindig igaz az xh output értékre. Az (S2) feltétel jelentése: Az input speciÞkációból és a kezdeti predikátumból az output speciÞkáció következik. Az (S3) feltétel jelentése: Az útvonal utáni predikátumból az útvonal elõtti predikátum következik. Az (S1) és (S3) ellenõrzõ feltételekbõl következik, hogy qi∗ (x, xh ) minden i-re egy részcél állítás Li -ben, azaz valahányszor átmegyünk Li -n, qi∗ (x, xh ) 36
igaz az x aktuális értékre és az xh végsõ értékre. Emiatt q0∗ (x, xh ) az L0 beli részcél állítás, amely az (S2) ellenõrzõ feltétel miatt a program parciális helyességét biztosítja. Tétel (Manna): Az (S1)-(S3) feltételek fennállása esetén a P program parciálisan helyes a Φ és Ψ speciÞkáció szerint. A gyakorlatban szokás a qh∗ (x, xh ) ≡ (x = xh ) feltevéssel élni. A következõ példában bemutatjuk mindkét program helyesség igazolási módszert. Példa (a legnagyobb közös osztó program): A következõ program az a0 és b0 pozitív egész számok legnagyobb közös osztóját számítja ki. input (a0 , b0 ) L0 : (a, b) ← (a0 , b0 ) L1 : if a = 0 then L2 : output (b) else (a, b) ← (rem (b, a) , a) goto L1 , ahol rem(b, a) a b a-val történõ osztásának maradékát jelöli (0 ≤rem(b, a) ≤ a − 1). Az a és b pozitív egész számok legnagyobb közös osztóját a gcd (a, b) szimbólummal jelöljük. Legyen Φ (a0 , b0 ) : a0 > 0 ∧ b0 > 0, Ψ (a0 , b0 , bh ) : bh = gcd (a0 , b0 ) . A program helyességének invariáns módszer szerinti igazolásához a következõ invariáns állításokat használhatjuk: q0 (a0 , b0 , a, b) : a0 > 0 ∧ b0 > 0, azaz Φ (a0 , b0 ) , q1 (a0 , b0 , a, b) : a ≥ 0 ∧ b > 0 ∧ gcd (a, b) = gcd (a0 , b0 ) , q2 (a0 , b0 , a, b) : b = gcd (a0 , b0 ) , azaz Ψ (a0 , b0 , b) . Ezután az (I1), (I2) és (I3) ellenõrzõ feltételeket kell használni. A qi (a0 , b0 , a, b) predikátumok az a és b programváltozókat kötik össze az a0 és b0 kezdeti értékeikkel. A program helyességének részcél módszer szerinti igazolásához a következõ részcél állításokat használhatjuk: q0∗ (a, b, bh ) : a ≥ 0 ∧ b > 0 ⇒ bh = gcd (a, b) , q1∗ (a, b, bh ) : a ≥ 0 ∧ b > 0 ⇒ bh = gcd (a, b) , q2∗ (a, b, bh ) : b = bh . 37
Ezután alkalmazzuk az (S1), (S2) és (S3) ellenõrzõ feltételeket. A qi∗ (a, b, bh ) predikátumok az a és b program változókat a b változó bh végsõ értékéhez kapcsolják. Feladat: A következýo program adott intervallumon unimodális függvény minumumhelyét adott eps pontossággal határozza meg. Egy f ∈ C [a, b] függvényt unimodálisnak nevezzük, ha tetszý oleges x1 , x2 ∈ [a, b], x1 < x2 esetén x2 ≤ x∗ ⇒ f (x1 ) > f (x2 ) , x1 ≥ x∗ ⇒ f (x1 ) < f (x2 ) .
(a) (b)
Az unimodális f függvény az x∗ minimumhelytýol balra szigorúan monoton csökkenýo, týole jobbra pedig szigorúan monoton növýo. input (x1 , x2 ) L0 : (y1 , y2 ) ← (x1 , x2 ) L1 : if y2 − y1 ≤ eps then L2 : output (y1 ) else y4 ← y1 + 0.618 ∗ (y2 − y1 ) y3 ← y2 − 0.618 ∗ (y2 − y1 ) if f (y3 ) < f (y4 ) then y2 ← y4 else y1 ← y3 goto L1 , Igazoljuk mindkét módszerrel a program helyességét! 5.1.3
A módszerek összehasonlítása
A részcél módszer és az invariáns állítások módszere ekvivalens. Igaz a következõ állítás. Tétel: Bármely invariáns programhelyesség igazolás átalakítható egy részcél bizonyítássá és fordítva. Bizonyítás: A) (invariáns bizonyítás⇒részcél bizonyítás). Tegyük fel, hogy van egy invariáns bizonyításunk arra, hogy P parciálisan helyes Φ és Ψ szerint. Legyenek qi (x0 , x) az (I1) Φ (x0 ) ⇒ q0 (x0 , x0 ), (I2) qh (x0 , xh ) ⇒ Ψ (x0 , xh ), (I3) Minden Li és Lj közti alapvetõ útvonalra fennáll, hogy tα (x) ∧ qi (x0 , x) ⇒ qi (x0 , gα (x)) . feltételeket minden x, x0 és xh esetén kielégítýo invariáns állítások. 38
DeÞniáljuk a részcél állításokat a következýoképpen: qi∗ (x, xh ) ≡ ∀y [qi (y, x) ⇒ Ψ (y, xh )] . Azt kell igazolnunk, hogy az (S1) qh∗ (xh , xh ), (S2) Φ (x0 ) ∧ q0∗ (x0 , xh ) ⇒ Ψ (x0 , xh ), (S3) Minden Li és Lj közti alapvetõ útvonalra fennáll, hogy tα (x) ∧ qj∗ (gα (x) , xh ) ⇒ qi∗ (x, xh ) feltételek minden x, x0 és xh esetén fennállnak. (S1) igazolása: qh∗ (xh , xh ) ≡ ∀y [qi (y, xh ) ⇒ Ψ (y, xh )]. De ez (I2) következménye. (S2) igazolása: Φ (x0 ) ∧ q0∗ (x0 , xh ) ⇒ Ψ (x0 , xh ) most azonos a Φ (x0 ) ∧ ∀y [q0 (y, x0 ) ⇒ Ψ (y, xh )] ⇒ Ψ (x0 , xh ) feltétellel. 1. Φ (x0 ) adott. 2. ∀y [q0 (y, x0 ) ⇒ Ψ (y, xh )] adott. 3. Az 1. és (I1) miatt q0 (x0 , x0 ) igaz. 4. De akkor Ψ (x0 , xh ) is igaz 2. és 3. miatt. (S3) igazolása: A tα (x)∧qj∗ (gα (x) , xh ) ⇒ qi∗ (x, xh ) feltétel most azonos a tα (x) ∧ ∀y [qj (y, gα (x)) ⇒ Ψ (y, xh )] ⇒ ∀y [qi (y, x) ⇒ Ψ (y, xh )] feltétellel. 1. tα (x) adott. 2. ∀y [qj (y, gα (x)) ⇒ Ψ (y, xh )] adott. 3. qi (y, x) fennáll a feltevések miatt. 4. qi (y, gα (x)) igaz 1,3, és (I3) miatt. 5. Ψ (y, xh ) igaz 2 és 4 miatt. B) (részcél bizonyítás⇒invariáns bizonyítás). Tegyük fel, hogy van egy részcél bizonyításunk arra, hogy P parciálisan helyes Φ és Ψ szerint. Legyenek qi∗ (x, xh ) az (S1), (S2) és (S3) feltételeket kielégítýo részcél állítások. Legyen továbbá qi (x0 , x) ≡ ∀y [qi∗ (x, y) ⇒ Ψ (x0 , y)] . (I1) igazolása: Φ (x0 ) ⇒ q0 (x0 , x0 ) most azonos a Φ (x0 ) ⇒ ∀y [qi∗ (x0 , y) ⇒ Ψ (x0 , y)] 39
feltétellel. 1. Φ (x0 ) adott. 2. q0∗ (x0 , y) fennáll feltevés alapján. 3. Ψ (x0 , y) fennáll 1.,2. és (S2) miatt. (I2) igazolása: Igazoljuk, hogy qh (x0 , xh ) ⇒ Ψ (x0 , xh ), azaz ∀y [qh∗ (xh , y) ⇒ Ψ (x0 , y)] ⇒ Ψ (x0 , xh ) . 1. ∀y [qh∗ (xh , y) ⇒ Ψ (x0 , y)] adott. 2. qh∗ (xh , xh ) fennáll (S1) miatt. 3. Ψ (x0 , xh ) fennáll 1. és 2. miatt. (I3) igazolása: A tα (x) ∧ qi (x0 , x) ⇒ qj (x0 , gα (x)) feltétel most £ ¤ tα (x) ∧ ∀y [qi∗ (x, y) ⇒ Ψ (x0 , y)] ⇒ ∀y qj∗ (gα (x) , y) ⇒ Ψ (x0 , y) . 1. 2. 3. 4. 5.
5.2
tα (x) adott. ∀y [qi∗ (x, y) ⇒ Ψ (x0 , y)] adott. qj∗ (gα (x) , y) fennáll feltevés miatt. qi∗ (x, y) fennáll 1., 3. és (S3) miatt. Ψ (x0 , y) fennáll 2. és 4. miatt.
Terminálás
Floyd (1967) módszerét ismertetjük. DeÞníció: Egy W nemüres halmaz szigorúan részben rendezettnek nevezzük, ha egy adott ≺ relációra nézve teljesülnek a következý o feltételek: (a) tranzitivitás: Ha a, b, c ∈ W és a ≺ b ≺ c, akkor a ≺ c. (b) aszimmetria: Ha a, b ∈ W és a ≺ b, akkor b ⊀ a. (c) irreßexivitás: Ha a ∈ W akkor a ⊀ a. DeÞníció: A W szigorúan parciálisan rendezett halmazt jól rendezettnek mondjuk, ha az nem tartalmaz a0 Â a1 Â a2 Â · · ·
(ai ∈ W , i = 0, 1, 2, . . . )
végtelen csökkený o sorozatot. Az N0 halmaz a szokásos < rendezéssel jól rendezett. Az egész számok Z halmaza ugyanezzel a rendezéssel pedig nem jól rendezett. A P program Φ (x0 ) speciÞkáció szerinti terminálásának igazolásához a következýoket kell tennünk. (1) Olyan, az L0 , L1 , . . . , Lh cimkéknek megfelelõ q0 (x0 , x) , q1 (x0 , x) , . . . , qh−1 (x0 , x) 40
predikátumokat keresünk, amelyekre minden x0 és xh esetén fennáll, hogy (W1) Φ (x0 ) ⇒ q0 (x0 , x0 ), (W2) Minden Li és Lj közti alapvetõ útvonalra tα (x) ∧ qi (x0 , x) ⇒ qj (x0 , gα (x)) . (2) Olyan (W, ≺) jól deÞniált halmazt és e0 (x0 , x) , e1 (x0 , x) , . . . , eh−1 (x0 , x) termináló függvényeket keresünk, amelyekre fennáll, hogy (W3) qi (x0 , x) ⇒ ei (x0 , x) ∈ W minden olyan Li -re amely valamely ciklusban van. (W4) tα (x) ∧ qi (x0 , x) ⇒ ei (x0 , x) Â ej (x0 , gα (x)) minden olyan Li és Lj közti alapvetõ útvonalra, amely valamely ciklusban van. Megjegyzések: A (W1) jelentése: az input speciÞkációból a kezdeti predikátum következik. A (W2) jelentése: Az alapvetýo útvonal kezdýo predikátuma implikálja az utvonal utáni predikátumot. A (W3) jelentése: A kifejezés értéke W -hez tartozik valahányszor a vezérlés Li -n átmegy. A (W4) jelentése: Amikor a vezérlés Li -týol Lj -re átadódik a termináló függvény értéke csökken. A (W1) és (W2) feltételekbýol az következik, hogy minden qi (x0 , x) invariáns állítás Li -ben. A (W3) és (W4) feltételekben ez megszorítja az ei értelmezési tartományát. Tétel: A (W1)-(W4) terminálási feltételek fennállása esetén a P program terminál Φ szerint. Bizonyítás: Állításunkkal ellentétben tegyük fel, hogy a program nem terminál valamilyen olyan x0 értékre, amelyre Φ (x0 ) igaz. Ekkor a program átmegy cimkék egy végtelen Li1 , Li2 , . . . sorozatán. Az x megfelelýo értékei legyenek rendre xi1 , xi2 , . . . . Ekkor (W1) és (W2) miatt a qi1 (x0 , xi1 ) , qi2 (x0 , xi2 ) , . . .
41
állitások teljesülnek és a (W3), (W4) feltételek miatt ei1 (x0 , xi1 ) Â ei2 (x0 , xi2 ) Â · · · . Vagyis kaptunk egy végtelen csökkenýo sorozatot, ami ellentmondás. Példa: Tekintsük ismét a négyzetgyök egészrésze programot input (a) L0 : (b, c, d) ← (0, 1, 1) L1 : if c > a then Lh : output (b) else (b, d) ← (b + 1, d + 2) c←c+d goto L1 Legyen Φ (a0 ) ≡ (a0 ≥ 0), q0 (a0 ) ≡ (a0 ≥ 0) és q1 (a0 , a, b, c, d) ≡ (a = a0 ) ∧ (c − d ≤ a) ∧ (d > 0) . Igazoljuk, hogy (W1) a0 ≥ 0 ⇒ a0 ≥ 0 (W2) a0 ≥ 0 ⇒ q1 (a0 , a0 , 0, 1, 1), c ≤ a ∧ q1 (a0 , a, b, c, d) ⇒ q1 (a0 , a, b + 1, c + d + 2, d + 2). Legyen (W, ≺) az (N, <) jól rendezett halmaz, e1 (a0 , a, b, c, d) = a − c + d és igazoljuk, hogy (W3) q1 (a0 , a, b, c, d) ⇒ a − c + d ≥ 0, (W4) c ≤ a ∧ q1 (a0 , a, b, c, d) ⇒ a − c + d > a − (c + d + 2) + (d + 2).
6
Programok transzformálása és optimálása
Cél: a programok gyorsítása, hatékonyságának növelése. Eszközök: sokféle Példák:. 1. rekurzió átalakítása ciklussá 2. függvényhívások törzsének beépítése a hívó eljárásba 3. algebrai, logikai kifejezések átalakítása 4. stb. 1. Példa: Tekintsük az alábbi program részletet! if (i<=n) and (not (i=n)) then begin y:=x*x*x+3*x*x+5*x+2 end{if }; Ennek elsýo javítása: 42
if (i
43
3. Példa: Alakítsuk át a javított SelectionSort eljárás FindMax függvényhívását a függvénytörzs SelectionSort eljárásba helyezésével! A FindMax eljárás kommentárok nélkül: function FindMax(var A:InputArray; m,n:Integer):Integer; {assume mA[j] then j:=i; until (i=n); FindMax:=j; end{FindMax}; Helyezzük be ezt a függvényeljárást a SelectionSort eljárásba! procedure SelectionSort(var A:InputArray; m,n:Integer); var MaxPosition, Temp, i, j: Integer; begin while mA[j] then j:=i; until (i=n); MaxPosition:=j; Temp:=A[m]; A[m]:=A[MaxPosition]; A[MaxPosition]:=Temp; m:=m+1 end{while}; end{SelectionSort} Itt a FindMax változó helyett a MaxPosition változót használtuk fel. Valójában még egy kicsit lehet javítani a programon, ui. a j változó felesleges. procedure SelectionSort(var A:InputArray; m,n:Integer); var MaxPosition, Temp, i: Integer; begin
44
while mA[MaxPosition] then MaxPosition:=i; until (i=n); Temp:=A[m]; A[m]:=A[MaxPosition]; A[MaxPosition]:=Temp; m:=m+1 end{while}; end{SelectionSort} Az alábbi statisztika mutatja, hogy a fenti két javítás hatásos (a futási idýok msec-ben): Tömb méret (n) 125 250 500 1000 2000
Iteratív SelecionSort 3.5 13.9 55.4 221.1 884.4
Rekurzív SelectionSort 3.9 15.4 61.1 242.8 968.6
Feladat: Mit csinál a következýo program? Alakítsuk át iteratív algoritmussá! procedure ReverseString(var S: String; m,n: Integer); var c: Char; begin if m
7
Programok tesztelése
A minýoségi szoftver fejlesztés egyik legfontosabb eszköze: a gondos és szisztematikus program tesztelés. Tegyük fel, hogy adott egy részletes programterv és annak, mondjuk Pascal nyelvu ý programja. Kérdés: Hogyan teszteljünk ? 45
7.1
Bottom-up tesztelés
Ennek akkor is van értelme, ha a programtervezés top-down módszerrel történt. Lépései a következýok: 1. Azonosítjuk azokat a program részeket, amelyek a rendszer legalján vannak (mert semmilyen más részprogramot nem hívnak). (S1 szint/layer). 2. Addig teszteljük (és javítjuk) az S1 szint programjait, amíg nincsenek rendben. 3. Azonosítjuk az alprogramok második S2 szintjét. Ezek azok a programok, amelyek az S1 szint programjait meghívják, de nem hívnak meg más programokat. 4. Addig teszteljük (és javítjuk) az S2 szint programjait, amíg nincsenek rendben. 5. Azonosítjuk az S3 programszintet, ahova azok a programok tartoznak, amelyek az S1 és S2 szint már tesztelt programjait hívják meg és semmi mást. 6. Addig teszteljük (és javítjuk) az S3 szint programjait, amíg nincsenek rendben. 7. Így folytatva elérünk a végsýo Sn (top) programszinthez (tkp. programhoz), amely meghívja az eddig tesztelt alprogramokat, de ýot magát már semmi nem hívja meg. 8. A tesztelést az Sn szint tesztelése zárja. Az alábbi ábra egy négy szintes program rendszert mutat be.
46
A
B
E
I
S4
C
F
J
S3
D
G
K
H
L
S2
S1
Program szintek Az ábra esetén a tesztelési sorrend szintek szerint: 1. I, J, K, L 2. E, F, G, H 3. B, C, D 4. A A bottom-up tesztelésben a tesztelés sorrendjét két dolog határozza meg: 1. A hívási rend (gráf). 2. A szubrutinok adatátalakítási módja. Pl. Elýoször tesztelnünk kell azt a rutint, amelyik a kezdýo adatokat inicializálja és csak aztán tesztelhetjük azokat a rutinokat, amelyek ezeket az adatokat használják. Bizonyos esetekben a szubrutinok kölcsönösen rekurzívak. Pl. adott az X, Y és Z szubrutin, ahol X meghívja Y-t, Y meghívja Z-t és Z meghívja X-et. Ilyen esetekben a rutinokat egy un. clusterben együtt kell tesztelni. A kulcs a tesztelés sorrendjéhez: Valahányszor lehetséges, mielý ott az X szubrutint teszteljük, teszteljük az összes olyan szubrutint, amelyet X hív meg, vagy X számára adatot készít elý o.
47
7.2
Tesztelési egységek, formázott hibakeresý o eszközök és teszt driverek
Tegyük fel, hogy azonosítottuk a szubrutinok bottom-up tesztelési sorrendjét. Kérdés: Hogyan teszteljük az egyes rutinokat? Egy adott szubrutin tesztelését egység tesztelésnek (unit testing) nevezik (6≡Pascal unit!). Követelmények1 : 1. A tesztelésnek a szubrutin összes lehetséges viselkedését le kell fednie (már, ha ez lehetséges). 2. A szubrutine minden egyes lehetséges végrehajtási útvonalát ellenýorizni kell. 3. A szélsýoséges, vagy határeseteket ellenýorizni kell. Pl. Mi történik, ha egy táblázat, vagy lista üres, vagy éppen tele van? Mi történik a következýo ciklusban, ha pl. n = 5? for i:=1to n do begin {valami} end{for} Az extrém esetek elképzelése, felfedése komoly képzelýoerýot és gyakorlatot igényel. 4. Ellenýorizni kell, hogy az adatszerkezetek inicializálása, illetve a szubrutin által létrehozott adatszerkezetek korrektek-e! Pl.egy létrehozott listában az utolsó cellában van-e NIL elem? A formázott hibakeresý o eszközök fontosságát már az 50-es években felismerték. Ezek tkp. egyszerýu rutinok, amelyek adatszerkezeteket (vagy azok graÞkus képét), vagy (hiba)üzeneteket nyomtatnak. Ezek segítségével ellenýorizni lehet, hogy: 1. A program eléri-e a programgráf egy bizonyos csomópontját? Hol akad el? 2. Milyen a program végrehajtási útvonala? 3. Történt-e változás egy csomópont (szubrutin) meghívása után? Pl. egy tipikus elýotte-utána tesztelésre formázott hibakeresýo eszközzel, ahol D az adatszerkezet, amelyet az R szubrutine megváltoztat. {Print a picture of D before executing R} R; {then call the subroutine R} {Print a picture of D after executing R} Tapasztalat, hogy a formázott hibakeresýo eszközök nagyjából felére csökkenthetik a tesztelési idýot. 1
Tkp. ez a teljes rendszer tesztelésére is vonatkozik.
48
Mindenesetre a program hibák helyét igen gyorsan lehet velük lokalizálni. Teszt driverek: Az S szubrutin T tesztdrivere egy olyan szubrutin, amely elýoállítja a teszt eseteket (adatokat), meghívja az S rutint minden esetben és ellenýorzi S outputját.
7.3
A tesztelés gráf modelljei és technikái
A vezérlýo gráf koncepcióján alapul (tesztelés bonyolultsága , program bonyolultsága, vezérlýo gráf ciklomatikus száma). Trivális tesztelési cél: A program minden részét legalább egyszer teszteljük. Ez a program méretétýol függýo bonyolultságú feladat. A szükséges tesztek minimális száma a tesztelési munka fontos mérýoszáma. Fedýo koncepciók (intuitív): a) A tesztek olyan halmaza, amely a program minden utasítását lefedi. b) A tesztek olyan halmaza, amely a program minden lehetséges vezérlési, vagy adatáramlási útvonalát lefedi. a)6=b). Elv: A program tesztelése a start pontnál kezdýodik és az end pontnál végzýodik. Útvonal: Élek összefüggýo sorozata, amely a start pontot az end ponttal összeköti. Program útvonal: Gráf útvonal, amely az érintett ciklusok egyszeri bejárását engedi meg. Útvonal teszt: Az útvonal bejárását úvonal tesztnek nevezzük. Csúcsfedý o: A G0 részgráf a G összefüggýo gráf csúcsfedýoje, ha G0 összefüggýo és G öszes csúcspontját tartalmazza. Élfedý o: A G00 részgráf a G összefüggýo gráf élfedýoje, ha G00 összefüggýo és G öszes élét tartalmazza. Pl. Tekintsük a következýo program gráfot ( (a) gráf) és két útvonal tesztjét ((b), (c) gráfok)!
49
a
a
1
a
1
1
b
b
2
3
2
3 5
c
5
c
4
+
4
d
d 6
d 6
6
e (a )
b
e (b )
e (c )
Útvonal teszt A gráf triviális csúcsfedýoi: 1,2,4,6 és 1,2,3,5,6. Egy triviális élfedýo: 1,2,3,4,5,6. Egy egyszeru ý útvonal teszt, amely bejárja a csúcsfedýot: 1,2,4,6, vagy 1,2,3,5,6. Két teszt szükséges az élfedýo bejárásához: Pl. 1. teszt: (b) 1,2,3,2,4,6 2. teszt: (c) 1,5,6. Útvonal teszt fedý o: útvonal tesztek halmaza, amely élfedýot tartalmaz. Az útvonal tesztek halmaza bejárja a gráf fedýot, ha az útvonal tesztek az összes összefüggýo ciklust bejárják. Ezek száma ≤ v (G) (a G gráf ciklomatikus száma). Az útvonalak száma, az útvonalak meghatározása gráfelméleti eszközöket igényel (jelentýos elmélet és gyakorlat, kapcsolat szoftver metrikával). Példa: Ciklus átalakítása ekvivalens ciklusmentes gráffá:
50
DO W HILE
1 1 2
3
4 4
2-3-4
5
5
FELADAT: Csináljuk meg ugyanezt a DO UNTIL szerkezettel!
7.4
Integritás tesztelés
A bottom-up tesztelésnél elýoször az egység teszttelést hajtjuk végre a rendszer minden egyes szubrutinjára. Ezt követi az integritás tesztelése (integration testing), amelynek célja az, hogy a szubrutinok helyes együttmý uködését ellenýorizzük. Pl. Az S szubrutin olyan inputokat hoz létre a T szubrutin számára, amelyre az nincs felkészítve. Az S és T szubrutinok egység tesztelése a speciÞkációik szerent ugyanakkor rendben volt. Ez tipikusan tervezési hibára utal, amelyet csak az integritási tesztelésnél tudunk kiszý urni (esetleg). A probléma különösen nagyméretý u és komplex rendszereknél lép fel.
7.5
Elfogadási tesztelés és regressziós tesztelés
Tegyük fel, hogy létrehoztunk egy olyan általános (keret) teszt programot (test suite), amely 1. egység és integritási tesztekbýol áll. 2. automatikusan (emberi közbeavatkozás nélkül) fut 3. Kinyomtathatja (kimentheti) a teszt eredményeket késýobbi vizsgálatok céljára. Ekkor abban a helyzetben vagyunk, hogy végrehajthatunk további két fontos tesztet: 1. az elfogadási tesztet (acceptance testing) 2. regressziós tesztet (regression testing).
51
Elfogadási teszt: Az a teszt, amelyet a rendszer aktív szolgálatba adása elýott kell elvégezni (tkp. a rendszer átadásához). Az átvételt követi a rendszer karbantartási fázisa a szoftver életciklusán keresztül. A felfedezett hibák javításait, vagy a rendszer továbbfejlesztéseit tesztelni kell a következýok szerint: 1. Ellenýorizni kell, hogy a hiba ki lett-e javítva. 2. Ellenýorizni kell, hogy az új rendszerelemek helyesen dolgoznak-e. 3. Ellenýorizni kell, hogy a változtatások után minden más elem is korrekten mý uködik (nem rontottunk-e el valamit?). Annak az ellenýorzést, hogy minden eddig jól dolgozó rész a változtatások után is jól mý uködik regressziós tesztelésnek nevezzük. A regressziós tesztelés elvei: 1. Keressük meg a hibát! 2. Javítsuk ki a hibát! 3. Egészítsük ki egy olyan teszt esettel a keret teszt programot , amely eldönti, hogy a hibát kijavítottuk, vagy sem! 4. Futtassuk a keret teszt programot. Megjegyzés: Egy hiba kijavítása sokszor új hibák sorát okozhatja. A regressziós teszteket ezért még a rendszer kihozása elýott kell megtervezni.
7.6
Top-down tesztelés és ”stub”-ok
Bizonyos esetekben célszerýu egy rendszer csúcs szintjeit tesztelni, mielýott a felhasznált komponenseket teszteljük. Ez tkp. a bottom-up tesztelési sorrend megfordítása. A korábbi példa esetében ez a következýo sorrendet jelenti:
52
A
B
E
I
S4
C
F
J
S3
D
G
K
H
L
S2
S1
Program szintek 1. A 2. B, C, D 3. E, F, G, H 4. I, J, K, L Általában, az Si+1 szintet az Si szint elýott teszteljük a top-down tesztelésnél. A bottom-up tesztelésnél a probléma felmerülésekor azonnal tudjuk, hogy mely elemnél merült fel a hiba. A top-down tesztelésnél erre tkp. nincs garancia. Miért szükséges akkor? Képzeljünk el egy nagy rendszert, amelynek részeit különbözýo csoportok, különbözýo idýopontokban készítik el. A fejlesztés közben is szükséges az elkészült részek tesztelése függetlenül a többi alrendszertýol. A tesztelés alap eszköze az un. ”stub” program (koncepció). Ez olyan program, amely helyettesíti az igazi szubrutint és elýoállítja annak outputjait bizonyos teszt esetekben. Pl. vizsgáljuk a következýo rutint! function Compound(A,r: real; n: integer):real; begin Compound:=A*Power(1+r/100,n); end{Compound} 53
A függvény meghívja a Power(x,n) függvényt, amely xn értékét számolja ki. A teszt driver a Compound(A,r,n) rutint a következýo három hívással teszteli: Compound(100,6.0,5) {$100 invested at 6% for 5 years} Compound(100,6.0,0) {$100 invested at 6% for 0 years} Compound(100,0.0,5) {$100 invested at 0% for 5 years} A három teszt eset a következýo Power(x,n) hívásokat generálja: Power(1.06,5), Power(1.06,0), Power(1.00,5). Ekkor (és csak ekkor) a Power(x,n) rutint a következýo stub rutinnal tesztelhetjük: function Power(x: real; n:integer):real; begin if (x=1.00) or (n=0) then Power:=1.00 else if (x=1.06) and (n=5) then begin Power:=1.3382256 end{if } end{Power}; Megjegyzés: Tkp. a graÞkus, vagy automatikus adatbázistervezýo rendszerek is ilyen stub koncepciót használnak. Példa: Képzeljünk el egy szoftver projektet, amelyet 5 részre osztanak: (a) az adatokhoz szükséges számolások (b) felhasználói interfész (felület) (c) Jelentések nyomtatása (d) adat fájlok mentése és helyreállítása (e) A fýo program írása, amely 1. felhasználja az (a)-(d) egységeket, 2. elfogad és interpretál felhasználói utasításokat 3. végrehajt fájlok nyitására és zárására vonatkozó utasításokat, számításokat hajt végre és jelentéseket (eredményeket) nyomtat. A top-down tesztelés és a stubok másik hasznos felhasználási területe: az egymástól kölcsönösen függýo komponensek tesztelése.
7.7
Tesztelési tervek
Közepes, vagy nagyméretý u projektekhez elengedhetetlen a tesztelési terv elkészítése és dokumentálása. A tesztelési terv tartalma: 1. A teszt esetek felsorolása az input és elvárt output adatokkal együtt. 2. A tesztek céljai. 54
3. A tesztek sikerességének és sikertelenségének egzakt feltételei. A tesztelési terveket elýozetesen ellenýorizni kell a következýo szempontokból: 1. A tesztelés részletessége és gondossága. 2. Garantálja-e hogy a rendszer speciÞkációi teljesülnek?
7.8
A tesztelés és a veriÞkálás összehasonlítása
A tesztelés és veriÞkálás két különbözýo tevékenység, amely a szoftver iránti bizalom növelését szolgálja. A tesztelés felfedhet hibákat, de soha nem bizonyítja a hiányukat. A veriÞkálás azt ellenýorzi, hogy a program tényleg azt csinálja-e, amit csinálnia kell. Nem ellenýorizheti azonban, hogy ezek a formális logikai állítások ténylegesen kifejezik-e a program tényleges mý uködését. Pl. Legyen a feladat az A[m..n] tömb csökkenýo sorrendbe rendezése. Ez így nem teljes, mert nem tartalmazza azt, hogy a rendezést az eredeti elemek sorrendjének megváltoztatásával és egyetlen elem törlése nélkül kell végbemennie. Ha ez nincs, akkor az alábbi program is verÞkálható: for i:=m to n do A[i]:=A[m]; Következésképpen a tesztelés és a veriÞkálás egymást kiegészítik.
8
Mérés és tuningolás
Célja: A ténylegesen mý uködýo programok hatékonyságának javítása. Statisztikai megÞgyelések: 1. A futási idýo 80-90 % a kód egy kis szegmensében (7-10%) telik el . 2. A helyek, ahol a program nem hatékony, gyakran meglepýoek és nem is könnyu ý ýoket elýore jelezni. Következmény: 1. Mérjük a futásidýot és keressük a lassú helyeket. 2. Megpróbáljuk javítani a hatékonyságot. A javítási kisérlet után újra mérünk. Ha ez nem elég, akkor újabb javítási kisérletet teszünk, és így tovább. Ezt az iteratív eljárást nevezik tuningolásnak. Az idýo mérése lehet: 1. execution-time proÞler (ha van) 2. Gépi idýo mérési pontok elhelyezése a programban. Tekintsük a bináris keresés következýo megvalósításait!
55
Feltevés: A[1..n] elemei páronként különbözýok és növekvýoen rendezettek: A [1] < A [2] < · · · < A [n] . Elsý o program (iteratív): function BinarySearch(K:Key):Integer; {to Þnd the position of the search} {key K in the ordered array A[1..n]} var L, {L=left boundary of search interval} Midpoint, {Midpoint=midpoint of search interval} R: Integer; {R=right boundary of search interval} Found: Boolean; {Found=a ßag set to true if K is in A[1..n]} begin L:=0; R:=n+1; Found:=false; Midpoint:=(L+R) div 2; while (L<Midpoint) and (not Found) do begin if K=A[Midpoint] then begin BinarySearch:=Midpoint; Found:=true end else if K>A[Midpoint] then L:=Midpoint; else begin R:=Midpoint; end{if}; end{while}; if not Found then BinarySearch:=0 end{BinarySearch} Vegyük észre, hogy L=0 és R=n+1. Ez az un. nyílt intervallum technika a kézenfekvýo zárt intervallum (L=1, R=n) helyett. Miért lehet ez elýonyös? Második program (rekurzív): function BinarySearch(K:Key;L,R:Integer):Integer; {to Þnd the position of the search key K in the subarray A[L+1..R1]} var 56
Midpoint, {Midpoint=midpoint of search interval} begin Midpoint:=(L+R) div 2; if L=Midpoint then BinarySearch:=0 else if K=A[Midpoint] then BinarySearch:=Midpoint; else if K>A[Midpoint] then BinarySearch:=BinarySearch(K,Midpoint,R) else begin BinarySearch:=BinarySearch(K,L,Midpoint) end{if }; end{BinarySearch} A K kulcs A[1..n]-beli kereséséhez a BinarySearch(K,0,n+1) hívást kell alkalmazni. A két program futásidejének összehasonlítása µ sec-ben: Tömb méret 10 50 100 200 400 800
Iteratív 3.5 5.1 5.9 6.8 7.6 8.5
rekurzív 4.3 6.7 7.9 9.1 10.3 11.5
Jelentéktelennek tý uný o változtatások sokszor jelentý os futásidý o változást okoznak. Vizsgáljuk az iteratív változat alábbi változatait: A) Alapváltozat. B) Ugyanaz mint A, de L,R, Midpoint dupla pontosságú egész C) Ugyanaz mint A, de a Midpoint:=(L+R) div 2 utasítást kicserélték a Midpoint:=Trunc((L+R)/2); utasításra és a lebegýopontos számításokat szimulálták (1 lebegýopontos szimulált mý uvelet=30-40 nem lebegýopontos mý uvelet).
57
Tömb méret 10 50 100 200 400 800
Iteratív A 3.5 5.1 5.9 6.8 7.6 8.5
Iteratív B 11.8 19.2 22.7 26.3 30.0 33.7
Iteratív C 110.0 185.6 221.0 257.4 294.6 332.0
rekurzív 4.3 6.7 7.9 9.1 10.3 11.5
Generális elv: Things are not what they seem to be. További észrevételek: 1. A futásidýok gép, nyelv és fordító programfüggýok. Így a mérési eredmények is. 2. Ezért a mérések még inkább fontosak. Feladat: Ellenýorizzük a fenti táblázatot saját méréssel!
9
Szoftverek újrahasznosítása és bottom-up programozás
Szoftver komponensek mint építõelemek felhasználása valamilyen szinten mindig szükséges. Okok: - praktikus - gazdasági A szoftver fejlesztés költségeinek becslése: - COCOMO (COnstructive Cost MOdel) modellel - ember-hónapok (PM=Person-Months) számában - forráskód hosszában (KDSI=Kilo-Delivered Source Instruction) A regressziós képlet: PM = 2.4 (KDSI)1.05 . Példa: Egy 37600 soros program fejlesztéseinek összes becsült költsége (programmal, dokumentációval, teszteléssel, stb.) a képlet alapján: KDSI=37.6,PM=2.4∗ 37.61.05 ≈ 108.2 ember-hónap≈9 ember-év. Megjegyzések: A fenti képlet csak egy alapbecslés. Ha tapasztalt szoftvercsoport fejleszt, akkor 2.4 helyett a szorzó 0.55 lesz. A fenti példában az eredmény ekkor 59.5 ember-hónapra csökken≈5 ember-év. A képletnek további Þnomabb vátozati is léteznek, amelyek más szempontokat is Þgyelembe vesznek. 58
Lényeges: a legfontosabb tényezõ a szoftver nagysága. A költségek lényegesen csökkenthetõk programozási építõelemek felhasználásával. Példa: Két variáns a WP-2000 szövegszerkesztõ fejlesztésére: a) A fejlesztés nulláról indul és a program becsült hossza 68546 sor. b) Rendszerhéj és rutinkönyvtár megvásárlása 50000$/db áron és 34273 további programsor megírása. Egy programozó évi teljes bére 100000$ (1994). Házi feladat: Mi az elõnyösebb megoldás? Elõnyök-hátrányok: 1. Ha kész, tesztelt szoftvert veszünk, akkor a programírási és tesztelési költségeket csökkenthetjük, a program megbízhatóságát növelhetjük. 2. Ha saját fejlesztést csinálunk, akkor az újra felhasználható építõelemek segítségével késõbbi fejlesztéseket könnyíthetünk meg és piaci nyerõ pozícióba kerülhetünk. 3. Készelemek felhasználása esetén a bottom-up programozás (és tesztelés) kerül nyerõ pozícióba.
10
Programok struktúrálása és dokumentálása
Általános szoftver követelmények: 1. A program dolgozzon korrekten és legyen mentes a hibáktól. 2. Legyen elég hatákony. 3. Fejezzék be az elõírt határidõn és költségkereten belül. 4. A jövõben módosítható legyen, ha ez szükséges. Programozási követelmények (szállóigék): (a) Használjunk értelmes változóneveket! (b) A névvel rendelkezõ konstansokat egyszer és a program elején deÞniáljuk. (c) Kerüljök a goto utasítást és soha ne írjunk spagetti kódot. (d) Írjunk rövid szubrutinokat, amelyek csak egy dolgot tesznek, de azt jól! (e) Modularizáljuk a programokat úgy, hogy az egyes részek egyszerûen és világosan mûködjenek együtt. Példa: Mit csinál az alábbi program? function G(x:Real; n:Integer):Real; var p:Real; begin if n=0 then G:=1.0
59
else begin p:=G(x,n div 2); if (n mod 2)=0 then G:=p*p else begin G:=x*p*p end{if} end{if } end{G} Kifogások: változónevek, kommentárok, stb. Példa: Tegyük fel, hogy π értékét sokféleképpen használják egy programon belül. Pl. P i := 3.14, const Pi=3.14159, const Pi=3.141592654, Pi:=3.14195? Mi történik, ha valamelyik hibás, vagy ha növelni kell a π pontosságát? Következtetés: (b) követelmény.
A programozás komplex és nemvárt hibákkal teli kognitív (tudatos szellemi és tanulási) tevékenysé Tekintsük a következõ példát (Soloway)! A feladat az átlagos csapadék meghatározása. Programot kell írni, amely a felhasználótól bekéri a napi esõ adatokat és a végén kinyomtatja az átlagot. Az adatok végét egy speciális õrszem (sentinel) adat, a 99999 jelzi. Negatív csapadékértékek nem megengedettek. Tekintsük a következõ programot! program AverageRainfall1(input,output); var sum, rainfall, average : real; count : integer; begin {main program} sum:=0.0; count:=0; WriteLn(’Please input a rainfall’); ReadLn(rainfall); while rainfall<>99999 do begin while rainfall<0 do begin WriteLn(’Rainfall cannot be<0. Input again.’); ReadLn(rainfall) end; 60
sum:=sum+rainfall; count:=count+1; WriteLn(’Please input a rainfall’); ReadLn(rainfall) end; if count>0 then begin average:=sum/count; WriteLn(’Average rainfall=’, average:4:2) end else WriteLn(’No valid inputs. No average calculated.’) end{main program}. Ez a program hibás. A szerzõ túl sok mindent próbált egyszerre megoldani (lásd a (d) szabályt!). Ha elõször negatív értéket adunk be, akkor a belsõ ciklusba kerülhetünk, ahol beadhatjuk a sentinel értéket, de a program nem fog megállni. Tekintsük a következõ javított változatot! program AverageRainfall2(input,output); const sentinel=99999; var sum, rainfall : real; count : integer; function GetValidInputFromUser: real; var rainfall: real; begin Write(’Please input a rainfall:’); ReadLn(rainfall); while rainfall<0 do begin WriteLn(’Rainfall cannot be <0. Input again:’); ReadLn(rainfall); end{while}; GetValidInputFromUser:=rainfall; end{GetValidInputFromUser}; begin {main program} sum:=0.0; count:=0; rainfall:=GetValidInputFromUser; while rainfall<>sentinel do begin 61
sum:=sum+rainfall; count:=count+1; rainfall:=GetValidInputFromUser ReadLn(rainfall) end{while}; if count>0 then WriteLn(’Average rainfall=’, (sum/count):4:2) else begin WriteLn(’No valid inputs. No average calculated.’) end{if }; end{main program}. A programban egy szubrutin végzi a beolvasást. A fõprogram egy while szerkezet, amely nem felel meg a programozói logikának. Vizsgáljuk meg az alábbi két megoldás változatot is, az elsõnél feltételezve, hogy a ciklusban van egy exit lehetõség. loop rainfall:=GetValidInputFromUser; exit when (rainfall=sentinel); sum:=sum+rainfall; count=count+1; end{loop} repeat rainfall:=GetValidInputFromUser; if (rainfall<>sentinel) then begin sum:=sum+rainfall; count:=count+1 end{if } until(rainfall=sentinel) Értékelés: a repeat until szerkezet repetitív, felesleges mûveletet igányel és nem természetes. A loop exit szerkezet megßele a programozói pszichológiának. A programozási stílus elve: Egy projekt programozóinak bizonyos jól deÞniált programozási stílus elveket (konvenciókat) kell követniük. Ez segíti a munkát, mert .... Dokumentáció: A programozási feladat nagymértékben meghatározza. - User kézikönyv tömegeknek - Programozói kézikönyv fejlesztõknek, stb. - Elektronikus formák. 62
- Hipermédia rendszerek. - Már a programfejlesztésnél kell - az adatszerkezeteket, egység (modul) interfészeket dokumentálni - a szubrutinokat kommentálni (funkció, változók, input, output, extrém esetek, stb.). Tipikus problémák: 1. Formázott hibakeresõ üzenetek hiánya. 2. A szoftver rendszer dokumentációjának meg nem írása. 3. A felhasználói dokumentum ellenõrzésének elmulasztása. Hasznos javaslatok: 1. Használjunk mérést és tuningolást a program hatékonyságának növelésére. 2. A program dokumentációját a program stratégiák programmá való átírásával párhuzamosan végezzük. 3. Alkalmazzunk közös programozói stílus elemeket! 4. Teszteljünk és veriÞkáljunk!
63
