A programozás alapfogalmai

A programozás alapfogalmai

Ahhoz, hogy a programozásról beszélhessünk, definiálnunk kell, hogy mit értünk a programozás egyes fogalmain. Ha belegondolunk, nem is olyan könny˝u megfogalmazni, mi is az a program, vagy hogy mikor old meg egy program egy feladatot. Amikor programot írunk, általában egy a külvilágban adott feladatot akarunk számítógéppel megoldani. Ehhez kiválasztjuk a külvilág azon elemeit, amelyek kapcsolódnak a feladathoz, és megpróbáljuk elkészíteni ezeknek az elemeknek egy számítógépes modelljét. Ám a számítógépek változnak! Ezért a továbbiakban bevezetünk egy absztrakt modellt, amelyben leírjuk azokat fogalmakat, amelyek a programozás során el˝okerülnek, és e modell segítségével a gyakorlatban használható eszközöket adunk.

2.1. Az állapottér fogalma Az els˝oként bevezetendo˝ absztrakt fogalom tulajdonképpen a számítógép memóriájának ad egy a továbbiakban kényelmesen használható megfelel˝ot. 1. DEFINÍCIÓ : Á LLAPOTTÉR Legyenek

   
 tetsz˝oleges véges vagy megszámlálható nem üres halmazok. Ekkor az


  
 halmazt állapottérnek, az
 halmazokat pedig típusértékhalmazoknak nevezzük. Amikor egy modellt készítünk, el kell döntenünk, hogy a valóság mely részét kívánjuk modellezni, és melyek azok a jellemz˝ok – és milyen értékeket vehetnek fel – amiket a modellünkben figyelembe akarunk venni. 19

20

2. A PROGRAMOZÁS ALAPFOGALMAI

Az állapottér fenti definíciójában az egyes komponenseket tekintsük úgy, mint egyes jellemz˝ok lehetséges értékeinek halmazát. A típusértékhalmaz elnevezés arra utal, hogy ezek a halmazok bizonyos közös tulajdonsággal rendelkez˝o elemekbo˝ l állnak. A kés˝obbiekben majd kitérünk arra is, hogy ez a közös tulajdonság mit is jelent. Mivel a jellemz˝ok értékhalmaza lehet azonos, az állapottér komponensei között egy halmaz többször is szerepelhet.

2.2. A feladat Az állapottér fogalmának segítségével könnyen megfogalmazhatjuk, hogy mit értünk programozási feladaton. Azt kell megfogalmaznunk, hogy a memória egy adott állapotából (azaz az állapottér egy pontjából) milyen memóriaállapotba (azaz az állapottér mely pontjába) akarunk eljutni. 2. DEFINÍCIÓ : F ELADAT Feladatnak nevezzük az 

relációt. A feladat fenti definíciója, ha belegondolunk, természetes módon adódik, hiszen a feladatot legegyszeru˝ bben úgy formalizálhatjuk, ha a feladatot egy leképezésnek tekintjük az állapottéren, és az állapottér minden pontjára megmondjuk, hogy hova kell bel˝ole eljutni. Az, hogy egy feladatnak mi lesz az állapottere, természetesen magától a feladattól függ, ám még a feladat ismeretében sem egyértelmu˝ . Például egy pont síkbeli koordinátáit megadhatjuk a derészögu˝ koordináta-rendszerben, de megadhatjuk polárkoordinátákkal is. Mégis, az, hogy mit választunk állapottérnek, nagyon fontos dolog, hiszen meghatározza, hogy a továbbiakban mit, és hogyan tudunk leírni. Ha túl kevés jellemz˝ot vizsgálunk – azaz az állapottér túl kevés komponensb o˝ l áll – akkor lehetnek olyan fogalmak, amiket nem tudunk benne leírni, ha túl sok a komponens, akkor túl bonyolult lesz a modell.

