2008 tavasz

Programozási tételek [email protected] PPT 2007/2008 tavasz http://nik.bmf.hu/ppt 1

Témakörök Strukturált programozás paradigma Alapvető programozási tételek Összetett programozási tételek Programozási tételek összeépítése Feladatok megoldása tételek segítségével

2

Programfejlesztés folyamata • A PPT tárgy keretein belül a programfejlesztés folyamatából csak a tervezés lépéseivel foglalkozunk • Ennek célja a kitűzött feladatot megoldó algoritmus (program) megtervezése • Ezen a szinten implementációs kérdésekkel nem foglalkozunk, így konkrét nyelvi megvalósítás sem kerül szóba (bár értelemszerűen olyan megoldást részesítünk előnyben, ami illeszkedik a fejlesztés későbbi fázisaihoz) • További szintekre bontható – előzetes tervezés – architektúra – finom tervezés – algoritmusok

Analízis

Tervezés

Implementáció

Tesztelés 3

Relációalapú modell • Állapottér – Elemei tartalmazzák a lehetséges állapotokat – Ezek komponensei a modellezni kívánt jellemzők

• Feladat – Az állapottér minden pontjához hozzárendel egy vagy több pontot – Példáinkban általában azt feltételezzük, hogy csak egy pontot rendelünk hozzá – Nem feltétlenül determinisztikus, bár a gyakorlatban általában ezt feltételezzük

(1, 4, 2)

(1, 4, 1) (1, 4, 3)

(1, 5, 1)

(1, 5, 2)

(1, 5, 3) (2, 4, 1)

(2, 4, 2)

(2, 4, 3) (2, 5, 2)

(2, 5, 1) ( , , )

4

Relációalapú modell • Program – Időben dinamikus folyamat – Futását állapotok sorozataként tudjuk egyszerűen leírni – Az állapottér minden pontjához hozzárendel egy ilyen sorozatot – Működése nem feltétlenül determinisztikus

• Programfüggvény – A gyakorlatban a program futásának menete lényegtelen, csak a kiinduló és a vég állapot lényeges számunkra – Egy program „programfüggvénye” hozzárendeli a kiinduló állapothoz a vég állapotot (ha van ilyen)

(1, 4, 2)

(1, 4, 1) (1, 4, 3)

(1, 5, 1)

(1, 5, 2)

(1, 5, 3) (2, 4, 1)

(2, 4, 2)

(2, 4, 3) (2, 5, 2)

(2, 5, 1) ( , , )

5

Relációalapú modell • Feladat – programfüggvény – Látjuk, hogy a programfüggvény ugyanolyan típusú reláció, mint a feladat volt (az állapottér egy pontjához hozzárendelik az állapottér egy vagy több pontját) – Ennek segítségével egyszerű kapcsolatot teremthetünk egy adott feladat és egy adott program között

• Megoldás – Egy programot egy feladat megoldásának tekintjük, ha bármelyik lehetséges bemenethez a programfüggvény a feladat által meghatározott állapotokat rendeli (vagy annál szűkebb halmazt)

(1, 4, 2)

(1, 4, 1) (1, 4, 3)

(1, 5, 1)

(1, 5, 2)

(1, 5, 3) (2, 4, 1)

(2, 4, 2)

(2, 4, 3) (2, 5, 2)

(2, 5, 1) ( , , )

6

Struktúrált programozás paradigma • Struktúrált programnak tekintjük azokat a programokat, amelyek csak a megengedett elemi programokat tartalmazzák a megengedett programkonstrukciók alkalmazásával • Elemi programok – üres program – hibás program/törlődés – értékadás (állapot változtatás)

• Megengedett konstrukciók – szekvencia – elágazás – ciklus

• Bizonyítható, hogy a fenti szabályok megtartásával minden algoritmussal megoldható feladatra adható megoldás 7

Szekvencia • Egy programot közvetlenül egy másik után végzünk el (,)

S1

(,)

S2

(,)

• Jelölése struktogramban S1 S2 • Általunk használt pszeudokód S1 S2

8

Elágazás • Adott N darab feltétel–program páros, az igaz feltételekhez tartozó programok végrehajtása (,)

S1

(,) (,)

(,)

(,) S2

(,)

(,)

S1

(,)

S2

(,)

(,)

(,) ∞

(,)

• Gyakorlatban ennek csak egy egyszerűsítésével foglalkozunk, ahol N=2, és a feltételek diszjunktak • Jelölése struktogramban L S1 S2 • Általunk használt pszeudokód Ha L akkor S1 különben S2 Elágazás vége 9

Ciklus • Megadott feltétel teljesülése esetén egy program (ciklusmag) végrehajtása (L?) S

(,)

(L?) S

(,)

(L?) S

(,)

(L?) S

(,)

