Programozási Módszertan – definíciók, stb. 1. Bevezetés Egy adat típusát az adat által felvehető lehetséges értékek halmaza (típusérték‐halmaz, TÉH), és az ezen értelmezett műveletek (típusműveletek) együttesen határozzák meg (vagy más szóval – specifikálják). Természetes szám típus (
0,
( ); Karakter típus ( , műv:
); Egész szám típus ( , (x),
+
,
‐
); Valós szám ( ,
+
, ‐); Logikai típus
(x)); Halmaz típus (TÉ: véges elemszámú halmazok E
alaphalmazból, ez fölött: 2E); Sorozat típus (TÉ: véges sorozatok, E alaphalmazból: E*, műv: |s|, si); Vektor típus, 1D tömb (véges sorozatok n‐től m‐ig cimkézve E alaphalmazból: Enm=1); Mátrix típus (azonos méretű téglalapba rendezett elem‐együttesek E elemi halmaz fölött: Emxnkxl=1x1)...
Állapottér (ÁT): Legyenek A1,A2,… ,An tetszőleges véges vagy megszámlálható nem üres halmazok: ezek a típusértékhalmazok (TÉH). Rendeljük hozzájuk egyértelmű módon a páronként különböző c1, ... , cn címkéket. Ekkor a {{c1: a1, ... , cn: an} | ai ∈ Ai (i= 1,...,n)} halmazt az A1,A2, ... ,An TÉH‐okból képzett állapottérnek nevezzük, amit a továbbiakban a (c1: A1, ... , cn: An) szimbólummal jelölünk. Ha a cimkéknek rögzítjük a sorrendjét, akkor az A= A1×A2×...×An halmazt (Descart szorzatot) is állapottérnek nevezzük.
Állapotok: az ÁT elemei. Ezek maguk is halmazt alkotnak: a cimkézett értékek halmazát. Feladatnak nevezzük az F ⊆ A×A relációt. Az F reláció ÉT‐a (
kezdőállapotait jelöli ki. Egy adott ∈
F) a feladat
F‐re az F(
) képhalmaz az
kezdőállapothoz tartozó célállapotokat tartalmazza.
A**: az A halmaz elemeiből képzett összes (véges és végtelen hosszú) sorozatot tartalmazóhalmaz A∞: a végtelen hosszúsorozatok halmaza red(α): az α sorozat redukáltja (azaz az eredeti sorozat minden azonos elemekből álló részsorozatát az ismétlődő egyetlen elemmel helyettesítjük)
τ (α): a véges sorozat utolsó eleme Program: az S⊆A×A** reláció, ha n
S = A o ∀
∈A: ∀α∈S( ) : α1=
p∀α∈ S: α = red(α).
Programfüggvény, (hatásreláció): p(S) ⊆ A×A reláció az S ⊆ A×A** program PrFv‐e, ha: n Dp(S)= { ∈A | S( )∈A*} o∀ ∈ Dp(S) | p(S)(a) = { b∈A |∃α∈S( ) : ( ) = b }.
Megoldás: Az S program megoldja az F feladatot, ha n
1
F ⊆
p(S) o ∀
∈
F: p(S)(
) ⊆ F( ).
:megoldás
LGyEF:
Leggyengébb előfeltétel: Legyen S⊆A×A** program, R: A→
állítás. Ekkor az S program R
utófeltételhez tartozó LGyEF‐e az az állítás, amelyre:⌠ (S, R)⌡= { ∈
p(S) | p(S)(
) ⊆ ⌠R⌡}.
A leggyengébb előfeltétel tehát pontosan azokban a pontokban igaz, ahonnét kiindulva az S program biztosan terminál, és az összes lehetséges végállapotra igaz R.
Néhány fontos tulajdonság: Legyen S⊆A ×A** program, R1, R2: A →
állítások. Ekkor:
n. (S, HAMIS) = HAMIS (a csoda kizárásának elve) o. Ha R1ÖR2, akkor (S, R1) Ö (S, R2) (monotonitási tulajdonság) p. (S, R1) ^ (S, R2) = (S, R1^R2) q. (S, R1) v (S, R2) Ö (S, R1 v R2)
A feladat specifikációja: Általában a feladat nem függ az ÁT összes komponensétől, azaz az ÁT több pontjához is ugyanazt rendeli. Ezeket a pontokat fogjuk össze egy ponttá a paramétertér segítségével.
Paraméter: Legyen F ⊆ A ×A feladat. A B halmazt a feladat pm‐ének nevezzük, ha van olyan F1 és F2 reláció, hogy n F1 ⊆ A ×B o F2 ⊆ B ×A p F = F2○F1 , ahol ○ az ún. reláció kompozicióművelet.
Specifikáció tétele: Legyen F A×A feladat, B az F egy paramétertere, F1 Jelölje
A×B, F2 B×A, F=F2○F1. B, és definiáljuk a következő állításokat az F feladat Qb előfeltételére, ill. Rb utófeltételére):
n ⌠Qb ⌡= { o ⌠Rb⌡= { Ekkor ha
A | ( , ) F1} = F1(‐1)( ) A | ( , ) F2} = F2( ) B: QbÖ (S,Rb), akkor az S program megoldja az F feladatot.
2. Elemi programok Elemi program: egy A állapottéren egy S program, ha: ∀ ∈A : S( ) ⊆ {< >,< , , ,...>,< , > | ≠ }. Üres program, SKIP: nem csinál semmit: ∀ ∈A : SKIP( ) = {< >}. Rossz program, „törlődés”, ABORT: soha sem terminál: ∀ ∈A : ABORT( ) = {< , , , ... >}. Értékadás (ÉA): programváltozó (~az akt. állapot egy komponense) új értéket kap (~megváltozik). Új állapot: ezzel az egy komponenssel tér el az előző állapottól. Az ÁT‐en 1 lépést: 2 állapotból álló végrehajtási sorozatot eredményez. ÉA: S program, ami az ÁT bármelyik állapotához a belőle kiinduló 2elemű állapotsorozatot rendeli. 2
Szimultán ÉA: Egy időben több változónak is új értéket adunk (állapotkülönbség több komponensű…) Egyszerű ÉA: csak egy változó értékét változtatja meg. Értékkiválasztás: az ÉA nem‐determinisztikus. Jelölés: :∈ F( ) („legyen eleme”) Értékadás: az F reláció függvény determinisztikus. Jelölés: := F( ) („legyen egyenlő”) Parciális értékkiválasztás: Parciális ÉA:
F ⊂ A és az ÉA nem‐determinisztikus.
F ⊂ A és az F determinisztikus (F parciális függvény)
Általános ÉA: Legyen A = A1 × . . . × An, F = (F1, . . . , Fn), ahol Fi ⊆ A×Ai. Az S program általános értékadás, ha: n
n
i =1
i =1
S = { ( , red(< , >)) | , ∈A ^ ∈ I DFi ^ ∈F( ) } ∪ { ( ,< , , ,...>) | ∈A ^ ∉I DFi }. Elemi pr.‐ok programfüggvénye: n p(SKIP)=idA, o p(ABORT)=∅, p p( :=F( )) = F, p( :∈F( )) = F. El.pr.‐ok LGyEF‐e: n (SKIP,R) = R ; o (ABORT,R) = hamis ; p ÉA‐ok: ‐ F:A→A globális fv: ⌠ ( :=F( ),R)⌡= { ∈A|F( )⊆⌠R⌡} = F(−1)(⌠R⌡)=⌠R○F⌡ ‐ F: parciális fv: ⌠ ( :=F( ),R)⌡= { ∈A|F( )⊆⌠R⌡}
F = F
(−1)
(⌠R⌡)
F
3. Programkonstrukciók ?2: α∈A* és β∈A**. 2(α, β) = red( kon(α, β) ). Szekvencia: Legyenek S1, S2 ⊆ A×A** programok. Az S⊆A×A** relációt az S1 és S2 szekvenciájának nevezzük, és (S1; S2)‐vel jelöljük, ha
∀ ∈A: S( ) = { α∈A∞ | α∈S1( ) } ∪ {
Elágazás: Legyenek π1, ..., πn : A→
2(α, β)∈A
**
| α∈S1( ) ∩ A* ^ β∈S2(τ(α)) }. **
feltételek, S1, ..., Sn programok An. Ekkor az IF ⊆ A × A relációt
az Si‐kből képzett πi ‐k által meghatározott elágazásnak nevezzük és (π1:S1, ..., πn:Sn)‐el jelöljük, ha ∀ ∈A: n
IF( ) = U i( )∪ 0( ) – ahol ∀ ∈[1.. ]: i =1
?n: α1,…,αn‐1 ∈A* és αn∈A**. n(α1,…,αn) = red( kon(α1,…,αn) ). ?∞: α ∈A* ( ∈ ).
1 2 1 2 ∞(α ,α ,…) = red( kon(α ,α ,…) ).
3
Ciklus: Legyen π feltétel és S0 program A‐n. A DO ⊆ A×A** relációt az S0‐ból a π feltétellel képzett ciklusnak nevezzük, és (π , S0)‐lal jelöljük, ha n ∀ ∉⌠π⌡: DO( ) = {< >} , és o ∀ ∈⌠π⌡:
{ α∈A** | ∃ α1, …, αn ∈A** : α=
1 n 1 n(α , …, α ) ^ α ∈S0(
) ^ ∀ ∈[1.. ‐1]:(αi∈A* ^ αi+1∈S0(τ(αi)) ^
π(τ(αi))) ^ (αn∈A∞ v (αn∈A* ^ ¬π(τ(αn)) )) } ∪ { α∈A∞ |∀ ∈ :∃αi∈A*: α=
1 2 ∞(α ,α ,…) ^
α1∈S0( ) ^ αi+1∈S0(τ(αi)) ^ π(τ(αi)) }.
Levezetési szabályok: Szekvencia lev.sz.: Legyen S = (S1; S2), és adott Q, R és Q' állítás A‐n. Ha n QÖ (S1,Q') és o Q'Ö (S2,R) akkor: Q Ö (S, R).
Elágazás lev.sz.: Legyen IF =(π1:S1, ..., πn:Sn), és adott Q, R állítás A‐n. Ha n
, és
o ∀ ∈[1.. ]: Q ^ πi Ö (Si, R), akkor: Q Ö (IF, R). Ciklus lev.sz.: Legyen DO =(π, S0), és adott I (invariáns), Q, R állítás A‐n, valamint t:A→ (termináló) függvény. Ha: n Q Ö I ; o I^π Ö (S0,I) ; p I^¬π ÖR ; q I^π Öt>0 ; r I^π^t=t0 Ö (S0, t
4. Levezetés Megengedett program: az üres program; a megengedett F relációjú :∈F(
) értékadás; valamint a
szekvencia, a megengedett feltételeket használó elágazás és a megengedett ciklusfeltételű ciklus programszerkezeteinek segítségével az üres programból és megengedett értékadásokból felépített program.
Megengedett elemek: n megengedett típusok (bevezetett és kiegészített) ; o megengedett relációk (+eng. típ.műveletek kompoz.‐jával) ; p megengedett értékadás ( :∈F( )‐ban F +eng.) ; q megengedett feltételek (+eng. műv. log.kif.) A programtervezés célja az, hogy egy feladatot egy megengedett programmal oldjunk meg. Ha a triviális megoldás nem megengedett, részfeladatokra kell bontani, finomítani, újra részletezni, amíg csupa +eng. nem lesz.
Finomítás: Egy (rész)FA.‐ot triviálisan megoldó nem‐megengedett ÉA‐t: n vagy egy bonyolultabb szerkezetű programmal helyettesítjük (procedurális programtervezés) ; o vagy pedig az ÉA. jobboldali kifejezésének kiszámításánál használt, nem +eng. típusműveleteket valósítjuk meg (típus‐orientális programtervezés).
Procedurális programtervezés: n Levezetés: top‐down módszer; a feladatból (azaz a triviálisan megoldó nem‐megengedett értékadásból) indulunk ki, és azt a programszerkezetek levezetési szabályainak segítségével bontjuk részfeladatokra.
4
o Visszavezetés: korábbi megoldás (minta) alapján, azaz analóg módon oldjuk meg; a mintafeladat és az új feladat eltéréseit a mintaprogram megoldására átvezetjük. példák…
5. Visszavezetés Analóg programozás: Ha egy FA. megoldását egy hozzá hasonló, már korábban megoldott FA. megoldása alapján, a két FA. hasonlóságára építve készítjük el, ezt analóg programozásnak nevezzük. Ez sokféle módon valósulhat meg. n Analóg levezetés: A mintafeladatot megoldó program előállítási folyamatát másoljuk le az adott feladat levezetésének elkészítéséhez; azaz egy “kitaposott út” mentén hozott korábbi döntéseket (mi legyen a programszerkezet, a ciklus‐invariáns, stb.) kölcsönözzük. o Analóg visszavezetés: Közvetlenül a mintafeladatot megoldó programot – nem pedig előállításának folyamatát – használjuk fel; azaz a mintaprogramot módosítjuk a kitűzött és a mintafeladat közötti különbségek alapján.
Összegzés: Legyen adott az
:
→
függvény. Feladatunk az, hogy egy adott [ .. ] ⊆ intervallumban
összegezzük az függvény értékeit.: A = ( :
, :
, :
) Q = ( = ‘ ^ = ‘) R = (Q ^ =
) Bővítsük ki az állapotteret k komponenssel: A' = ( : , : , : , : ) Ekkor az invariáns: I = (Q ^ ∈[ .. +1] ^ =
)
Az összegzés programozási tétele:
A levezetési szabályok vizsgálata: n Q Ö I – Ez nem teljesül, csak ha egy értékadást (k, s := m, 0) beteszünk a ciklus elé:
o I^¬π ÖR
Q Ö ( , := , 0, I) =(Q ^ ∈[ .. +1] ^ 0 =
)
– Ebből meghatározhatjuk a ciklus feltételét: ¬π = ( ‐1 = ), azaz π = ( ≠ +1)
p I^π Öt>0 – Legyen = – +1; ez pozitív lesz P és π miatt. q I^π ^ = 0 Ö (S0, < 0) – A ciklusmag csökkenti a terminálófüggvényt, ha növeli értékét ( := +1).
r I^π Ö (S0,I)
I^π ^ ‐ +1= 0 Ö ( := +1, – +1< 0) = – < 0
– Vizsgáljuk meg I leggyengébb feltételét, ha (k := k+1)‐et végrehajtjuk. ( := +1, I) =
(Q ^ +1∈[ .. +1] ^ =
) = Q‘.Kell még egy utasítás ( := + ( )) a ciklusmagba:
I ^π Ö ( := + ( ), Q‘ ) = (Q ^ ∈[ .. +1] ^ + ( )=
példák – analóg levezetéssel, visszavezetéssel, behelyettesítéssel…
5
)
6. Programozási tételek Számlálás: Adott egy β: [m..n]→
feltétel. Határozzuk meg, hogy az [m..n] ⊆
intervallumon a β feltétel hányszor veszi fel az
értéket. Levezetése: Æ
Kibővítjük az ÁT.‐ünket:
Így az invariáns:
Analóg levezetéshez az összegzés használható.
Maximumkeresés: Adott egy
: [ .. ]→
függvény, amelynek értékkészletén definiáltunk egy teljes
rendezési relációt. Határozzuk meg, hogy az függvény hol veszi fel az [ .. ]⊆ nem üres intervallumon a legnagyobb értéket, és mondjuk meg, mekkora ez a maximális érték! _ ÁT‐et kibővítjük egy komponenssel. Az invariáns: Itt nem engedjük meg az üres intervallumot (mint az előbb), mivel nincs értelme annak maximumát keresni.
Lineáris keresés: Adott az β: [
.. ]→
feltétel.
Keressük meg az [ .. ]⊆ intervallumban balról az első olyan számot, amely kielégíti a β feltételt! Most nincs szükség állapottérbővítésre, az
változó megteszi. Az invariáns:
6
Kiválasztás: Adott az β:
→
feltétel, valamint egy egész szám. Keressük meg
az számtól jobbra eső (az ‐et is beleértve) az első olyan számot, amely kielégíti a β feltételt, ha tudjuk, hogy van ilyen szám! (Ez egy spec. keresés.) Az invariáns:
Feltételes maximumkeresés: Adott egy
: [ .. ]→
függvény, amelynek értékkészletén
definiáltunk egy teljes rendezési relációt és adott egy β: [ .. ]→
feltétel. Határozzuk meg, hogy az
függvény hol veszi fel az [ .. ] ⊆ intervallum β‐t kielégítő elemei közül a legnagyobb értéket, és mondjuk meg, mekkora ez a maximális érték!
Feltétel fennállásáig tartó keresés: Adott egy
egész szám, és egy olyan δ: →
az egészek számegyenesén ‐től jobbra valahol biztosan felvesz egy ‐től jobbra értelmezve egy β : →
feltétel, amely
értéket. Legyen az egész számokon
feltétel. Keressük meg az számtól jobbra eső (az ‐et is beleértve)
az első olyan számot, amely kielégíti a β feltételt azon az [ .. ] intervallumon, ahol∀ ∈ [ .. ]:δ( ), de ¬δ( +1) teljesül!
Kibővitjük az állapotteret egy : komponenssel, amely mindaddig értékű lesz, amig az ‐től jobbfelé haladva csak olyan számokkal találkozunk, amelyekre a δ feltétel teljesül.
7