2.3. A program Ha a gyakorlatban azt mondjuk, egy program fut, akkor amögött azt értjük, hogy a számítógép memóriájának tartalma folyamatosan változik. A programfutás tehát egy id˝oben dinamikus folyamat. Vezessünk be egy könynyebben kezelhet˝o statikus modellt! Hogyan kaphatunk egy ilyen statikus modellt? Tekintsük például az alábbi – a programozástól igazán messze es˝o – problémát: Adott egy kémiai kísérlet, amely túl gyorsan játszódik le ahhoz, hogy az ember pontosan regisztrálni tudja az egymásutáni eseményeket. Ez a programfutáshoz hasonlóan egy id˝oben dinamikusan lejátszódó folyamat. Hogyan követhet˝o nyomon mégis a kísérlet? Például úgy, hogy a kísérletet filmre vesszük, és a továbbiakban a képkockák által rögzített statikus állapotokat vizsgáljuk. Így az id˝oben változó folyamatot egy statikus állapotsorozattal írjuk le.

21

2.4. A PROGRAMFÜGGVÉNY

A fenti példa szemléletesen mutatja, hogyan adhatunk statikus modellt egy dinamikus folyamat leírására. A program definíciójában a program id˝obeni futásának jellemzésére az el˝obbi páldával analóg módon vezetünk be egy statikus modellt: a futást állapottérbeli sorozatokkal írjuk le. Ahogy a program futása során a memóriatartalom változik, úgy jutunk az állapottér újabb és újabb pontjaiba, így ezeket a pontokat egy sorozatba f˝uzve valójában "filmre vesszük" a programfutást. 3. DEFINÍCIÓ : P ROGRAM Programnak nevezzük az  1. $&%'
, 2. (*)+,
.-/(102+3546)87-90  3. (*02+;:;%<- 0=?>@BAC4D0E7 .


!
"#" )

relációt, ha

,

Az absztrakt program értékkészlete olyan sorozatokat tartalmaz, amelyek a konkrét program egy végrehajtását jellemzik. A fenti megszorítások értelemszeru˝ ek: az els˝o azt kívánja meg, hogy a program futását jellemz˝o sorozat abból a pontból induljon el, amihez hozzárendeltük. A programnak tetsz˝oleges állapotból el kell indulnia, hiszen egy program és annak sincs értelme, hogy a program egy állapotban egymás után véges sokszor lehessen (a program áll?).

2.4. A programfüggvény Ahhoz, hogy egy program és egy feladat viszonyát megvizsgáljuk, elegendo˝ , ha a programról tudjuk, hogy az állapottér egy adott pontjából kiindulva, az állapottér mely pontjába jut, mert a megoldás szempontjából a közbülso˝ állapotok lényegtelenek. Természetesen vannak olyan – a programok min˝oségére vonatkozó – további kritériumok, amelyek szempontjából egyáltalán nem mindegy, hogy a program hogyan oldja meg a feladatot (ilyen lehet például a hatékonyság, program id˝o- és tárigénye), de mi a továbbiakban ezekkel egyel˝ore nem foglalkozunk. Ezért vezetjük be a programfüggvény fogalmát, amely tehát csak a program futásának eredményét jellemzi. 4. DEFINÍCIÓ : P ROGRAMFÜGGVÉNY A FG4HI7J
!
reláció az J