• Jelölése struktogramban L S • A programozási nyelvek általában többféle ciklust ismernek, ennek megfelelően a pszeudokódban is többfélét használunk: Ciklus amíg L S Ciklus vége

Ciklus S Ciklus amíg L

Ciklus i ← i0-től i1-ig S(i) Ciklus vége

• Mindhárom egyszerűen helyettesíthető az elsővel 10

Összetett feladatok megoldása Funkció-orientált programtervezés Levezetés

Analóg programozás

Analóg levezetés

Moduláris programozás

Visszavezetés

• Levezetés – A levezetés egy olyan módszer, amelyik a feladat megoldó programját lépésről lépésre alakítja át megengedett megoldássá, és ehhez a nevezetes programszerkezeteket használja fel – A feladat triviális megoldásából indulunk ki, és folyamatosan felbontjuk a strukturált programozásnál megismert szerkezetek segítségével. Véget ér, ha egy megengedett programhoz érünk – A levezetés menete biztosítja, hogy ez a program helyes lesz 11



Analóg levezetés


Visszavezetés

• Analóg programozás – A gyakorlatban általánosan használt technika – Alapja, hogy ha olyan feladatot kell megoldanunk, amelyhez hasonlóhoz rendelkezünk már megoldással, akkor az előző megoldás módosításával próbáljuk előállítani a programot – Ez nyilván számos megoldott feladat ismeretét igényli és nagy tapasztalatot, szakértelmet (gyakorlást)

12



Analóg levezetés


Visszavezetés

• Analóg levezetés – Az analóg programozási technikák jelentősen eltérhetnek egymástól aszerint, hogy milyen mértékben hagyatkoznak a már ismert megoldás levezetésére – Az analóg levezetés alapelve, hogy a megoldandó feladat levezetését átvizsgáljuk, és az ott hozott döntéseket az új levezetés során felülvizsgáljuk, esetenként átvesszük

13



Analóg levezetés


Visszavezetés

• Visszavezetés – Az analóg levezetéshez képest jelentős különbséget jelent, hogy ebben az esetben nem a mintaprogram előállítási folyamatait ismételjük meg, hanem magát a mintaprogramot adaptáljuk az új feladatnak megfelelően – Ez a technika kellő elővigyázatossággal a gyakorlatban jól használható – Ehhez természetesen szükség van már levezett mintaprogramok gyűjteményére → programozási tételek 14



Analóg levezetés


Visszavezetés

• Moduláris programozás – Összetett problémák esetén gyakran van arra szükség, hogy több programozási tételt használjunk – A teljes feladatot részekre bontjuk, majd ezeket a visszavezetés módszerével megoldjuk – Pl. programozási tételek egymásbaágyazása, egyéb program átalakítások

15


16

Programozási tételek • A programozási tételek jól megválasztott, egyszerű feladatok megoldásai – segítségükkel a gyakorlatban szükséges feladatok jelentős része megoldható – helyességük egyszerűen bizonyítható – használatuk célszerű, hiszen (mások által is) jól áttekinthető kódot eredményeznek

• Egy lehetséges csoportosításuk – – – –

egy sorozathoz egy értéket rendelő feladatok egy sorozathoz egy sorozatot rendelő feladatok egy sorozathoz több sorozatot rendelő feladatok több sorozathoz egy sorozatot rendelő feladatok

• Feldolgozandó intervallum alapján megkülönböztetünk – rögzített intervallumos programozási tételeket – feltételig tartó programozási tételeket (ezeket a változatokat nem tárgyaljuk) 17

Sorozatszámítás • A tétel pszeudokódja Eljárás Sorozatszámítás(A, N, R) R ← R0 Ciklus i ← 1-től N-ig R ← R művelet A[i] Ciklus vége Eljárás vége

• Megjegyzések – adatok sorozatához egy értéket rendelő függvényt helyettesít – minden olyan esetben használható, ha ezt a függvényt felbonthatjuk értékpárokon kiszámított függvények sorozatára – az induláskor használt nullértéket értelemszerűen a kérdéses függvény (esetleg a feladat) alapján kell megválasztani összegzés

faktoriális

elemek uniója

R0

0

1

{}

művelet

R ← R + A[i]

R ← R * A[i]

R ← R ∪ A[i] 18

Eldöntés • A tétel pszeudokódja Eljárás Eldöntés(A, N, VAN) i ← 1 Ciklus amíg (i ≤ N) és ¬(A[i] teljesíti T-t) i ← i + 1 Ciklus vége VAN ← (i ≤ N) Eljárás vége

• Megjegyzések – a T tulajdonság helyes megválasztásával a tétel sokféle szituációban alkalmazható – a „minden elem T tulajdonságú” feladatot egyszerűen visszavezethetjük az eldöntésre a T tulajdonság tagadásával – a sorozatszámításnál megismert módszerrel ellentétben ez az algoritmus az első T tulajdonságú elem megtalálása után már nem folytatja a keresést 19

