Programoz´asi m´odszertan 1. Alapfogalmak
Feldhoffer Gergely
2012
1
F´el´eves tananyag terve
Program helyess´eg´enek bizony´ıt´asa Reprezent´aci´ o Logikai-matematikai eszk¨ ozt´ar Programoz´asi t´etelek bizony´ıt´asa Levezet´es - visszavezet´es
Programhelyess´eg bizony´ıt´as´anak alternat´ıv formalizmusai Gyakorlatban haszn´alhat´ o eszk¨ oz¨ ok debug technik´ak (gdb haszn´alat) feh´er doboz tesztel´esi eszk¨ oz¨ ok (coverage) szimul´aci´ os seg´edeszk¨ oz¨ ok (valgrind)
´ A tananyag elm´eleti r´esz´et F´ othi Akos dolgozta ki, a di´akban nagyban felhaszn´alom Feh´er Tam´as jegyzet´et.
2
Jegyszerz´es
A f´el´ev sor´an a gyakorlati r´eszb˝ ol k´et ZH-t kell meg´ırni, egy elm´eleti pap´ırost, ´es egy g´eptermit. Az itt kapott ´ert´ekel´es az alapja az al´a´ır´asnak. A f´el´ev v´eg´en vizsg´azni kell. A tant´argyra kapott jegy a vizsg´an kapott jegy, a ZH eredm´enyeket szubjekt´ıven veszem figyelembe.
3
Jegyszerz´es
A f´el´ev sor´an a gyakorlati r´eszb˝ ol k´et ZH-t kell meg´ırni, egy elm´eleti pap´ırost, ´es egy g´eptermit. Az itt kapott ´ert´ekel´es az alapja az al´a´ır´asnak. A f´el´ev v´eg´en vizsg´azni kell. A tant´argyra kapott jegy a vizsg´an kapott jegy, a ZH eredm´enyeket szubjekt´ıven veszem figyelembe. Amennyiben a pap´ıros ZH eredm´enye elmarad a v´arakoz´ast´ol, a pluszm´ınusz ´ırat´as jog´at a f´el´ev m´asodik fel´ere fenntartom, rem´elj¨ uk erre nem ker¨ ul sor.
4
Mi az a program? A tov´abbiakban adunk egy olyan defin´ıci´ ot a programra, ami nem t¨ok´eletesen fedi az intuit´ıv program fogalmat, valahol az algoritmus ´es a program ´altal´anosan haszn´alt fogalmai k¨ oz´e poz´ıcion´alva Az algoritmus megold´asi menetet r¨ ogz´ıt, f¨ uggetlen¨ ul a reprezent´aci´ot´ol, implement´aci´ ot´ ol. A program ´altal´aban konkr´et algoritmus konkr´et reprezent´aci´oj´anak konkr´et implement´aci´ oja. Egy matematikai algoritmus p´eld´aul ´ert´ekes lehet akkor is, ha ´abr´azolhatatlanul nagy sz´amokra lehet csak levezetni az ´erdekes esetben – vagy egy v´egtelen sor n-edik r´esz¨ osszeg´enek pontos ´ert´eke is nehezen ´abr´azolhat´ o teljes pontoss´aggal. Az ´altalunk haszn´alt program defin´ıci´ ot u ´gy terjesztj¨ uk ki a hagyom´anyos program fogalomb´ ol, hogy megenged¨ unk a val´os´agban implement´alhatatlan t´ıpusokat, mint pl. N vagy R
´ Allapott´ er A program viselked´es´et az azt futtat´ o g´ep bels˝ o ´allapota szab´alyozza. Ezen ´allapot t¨ obb, egyes´evel t´ıpushoz rendelhet˝o v´altoz´o egy¨ uttese. P´eld´aul egy sz´am´ıt´ og´ep processzor´anak regisztereinek ´ert´ekei, a mem´ ori´aj´anak ¨ osszes ´ert´eke, a h´att´ert´arak ´es inputeszk¨oz¨okb˝ol sz´armaz´ o adat egy¨ utt lefedi azt a k¨ort, ami egy program k¨ovetkez˝o l´ep´es´et meghat´arozza. Mivel ez kezelhetetlen¨ ul nagy dimenzionalit´as, illetve a t´ıpusoss´ag el˝onyeit nem tartalmazza, a bizony´ıt´as sor´an megel´egsz¨ unk a program ´altal haszn´alt v´altoz´ ok gy˝ ujtem´eny´evel. Ezek direktszorzata az ´allapott´er: ´ Def (Allapott´ er) Legyenek A1 , A2 , . . . , An tetsz˝ oleges v´eges, vagy megsz´aml´alhat´o nem u ¨res halmazok. Ekkor az A = A1 × A2 × · · · × An halmazt ´ allapott´ ernek, az Ai halmazokat pedig t´ıpus´ ert´ ekhalmazoknak nevezz¨ uk. 6
A feladat fogalma
A feladat az ´allapott´er valamely pontj´ar´ ol (input) eljutni a megfelel˝o pontba (eredm´eny), vagyis Def (Feladat) Feladatnak nevezz¨ uk az F ⊆ A × A rel´aci´ ot. Vegy¨ uk ´eszre, hogy nem k¨otj¨ uk ki, hogy minden kezdeti ´allapotr´ ol rendelkezzen a feladat nem csak egyetlen j´ o megold´ast rendelhet a feladat az inputhoz
7
A feladat fogalma
P´eld´aul az ¨osszead´as feladata a k¨ ovetkez˝ o:
A=Z×Z×Z F = {((a, b, c), (d, e, f ))|f = a + b}
Amennyiben az ¨osszead´ast´ ol elv´arjuk, hogy megtartsa a bemen˝o param´eterek ´ert´ek´et, akkor F = {((a, b, c), (d, e, f ))|f = a + b ∧ d = a ∧ e = b}
8
Az ´allapott´erbeli pontok sorozatai Egy program az azt futtat´ o g´ep mem´ ori´aj´at folyamatosan v´altoztatja. Ez az ´allapott´er sokdimenzi´ os ter´eben egy pontsorozatk´ent foghat´ o fel: minden id˝ opillanatban az ´allapott´ert egy adott pontj´aban vagyunk, ´es ahogy az id˝ o telik, megv´altozik valamelyik v´altoz´onk ´ert´eke, ugrunk a k¨ ovetkez˝ o ´allapotba. Jel¨olj¨ uk A∗ -gal az A halmaz elemeib˝ ol k´epzett v´eges sorozatokat, ∞ ∗∗ A -vel a v´egtelen sorozatokat, A legyen A∗ ∪ A∞ . Jel¨olje red(α) egy α ∈ A∗∗ sorozat reduk´ altj´at, ha β = red(α) u ´gy kaphat´o α sorozatb´ol, hogy minden v´eges hossz´ u azonos ´allapotokb´ol ´all´o r´eszsorozatot egyetlen elemre r¨ ovid´ıt¨ unk. Jel¨olje τ (α) egy α ∈ A∗ v´eges sorozat utols´ o elem´et, azaz ha α =< a1 a2 . . . an > akkor τ (α) = an .
A program fogalma
Def (Program) Programnak nevezz¨ uk az S ⊆ A × A∗∗ rel´aci´ ot, ha 1
DS = A
2
∀a ∈ A : ∀α ∈ S(a) : α1 = a
3
∀α ∈ RS : α = red(α)
Azaz 1
A program minden lehets´eges kezdeti ´allapotb´ol elindul.
2
Minden a elemhez rendelt α sorozat els˝ o eleme az a, kezdeti ´allapot.
3
A programban minden l´ep´essorozat reduk´alt
A Program tulajdons´agai
Ha egy α ∈ RS elemei k¨ oz¨ ott k´et egym´ast k¨ ovet˝ o ´allapot egyforma, akkor garant´altan v´egtelenszer ugyanaz az ´allapot fog ism´etl˝odni a reduk´alts´ag miatt
Egy a ∈ A kezdeti ´allapothoz rendelhet t¨ obb A∗∗ -beli elemet is a program, ilyenkor a program nemdeterminisztikus. M´as szavakkal a program determinisztikus, ha ∀a ∈ A : |S(a)| = 1. A nemdeterminisztikus program m˝ uk¨ od´es´et u ´gy kell tekinteni, hogy a lehets´eges utak k¨oz¨ ul b´armelyiket v´alaszthatja.
Programf¨uggv´eny
Def (Programf¨ uggv´eny) A p(S) ⊆ A × A rel´aci´ o az S ⊆ A × A∗∗ program programf¨ uggv´ enye, ha 1
Dp(S) = {a ∈ A|S(a) ⊆ A∗ }
2
p(S)(a) = {b ∈ A|∃α ∈ S(a) : τ (α) = b}
Azaz 1
A programf¨ uggv´eny ´ertelmez´esi tartom´anya az ´allapott´er azon elemeit tartalmazza, amelyekre a program termin´al
2
determinisztikus program eset´eben a v´eg´allapotb´ol ´all´o egy elem˝ u halmazt, nemdeterminisztikus esetben a lehets´eges v´eg´allapotok halmaz´at rendeli a kezdeti ´allapothoz
12
Megold´as
Def (Megold´as) Azt modjuk, hogy as S program megoldja az F feladatot, ha 1
DF ⊆ Dp(S) ,
2
∀a ∈ DF : p(S)(a) ⊆ F (a).
Azaz 1
A feledatban meghat´arozott pontokb´ ol a program termin´al
2
A program lefut´asa ut´an a v´eg´allapot csak olyan elem lehessen, amit a feladat hozz´arendelt a kezdeti ´allapothoz.
Megold´as
A program viselked´es´et nem szab´alyozza a DF -en k´ıv¨ uli ´allapotokra a feladat, ezen pontokban tetsz˝ oleges viselked´es mellett megoldhatja a program az F feladatot
Determinisztikus program eset´eben a szakirodalom n´eha haszn´alja azt a megold´asdefin´ıci´ ot, ahol a ∀a ∈ DF : p(S)(a) ∈ F (a) felt´etel szerepel.
14
Alapfogalmak o¨sszefoglal´o Az ´allapott´er le´ırja, hogy milyen lehets´eges ´allapotokat ´erinthet a program a fut´asa sor´an A feladat megadja, hogy mely pontokb´ ol mik az elfogadhat´o eredm´enyek A program minden kezdeti ´allapotb´ ol indul´ o, id˝ oben ´allapotok k¨oz¨ott ugr´al´o folyamat, amit sorozatok form´aj´aban kezel¨ unk Azok ezek a sorozatok v´eget ´ernek, ott van eredm´eny, ezeket az ´ert´ekeket rendeli a programf¨ uggv´eny a kezdeti ´allapotokhoz A program akkor oldja meg a feladatot, ha minden olyan pontb´ol, amir˝ol a feladat rendelkezik, a megengedett megold´asok egyik´eben ´allhat csak meg 15