"#" program programfüggvénye, ha 1. $KL %NM OB)P+
!QB54D)R7SJ
"UT , 2. FV46I74D)R7I!OW+<
!Q XY0Z+<54D)R7S-U[\460V7?W T . Az els˝o követelmény azt fogalmazza meg, hogy csak azokban a pontokban van értelme azt vizsgálni, hogy hova jut egy program, ahonnét kiindulva a program nem "száll el". A második pont értelemszeru˝ en azt írja le, hogy ahova a program eljut, az a sorozat utolsó eleme. A programfüggvény elnevezés megtéveszt˝o lehet, hiszen egy program programfüggvénye nem feltétlenül függvény, s˝ot az sem biztos, hogy determinisztikus reláció

22

2. A PROGRAMOZÁS ALAPFOGALMAI

(parciális függvény). Történeti megfontolások alapján azonban mégis megtartottuk ezt az elnevezést.

2.5. Megoldás Vegyük észre, hogy a programfüggvény ugyanolyan típusú reláció mint a feladat volt. Így tehát a programfüggvény fogalmának bevezetésével lehet˝oségünk nyílik arra, hogy kapcsolatot teremtsünk egy adott feladat és egy adott program között. Természetesen ennek a kapcsolatnak azt kell leírnia, hogy mikor mondjuk egy programról azt, hogy megold egy adott feladatot. 5. DEFINÍCIÓ : M EGOLDÁS Azt mondjuk, hogy az  program megoldja az  feladatot, ha 1. $^]$K/L %9M , 2. (1)+,$ ] -_FG4HI7_46)8754D)R7 . Ezzel a definícióval végül is azt kívánjuk meg, hogy az állapottér olyan pontjaihoz, ahol a feladat értelmezve van, a program csak véges sorozatokat rendeljen (termináljon) és a sorozatok végpontjait a feladat hozzárendelje a kezd˝oponthoz.

$KL %NM

4D)R7 FV46I74D)R7

) $ ]





2.1. ábra. Megoldás

2.6. Példák 1. példa: Legyen
`ONa #b

T 1
O9a9b T c
d!ONa #bRfegihcj T Y
kl
*
G
d . mnO84i4D)C#W/fo7_ 46Ag@9#p*7i7^QCp!q)Pr`W T g4sa9a  aB7P ? Hány olyan pontja van az állapottérnek, amelyekhez a feladat ugyanazt rendeli, mint az 4sa9a9aB7 -hez?

23

2.6. PÉLDÁK

Megoldás:

4sa9a9aB7tON4ia a9b97u 4ia #bRb97uB46bR a #b 7uB46bYbR#b 7 T