Kiválasztás • A tétel pszeudokódja Eljárás Kiválasztás(A, N, SORSZ) i ← 1 Ciklus amíg ¬(A[i] teljesíti T-t) i ← i + 1 Ciklus vége SORSZ ← i Eljárás vége

• Megjegyzések – az eldöntéssel ellentétben ez visszaadja az első T tulajdonságú elem sorszámát – a tétel feltételezi, hogy biztosan van legalább egy ilyen tulajdonságú elem! – sorszám helyett visszaadhatjuk az elem értékét is, de célszerűbb a sorszám használata (ez alapján az elem is azonnal meghatározható) 20

Lineáris keresés • A tétel pszeudokódja Eljárás Keresés(A, N, VAN, SORSZ) i ← 1 Ciklus amíg (i ≤ N) és ¬(A[i] teljesíti T-t) i ← i + 1 Ciklus vége VAN ← (i ≤ N) Ha VAN akkor SORSZ ← i Eljárás vége

• Megjegyzések – tekinthető az eldöntés és a keresés tétel ötvözetének is: választ ad arra, hogy van-e T tulajdonságú elem a sorozatban, és ha van, akkor visszaadja a sorszámát is – értelemszerűen így nem feltételezi, hogy biztosan van ilyen elem a listában. ha nincs, akkor a VAN változó értéke hamis, ilyenkor a SORSZ mező nem kap értéket – rendezett lista esetén használható a már ismert logaritmikus keresés 21

Megszámlálás • A tétel pszeudokódja Eljárás Megszámlálás(A, N, DB) DB ← 0 Ciklus i ← 1-től N-ig Ha (A[i] teljesíti T-t) akkor DB ← DB + 1 Elágazás vége i ← i + 1 Ciklus vége Eljárás vége

• Megjegyzések – amennyiben nincs T tulajdonságú elem a listában, akkor értelemszerűen 0 kerül a DB változóba – valójában egy sorozatszámítás, amely minden T tulajdonságú elem esetén 1-et hozzáad a DB értékéhez

22

Maximumkiválasztás • A tétel pszeudokódja Eljárás Maximumkiválasztás(A, N, MAX) MAX ← 1 Ciklus i ← 2-től N-ig Ha A[i] > A[MAX] akkor MAX ← i Elágazás vége Ciklus vége Eljárás vége

• Megjegyzések – reláció megfordításával értelemszerűen minimumkiválasztás lesz a tétel célja – sorszám helyett visszaadhatjuk az elem értékét is, de célszerűbb a sorszám használata (ez alapján az elem is azonnal meghatározható) – feltételezzük, hogy legalább egy elem létezik a listában – több maximális elem esetén az elsőt adja vissza 23


24

Másolás • A tétel pszeudokódja Eljárás Másolás(X, N, Y) Ciklus i ← 1-től N-ig Y[i] ← művelet X[i] Ciklus vége Eljárás vége

• Megjegyzések – az eredmény mindig ugyanannyi elemszámú, mint a bemenet – a művelet segítségével az egyszerű másoláson túl az egyes elemekkel egy-egy elemi műveletet is el lehet végezni (pl. másoljuk át az abszolútértéküket) – nincs azonban lehetőség az elemek közötti összefüggésekre építeni

25

Kiválogatás • A tétel pszeudokódja Eljárás Kiválogatás(X, N, Y, DB) DB ← 0 Ciklus i ← 1-től N-ig Ha (X[i] teljesíti T-t) akkor DB ← DB + 1 Y[DB] ← X[i] Elágazás vége Ciklus vége Eljárás vége

• Megjegyzések – az X[i] helyett néha csak az i index értékét másoljuk az Y-ba – egyszerű módosítással megoldható, hogy nem másik listába, hanem az eredeti elemeket tartalmazó X lista elejére gyűjtjük a megfelelő elemeket – szintén gyakran használatos változat, ha csak megjelöljük az eredeti listában a megfelelő elemeket 26

Szétválogatás • A tétel pszeudokódja Eljárás Szétválogatás(X, N, Y, DBY, Z, DBZ) DBY ← 0; DBZ ← 0 Ciklus i ← 1-től N-ig Ha (X[i] teljesíti T-t) akkor DBY ← DBY + 1 Y[DBY] ← X[i] különben DBZ ← DBZ + 1 Z[DBZ] ← X[i] Elágazás vége Ciklus vége Eljárás vége

• Megjegyzések – egyszerűen megoldható, hogy csak egy sorozatba helyezzük át az elemeket (a T tulajdonságú elemek kerüljenek az elejére, a nem T tulajdonságúak pedig a végére) – érdemes átgondolni, hogyan lehetne egyszerűen megoldani a szétválogatást az eredeti sorozatban 27