Mivel a feladat hozzárendelése nem függ az állapottér harmadik komponensét o˝ l, a feladat ugyanezeket a pontokat rendeli az összes 4ia  a #v 7 alakú ponthoz. Más pontokhoz viszont nem rendelheti ugyanezeket a pontokat, mert akkor az összeg nem lehetne b ! Tehát öt olyan pontja van az állapottérnek amelyhez a feladat ugyanazt rendeli, mint az 4sa9a9aB7 -hez. 2. példa: Legyen
k`ONa #bRfegihcj

T =
!,
"#" . 2O 4sa Bwsa/b jRa/xi7_ 4sa9 wsa h9eNj b xf7u 4ia  wia eNbS  ixi7uy46bY w6bYaBxf7u 46bRBw6bUhNxi7_ 4Deg wDe9e e9e e e   zxi7_{4Dhg wDhga/jRah8xi7_ 4|hc w|hNeYa/b jRa/xi7_ 4|hgBw|hcaBjh8b xf7u}46jY w6j9bh8xi7u 4HjR wHjUe hNxi7_ 46jY w6j9bUe hNxi7 T !O846bR aB7*4HbRfhN7*4Dhga/7*4|hcb97*4|hcj 7 T . a) Adjuk meg FG4HI7 -t! b) Megoldja-e  a feladatot?

Megoldás: a) Mivel a program az a -hez és a e -hoz végtelen sorozatot is rendel, a programfüggvény értelmezési tartománya:

$KL %NM O/bYihg#j T

Ekkor a programfüggvény:

FV46I7ION4HbRa/7uB46bRfhN7_ 4|hcih87u 4Dhg aB7uB4|hcb 7_ 4HjRih87 T

b) A megoldás definíciója két pontjának teljesülését kell belátnunk.

~ $ ] !ObRih T O/bYihg#j T J$KL %NM . ~~ EFV46I746b 7IO9a9ih T O9a fh T ?4Hb 7 , FV46I74|hN7IO hca9b T € ONa #bRj T 4|h87u tehát az  program nem megoldása az  feladatnak.

3. példa: Fejezzük ki a programok uniójának programfüggvényét a programok programfüggvényeivel! Megoldás: Legyenek ‚/#*ƒ
,
"#" programok. Ekkor a programfüggvény értelmezési tartományának definíciójából kiindulva:

OB)+
`QfFV46 t‡   7_46)875
" T   OB)+
`QfFV46  7_4D)R7S
"‰ˆ FG46  7_46)R7S
" T   $KL %9„zM1Š $KL %†M

Legyen )P+;$K/L % „sM1Š $K/L %†fM . Ekkor VF 46‚ ‡ \ 7_46)R7‹ OB[\4D0E7QB0Œ+Œ4H‚ ‡ *B74D)R7 T   OB[\4D0E7QB0Œ+3‚U4D)R7\,0Œ+<*N4D)R7 T   FV46‚7_4D)R7 ‡ FV46*B7_4D)R7_

$KL % „i…R%†iM 

24

2. A PROGRAMOZÁS ALAPFOGALMAI

4. példa: Legyen t és V egy-egy feladat ugyanazon az állapottéren! Igaz-e, hogy ha minden program, ami megoldása t -nek, az megoldása V -nek is, és minden program, ami megoldása G -nek, az megoldása E -nek is, akkor t és G megegyeznek? Megoldás: A leggyakoribb hiba, amit ennek a feladatnak a megoldásakor el szoktak követni, az az, hogy összekeverik az állítás feltételrendszerét magával a bizonyítandó állítással, és azt próbálják bebizonyítani, hogy valamelyik feladatnak minden program megoldása. Természetesen általában ez nem igaz, de nem is ez a feladat! Abból kell tehát kiindulnunk, hogy pontosan ugyanazok a programok oldják meg mindkét feladatot, és meg kell vizsgálnunk, hogy következik-e ebb˝ol az, hogy a két feladat megegyezik. Induljunk ki abból, hogy minden program, ami megoldása   -nek, az megoldása   -nek, és válasszunk egy olyan programot, amelynek programfüggvénye megegyezik az   relációval. Ekkor a választott program triviálisan megoldja az   feladatot, tehát meg kell oldania   -t is, azaz:

~ Ž$ ]9† Z$ ]N„  ~~ (1)+,$ ] † - tU46)R7SV946)R7

Most felhasználva, hogy minden program, ami megoldása V -nek, az megoldása t nek is, és egy olyan program választásával, amelynek programfüggvénye megegyezik   -vel, az el˝oz˝oekkel analóg módon adódnak a fordított irányú állítások:

~

~~~

~~H~ $^] „ $^] †  ~‘ m(*)+'$^] „ -   4D)R7   4D)R7_

Az és állításokból következik, hogy a két feladat értelmezési tartománya mege~~ ~‘ gyezik, míg az és állítások garantálják, hogy ezen közös értelmezési tartomány egyes pontjaihoz mindkét feladat ugyanazokat a pontokat rendeli, azaz E?G . 5. példa: EV . Az  program megoldja V -t. Igaz-e, hogy  megoldja t -et is? Megoldás: Próbáljuk meg bebizonyítani az állítást. Ehhez a megoldás definíciója két pontját kell belátnunk.

~ $ ]N„ $KL %NM , ~~ I(*)P+;$ƒ] „ -_FG4HI7_46)R7J  46)R7 . ~ Az pont teljesülése könnyen látható, ugyanis  ~H~

megoldása V -nek, tehát

$ ]8„ Z$ ] † $K/L %9M

Az pont bizonyításánál azonban gond van, hiszen az alábbi két állítás áll rendelkezésünkre:

(*)+,$^] „ ’ - FV46I74D)R7J  46)R7u (*)+,$ ]N„ q - t46)875V946)87_

és ezekbo˝ l a kívánt állítás nem bizonyítható. Elakadtunk a bizonyításban, lehet, hogy nem igaz az állítás? Készítsünk ellenpéldát felhasználva azt, hogy hol akadtunk el a bizonyításban!

25

2.7. FELADATOK

V

Legyen
!ONa b T , t`O84sa  aB7 T , V!O84sa  aB7_ 4sa9b97 T és FG4HI7 egyezzen meg az feladattal. Ekkor  triviálisan megoldja V -t, de nem megoldása t -nek, ui.

aƒ+;$ ]N„ ˆ FG4HI7_4iaB7IGN4sa/7I`O9a9b Tk  € O9a T ?E 4sa/7u

Tehát az állítás nem igaz.

2.7. Feladatok 1. Legyen
O/“u”#•u–f—

2.

3. 4.

T 2J

"#" . 2O 46“ wH“”—G“5xf7u 46“ wH“–ƒ•—Gxf7u 46“ wH“•ƒ”˜   #xi7_ ” wH”S“5xf7u • wH•ƒ–xf7u • wH•ƒ•ƒ•ƒ•ƒ•ƒ•  sxi7_ – wH–“S—V“–xi7_™– wH–ƒ•“”—V“5xi7_™– wH–“S—E–ƒ”Sxi7_ —I w6—V”5•xf7u —I w6—V•xf7u —I w6—V”5•“5xf7 T !ON4”“57*4”#•7*4–“57*4–#”S7*4–#–7 T . a) Adjuk meg FV46I7 -t! b) Megoldja-e  a feladatot? Legyen  program,  olyan feladat, hogy  megoldása  -nek. Igaz-e, hogy a) ha  nem determinisztikus, akkor  sem az? b) ha  determinisztikus, akkor  is az? c) ha  nem determinisztikus, akkor FG4HI7 sem az? d) ha FG4HI7 determinisztikus, akkor  is az? e) ha  determinisztikus, akkor FG4HI7 is az? f) ha  nem determinisztikus, akkor FG4HI7 sem az? Igaz-e, hogy FG46‰7 értelmezési tartománya éppen
" o˝ sképe  -re nézve? Mondhatjuk-e, hogy az  program megoldja az  feladatot, ha igaz a következ˝o

állítás:

š +'$ ]Z› 54 š 7J
" ˆ FG46‰7_4 š 75J4 š 7u

5. Legyenek ‚ és \ programok,  pedig egy feladat egy tetsz˝oleges közös állapottéren. Teggyük fel továbbá, hogy ‚’* és * megoldja az  feladatot. Igaz-e, hogy ‚ megoldja  -et? 6. Legyen
œk,œ ,

tUfVƒ

. ‘ E!ON4f4|V u7  4Dž‚fŸR7f7SQ=Ÿ*Q  T ,   !ON4f4|V ‘ u7  4Dž‚fŸR7f7SQž;? ˆ Ÿ\Q  T .

Ugyanaz-e a két feladat? (Van-e valamilyen összefüggés közöttük?)

26

2. A PROGRAMOZÁS ALAPFOGALMAI

7.

J
`,
. ‚ , * programok
-n. Az ‚ és az * is megoldja az  feladatot. Igaz-e, hogy az Œ 46‚ ‡ *B7 program is megoldja az  feladatot?

8. Tekintsük a következ˝o szövegesen megadott feladatot: Adott egy sakktábla, és két rajta lév˝o bástya helyzete. Helyezzünk el a táblán egy harmadik bástyát úgy, hogy az mindkett˝onek az ütésében álljon! Készítsük el a modellt: írjuk fel az állapotteret és az  relációt! 9. Tudjuk, hogy  megoldja  -et (az
állapottéren). Igaz-e, hogy

4D)P+
ˆ 464D)R7 J ¡ $ ]¤£ €
" FG4HI7_46)R7 J € 46)87f7i7 › )¢+; 10. Legyen 
!
egy feladat és 
!;
"#" egy program. Jelöljük ƒ¥ -vel azt a relációt, amely  és FV46I7 metszeteként áll el˝o. Igaz-e, hogy a) ha $

]‚¦  $ ]

, akkor  megoldja  -et?

b) ha  megoldja  -et, akkor $

]\¦ J$ ]

?