Metszet • A tétel pszeudokódja Eljárás Metszet(X, N, Y, M, Z, DB) DB ← 0 Ciklus i ← 1-től N-ig j ← 1 Ciklus amíg (j ≤ M) és (X[i] ≠ Y[j]) j ← j + 1 Ciklus vége Ha j ≤ M akkor DB ← DB + 1 Z[DB] ← X[i] Elágazás vége Ciklus vége Eljárás vége

• Megjegyzések – felismerhető benne egy kiválogatás tételbe ágyazott eldöntés tétel kódja – gyakran nincs szükség az összes metszetbeli elemre, csak egy elemről kell eldönteni, hogy az benne van-e a metszetben 28

Egyesítés (unió) • A tétel pszeudokódja Eljárás Egyesítés(X, N, Y, M, Z, DB) Z ← X; DB ← N Ciklus i ← 1-től M-ig j ← 1 Ciklus amíg (j ≤ N) és (X[j] ≠ Y[i]) j ← j + 1 Ciklus vége Ha j > N akkor DB ← DB + 1 Z[DB] ← Y[i] Elágazás vége Ciklus vége Eljárás vége

• Megjegyzések – amennyiben a két lista rendezett, lehetőségünk van jóval hatékonyabb algoritmusok készítésére (összefuttatás, összefésülés) 29


30

Programozási tételek összeépítése • Összetettebb programok esetén szintén használhatjuk a programozási tételeket, ilyenkor gyakran szükség van az egymásbaépítésükre • Gyakori megvalósítások – tételek egymás után – tételek egymásba ágyazva – egyéb (optimalizált) megoldások

• Egy példa az összeépítésre (megszámolás-eldöntés) Eljárás SzámolásÉsEldöntés(N, X, K, VAN) i ← 1; DB ← 0 Ciklus amíg (i ≤ N) és (DB < K) Ha (A[i] teljesíti T-t) akkor DB ← DB + 1 Elágazás vége i ← i + 1 Ciklus vége VAN ← (DB = K) Eljárás vége 31

Példák tételek összeépítésére • Megszámolás-eldöntés – pl. egy N elemű sorozatban van-e legalább K darab T tulajdonságú elem?

• Megszámolás-kiválasztás – pl. hol van a K-adik T tulajdonságú elem?

• Megszámolás-keresés – pl. van-e K darab T tulajdonságú elem, és ha igen, hol található a sorozatban a K-adik?

• Maximumkiválasztás-megszámlálás – pl. hány darab maximális elem van a listában?

• Maximumkiválasztás-kiválogatás – pl. melyek a maximális elemek a listában? (értelemszerűen az indexeket várjuk)

32

Példák tételek összeépítésére • Kiválogatás-sorozatszámítás – pl. adjuk össze az összes T tulajdonságú elemet!

• Kiválogatás-maximumkiválasztás – pl. keressük meg a T tulajdonságú elemek közül a maximálisat!

• Kiválogatás-másolás – pl. másoljuk le a sorozat T tulajdonságú elemeit (esetleg végezzünk rajtuk valamilyen elemi műveletet is)!

• Másolás-sorozatszámítás – pl. adjuk meg a sorozat elemeinek négyzetösszegét!

• Másolás-maximumkiválasztás – pl. adjuk meg a sorozat elemei közül azt, amelyiknek maximális az abszolútértéke!

• Egyéb összeépítések 33


34

Néhány egyszerű példa • Egy N elemű sorozat Kmin és Kmax közötti számokat tartalmaz, határozzuk meg, hogy – – – –

van-e olyan szám, amelyik többször szerepel a sorozatban? hány szám szerepel többször is a sorozatban? melyik számból van a legtöbb a sorozatban? hány elemből áll a leghosszabb azonos számokból álló részsorozat? – adjon megoldást a fentiekre, amennyiben a sorozat rendezett! – adjon megoldást a fentiekre, amennyiben tetszőleges számok szerepelhetnek a sorozatban (Kmin, Kmax ismeretlen)!

• Egy NxM-es mátrix számokat tartalmaz, határozzuk meg, hogy – – – –

melyik sorban van a legtöbb 0? van-e olyan sor, amelyik csak 0-t tartalmaz? van-e két olyan sor, amelyek azonos számú 0-t tartalmaznak? a legtöbb nullát tartalmazó sorok közül adjuk meg azt, ahol a 0-tól eltérő számok összege a legnagyobb! 35

Javasolt/felhasznált irodalom • Fóthi Á.: Bevezetés a programozáshoz ELTE Eötvös Kiadó, 2005 • Pap, Szlávi, Zsakó: µlógia19 – Módszeres programozás: Programozási tételek ELTE TTK, 2002 • Gregorics Tibor: A programozás alapjai - Tervezés http://people.inf.elte.hu/gt

36

2008 tavasz

Recommend Documents