Programming | Programming theory » Fóthi-Steingart - Bevezetés a programozáshoz

F ÓTHI Á KOS , S TEINGART F ERENC

EGYETEMI JEGYZET c Ez a másolat egy készülő egyetemi jegyzet munkapéldánya. A teljes jegyzetről, vagy annak bármely részéről további egy vagy több másolat készítéséhez a szerzők előzetes írásbeli hozzájárulására van szükség. A másolatnak tartalmaznia kell a sokszorosításra vonatkozó korlátozó kitételt is A jegyzet kizárólag egyetemi oktatási vagy tanulmányi célra használható. A szerzők hozzájárulásukat adják ahhoz, hogy az ELTE-n az 2000-2001-es tanévben elsőéves programozó-matematikus hallgatók bármelyike saját maga részére, tanulmányaihoz egy példány másolatot készítsen a jegyzetb ől. Minden észrevételt, amely valamilyen hibára vonatkozik örömmel fogadunk. Budapest, 2002. szeptember 30 A SZERZ ŐK Tartalomjegyzék 1. Alapfogalmak 1.1 Alaphalmazok 1.2 Sorozatok 1.3 Direktszorzat 1.4 Relációk 1.41 Logikai relációk

1.42 Lezárt, korlátos lezárt 1.5 Példák 1.6 Feladatok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 7 8 8 9 10 11 12 15 2. A programozás alapfogalmai 2.1 Az állapottér fogalma 2.2 A feladat 2.3 A program 2.4 A programfüggvény 2.5 Megoldás 2.6 Példák 2.7 Feladatok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . 17 17 18 18 19 19 20 22 3. Kiterjesztések 3.1 A feladat kiterjesztése 3.2 A program kiterjesztése 3.3 Kiterjesztési tételek 3.4 Példák 3.5 Feladatok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 25 26 27 31 33 4. A típus 4.1 A típusspecifikáció 4.2 A típus 35 35 36 . . . . . 3 4 TARTALOMJEGYZÉK 4.3 Példák 4.4 Feladatok 5. Specifikáció 5.1 A leggyengébb előfeltétel 5.2 A feladat specifikációja 5.3 A változó fogalma 5.4 A típusspecifikáció tétele 5.5 Példák 5.6 Feladatok 38 41 . . . . . . 43 43 45 46 47 49 50 6. Elemi programok 6.1

Feladatok 53 56 7. Programkonstrukciók 7.1 Megengedett konstrukciók 7.2 A programkonstrukciók programfüggvénye 7.3 Levezetési szabályok 7.4 A programkonstrukciók és a kiszámíthatóság 7.41 Parciális rekurzív függvények 7.42 A parciális rekurzív függvények kiszámítása 7.43 Következmény 7.44 Relációk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 57 60 62 68 68 69 73 73 8. Típuskonstrukciók 8.1 A megengedett konstrukciók 8.2 Szelektorfüggvények 8.3 Az iterált specifikációs függvényei 8.4 A függvénytípus 8.5 A típuskonstrukciók típusműveletei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . 75 75 78 79 80 81 9. Alapvető programozási tételek 9.1 Összegzés 9.2 Számlálás 9.3 Maximumkeresés 9.4 Feltételes maximumkeresés 9.5 Lineáris keresés 9.6 Logaritmikus keresés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 85 87 88 89 90 93 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10. Függvényérték kiszámítása 10.1 Függvénykompozícióval adott függvény kiszámítása . 10.2 Esetszétválasztással adott függvény kiszámítása 10.3 Rekurzív formulával adott függvény kiszámítása

10.4 Elemenként feldolgozható függvény 10.41 Egyváltozós-egyértékű eset 10.42 Kétváltozós-egyértékű eset 10.43 Egyváltozós kétértékű eset 10.44 Általános változat 11. Visszalépéses keresés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 . 96 . 96 . 97 . 99 . 100 . 100 . 101 103 5 TARTALOMJEGYZÉK 12. Programtranszformációk 12.1 Koordináta transzformációk 12.11 Típustranszformációk 12.2 Állapottér transzformáció 12.3 Egyszerű programtranszformációk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 . 107 . 107 .

111 . 112 13. Szekvenciális megfelelő 117 14. Programinverzió 121 14.1 Egyváltozós eset 121 14.2 Kétváltozós eset 123 15. Időszerűsítés 15.1 Az időszerűsítés definíciója 15.2 Időszerűsítés egyértelmű módosítófile-lal 15.21 Visszavezetés halmazok uniójára 15.22 Visszavezetés egyváltozós elemenkénti feldolgozásra 15.23 Visszavezetés kétváltozós elemenkénti feldolgozásra 15.3 Időszerűsítés nem egyértelmű módosítófile-lal 15.31 Megoldás adatabsztrakcióval 15.32 Kulcsok egyértelműsítése 15.33 Megoldás függvényabsztrakcióval . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 125 127 127 129 131 132 132 134 135 6 TARTALOMJEGYZÉK Alapfogalmak Ahhoz, hogy bármiről érdemben beszélhessünk, meg kell állapodnunk egy

jelölésrendszerben. Az alábbiakban bevezetjük azokat a jelöléseket és alapvet ő definíciókat amelyeket a továbbiakban gyakran fogunk használni 1.1 Alaphalmazok Először bevezetjük a matematikában gyakran használt számhalmazok jelöléseit.
  
       !    a természetes számok halmaza, a nemnegatív egészek halmaza, az egész számok halmaza, a racionális számok halmaza, a valós számok halmaza, a komplex számok halmaza, a logikai értékek halmaza,   az üres halmaz.
Vegyük
észre, hogy a természetes számok halmazát ( ) és a nemnegatív egészek  halmazát ( ) külön jelöljük. Ennek az az oka, hogy az általunk használt jelölésrendszerben a természetes számok hamaza nem tartalmazza a nullát $#%# &( $& Megjegyezzük továbbá, hogy " -vel fogjuk jelölni, a valós " intervallum egész elemeinek halmazát, azaz " $#)#*&+ " $(&,-.#

Természetesen használni fogjuk a matematikában megszokott halmazelméleti /  műveleteket: ,  unió, metszet, 7 8 1. ALAPFOGALMAK  és relációkat:
 1.2 Sorozatok    eleme, részhalmaza, valódi része.           .           Ha egy adott halmaz, akkor az egy -beli véges, vagy végtelen sorozatot jelöl.   # ##  . Az -beli véges sorozatokat alakban írhatjuk le. A véges sorozat hosszát jelöli. -nel Az -beli véges sorozatok halmazát -gal, a végtelen sorozatok halmazát jelöljük. Az előző két halmaz uniójaként előálló -beli véges, vagy végtelen sorozatok halmazát -gal jelöljük. Egy sorozatat értelmezési tartományát -val jelöljük, és a következő halmazt értjük rajta: #)#  ha
"  ha                !    "   ## #  $#% Legyenek  " és    . Ekkor azt a sorozatot, amit   # ##  $#%      az 

kapunk, a fenti sorozatok    sorozatok egymás  után # ##  írásával konkatenációjának nevezzük, és &(*)+,    $#-   /. -nel jelöljük Egy  -beli sorozat redukáltjának nevezzük azt a sorozatot, amit úgy kapunk, hogy az eredeti sorozat minden azonos elemekből álló véges részsorozatát a részsorozat egyetlen elemével helyettesítjük. Egy   sorozat redukáltját 0*123+4 . -ával jelöljük. Bevezetjük még a utolsó elemét: 5 függvényt, ami egy véges sorozathoz hozzárendeli annak 5768:9; , <= " : 5%+4 . ?>  > # 1.3 Direktszorzat  # ##    # ##   G   JI   ## # KIML :  ,A@ H B
DC G és N :FE "G tetszőleges  # halmazok, ## 3P  . Ekkor az OBH    RJSQ   UT +   # ##    .   R  UT  & "F #%# ) $ L direktszorzatnak a V RJSQ  W T VX P direktszorzat altere és a RJSQ  "Y T V altere. direktszorzat kiegészítő A Z0 [68]9 függvényt

projekciónak nevezzük, ha <%& "F #%#  6^Z0 [:+  . R ` ahol I R a # Legyenek  , H 9 1.4 RELÁCIÓK V .  Q       .  . Z 0 [ + +  +!Z 0 [ V +   Z0 [ +  .
 ahol   Z0 [B+, .  < 76
 Z 0M[:+, A projekciót az alábbi módon kiterjesztjük terek direkt szorzatára, és sorozatterekre is:   legyen és mint fent, , illetve . Ekkor  +  V Q  . V és 1.4 Relációk Relációnak nevezzük egy tetszőleges direktszorzat tetszőleges részhalmazát. A továbbiakban csak olyan relációkkal foglalkozunk, amelyek kétkomponensű direktszorzat részei. Ezeket a relációkat bináris relációknak nevezzük Legyenek és tetszőleges halmazok,  pedig egy tetszőleges reláció. Ekkor a reláció értelmezési tartománya: V    a reláció értékkészlete: V &  ] a reláció értéke egy adott helyen:  egy  + . N
  & halmaz  szerinti képe  +,N . & V  V

&  V V
 Q 6 + $(& .    63+ $& .    + (& .   N 6 + $(& .    Azt mondjuk, hogy egy reláció determinisztikus,vagy parciális függvény, ha  6  +  .   < # Függvénynek nevezünk egy relációt akkor, ha V  6  +  .  # . Ekkor az  #- reláció ha V az  inverze, &  . $& . % #    Q  +  ` +   < 
 Q # V
tetszőleges halmaz. Ekkor az Legyen N  #- +4N .    +  , N !  halmazt a N halmaz  reláció szerinti inverz képének nevezzük. Vegyük észre, hogy az Legyen  inverz kép fogalma megegyezik az inverz reláció szerinti kép fogalmával. Ugyanekkor az N  %#  4+ N .    +  .
N  halmazt a halmaz  reláció szerinti ősképének nevezzük. Vegyük észre, hogy az őskép mindig része inverz képnek. A két kép kapcsolatát mutatja az alábbi ábra:  . A relációk között értelmezünk műveleteket is. Legyen  és    Ekkor

az  relációt a  és  relációk kompozíciójának nevezzük, ha
 Q V
V
 Q V $& $ . &  Q    +   6+ .   + & !   #
 Q relációt a  és  relációk szigorú kompozíciójának nevezzük, ha Az " V $& " #$ + $ .  Q   & 6 + .   + &   % + 
& Q # 10 1. ALAPFOGALMAK N   
@     @    V  1.1 ábra Inverz kép és őskép   &      & &   &  V  1.2 ábra Kompozíció és szigorú kompozíció 1.41 Logikai relációk
 Q  típusú relációkat – ahol tetszőleges halmaz –, logikai relációknak Az  nevezzük. A logikai relációkra bevezetünk néhány jelölést: Legyen  . Ekkor az  gyenge igazsághalmaza:
 Q erős igazsághalmaza:   %#  +   .    %#  +   . #  Vegyük észre, hogy ha  függvény, akkor az erős és gyenge igazsághalmaz megegyezik.

A függvényekre alkalmazott igazsághalmaz-képzésnek van egy inverz művelete, a karakterisztikus függvény megadása: legyen . Ekkor a  függvény a halmaz karakterisztikus függvénye, ha N  N
  +4N .  N # +,N . 6  9 11 1.4 RELÁCIÓK A fenti definíciókból következik, hogy tulajdonképpen mindegy, hogy egy halmaz részhalmazairól, vagy a halmazon értelmezett logikai függvényekr ől (állításokról) beszélünk, hiszen ezen fogalmak kölcsönösen egyértelműen megfelelnek egymásnak. 1.42 Lezárt, korlátos lezárt
 Q  Legyen  egy homogén reláció. A reláció nulladik hatványa: ) ) A reláció -edik hatványa,  
+ $  .   : #     $ #-  #
 Q  reláció lezártja az az 
 Q  Az       ( : 68   +  .  <  R <    6  + . &    &
 6 &  reláció, amelyre:
+ .  6`  
&    +4  .   és . A lezárt tehát olyan pontokban van

értelmezve, amelyekb ől kiindulva a relációt nem lehet végtelen sokszor egymás után alkalmazni, és ezekhez a pontokhoz olyan pontokat rendel, amelyeket úgy kapunk, hogy a reláció véges sokszori alkalmazásával ! , mindig kikerülünk az eredeti reláció értelmezési tartományából. Tehát   teljesül. Az  reláció korlátos lezártja az az  reláció, amelyre: <  
 Q   R   /&
 6    6  +  . +   + .   ! 
 Q   és Vegyük észre, hogy egy reláció lezártja, és korlátos lezártja különbözhet. A definíciókból látható, hogy ez a különbözőség csak az értelmezési tartományok között jelentkezhet. Ennek azonban szükséges feltétele, hogy egy alkalmas pontból kiindulva a relációt ne lehessen végtelen sokszor alkalmazni, de a véges sokszori alkalmazások hosszára ne tudjunk korlátot mondani. Természetesen ez csak akkor lehetséges, ha végtelen sok véges alkalmazás-sorozatot tudunk a

pontból indítani. Nézzünk erre egy   egyszerű példát: legyen  , és
 + .   
    Ekkor Legyen  Q  
   Q
 .  és  `6  9 + , +  Q  . /   ha  ha .A   + $ .  Q ]   O    relációt feltételes relációnak nevezzük. Vegyük észre, hogy egy feltételes reláció nem ugyanaz, mint a reláció leszűkí    ! Továbbá fontos megjegyezni, tése a feltétel igazsághalmazára, azaz   hogy a feltételes reláció értelmezési tartománya mindig a feltétel igazsághalmaza, azaz .   A továbbiakban egy feltételes reláció lezártját illetve korlátos lezártját a reláció feltételre vonatkozó lezártjának illetve feltételre vonatkozó korlátos lezártjának fogjuk nevezni.   >  12 1. ALAPFOGALMAK 1.5 Példák V V V . Q % Q  Q % Q  Q Q% halmazok elemeit, V 1. példa: Írjuk , +,  , és    fel az  
 ,   Z ! ha  Megoldás: V  QQ +  .  + 
 +

  +    + 
 +    V + Z + + Z + +, Q . Q + +  Z   + + 

 Z   + +    Z   + +    Z   + +  

 Z   + +     Z   V ++ ++ ++ ++ ++ ++  Q Q +  Z  .  + 

 Z    +    Z   +    Z   +  

 Z   +     Z  # + + + + + +

    Q 
    . 2. példa: Legyen   + 
.  +   +
  +    +    +     +   # a) b) c) d) Mi a reláció értelmezési tartománya és értékkészlete? Determinisztikus-e, ill. függvény-e a reláció? #%
#%  # Mi  hatványa?    halmaz inverz képe, ill. ősképe? Mi a Megoldás: a)    . + 
     , 
    .  + .  b) A reláció nem determinisztikus, ugyanis pl. determinisztikus, függvény sem lehet. c) A reláció #
! Mivel a reláció nem hatványa az identikus leképezés, azaz:  

+ .  +

 +    +   +    #   , azt kell megvizsgálnunk, hogy mely pontokból hogyan lehet a Mivel  relációt egymás után kétszer alkalmazni:  +  + + .  . 
.  + . + .  #% +  .+  .  9 +   . 9 + +   .  +
 .  +   + . +

.  +
  +    +    +    a reláció inverzének definíciója alapján:  . 9   
+   .  +   .  +  . .  +  +   . A fenti táblázat alapján: 9 9 + 9 +   .
9  
+ 
 . 9 
.  +   +    +    +   # # 13 1.5 PÉLDÁK d) Írjuk fel, hogy mit rendel a reláció az értelmezési tartomány egyes pontjaihoz:  + .
  + .    +
.     + .       Az inverz kép definíciója alapján:  %#  +   Az őskép definíciója alapján:    #  %#  +    3. példa: Megadható-e valamilyen

összefüggés egy a halmaz között? Megoldás: Legyen  , . Ekkor V N V
 Q N
 +  -#  +4N .  + #  N halmaz inverz képének képe, és    + . ,  N   .#  +    S  !  .
     Vegyük észre, hogy általános esetben nem tudunk mondani semmit a két halmaz viszonyáról, ugyanis N
  , akkor N
  +  -#  4+ N . és  ii.) ha   %#  4+ N . 6  + 
 N , akkor  +  -#  4+ N
 N V 
  Tekintsük számpéldán: Legyen    ,  .   e
fenti  esetet egy egyszerű
 
. #    . . + + . Ekkor N esetén  +  +,N , azaz egyik irányú tartalmazkodás sem áll fenn.V V 

#% +  /  . Q  4. példa: Legyen  ,  . Hogyan lehetne jellemezni az  #% +  ,  . halmazt az  #- +  és  #- +  halmaz segítségével? és az  i.) ha Megoldás: /  %#  +   .    /     +  .
+   /       + .
     + .
 # A másik irányú tartalmazkodás sajnos nem áll fenn,

ugyanis lehet olyan amelyre /      és      de     # + .
+ .
V + .

 Nézzük ezt egy számpéldán: Legyen  ,/  +
 % #  . #  . # %   . Ekkor  +  és  +  üres, de  +   . Vizsgáljuk most meg a metszetet!  %#  +  ,  .          -#  +  . ,   .+ # 
+  .
+   , ,    + .
#     + .
 #- +  . .  ,      , 14 1. ALAPFOGALMAK Tehát bebizonyítottuk, hogy két tetszőleges halmaz metszetének ősképe egyenlő a két halmaz ősképének metszetével. V V
 Q 

Q . Igaz-e, hogy %#  
#% +
 . #- 5. példa: Legyenek Megoldás: V +   .  Q    && + .  Q   #% 
%#  # +  . #-
V 6+ $&  & .  + & !  (&
%#   + . 6+ .  #- 
V V
 Q 

Q . Igaz-e, hogy %#  #
#-  +
# . #- 6. példa: Legyenek Megoldás: +    . V 6 + $& .   + & !
  V

+ .
  +   .  Q ] & 6 + &  .  -#   +  &
#%   .
 V +    .  Q & &  . #-  +  & .
#%   +  
6 +  ]  #- + .
  @  #- #
#- # V 

 Számpéldán szemléltetve: legyen  , +  .+ 
 + #
. #% Ekkor  Q ] & +
#
. -#  #% # -#    Q Q     !   . +
   +  #
+ 0 1*2+!Z 0 @  .   
  +   . 7. példa: . , ahol . . Az sorozat további elemeit úgy kapjuk meg, hogy a pontok koordinátáit az els ő koordinátával kezdve ciklikusan 1-gyel növeljük. ?   Megoldás: Írjuk fel el őször a sorozat első néhány tagját:  Az    +   . +
sorozat projekciója Z 0 @   Q 4+  .  + A fenti sorozat redukáltja: .  +
     . +

 

. + 

+4 . .  +    .
-ra: .  +
  +
  +

 +  
 +  
` 0*123+ Z0  @

  ,+  .  +  .  +
  +

 + 
 A fentiekből jól látható, hogy a redukció pontosan azokat az elemeket hagyja ki a sorozatból, amelyekben a növelés a második komponensben történt, így az eredménysoro zat elemeit is a koordináták ciklikus eggyel növelésével kapjuk meg, az pontból kiindulva. + . 15 1.6 FELADATOK 1.6 Feladatok N 1. Milyen összefüggés van egy halmaz ősképe között? És ha  függvény?  .  ++  2.
.  + +  
  
 . Mi a halmaz inverz képe, ill. ősképe? 3.  relációra vonatkozó inverz képe és + (& .  $& N
   &:   / + $+ & .  $+ & +
    &: 
  + +   +  +  
 Mi a N +   halmaz inverz képe, ill. ősképe?
  $& . + +$( & 
+ +    &     6
Q
9
. Mi a N , ahol +  V V halmaz ősképe ill. inverz képe?V 
 Q #%   .
Van-e valamilyen

összefüggés az  #% + O  halmaz és +  halmaz között? az  O"+                 4.  
     5. 6. Készíts olyan nem üres relációt, amelyre igaz, hogy értékkészlete minden valódi részhalmazának ősképe üres halmaz!    .  

 Q  , 
 Q  ,   
  +   
  +    (   +
      +     +   , . + +  + + + + + , és . Mi , ill +  . igazsághalmaza? 
 Q  . Igaz-e, hogy +  #$ #%  #-  #% ? 8.  
 Q  . Igaz-e, hogy +  #- +  *. #% ? 9. 
 Q  . Igaz-e, hogy <-N
 6  #- +  #- +4N +  #- +,N ? 10.  

Q
11.   .  + $& . 
   &    Z 0   + &  a)  + $& .  &    &   &   + $& .  &   b)   Add meg a  #%  és #$ -t relációt!  
12. Legyen   "  Q  , és vezessük be az alábbi jelölést: ha
 Q 

7. Legyen      tetszőleges reláció, akkor    Igaz-e, hogy komplementere: + $(& .  Q  8+ $&  #$
"  #     #- # "
  Igaz-e a fenti állítás nem-szigorú kompozíció esetén? 13. Legyen   "
 Q  . Igaz-e, hogy 
"   #$
 " #   
"  #$
 # "    14. Legyen  és  két reláció a természetes számok halmazán!  egy természetes számhoz rendeli önmagát és a kétszeresét,  egy páros természetes számhoz a felét. 16 1. ALAPFOGALMAK a) Írd fel a két relációt, és add meg az értelmezési tartományukat! & b) Írd fel az  reláció . hatványát ( c) Írd fel a  #  d)  &
) és ennek az értelmezési tartományát! relációt és az értelmezési tartományát! ! Írd fel az relációt és az értelmezési tartományát!  ) 15. Legfeljebb ill legalább milyen hosszú egy és egy hosszúságú sorozat redukáltjának

konkatenációja, ill konkatenációjának redukáltja?  16. Igaz-e, hogy egy sorozat redukáltjának projekciója ugyanolyan hosszú, mint az sorozat redukáltja?   17. Igaz-e, hogy egy sorozat projekciójának redukáltja ugyanolyan hosszú, mint az sorozat redukáltja?  18. Legyen    Q   + +  Z 0 [ +, . ? b) 0 1M23+ Z0 [ +4 . Q a) ?   Q     . 
   .  V ,  +  
 +   Q  , ahol  
+  .  + 
   + 
   .  +       #)#  . 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ű 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őkerülnek, és e modell segítségével a gyakorlatban használható eszközöket adunk. 2.1 Az állapottér fogalma Az elsőként bevezetendő absztrakt fogalom tulajdonképpen a számítógép memóriájának ad egy a továbbiakban kényelmesen használható megfelelőt. 1. DEFINÍCIÓ : Á LLAPOTTÉR Legyenek

  
 tetszőleges 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ők – é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ők 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ő elemekből állnak. A későbbiekben majd kitérünk arra is, hogy ez a közös tulajdonság mit is jelent Mivel a jellemzők é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 legegyszerű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őle 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értelmű. Például egy pont síkbeli koordinátáit megadhatjuk a derészögű 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őt vizsgálunk – azaz az állapottér túl kevés komponensb ő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őben dinamikus folyamat. Vezessünk be egy könynyebben kezelhető statikus modellt! Hogyan kaphatunk egy ilyen statikus modellt? Tekintsük például az alábbi – a programozástól igazán messze eső – 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őben dinamikusan lejátszódó folyamat. Hogyan követhető 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őben 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őbeni

futásának jellemzésére az előbbi 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űzve 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 értelemszerűek: az első azt kívánja meg, hogy a program futását jellemző sorozat abból a pontból induljon el, amihez hozzárendeltük. A programnak tetszőleges á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, elegendő, 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ülső állapotok lényegtelenek. Természetesen vannak olyan – a programok minősé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ő- és tárigénye), de mi a továbbiakban ezekkel egyelőre 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. FV46I7 4D)R7I!OW+<
!Q

XY0Z+<54D)R7S-U[460V7?W T Az első 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 értelemszerűen azt írja le, hogy ahova a program eljut, az a sorozat utolsó eleme. A programfüggvény elnevezés megtévesztő lehet, hiszen egy program programfüggvénye nem feltétlenül függvény, sőt 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ősé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őponthoz. $KL %NM 4D)R7 FV46I7 4D)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/fo 7  46Ag@9#p*7i7^QCp!q)Pr`W T g4sa9 a  aB7P ? Hány olyan pontja van az állapottérnek, amelyekhez a feladat ugyanazt rendeli, mint az 4sa9 a9 aB7 -hez? 23 2.6 PÉLDÁK Megoldás: 4sa9 a9 aB7tON4ia  a9b97u 4ia #bRb97uB46bR a #b 7uB46bYbR#b 7 T Mivel a feladat hozzárendelése nem függ az

állapottér harmadik komponensét ő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 4sa9 a9 aB7 -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/jRa h8xi7  4|hc w|hNeYa/b jRa/xi7  4|hgBw|hcaBjh8b xf7u}46jY w6j9bh8xi7u 4HjR wHjUe hNxi7  46jY w6j9bUe hNxi7 T !O846bR aB7*4HbRfhN74Dhg a/74|hcb974|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: FV46I7ION4HbR

a/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 . ~~ EFV46I7 46b 7IO9a9ih T O9a fh T ?4Hb 7 , FV46I7 4|hN7IO hc a9b 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‚ ‡ *B7 4D)R7 T   OB[4D0E7QB0Œ+3‚U4D)R7,0Œ+<*N4D)R7 T   FV46‚ 7 4D)R7 ‡ FV46*B7 4D)R7 $KL %

„iR%†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ől 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őzőekkel 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~~ és ~‘ állítások garantálják, hogy ezen közös értelmezési tartomány gyezik, míg az 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: (*)+,$^] „ ’ - FV46I7 4D)R7J  46)R7u (*)+,$ ]N„ q - t46)875V946)87 és ezekbő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”#•74–“574–#”S74–#–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
" ősképe  -re nézve? Mondhatjuk-e, hogy az 

program megoldja az  feladatot, ha igaz a következő állítás: š +$ ]Z› 54 š 7J
" ˆ FG46‰7 4 š 75J4 š 7u 5. Legyenek ‚ és  programok,  pedig egy feladat egy tetszőleges 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ő szövegesen megadott feladatot: Adott egy sakktábla, és két rajta lévő bástya helyzete. Helyezzünk el a táblán egy harmadik bástyát úgy, hogy az mindkettőnek 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ő. Igaz-e, hogy a) ha $ ]‚¦  $ ] , akkor  megoldja  -et? b) ha  megoldja  -et, akkor $ ]¦ J$ ] ? Kiterjesztések Az előző fejezetben bevezetük a program és a feladatat fogalmát, és definiáltuk az azonos állapottéren levő feladat–program párok között a megoldás fogalmát. A gyakorlatban általában azonban a feladat és a program különböző állapottéren van: példaként megemlíthetjük azt az esetet, amikor egy feladat megoldására a programban további változókat kell bevezetni, azaz a feladat állapotterét újabb komponensekkel kell b

ővíteni. A továbbiakban tehát a program és a feladat fogalmát fogjuk általánosítani, és megvizsgáljuk, hogy mit tudunk mondani a különböző állapottéren adott programok és feladatok viszonyáról. Az előző fejezetben megismert megoldásfogalom elég egyszerű módon leírja, mit is jelent az, hogy egy program megold egy feladatot. Ezért ezt a megoldásfogalmat megtartjuk, és megpróbáljuk a különböző állapottéren levő feladatot és programot egy “közös állapottérre hozni". 3.1 A feladat kiterjesztése Ha egy megoldó program állapottere bővebb, mint a feladaté, akkor a feladat állapotterét kibővítjük újabb komponensekkel, de értelemszerűen azok értékére nem adunk semmilyen korlátozást. 6. DEFINÍCIÓ :
  

Legyen a F ELADAT KITERJESZTÉSE állapottér altere az állapottérnek. Az feladat kiterjesztésének nevezzük, ha    relációt az    !

#"%$&()*+)"%$&(), .-0/  . Vegyük észre, hogy a feladat kiterjesztése az összes olyan -beli pontot tartalmazza, aminek B-re vett projekciója benne van -ben, azaz a kiterjesztett feladat az új állapottér-komponensekre nem fogalmaz meg semmilyen megszorítást.  25 26 3. KITERJESZTÉSEK
    
3.1 ábra Feladat kiterjesztése 3.2 A program kiterjesztése A program kiterjesztésének definíciójában az új komponensekre azt a kikötést tesszük, hogy azok nem változnak meg a kiterjesztett programban. Ezzel azt a gyakorlati követelményt írjuk le, hogy azok a változók, amelyeket a program nem használ, nem változnak meg a program futása során. 7. DEFINÍCIÓ : P ROGRAM KITERJESZTÉSE Legyen a állapottér altere az állapottérnek, és jelölje a kiegészítő

alterét -ra. Legyen továbbá program a állapottéren Ekkor az -beli  relációt az S program kiterjesztésének nevezzük, ha 
 
  

    
! "%$&    
 "%$&    

        "%$&    "%$&   - A fenti definíció alapján a kiterjesztett program értékkészletében csak olyan sorozatok vannak, amelyek “párhuzamosak” valamely sorozattal az eredeti program értékkészletéből. Vajon a kiterjesztés megtartja a program-tulajdonságot? Erre a kérdésre válaszol az alábbi tétel. 1. TÉTEL : P ROGRAM KITERJESZTÉSE Legyen a állapottér altere
az állapottérnek, és jelölje
alterét -ra. Legyen továbbá program a állapottéren, és
-ra. Ekkor program  
 

 a

kiegészítő  az kiterjesztése A tétel bizonyítása rendkívül egyszerű, a feladatok között szerepel. 27 3.3 KITERJESZTÉSI TÉTELEK
 
3.2 ábra Program kiterjesztése 3.3 Kiterjesztési tételek Az alábbiakban következő tételcsoport a megoldás feltételeinek teljesülését vizsgálja a kiterjesztett

feladatok és programok között. 8. P

ROGRAMOK EKVIVALENCIÁJA
   programok, altere mind , Legyenek 

 mind -nek. Azt mondjuk, hogy ekvivalens -vel -n, DEFINÍCIÓ :        "$ &  "
    "$ & #" 
  /

 -nek, A fenti definíció annak formális leírása, hogy két program ugyanakkor terminál, és ha terminál, akkor ugyanazt az eredményt adja. A definíciónak egyszerű következménye az is, hogy a két ekvivalens program a közös altéren pontosan ugyanazokat a feladatokat oldja meg. Valójában attól, hogy két program ekvivalens – azaz megegyezik a programfüggvényük – egyéb tulajdonságaik nagyon eltérők lehetnek. Ilyen – nem elhanyalgolható – különbség lehet például a hatékonyságukban. Egyáltalán nem mindegy, hogy egy program mennyi ideig fut és mekkora memóriára van szüksége. Tehát az, hogy egy program helyes (megold egy feladatot) még korántsem elegend ő. A

program ezen jellemzőinek vizsgálata azonban meghaladja e könyv célját és kereteit. 9. DEFINÍCIÓ : B ŐVÍ TETT IDENTITÁS Legyen altere -nak, a kiegészítő altere -ra,         A bővített identitás felett, ha         .


    
 "%$ &    "%$ &     "$ &     " $ &              , hogy feladat.        28 3. KITERJESZTÉSEK
        
3.3 ábra Bővített identitás Ez a definíció tulajdonképpen azt írja le, hogy a feladat altérre vett projekciójának – mint relációnak – tartalmaznia kell az identikus leképezés megszorítását a projektált feladat értelmezési tartományára. De lássuk a második tulajdonságot! 10. DEFINÍCIÓ : V ETÍ TÉSTARTÁS  Legyen altere -nak,         feladat.  A  vetítéstartó
felett, ha 
  #"$ &     "%$ &     "$ &   

  "%$ &        .

           
3.4 ábra Vetítéstartás A kiterjesztett feladatok és programok illetve az eredeti állapottéren levő feladatok és programok közötti kapcsolatokról szóló tételek kimondásához szükségünk van még egy definícióra: 29 3.3 KITERJESZTÉSI TÉTELEK 11. DEFINÍCIÓ : F ÉLKITERJESZTÉS  Legyen altere -nak, félkiterjesztés felett, ha 

    feladat, 
%" $ &     . . Azt mondjuk, hogy a
    
3.5 ábra Félkiterjesztés Az imént bevezetett definíciók segítségével kimondhatók azok az állítások, amelyek a kiterjesztések és a projekció valamint a megoldás közötti kapcsolatot vizsgáló tételcsoportot alkotják. 2. TÉTEL : K ITERJESZTÉSI TÉTELEK
Legyen altere
-nak, a
kiegészítő altere -ra, program -n, feladat, illetve -nek illetve -nek a kiterjesztése
-ra. Legyen továbbá olyan feladat, melyre , és
pedig olyan program,

amely ekvivalens -sel -n. Ekkor az alábbi állítások teljesülnek:


   
 (1) ha
 (2) ha (5) (6) (7) 
.
  megoldása     -nek, akkor
megoldása -nek, akkor
 "%$ &     

      megoldása -nek, megoldása
  -nek,   -nek, akkor megoldása  -nek,
ha megoldása 
-nek és "   vetítéstartó
felett, vagy  félkiterjesztés  felett, akkor megoldása  -nek,

ha megoldása  -nek, akkor  megoldása   -nek,
ha megoldása  -nek és  bővített identitás
 felett és vetítéstartó

felett, akkor  megoldása  -nek,


ha megoldása  -nek és "  félkiterjesztés  felett, akkor megoldása   -nek. (3) ha (4)

megoldása Bizonyítás: Mielőtt sorra bizonyítanánk
az egyes tételeket, vegyük észre, hogy a (4)

tételből következik az első három, hiszen ekvivalens -sel -n és vetítéstartó, 
"   30 3.

KITERJESZTÉSEK "$ &         illetve és félkiterjesztés  -en. Hasonló meggondolások alapján a (6) tételből is következik az (5) tétel, hiszen bővített identitás felett és vetítéstartó felett. Elegendő tehát a (4), (6), és (7) tételeket bizonyítani  tetszőleges. Ekkor Tekintsük először a (4) tétel bizonyítását: Legyen  
        "%$&(      
 
"%$&(  
  megoldás  
   ekv.
 , s így a megoldás első kritériumának teljesülését bebizonyítottuk. tehát   tetszőlegesen rögzített. Ekkor Tekintsük most a második kritériumot: legyen  
"
+  
    
 "$ & #" 
    "$ &       "
 vetítéstartó, akkor legyen    olyan tetszőlegesen rögzített elem, melyre "$ &     . Ekkor " 
    "%$& #" 
 

   "$ &           Ha  félkiterjesztés, akkor "%$ &
    , azaz       "%$ &         Ha és így a megoldás definíciója miatt     "%$ &      "
+        tehát " 
         
  
 "%$ & " 
      "$ &    


 "$ &(#"
+    "
+     

 és ezzel beláttuk, hogy az program megoldja az Nézzük most a (6) tétel bizonyítását. 1.   Legyen 
   , ui. 
 . Ekkor "%$& "%$&    
 . 
   . ekkor     ,  "%$&      feladatot.  . Felhasználva, hogy
 megoldása -nek, A program kiterjesztésének definíciójából következik, hogy 31 3.4 PÉLDÁK 2.       "
 +        , ui.   "
  

  . Ekkor – felhasználva, Legyen

 tetszőlegesen rögzített,  hogy az kiterjesztése –  -re fennáll az alábbi tulajdonság:   %" $ &       "%$ &    

Legyen +  "%$ &    . Ekkor + "   #"%$&(   Mivel megodja  -et, adódik, hogy +    "%$&(    Ekkor – mivel  vetítéstartó
felett és  a   . Felhasználva, hogy  projekciója – adódik, hogy          "$ &      bővített identitás
 felett,           , amelyre "%$ &         "%$ &     és "$ &         / Ekkor viszont      , azaz       . Most már csak a (7) állítás bizonyítása van hátra:    . Ekkor a feladat kiterjesztése definíciója alapján "%$ &   
"
 félkiterjesztés  felett,   
  .    tetszőlegesen rögzített. Ekkor (2) Legyen 
(1) Legyen  Mivel

"$ &   ,  . " 
 #"%$ &       #"%$ &      ekv.   "$ &  " 
  *    #"$ &     megoldás 
 

innét a feladat kiterjesztésének definíciója alapján a "
+   
 

  "%$ &
relációt alkalmazva: " 
         / Ezzel a (7) állítást is bebizonyítottuk. A gyakorlatban használt kiterjesztéseknek, azaz az állapotér gyakorlatban el őforduló bővítéseinek ezek a tételek adják meg az elméleti hátterét. Ezen tételek fennállása garantálja például, hogy az új változó bevezetése nem rontja el a megoldást. 12. DEFINÍCIÓ : A MEGOLDÁS ÁLTALÁNOSÍ TÁSA
Legyen feladat és program. Azt mondjuk, hogy

a megoldása -nek, ha létezik állapottér, aminek és is altere és   kiterjesztése -re -re való kiterjesztésének megoldása.      


A

kiterjesztési tételekből következik, hogy a definícióban a létezik helyett minden is írható. 3.4 Példák    0  - 
 
   1. példa: kiterjesztettje -re?   0  - .       .     0 0    0 - Mi az     32 3. KITERJESZTÉSEK Megoldás: A feladat kiterjesztésének definíciója alapján:      0 +   +   0 +   0+   0 0+   +   0 +   +   0 0+   0+                                  0   0           0          0                     -           0    0         %       % 0              0 +   +   0 0+   0+   0 +   +   0 0+   +                             +  

   !       - ) a következő program:
        0             0   +                 0           0 +   0          0  +         0     
Megoldja-e az  ( -re való kiterjesztettjét? Megoldás: Írjuk fel az    -re való kiterjesztettjét:                 +       0     0                 +       0             +   0       +   0 0      +          +    0      +   0       +   0 0      +          +    0     +  0      +   +    +        +   

2. példa: Adott az

 és az állapottéren az állapottéren (  (                                  feladat,                     

                                                                                                        Az S program programfüggvénye: " 
        +               +    0            +          0   0      
 triA megoldás definíciója két pontjának teljesülését kell belátnunk.     viálisan teljesül, hiszen mindkét halmaz a teljes állapottér. Vizsgáljuk meg most, hogy
    "            teljesül-e! " 
       -            -       "
+   0     0  -            -      0 " 
      -    0 0   -      " 
      -    0 0   -     0 " 
      -    0 0

  -     
" +      0 -    0 0   -     0 " 
     -    0 0   -     "
+    -    0 0   -    0
Tehát az program megoldja az  feladat kiterjesztettjét.                                                                                                         33 3.5 FELADATOK 3. példa: Igaz-e, ha


  altere
-nek, akkor


   "%$ 
    Megoldás: Próbáljuk meg az állítást kétirányú tartalmazkodás belátásával bizonyítani.


  Legyen 

 . Ekkor   "%$  
      
   "$  #"        +  "   "$           
 
  "%$      ."%$   "

   /
 
  Legyen  ."%$ 
  Ekkor  
   "$    
   + 
     " 
     "%$   ,."%$  #"    


  "$ 
    és ezzel az állítást bebizonyítottuk. 3.5 Feladatok 1.   
   .     /    $  ! $  - . Mi az 
-re?

program,  altere

-nek, akkor
  -ra történő Igaz-e, ha 

-re azonos -sel? projekciójának kiterjesztése
 kiterjesztettje 2. 3. Bizonyítsuk be, hogy egy program kiterjesztettje valóban program! 4.         . Mondjunk példát olyan programra, amelynek egyetlen 
 . valódi altérre vett projekciója sem program.     5. Legyen altere Igaz-e, hogy
-nek,          / / /    ,    

,   az  kiterjesztettje
  "$       , akkor    az  kiterjesztettje?   b)    "$ 
   ? ill.    "$ 
   ? 

, ahol
   , Legyen     , ,   
,   
,             , és legyen            az  kiterjesztése rendre
-re, -re,  -re. Igaz-e, hogy     az    kiterjesztése  -re? Add meg az   és az    közötti kapcsolatot a projekció és a kiterjesztés fogalmának segítségével! .  az 
és altere  -nak.        

    projekciója
-re.  az  kiterjesztése  -ra Igaz-e, hogy az feladat   -ra  való kiterjesztettjének -re vett projekciója megegyezik  -vel? a) ha 6.     7. -re.     34 3. KITERJESZTÉSEK Specifikáció A megoldás definíciója közvetlenül elég nehézkesen használható a programok készítése során, hiszen az, hogy egy program megold-e egy feladatot az a megoldás eddigi definíciója alapján csak nehezen ellenőrizhető. Ezért bevezetünk néhány új fogalmat, majd ezek segítségével egy elégséges feltételt adunk a megoldásra. 5.1 A leggyengébb

előfeltétel Először a program futásának adjuk meg egy a programfüggvénynél kényelmesebben használható jellemzését.
   

 "!$#&%(*),+.-0/2143 5 6   %78  "292: 16. DEFINÍCIÓ : L EGGYENGÉBB EL ŐFELTÉTEL Legyen program, állítás. Ekkor az program utófeltételhez tartozó leggyengébb előfeltétele az az állítás, amelyre:
A leggyengébb előfeltétel tehát pontosan azokban a pontokban igaz, ahonnét kiindulva az program biztosan terminál, és az összes lehetséges végállapotra igaz . Természetesen a leggyengébb előfeltétel igazsághalmazán kívül is lehetnek olyan pontok, amelyből a program egy futása eljut az utófeltétel igazsághalmazába, csak azokból a pontokból nem garantált, hogy oda jut. Egy program működése úgy is jellemzhető, hogy megadjuk a program tetszőleges utófeltételhez tartozó leggyengébb előfeltételét. A feladat megoldása során az a célunk,

hogy olyan programot találjunk, amelyik bizonyos feltételeknek eleget tevő 45 46 5. SPECIFIKÁCIÓ pontokban terminál. Ezért azt mondhatjuk, hogy ha a számunkra kedvező végállapotokra megadjuk a program leggyengébb előfeltételét, akkor a programfüggvény meghatározása nélkül jellemezzük a program működését A most következő tétel a leggyengébb előfeltétel néhány fontos tulajdonságát mondja ki.  
;;$<,  program, =>$2?@ állítások. Ekkor      (1)
AB,CEDF
G!HJAB ,CEDF
,  (2) Ha =EI 
L=KNM ,Jakkor 
L !
 =K 
I L=OMP
 , , (3) 
L=KNQ J
L I J
 =;QP . (4) 3. TÉTEL : A Legyen TULAJDONSÁGAI Az első tulajdonságot a csoda kizárása elvének, a másodikat monotonitási tulajdonságnak nevezzük. Bizonyítás: RS%T U
AT"CE D7
   . Ekkor a leggyengébb elő%VV),+W-X/F1 és 5
 %SY AB"CED7
Z[!] Ez UJ

=K ` UJ
L a . Ekkor %T^),+W-X/F1 és 2. Indirekt: 5
  %SK Tegyük  =,bM(fel,5 
hogy  %S(RSc %^  d . Ez
 viszont ellentmond annak a feltételnek,   mely szerint = K " 1. Indirekt: Tegyük fel, hogy feltétel definíciója szerint: nyilvánvaló ellentmondás. 3. Az állítást két részben, a mindkét irányú következés belátásával bizonyítjuk  UJ
L a UJ
 =K  5 
   d  =, 5.1 ábra A leggyengébb előfeltétel és a metszet kapcsolata (a) 
L=KNM J
L I J
 =;MP , ui.: U
L=fgM 
a . Ekkor %h 
L=Ka és %e 
  , Legyen %e    azaz 5 
 %7 i  " . Ekkor azonban 5
 %h%7ih ),+W -X= /F1késj 5  "
, ! %S` =O MP=," ,,illetve azaz %e
L=lM*a . 47 5.2 A FELADAT SPECIFIKÁCIÓJA (b) J
 =;MPI 
L=fNM J
L  , ui.: 
L=?MB  . Ekkor a leggyengébb

előfeltétel definíciója Legyen %m  =nM +.-0/21 és 5 
  %Sp   =o MY"  Felhasználva, alapján %no), hogy     "q! =, ij " , adódik, =, és 5
 %S  " , azaz hogy 5
G %SK %h
L=Ka és %e UJ
L  , tehát %e UJ
 =KNM 
  . 5 
  
  
L=Ka   "  =, 5.2 ábra A leggyengébb előfeltétel és az unió kapcsolata %eU  UJ
 =KFQ 
  h%
L=f  U a  %h
L=f  %e U  
L=f  e% UU J 
a . %e 
 =hQ %h  
L=lQP a 4. Legyen . Ekkor vagy Ha , akkor – a monotonitási tulajdonság alapján – . Hasonlóan ha , akkor . 5.2 A feladat specifikációja A következőkben bevezetjük a feladat megadásának egy másik módját, és kimondunk egy a gyakorlat szempontjából nagyon fontos tételt. Általában a feladat nem függ az állapottér összes komponensét ől, azaz az

állapottér több pontjához is ugyanazt rendeli. Ezeket a pontokat fogjuk össze egy ponttá a paramétertér segítségével. ro[$< rt rZu s r tv E <se rwu  Vs <K r ! Zr ukx8rt.: 17. DEFINÍCIÓ : PARAMÉTERTÉR Legyen feladat. A halmazt a feladat paraméterterének nevezzük, ha van olyan és reláció, hogy Fontos észrevenni, hogy paraméterteret mindig lehet találni. Például maga a feladat állapottere minden esetben választható paramétertérnek úgy, hogy a definícióban 48 5. SPECIFIKÁCIÓ rt ru r szereplő relációnak az identikus leképezést, -nek pedig magát az feladatot választjuk. Ám az, hogy egy konkrét esetben mit is választunk paramétertérnek a feladattól függ Általában úgy választjuk meg a paraméterteret, hogy a következő tételt kényelmesen tudjuk használni. rn;Pk s r r t lPks r u Osk , r$!yr u 8x r t : z"Ps  =K{|}! #.%(<~3  % z€8Pr t 9,![r t -U t 1  z€  ,{|}!

#.%(<E3  zW%S8‚r u 9,!yr u  z€ƒ: 
 { € akkor az
program megoldja az r Ekkor ha „NzO s†K= { I 4. TÉTEL : S PECIFIKÁCIÓ TÉTELE Legyen feladat, az egy paramétertere, , Legyen , és definiáljuk a következő állításokat: feladatot. Bizonyítás: A megoldás definíciója két pontjának teljesülését kell belátnunk: 1. )K‡lY),+W-X/F1 , ui. Legyen %e*)K‡ tetszőleges. Ekkor az rt és rwu relációk definíciója miatt Rˆz"‚sV‰%e  = { 2: e%  =f{aK UJ
L,{ fŠ)"+W-X/F1ƒ:    2. „N%e*)‡;€5
 %S`Or %S , ui.  Legyen %*<)K‡ tetszőlegesen rögzített, z,Bs olyan, amelyre %P = {  . Ekkor a feltétel szerint: 5 
  %S`  {|,!yr u  z‹8lr u  r t  %Sgk!yr  %7€: De ekkor a tétel feltétele alapján: Vegyük észre, hogy a tétel feltételrendszerében használt jelölések felhasználhatók a feladat egy más módon történő leírására. Ha a feldatot úgy definiáljuk, hogy

megadjuk az állapotterét ( ), a paraméterterét ( ), valamint az elő- és utófeltételét ( illetve ) a paramétertér egy tetszőleges pontjára, akkor azt mondjuk, hogy a feladatot specifikáljuk. Paramétertérnek általában az állapottér egy alterét szoktuk választani. Azokat a komponenseket válogatjuk ki, amelyek értékétől függ, hogy a feladat mit rendel, amik paraméterezik a feladatot. A specifikáció tétele csak elégséges feltétel a megoldásra, azaz nem megfordítható: lehet adni olyan feladat-program párt, ahol a program megoldja a feladatot, de a specifikáció tétele nem teljesül. Ez természetesen attól is függ, hogy a feladatot hogyan specifikáljuk, azaz milyen paraméterteret választunk, és hogyan bontjuk a feladatot és relációk kompozíciójára.  ru s = rt 49 5.3 A VÁLTOZÓ FOGALMA 5.3 A változó fogalma Az eddig elmondottakból alapján a specifikáció tétele még nem lenne hatékonyan használható, hiszen a

paramétertér minden pontjára ellenőriznünk kellene a feltételek teljesülését. Ezért bevezetjük a változó fogalmát, aminek segítségével a feltételrendszer teljesülése egyszerűen ellenőrizhetővé válik. E!Œ t p4‹<"Ž 18. DEFINÍCIÓ : VÁLTOZÓ Az állapottér vényeit változóknak nevezzük. ‘8ˆ$’" egydimenziós projekciós függ- A változók használatával egyszerűsíthetjük az állapottéren értelmezett állítások (elő- és utófeltételek, leggyengébb előfeltétel) és relációk (programfüggvény) leírását. Mivel minden változó értelmezési tartománya az állapottér, és értékkészlete egy típusértékhalmaz, egy változót jellemezhetünk egy típussal, azaz beszélhetünk a változó típusáról. Ha a paramétertér is direktszorzat alakú – márpedig ez gyakran így van, ugyanis általában az állapottér egy altere – akkor a paramétertér egydimenziós projekciós

függvényeit paraméterváltozóknak nevezzük. Az állapottér illetve a paramétertér egyes komponenseihez tartozó vátozókat illetve paraméterváltozókat az adott komponens alá írjuk. Tekintsünk egy egyszerű példát: határozzuk meg két egész szám maximumát! “!•”“— E”“˜ –” ™ sš! —”›œ ˜S” œ — ˜ ™ Az első sor tehát azt jelenti, hogy az állapottér három egész komponensb ől áll, melyeknek változói rendre , és . Hasonlóan a második sor jelentése: a paramétertér két egész komponensb ől áll, az első komponens változója , a másodiké . A paramétertér egy tetszőleges eleméhez tartozó elő- és utófeltétel az állapottér egy tetszőleges pontjában: z % =ž&Ÿ - { 1 ¡ ¢‹Ÿ - { 1  %S!  —™  S% k! —— œœ  z€£M "ž Ÿ - { 1 ¡ ¢ Ÿ - { 1 %S! %S`¤ €z £M —œ ˜  %7! ™  %S8¤ ˜Sœ ˜ œ  z€g ˜ œ  z‹NM  ™  S% ! — œ  €z NQ ™  S% ! ˜ œ 

€z g A fenti jelölést tovább szoktuk egyszerűsíteni: mivel az állapottér változói és a paraméterváltozók mindenütt azonos argumentummal szerepelnek, az argumentumot – hiszen az nyilvánvaló – nem írjuk ki: = ž4ŸU¡ ¢€Ÿ !  —™ ! ž4ŸU¡ ¢€Ÿ ! ¤ —œM —œM ˜ ! ˜ œ ™ ¤ ˜ œ M  ™ ! — œ Q ™ ! ˜ œ g  A jelölés tovább egyszerűsíthető! Mivel ezek a feltételek a paramétertér pontjaihoz tartoznak, nyilvánvaló, hogy a paraméterváltozók értékeitől függnek. Ha nyilvánvaló, akkor az állítások indexe el is hagyható. A feladat specifikációja tehát: 50 5. SPECIFIKÁCIÓ “!•”“— E”“˜ –” ™ s@!—”¦œ V˜7” œ =~  —™ ! —— œ œ M ™˜ ! Œ ¤ M ¤ ˜œ ˜Sœ  M  ™ ! — œ Q ™ ! ˜Sœ  A változók segítségével könnyen felírhatunk olyan függvényeket, amelyek az állapottér komponensein vannak értelmezve. Ha nem okoz félreértést, akkor az  x   0bizonyos §

‹:4:‹:‹ X¨  jelölés helyett az    § 4:‹:4:‹g 0¨  jelölést használjuk. A későbbiekben bevezetünk majd olyan eszközöket, amelyek segítségével a feladat specifikációjából kiindulva olyan programokat készíthetünk, amelyek megoldják a feladatot. 5.4 A típusspecifikáció tétele A típusspecifikáció és a típus fogalmának bevezetésével tulajdonképpen a feladat fogalmát általánosítottuk, míg a megfeleltetés a megoldás fogalmának volt egyfajta általánosítása. Az imént megismert specifikáció tétele a megoldásra adott elégséges feltételt Próbáljunk most a -n keresztüli megoldásra egy hasonló feltételt adni! ªˆ«m! U ¬ L D‹«&|­ ª®!  FLD¯L°w 4  D‰.±! D‹«L rV‚­ r  s =K{ {
;P°
r  = ²{ }! ³=K{£xG´µ  "²{ }!  ,{wxG´ ahol ´ a program és a feladat állapottere közötti, a -n keresztüli defi
 megoldás níciójában szereplő

leképezés. Ekkor ha „Nzd‚sF= ²{ I ²{ € akkor az
program a -n keresztül megoldja az r feladatot. Bizonyítás: A -n keresztüli megoldás definíciója két pontjának teljesülését kell belátnunk: 1. ) ‡ Y) +W-X/F1 ¶·²‘¸0¹ §º , ui. ‘ ² ¶  &  Legyen %e*) ‡ . Ekkor Rˆz"PsV2%e =K{| Mivel D‰! D‹«  , ´ -U t 1  %7 !yc iMh´ - t 1  %S8  = ²{ F:  UJ
L"²{   : Felhasználva, hogy = ²{ K ´ -U t 1  %78;),+W-X/F1M±5 
  ´ - t 1  %Sg`  ²{ 2: 5. TÉTEL : T ÍPUSPECIFIKÁCIÓ TÉTELE Legyen és adott típusspecifikáció és típus, és tegyük fel, hogy a reprezentáció helyes, azaz . Legyen továbbá , az állapottere , egy paramétertere , elő és utófeltétele pedig és . Legyen és tegyük fel, hogy állapottere illeszkedik állapotteréhez. Definiáljuk a következő állításokat: 5.4 A TÍPUSSPECIFIKÁCIÓ TÉTELE 51  ,²{ ,!  {£xG´ , 5 
  ´ -U t 1 

%SgiY) ² tehát %hh) ²‘¶ +W-X/F1 ¶·²‰¸X¹ §º :  -U t 1 Or  %S , ui. 2. „»%(P)K‡Š‘´>¼‚5
w¼p´ Legyen %En)K‡ . A bizonyítás első részében leírt lépéseket folytatva: mivel 5 
G  ´ -U t 1  %7`  { xG´ , ´  5 
  ´ - t 1  %Sggi  { Klr  %Sƒ: Mivel Az, hogy a fenti tétel feltételei között kikötöttük, hogy a program állapottere illeszkedik a feladat állapotteréhez tulajdonképpen elhagyható. Ekkor a tétel a feladat és a program olyan kiterjesztéseire mondható ki, amelyek állapotterei illeszkednek egymáshoz (pontosan úgy, ahogy a megfeleltetést definiáltuk nem illeszkedő állapotterek között). A következő példában megmutatjuk, hogy -t gyenge igazsáhalmaz helyett erős igazsághalmazzal definiálnánk, akkor a tétel nem lenne igaz. Legyen , , , . Legyen állapottere és a paramétertér is legyen ugyanez: . Legyen specifikációja: = ²{ ª « ! ¬ D « |­¯ ¬

!¦#2½2L¾S9 D « !"¿ ¬ ­V!¦#.rq9 r ¬ H! s~! r  = t }! #F½‘92  t }! #W¾79  = u }! ˆ  u }! #F½‘9 #2½‘9 és r  ½&(!@#W¾79  . Legyen Ekkor )K‡o! továbbá az elemi értékek halmaza À›!  #.% z&9 , ªŒ! 7D°Z , „»ÁYPÀ  ‰D ÁG!  3 Á`3‰!Œ½& , és az egy hosszú sorozatokra: g %SÃgG!$  z€ÃG!–#F½‰ ¾792:  Tegyük fel, hogy °Š!#.
89 ,
oÀ±q Àq‹LL , és rendelje
az állapottere minden pontjához az önmagából álló egy hosszú sorozatot. Ennek a programnak az állapottere illeszkedik a fenti feladat állapotteréhez, és ´P!$ . Ekkor  =ftxG´"!H és  =uGxG´,!yˆ tehát = t xG´ I 
 t xG´N = t xG´ I
 t xG´N Az viszont könnyen látható, hogy ´>¼B5 
G·¼p´ -U t 1  ½.!E#F½‰ ¾79q;c r  ½!E#W¾79 tehát a típus nem felel meg a specifikációnak. 52 5. SPECIFIKÁCIÓ 5.5 Példák ~!V#&ÄTÅ.%FÆ 6

s±%FÇ4È· CEÉ ™ %FÊƃËGÌ 6 ™ ƃÍÉWÅFs
m!E#ÏÄTÅ.%FÆ 6   ÄTÅ%FÆ 6 s±6 %F™ Ç4ȝÀ ˜ s±%7Ç‹È  sf%76 Nj™ È   sf%76 Nj™ È£ËGÌ ˜ ƃs Ê.ÉΣÀÐCEÉ ™ %FÊÆÑ ËÌ ˜ Æ   ËÌ ˜ ƃs ÊWÉ.Σà 6 ™ ÍÉWÅ  s ÊWÉ.Î  s ÊWÉÎs±%7NjȷLËÌ ÆgÃ9 Legyen továbbá az Œ‰H állítás: „ — <$;  — G!  — zeneszerző . 1. példa: Legyen program. ˜ Ê.ÉÎ9 ,
H–nB    sf%7NjȣLCEÉ ™ %FÊ&ÆgÀ  CEÉ ™ %FÊ.ƃÄ^Å%2Æ 6 À  ÍÉWÅFLCEÉ ™ %2Ê.ÆgÀ Mi lesz a fenti program -hez tartozó leggyengébb előfeltétele? Megoldás: Írjuk fel először a program programfüggvényét: 5 
G!E#  ^Ä Å.%2™ Æ 6 Lsf%7Njȃ 6  sf%76 Nj™ È£LCE˜ É ™ %2ÊÆg€  s±%FÇ4È·Ls ˜ ™ ÊWÉΣƒ  sCE˜ É Ê.ÉF% ÎÊLƃËÄTÌ 6 ř %FÆg Æ ƒ 9 ËÌ ÆƒLs ÊWÉΣƒ ÍÉWÅFLCEÉ

%FÊÆgƒ EzekUután, előfeltétel definícióját felhasználva: 
a aleggyengébb ,!–#&Ä^Å.%2Æ 6 LÍÉWÅ2Ls ˜ ÊWÉÎ9 , ui 5 
  ÄT Å.%FÆ 6 Ò! #&s±%7Nj™ ÈN9  " †! #.CE6É ™ %FÊÆ 9  " 5
5  
s  ˜ ÍÊWÉ.ÉWΣÅÓ ! #&ËGÌ Æ 9  " 5 
G   s±™ %7Njȝ†! #.CEÉ ™ %F6 Êƃs ˜ ÊWÉÎ9(c  " 5
  CE É %F6 ™Ê&Æg†! #&Ä^˜ Å.%2Æ 9qc  " 5
 ËGÌ ÆgÑ! #&s Ê.ÉÎ9(c " 2. A t LA u 7–› . Igaz-e, hogy ha minden
O[$‚ L programra példa: 
AetƒGLegyen ! 
A>u4 , akkor  Aet ,!  A>u‹ ? Megoldás: Felhasználva, hogy a leggyengébb előfeltételek minden programra megegyeznek, egy alkalmas program választásával a válasz egyszerűen megadható: rendelje az program az állapottér minden eleméhez az önmagából álló egy hosszúságú sorozatot. Ekkor könnyen látható, hogy

tetszőleges utófeltétel esetén:
Ekkor viszont J
L !Hq: Aetb!   
Aet€!   
A>u‹k![A>u‰ tehát a két feltétel megegyezik. H![O*ÏrnlE< r$!–# g LԈ€  œ LÔ œ gi3‘Ô œ !yÔM  œ !  MPÔ¯ 9 3. példa: Specifikáljuk a következő feladatot: , 53 5.6 FELADATOK Megoldás: “!VÕ — ? ˜ sš!@—֜ o˜S œ =n  —— ! — —œ œ M ˜ ˜S! œ ˜7œ ˜ ˜Sœ Œ ! M NM !  4. példa: Legyen r¦“p ,
   L program, s egy tetszőleges halmaz Legyenek továbbá r t $nTs és r u Œs B olyan relációk, hogy r•!nr u xbr t , valamint „Nzd<s : .= × { }! r t  t  z€  ,{g}! r u  z€€: × 
 {g , akkor
megoldja r -et? Igaz-e, hogy ha „Nzd<sV =K{GI Megoldás: Próbáljuk meg a megoldás definíciója két pontját belátni. Legyen %eP) ‡ Be kellene látnunk, hogy %e*)"+W-X/F1 . Nézzük meg a specifikáció tételének

bizonyítását:  × ott felhasználtuk, hogy ekkor van olyan zeOs , hogy %Y = {  . Igaz ez a = { -re is? × Sajnos – mivel = { -t ősképpel definiáltuk, ez nem feltétlenül van így. Próbáljunk a fenti gondolatmenet alapján ellenpéldát adni:     Legyen  !Õ#F½‘9 , sš!Õ#F½‰ ¾79 , r!Ø# ½2‹½. 9 , rte!Õ# ½‰‹½ƒ ½‰ ¾‰ƒ9 , rZuh!Õ# ¾ˆ‹½&ƒ9 × 6 × 6 Ekkor =fti!Hȯ%FÙPÌ és =Kud!Hȝ%FÙ*Ì , tehát az állítás feltételei teljesülnek függetlenül a programtól (ui. “hamisból minden következik") Válasszuk most az alábbi programot:
Š!~#  ½2‹Ú$½‰4½‰4:Û:X:Üdƒ9 . Ez a program nem megoldása a feladatnak, de teljesülnek rá is az állítás feltételei. Tehát az állítás nem igaz 5.6 Feladatok 1. Legyen  =  2H@  Ìk‚Ý . Igaz-e, ha „»Ì<ÝH =£I¦=XÞ t  tetszőleges állapottér,  RSÎ<Ý? 
L=KŽ7G! J
  R7Î<ÝH =Žˆgß  

  2. Igaz-e, 
·u‘hogy? ha
£t&L K!
NuW , akkor
£t8à^
·u‘K!
wt&Q UJ
t gá  # ˜ 9Wga,⠗ U
u gá  # ˜ 9Wg  , akkor 3. Igaz-e, ha „ —  ˜ Tn — )"+W-X/ § 1!l),+W-X/WãL1 ? 
t LATf! 4. 
t  
u Vp,  programok Igaz-e, ha „»Aä“Ñ esetén
u A^ , akkor
t ekvivalens
u -vel? akkor 54 5. SPECIFIKÁCIÓ –!yå8å^G állapottér  åŒ!$#2½2L¾ˆæS9W és a s~!yå`å r t és r u feladatok. r t !$#  % t L% u   ƒ  z t  z u  Ԉg83&Ô>!  % t ÜO% u  9F 5. Adott az továbbá az paramétertér, r u specifikációja pedig: “! åÒ åÑ?  %t %u s@! åҜ  å œ %t %u  =n  % t ![ % œt MP % œ u !y% œ œu  ~ =OM ! % t ÜO% u g Azonosak-e az r t és r u feladatok? 6. Tekintsük az alábbi két feladatot: rt specifikációja: “! ”“— –”˜ s@!—” œ =n  — ! ——œ  ˜ çk˜ ~ =OM !n3 3  r u !E# g

%Lz€€  Ǒè7g`3&Çi!y%,M3 è3 ç è±!yÇW92: Megadható-e valamilyen összefüggés rt és rwu között?  7. Írd le szövegesen az alábbi feladatot: legyen 2”m›” , “!›”ÖE” EÝZ é Ù Î s@!”Óœ “” œ Ù Î  =n  Ù!O Ù œ M*ë Ž ΂![ Î œ MeÙêlΣ ~ =OM ! Ûì tFí Ì|g ahol ‰”m’#.½‰9 , í  Ìa! ï ½‰ ha R — ‚”;  Ì|! — Me„ˆð>ñ Ù:Û: λò£  ðF8êlق îˆ különben í 8. Igaz-e a specifikáció tételének megfordítása? (Ha
megoldja r -et, akkor „Nz s =K{GI J
L,{g 5.6 FELADATOK 9. Tekintsük az alábbi feladatot: 55 “!”E” Ô 5 sš!” œ Ô  =~  Ô(!HÔ œ MPî> ÚlԈ Œ =OM±5¯Ê.Ì Ù 5·Me„ÌGÜH½€5Ê&Ì Ù  Ì|ó3 Ôqô^̀3F¤$3 Ô±ôP5Z3    ahol 5Ê.ÌJÙ — G! — prímszám   ½&½. és a zq!  õ  ö‰ pontokhoz? Mit rendel a fent specifikált feladat az %! Fogalmazd meg szavakban a

feladatot! 56 5. SPECIFIKÁCIÓ Elemi programok Ebben a fejezetben bevezetünk néhány egyszerű programot. Ezeket a programokat a következő fejezetekben gyakorta fogjuk használni, ezért megvizsgáljuk a programfüggvényüket, és egy adott utófeltételhez tartozó leggyengébb előfeltételüket. 19. DEFINÍCIÓ : E LEMI PROGRAM Eleminek nevezünk egy
állapottéren egy  programot, ha 
   "!#%$!( & *)+ Az elemi programok közül is kiválasztunk néhány speciális tulajdonsággal rendelkezőt, és a továbbiakban csak velük foglalkozunk. Az első ilyen program, az üres program lesz, ami nem csinál semmit. 20. DEFINÍCIÓ : SKIP SKIP-nek nevezzük azt a programot, amire 
,-/.102  ( 3)4+ A második program a törlődés, aminek legfontosabb jellemzője, hogy soha sem terminál. 21. DEFINÍCIÓ : ABORT ABORT-tal jelöljük azt a programot, amire 5
,-
#68739

:; 57  ( 4 "*3)+ 58 6. ELEMI PROGRAMOK Az eddig felsorolt két elemi program segítségével még bajosan tudnánk egy adott feladatot megoldó programot készíteni, hiszen egyrészt nem túl sok olyan feladat van, aminek az
#68739-: program megoldása lenne (vajon van ilyen egyáltalán?) és a /.<042 program is csak egy nagyon szűk feladatosztálynak lehet megoldása (melyek ezek a feladatok?). A harmadik – és a programozási feladat megoldása szempontjából legfontosabb – speciális elemi program az értékadás. 22. DEFINÍCIÓ : É RTÉKADÁS  >?
#@ , A Legyen
(
-=8> program általános értékadás, ha ( BA/= +++ AC@ , ahol AED 
F>G
#D . Az  @  T !  O)^] R A DVUC=XWZY[ @ T  #^$  1 ` )
SR DVUE= WZY[  A definíció alapján könnyen látható, hogy az A
?>3
relációra fennáll az alábbi  (  IHKJML N*O! #IP$O!Q
SR tulajdonság: b@ ,

DcUE=  WZY W Y[ X ( X    a  A A = >dACe > >fA @ a ( A fenti A D komponensrelációk tehát pontosan azt írják le, hogy az adott értékadás miként változtatja meg az állapottér egyes komponenseit. 23. DEFINÍCIÓ : A Z ÁLTALÁNOS ÉRTÉKADÁS SPECIÁLIS ESETEI a Ha (
, akkor az  programot értékkiválasztásnak nevezzük, és      Y jelöljük. A W -val a Ha az A reláció függvény. akkor az  programot értékadásnak nevezzük,   és  ( A -val jelöljük. a Ha
, akkor  parciális értékkiválasztás. a Ha WZY g
és A determinisztikus (A parciális függvény), akkor  parciY g ális W értékadás . Ha egy kivételével az összes A D projekció – azaz az értékadás az állapottérnek csak egy komponensét (csak egy változó értékét) változtatja meg –, akkor  -et egyszerű értékadásnak, egyébként szimultán értékadásnak nevezzük. Az értékadás egy kicsit bonyolultabb mint előző két társa, de egy

kicsit “értékesebb" is, hiszen értékadással minden feladat megoldható! A kérdés persze csupán az, hogy az éppen adott feladat által definiált értékadás megengedett művelet-e. Ezzel a 59 kérdéssel a későbbiekben – a programozási feladat megoldása során – fogunk foglalkozni. Vizsgáljuk meg a fent definiált speciális elemi programok programfüggvényeit! 6. TÉTEL : E LEMI PROGRAMOK PROGRAMFÜGGVÉNYE L4l hCi/.102 (kj , 2. hCB
#68739-: (m ,  I ( A , 3. hC  ( A   I ( A . 4. hC  A 1. A tételt bizonyítása triviális, ezért itt nem bizonyítjuk (a feladatok között szerepel). Most, hogy megvizsgáltuk a programfüggvényeket, nézzük meg az elemi programok adott utófeltételhez tartozó leggyengébb előfeltételét. Mivel a SKIP program programfüggvénye az identikus leképezés, egy tetszőleges 9 utófeltételhez tartozó leggyengébb előfeltétele: nio  ip.<042 9 ( 9 + Hasonlóan egyszerűen látható, hogy

– mivel az
6;739-: program programfüggvénye üres – a leggyengébb előfeltétel definíciója alapján egy teszőleges 9 utófeltétel esetén nqo  B
6;739-: 9 (sr 4t jvu + Az általános értékadás leggyengébb előfeltételét külön vizsgáljuk a determinisztikus és nem determinisztikus, illetve a globális, és a parciális esetben. Legyen Aw
xy
függvény. Ekkor z nqo  ( { v|   A 9 P z | ) ( A 9 z |M ( z K| ( z |4+  = € A8}~ 9 A ~ = 9 8 9‚PA M ( (
$ Ha A parciális függvény, akkor az általa definiált értékadás is parciális, melynek leggyengébb előfeltétele: z nqo  ( { v|   A 9 $  z |)^ƒ ( A 9 z z | M ƒ + ( A } ~ =€ 9 ( A ~ = W Y 9 |Mƒ W Y W Y ( Most vizsgáljuk azt a két esetet, amikor A nem determinisztikus. Feltéve, hogy WZY
, az értékkiválasztás leggyengébb előfeltétele z nio   z |M{+ { „| (   $ P z |) (  A 9
A 9 A ~ = 9 ( M
Ugyanez parciális

esetben: z nqo   { v| ( M $  z |)^ƒ  A 9
A 9 WZY ( A ~ = z 9 |Mƒ + WZY 60 6. ELEMI PROGRAMOK Az értékadást általában változókkal írjuk le. Legyenek az állapottér változói rendre  +++   = e @ . Ekkor az  ( A program jelölésére az alábbi formulát használhatjuk =  e +++† @ ( A = =  e +++† @ † ACe =  e +++ @ †+++ A @ =  e +++ @ {+ A gyakorlatban az esetek többségében A komponenseinek nagy része projekció, azaz  +++ + @ (  D ++Ekkor A D = e az értékadás jelöléséből a bal oldalról D -t , a jobb +† @ -t elhagyjuk. Vegyük észre, hogy egyszerű értékadás oldalról pedig A D = e esetén a bal oldalon csak egy változó, a jobb oldalon pedig csak egy kifejezés marad. Jelölésünket abban az esetben még tovább egyszerűsíthetjük, ha az értékadás jobb oldala ( A D ) nem függ minden változótól. Ekkor a jobb oldalon csak azokat a

változókat tüntetjük fel, amelyektől A D függ. Nézzük meg egy egyszerű példán a fent leírtakat: Legyen az állapottér
(ˆ‡ >s‰ n A továbbiakban a fentihez hasonlóan az állapottér egyes komponenseihez tartozó  ( változókat  "  a komponensek alá fogjuk írni. Legyenek az értékadás komponensei: = e
:   A = = e    ACe = e Ekkor az   HŠ = azaz A = ( h és  N‹†+ = ( (  (  értékadás változókkal felírva:   A n (   ‹4{+  A jelölés fent leírt egyszerűsítéseit elvégezve az n (  ‹ egyszerű értékadást kapjuk. Ha felhasználjuk, hogy az értékadás leggyengébb előfeltétele 9Œ‚A , akkor egy változókkal felírt értékadás változókkal megadott előfeltételét egyszerűen kiszámíthatjuk: helyettesítsük az utófeltételben az értékadásban szereplő +++† változókat az új értékükkel. @ rendre az állapottér váltoErre bevezetünk egy új jelölést is:

legyenek = e zói. Ekkor nio DŽ +++ +++† †+++ +++ { VD s ( E A DŽ = @ AEDc = @ 9 €  "  ” ’ ” “ ” “ “ ’ ” ’ ” “ ” “ “ ’  "  ” ’ ” “ ” “ “ ’  93 [ {‘ Y }   •  [ ‘ Y }  • € ( 6.1 Feladatok 1. 4–O—˜) ( M*O! )O™ ( (  – x
› – œ{( O — › ————6 +++Iœ{˜ › ˜–MœO)
š><6 . Legyen  program
-n,  . x x ™ ™ Legyen  = az  kiterjesztése -re,  pedig olyan program -n, hogy  ekvivalens  -sel
-n. 61 6.1 FELADATOK (a) elemi program-e  ? (b) elemi program-e  = és biztosan elemi program-e  ? 2. Tekintsük az alábbi állapotteret:
(Fž > ž Mi az "¡¢ Ÿ (  Ÿ {  {      A A ( BA/= A e / A = Ÿ ( Ÿ A e  Ÿ ( , azaz az Ÿ utófeltételhez ( K !Q
$ †! ( ¡ R Ÿ †! ( h ) értékadás 9 ( A h Ÿ tartozó leggyengébb előfeltétele? 3. Legyen
tetszőleges állapottér Melyek azok a

feladatok az megoldása a /.102 program?
-n, amelyeknek 4. Legyen
tetszőleges állapottér Melyek azok a feladatok az megoldása a
#68739-: program?
-n, amelyeknek 62 6. ELEMI PROGRAMOK 68 7. PROGRAMKONSTRUKCIÓK 7.4 A programkonstrukciók és a kiszámíthatóság Ebben az alfejezetben kis kitérőt teszünk a kiszámíthatóság-elmélet felé, és megmutatjuk, hogy az imént bevezetett három programkonstrukció segítségével minden – elméletileg megoldható – feladatot meg tudunk oldani. Ehhez kapcsolatot létesítünk a kiszámítható függvények és a “jól konstruált” programok között. 7.41 Parciális rekurzív függvények 
 A Church tézis szerint a kiszámítható függvények halmaza megegyezik a parciális rekurzív függvények halmazával. A kiszámíthatóság ezen modelljében csak típusú függvények szerepelnek. Először az alapfüggvényeket definiáljuk:   
  "!$#%&

(
*) +-/, .       / 0001  
2  : -/, 3.   / 0001  !4%3 (
  56
879%30:0 ; <>=?@ , .       / 000A1  
  <B= @ , .   / 0001  "!C @ 0 : : A továbbiakban definiálunk néhány elemi függvény-operátort:  6J . Az és H kompozíciója az H
I  G LH K M
2 NO J , PLQARTS !4U
PVSXW  Y
PZQ&[ és 
ZP QRTS :  HLK ]  ! H   1A0 D
E FG  Kompozíció Legyen alábbi függvény: és Vegyük észre, hogy ez az operátor megegyezik az alapfogalmaknál bevezetett relációk közötti kompozícióval (tulajdonképpen a szigorú kompozícióval, de függvények esetén ez a kettő azonos).
 rögzített, és 5
`79%30:0 ^ ;  @
N ab c . E függvények ^ def000T J g
hij &k2lDmmmnl  3o  P S kTp S1q psrsrsr p S o. ! t J PVS c és uniója  / , @:u / 
P S k p S q psrsrsr p S o . : ,  / Tfe000Ad J  "!  / 

A000T J  1A0 v
6hw és H
 x e w . Az függvény H Rekurzió Legyen rögzített,  
2 x / O , és szerinti rekurziója y  H   / 0001  A y   H  0 0/ 0A1 000 1 #|%z%z{!  ^ {! H   / 000}   ^  y   H   / 000A}   ^ 1A0 y H  / Unió Legyen A függvényhez hasonlóan rekurzívan definiálhatnánk ennek a függvénynek az értelmezési tartományát, de ez kívül esik a jelenlegi vizsgálódásunk körén. Ezért csak azt mondjuk, hogy az értelmezési tartomány azon pontok halmaza, ahonnét kiindulva a fenti rekurzió elvégezhető. 69 7.4 A PROGRAMKONSTRUKCIÓK ÉS A KISZÁMÍTHATÓSÁG  ]
h   W
    000}  és  / 2 -operátor Legyen azt a
4 3x /  . A -operátort erre a függvényre alkalmazva    függvényt kapjuk, amelyre P
S . ! U   / 0001 
  000A1  !4% 5
79%30:0  %A; $,   / 0001  15 
PVS [ , 
/ P
S . : 

 ,  ]   / 000A1  ! 5 U  W   / 000A}    !4% [ 0 A fenti alapfüggvények és a bevezetett operátorok segítségvel már definiálható a parciális rekurzív függvények halmaza.        6
6 28. DEFINÍCIÓ : PARCIÁLIS REKURZÍV FÜGGVÉNY Az függvény akkor és csak akkor parciális rekurzív, ha az alábbiak egyike teljesül: az alapfüggvények valamelyike kifejezhető a fenti operátorok parciális rekurzív függvényekre történ ő alkalmazásával. 7.42 A parciális rekurzív függvények kiszámítása  "   Ahhoz, hogy a fenti függvényeket kiszámító programokat tudjunk adni, definiálnunk kell az ilyen függvények által meghatározott feladatot. Legyen egy tetszőleges függvény ( rögzített). Az által meghatározott feladat specifikációja: 1 !  l 000 l  l  l 000 l  /  /  !  l 000 l  /   >  / ! /  mmm g  !     / 0001  Y
VP S  >    /

000   !h   / 0001  } Most megmutatjuk, hogy minden parciális rekurzív függvény által meghatározott feladat megoldható “jól konstruált” programmal (jól konstruáltnak tekintünk egy programot, ha elemi programokból a fenti három konstrukcióval megkapható). A bizonyításhoz csak annyit kell feltételeznünk, hogy az alapfüggvények kiszámíthatók (megengedett) elemi programokkal A fenti feltételezést felhasználva elegendő azt megmutatni, hogy az elemi függvény-operátorok (kompozíció, unió, rekurzió, -operátor) kiszámíthatók jól konstruált programokkal. Kompozíció E
( i   H
   6J . Ekkor az HZK !  l 000 l  l  l 000 l  /  / J !  l 000 l     /   Legyen specifikációja: és által meghatározott feladat 70 7. PROGRAMKONSTRUKCIÓK  >  / | !  /  mmm g   !     >     / 000   !  ZH K ]     / 0001  
PZQRTS / 000A1  } 000 !

 0001 Jelöljük / 000A   !  / 000  -mel azt a programot, amely kiszámítja -et,  -nel azt, amelyik kiszámítja H -t. Tegyük fel, J  H / és hasonlóan  / hogy ez a két program vagy elemi értékadás, vagy jól konstruált program. Ebben az esetben a két program szekvenciája kiszámítja H K -et, azaz megoldja a fent speci  


fikált feladatot. Legyen előfeltétele:
a második program utófeltételhez tartozó leggyengébb   >   H  / 000  "!  ZH K ]   / 000}    / 000  Y
P Q   utófeltételhez tartozó leggyengébb előMost vizsgáljuk meg az első program ezen 
feltételét: 
 /  000A  HLK ]   


 0 !v00A}   /  2 0001  / 
 A00 0A}  ! 
   H      / 0000001}   
1"! /  P Q  /  P S  Könnyen látható, hogy ez a leggyengébb előfeltétel következik -ból, és így a szekvencia levezetési

szabálya és a specifikáció tételének alkalmazásával beláttuk, hogy a
/ 000A   !h    / 000  J  ! H 

/ 0001  / 000A 
program megoldja a fent specifikált feladatot, azaz kiszámítja Unió
 ^  !  l 000 l    l  / l 000 l   // /k . l .  l 000 l  !   J / l 000 l  J 3o  /    >  / !| /  mmm g   >     / / 000A  /  k és H kompozícióját. 5V
97 %30:0 ^ ;  @
 O  c . Ekkor az e függvények l Legyen rögzített, és uniója által meghatározott feladat specifikációja: !      / 0001  
P S k psrsrsr p S o .  000  J / 000A  J  o "!  / 00, A0 d J   / 000A1  1 Tegyük fel, hogy a komponens függvények 000kiszámíthatók   @  c  ! @   / jól00konstruált 0}  az 5 prog@ / rammal, vagy elemi értékadással. Jelölje -edik  % |5 ^ kiszámító programot. Ekkor ezeknek a programoknak a

szekfüggvényt    utófeltételhez venciája megoldja a fenti feladatot. Legyen J a ^ -adik program tartozó leggyengébb előfeltételét:  J >    / / 000  / ?k 000  J / / 000A  J /  o k d J   / 000A}  1 !  / 000T J   / 000}     / 0001  
PVS o     71 7.4 A PROGRAMKONSTRUKCIÓK ÉS A KISZÁMÍTHATÓSÁG 5
v7 %&090 ^ %;  @ 5  @x / Továbbá minden esetén jelölje az -edik program -hez tartozó leggyengébb előfeltételét. Könnyen látható, hogy az értékadás leggyengébb el őfeltételére vonatkozó szabályt alkalmazva:  / >   /   / 0001  A000T J   / 000A1  } !  / 000d J   / 0001     / 000}  Y
PVS k  mmm    / 000}  Y
PVS o   Ha most -t és / -et összehasonlítjuk, észrevehetjük, hogy megegyeznek. A szekvencia levezetési szabálya és a specifikáció tétele alapján a  / / 000 

/ ?k  !v /   / 000A1  . . ! J   / 0001   J / 000  J  o  h program megoldása a fent specifikált feladatnak, azaz kiszámítja Rekurzió  /  000d J -t. e   H
 x 
4  j Legyen rögzített, és . Tegyük fel, hogy mindketten kiszámíthatók jól konstruált programokkal vagy egyszerű értékadásokkal Az függvény szerinti rekurziója által meghatározott feladat specifikációja: H !  l 000 l  l  /  3x /  !  l 000 l  / 3x /  >  / ! /  mmm g x / !| x /    / 000A} x / 
P
S p Q . ,  >   ! y   H   / 0001 3x / } !   / 0001  illetve   ! Jelölje az ez -et és a H -t kiszámító programot       0  0  0 1   x . Oldjuk meg a feladatot egy olyan ciklussal, amelynek invariáns tuH / lajdonsága:  >   ^
87 %&090  x / ;   ! y   H   / 000}   ^ 1      A ciklus levezetési szabályát

vizsgálva azt találjuk, hogy -ból nem következik . Ezért adunk egy olyan feltételt, amelyből már következik , és adunk egy programot, amely -ból -be jut (így a megoldóprogram egy szekvencia lesz, amelynek második része egy ciklus). Legyen az alábbi:       >   ^ ! %  !h   / 0001  1  !F%3d   / 000}  szimultán értékadással elérhető. Az értékadás legEz a ^   gyengébb előfeltételére vonatkozó szabály felhasználásával könnyen látható, hogy az  következik -ból. !  3x / A ciklus levezetési szabályának második pontja alapján a ciklusfeltétel ^  !N x / D^ lesz. A harmadik pontnak megfelelően válasszuk a kifejezést termináló függvénynek. Az ötödik pont azt írja le, hogy az imént definiált termináló fügvény értékének a ciklusmagban csökkennie kell. Ez elérhető a eggyel való növelésével ^ 72 7. PROGRAMKONSTRUKCIÓK  A négyes pont kielégítéséhez vizsgáljuk

meg, hogy mi lesz a leggyengébb el őfeltétele a -t növelő értékadásnak a -re vonatkozóan. ^   ! !    ^ #|%Z
79%30:0  x / ;   ! y   H   / 0001   ^ #|%z1A0 Most már – a szekvencia szabálya alapján – csak egy olyan programot kell !h    ^ levezetési találnunk, amelyre  !    x / 000A}        . Ez a program a rekurzió definíció ^  lesz jához illeszkedően épp  H /   ^  ! ^ #|%3  
 Így a szekvencia és a ciklus levezetés szabálya valamint a specifikáció tétele garantálja, hogy a ^   !  ! y   H program megoldja a rekurzióját. %&d   / 000A1  ^ !|   x / H   / ! 000#|} %   ^   ^  ^ által meghatározott feladatot, azaz kiszámítja H szerinti -operátor
 x /   ] Legyen , és tegyük fel, hogy vagy jól konstruált programmal. Tekintsük a kiszámítható egyszerű értékadással által meghatározott feladatot: !  l 000 l  l

   !  / l 000 l     /    >  / !| /  mmm g  !|     / 000A} x / 
P
S . ,  >    !  ]   / 000A1  1 !v   / 0001  1 x / az -et kiszámító programot. Oldjuk meg a felaJelölje  datot egy olyan ciklussal, melynek invariánsa:  >  !h   / 000A}     5
87 %&090  %A;    / 000}  }5 !  %z  !b   / 000}  %-% szimultán értékadással teljesíthető. Az invariáns a   


Könnyen látható, hogy ennek a programnak a tele      !|   / 000A1   %-%   
 ! % 4   / 000}   M!a%  !  ! -re vonatkozó leggyengébb el őfelté-     / 000}  %z6!v   / 000A}  5
87 %&090:% %;    / 0001  15   %z !  %z következik -ból. A ciklus levezetési szabályának második pontja alapján a ciklusfeltétel
lesz. A feladat előfeltétele garantálja, hogy van olyan szám, amelyre

fennáll. Legyen  egy ilyen tulajdonságú, rögzített természetes szám Ennek az értéknek a segítségével definiálhatjuk a termináló függvényt:  . Ez kielégíti a levezetés szabály harmadik pontját Az ötödik pont megkívánja, hogy a termináló függvény a ciklusmag lefutása során csökkenjen. Ezt elérhetjük eggyel való növelésével 
 73 7.4 A PROGRAMKONSTRUKCIÓK ÉS A KISZÁMÍTHATÓSÁG A negyedik pont teljesítéséhez legyen leggyengébb előfeltétele:   ennek a növelésnek a !h   / 000A}    #|%z  5"
79%30:0     Most egy programot a ! h már  / csak 0001találnunk     #|%z kell értékadásra teljesül, hogy    !  % $ !v   / 0001    > 





 -re vonatkozó %;    / 0001  15 !  %z !  %- és   állítások közé. A   #|%zA   A specifikáció tétele, valamint a ciklus és a szekvencia levezetési szabálya garantálja, hogy a


   !|   / 000}  %-% !4  %  !v   / 000A1    #%  !  #%

program megoldja a ] által meghatározott feladatot, azaz kiszámítja  ] -et. 7.43 Következmény Az előzőekben megmutattuk, hogy ha az alapfüggvények kiszámíthatók egyszerű értékadással, akkor a belőlük – a parciális rekurzív függvényeknél megengedett – operátorokkal felépített függvények kiszámíthatók jól konstruált programokkal. A Church tézis szerint a kiszámítható függvények halmaza megegyezik a parciális rekurzív függvények halmazával. Ezek alapján kimondhatjuk az alábbi tételt: 17. TÉTEL : S TRUKTURÁLT PROGRAMOZÁS ÉS KISZÁMÍTHATÓSÁG Minden kiszámítható függvény kiszámítható egy jól konstruált programmal. 7.44 Relációk Eljutván az előző tételhez, fordítsuk most figyelmünket a relációk felé. Ahhoz, hogy a relációk kiszámíthatóságát megvizsgálhassuk, definiálnunk kell a kiszámítható

reláció fogalmát. 
6J l 6J  29. DEFINÍCIÓ : R EKURZÍVAN FELSOROLHATÓ RELÁCIÓ Legyen tetszőleges reláció. akkor és csak akkor rekurzívan felsorolható, ha van olyan parciális rekurzív függvény, amelynek értelmezési tartományára: . (
 e J   P S !  A kiszámíthatóság-elmélethez igazodva, a továbbiakban csak rekurzívan felsorolható relációkkal fogunk foglalkozni. Ahhoz, hogy megmutassuk, hogy minden kiszámítható (rekurzívan felsorolható) feladat – emlékezzünk, hogy minden feladat egy reláció – megoldható strukturált programmal, először megadjuk a rekurzívan felsorolható relációk egy másik jellemzését.  18. TÉTEL : K LEENE [1936] Ha egy tetszőleges reláció, akkor az alábbi három állítás ekvivalens: (1)  rekurzívan felsorolható 74 7. PROGRAMKONSTRUKCIÓK (2) (3)    !
egy parciális rekurzív függvény értékkészlete vagy  egy  rekurzív függvény értékkészlete.  Ennek a

tételnek a bizonyítása lásd Ref??? konstruktív, azaz megadja mind , mind pedig felépítését. Mi ezt a függvényt fogjuk használni a kiszámítható feladatunk megoldóprogramjában. Legyen egy rekurzívan felsorolható reláció, és jelölje az előző tétel konstrukciójával kapott (totális) rekurzív függvényt. Specifikáljuk a feladatot az alábbi módon:  6J l 6J  ! 6 J l 6J  !`6J    > 2!C   
 >    n  Y
 P Ez a feladat megoldható egy olyan ciklussal, amelynek invariáns tulajdonsága:  > g5"
     6!   5 } 
A ciklus levezetési szabályának felhasználásával könnyen belátható, hogy az alábbi program megoldása a fenti feladatnak: 5T     ! %3   %z !  C     !   5 #|%z 5  !C5]#% 


A bizonyításban a termináló függvény megadásánál ugyanazt a technikát alkalmazzuk, mint a -operátornál. Ezzel az előzőleg függvényekre kimondott tételünket

általánosíthatjuk relációkra: 19. TÉTEL : S TRUKTURÁLT PROGRAMOZÁS ÉS KISZÁMÍTHATÓ RELÁCIÓK Minden kiszámítható reláció kiszámítható egy jól konstruált programmal. Megjegyzés Az egyetlen feltevés, amit a fenti meggondolásokban használtunk az volt, hogy az alapfüggvények kiszámíthatóak. Így aztán ezek az eredmények kiterjeszthet ők a relatíve kiszámítható függvények (ugyanezen operátorokkal egy tetsz őleges alaphalmazból képzett függvények), vagy a parciális rekurzív funkcionálok halmazára is (Ref[1, page 174]). Típuskonstrukciók Az előző fejezetben megvizsgáltuk, hogy milyen lehetőségeink vannak meglevő programokból újak készítésére. A továbbiakban azt fogjuk megvizsgálni, hogyan használhatunk fel meglévő típusokat új típusok létrehozására Ezeket a módszereket típuskonstrukciós módszereknek, az általuk megkapható típusokat típuskonstrukcióknak nevezzük. 8.1 A megengedett konstrukciók

Természetesen sokféle lehetőségünk van meglevő típusból újat csinálni, de mi a továbbiakban csak három speciális típuskonstrukcióval fogunk foglalkozni: a direktszorzattal, az unióval és az iterálttal. Ezeket fogjuk megengedett típuskonstrukcióknak nevezni. Az első típuskonstrukciós módszer, amivel megismerkedünk a direktszorzat. Legyenek
      típusok, és jelöljük !"#$!&%$!&( -nel a nekik megfelelő típusértékhalmazokat, és )*"#)+%$)+( -nel pedig a hozzájuk tartozó elemi típusértékhalmazokat, és vezessük be az ),-)*"/.0)+%1322245)+( és 6 !"*7!8%179222:7!8( jelölést. 32. DEFINÍCIÓ : D IREKTSZORZAT A
;;<=>? típus direktszorzata a
" 
% $
( típusoknak, ha 1A@CBEDGFCB 85 86 8. TÍPUSKONSTRUKCIÓK ahol @CBIHJ6K7! , FLBMHN)PO176 FCB és Q=SRTGUV) O 76XWYZ[U]^  8`a=b=RLU)  O

a>SR$TcdeUf#g RhAij#[SRk" <R(:clk  A direktszorzat értékhalmazára bevezetjük a !3mn!" !&% !&(: jelölést. Ha a @ B leképezés kölcsönösen egyértelmű, akkor a direktszorzatot rekord típusnak nevezzük. A direktszorzat típusok általában rekordok, de nem mindig Például tekintsük a racionális számok halmazának egy lehetséges reprezentációját: 6o3pN7Vp , @CBIHJ6K7Vq : $nr$s:c t uUV@CB3vxwys{A z |+g}tL3r8~#s Egyszerűen látható, hogy a fent definiált @CB reláció a racionális számok halmazát reprezentálja, de nem kölcsönösen egyértelmű. ! t !" 6 )PO !&% t$" t<%  "  % !& !&( @CB  t<( t<    ( F B 8.1 ábra Rekord konstrukció Nagyon fontos továbbá, hogy az új típusértékhalmazt (! ) ne keverjük össze a közbülső direktszorzattal ( 6 ), hiszen egy adott 6 és ! között nagyon sokféle @CB leképezés megadható, és az

új típus szempontjából egyáltalán nem mindegy, hogy ezek közül melyiket választjuk. Tekintsük például a komplex egészek ( €xAT€‚T}UAp alakú számok) halmazát. Legyen továbbá 6mAp57Vpƒ$r s„Up , és @ [ s †   B  n r? : @CBC‡= n r? : s †   rEs4 s15r‚ A két @CB közötti különbség elsősorban akkor válik szignifikánssá, ha például a komplex egészek közötti szorzásműveletet kell implementálnunk a számpárok szintjén, hiszen ekkor az első és a második komponens értékét az ˆ€1JT<ˆi[E‰k<[;ˆ€=i‹Š0Tc‰4Œˆ€4‰/JTci  87 8.1 A MEGENGEDETT KONSTRUKCIÓK formula alapján különböz ő módon kell kiszámítani. A következő módszer, amivel régi típusokból újakat hozhatunk létre, az unió. Legyenek
C;<#$$$$?^Gn[k:c  típusok, és jelölje !"Ž !&%$!8( a hozzájuk tartozó típusértékhalmazokat, illetve

)/"#$)%$)+( a nekik megfelelő elemi típusértékhalmazokat. Vezessük be továbbá az )K)*".‘)+%‹]222Ž‘)+( és 6’!“"[V!&% 222.}!&( jelöléseket 33. DEFINÍCIÓ : U NIÓ Azt mondjuk, hogy a
;m 4$‚$” típus uniója a
>" ,
% ,  ,
( típusoknak, ha 1Œ@[•‘DGF[• ahol @ • HJ6’7}! , F • H–)PO17V6 és F • —Q=nR4T‹UV) O 7V6˜W#b4U]^  8`“a‚SRTGUf  l Az unió értékhalmazának jelölése: !Œn!"™ !&% ™™ !&( . Itt is külön elnevezést adtunk annak az esetnek, amikor a @[• leképezés kölcsönösen egyértelmű, ekkor az uniót egyesítésnek nevezzük. t<š t !" 6 )PO !&% t$" ! !& t% t   !&( @L•  t<(  ( F[• 8.2 ábra Unió konstrukció Ebben az esetben is nagyon fontos, hogy mindig megkülönböztessük a konstrukció közbülső szintjén levő uniót ( 6 ) az új típusértékhalmaztól (! ).

A harmadik megengedett típuskonstrukciós művelet az iterált, amellyel egy meglevő típusból alkothatunk új típust. Legyen
4›/; #›kc›=$“› típus, !8› a neki megfelelő típusértékhalmaz, és ) a
4› típus elemi típusértékhalmaza. 34. DEFINÍCIÓ : I TERÁLT Azt mondjuk, hogy a
;;<=>? típus iteráltja a
4› típusnak, ha 1Œ@CœeDGFCœ 88 8. TÍPUSKONSTRUKCIÓK ahol @CœƒHN6K7}! , FCœ„HJ)POh7}!1› O és F œ Q=SRT‹U) O 7! › O ŽW b=R " <R: ž:UV) O ‚ a SR  T  uUŸ › g RhMj#[nR"  R: ž$ l  Az iterált típusértékhalmazának jelölése: !Œ–¡tn!8›# . Az iterált típuskonstrukciónak három speciális esetét különböztetjük meg aszerint, hogy a @”œ leképezésre milyen feltételek teljesülnek. ¢ Ha a @Cœ leképezés kölcsönösen egyértelmű, akkor sorozat típuskonstrukcióról beszélünk, és típusértékhalmazát !3M£Ž¤Ž!8› -lal

jelöljük. ¢ Ha ¦G t cŽn§[$t eU‘@Cœ+¨¦EUª‚¤Ž«#¬]n§? akkor az iterált konstrukcót kombináció típusnak nevezzük. A kombináció értékhalmazának jelölése: !3Œij#¬9!8›Ž ¢ Ha ® ˆ¦$t c§[ t +U@Cœ+¨  ­‚ ^¯?" ® Q#¦?<l/  °‚  ¯?" Q§‚<lk akkor halmaz típuskonstrukcióról beszélünk. A halmaz típus értékhalmazának jelölése: !3M£Ž¤Žtn!8› . Természetesen az imént felsorolt három eset csak speciális formája az iteráltképzésnek; létezik olyan iterált is, amely egyik fenti kritériumot sem teljesíti. t ± 6 )PO  ›  › ! t " t % t  ^  t ²<´³  › @ œ !/› O   › 8.3 ábra Iterált konstrukció F œ 89 8.2 SZELEKTORFÜGGVÉNYEK 8.2 Szelektorfüggvények Az előzőkben definiált típuskonstrukciókra most bevezetünk néhány olyan függvényt és jelölést, amelyek leegyszerűsítik a rájuk vonatkozó állítások,

programok megfogalmazását. "¸ függvény komponenseit a ! rekord szeLegyen !Kµn!" !&%  !&( . A @GB ¶n· lektorfüggvényeinek, vagy röviden szelektorainak nevezzük. A fenti rekordnak tehát pontosan darab szelektora van, és ha £Ž -vel jelöljük az  -edik szelektort, akkor £ŽCa!Œ¹y!& , és Y8tUV!Ia@CBhˆ£ "t c£%=nt £Ž(&nt  G–tc Tehát a szelektorfüggvényeket arra használhatjuk, hogy lekérdezzük a rekord egyes mezőinek (komponenseinek) az értékét. A szelektorokat bele szoktuk írni a típusértékhalmaz jelölésébe; a fenti esetben a szelektorokkal felírt jelölés: !3mˆ£ "*a!"Ž£Ž%1a!&% £Ž(a!8(: A rekordtípushoz hasonlóan az egyesítéshez is bevezetünk szelektorfüggvényeket. Mivel az unió esetében a közbülső szinten a típusértékhalmazok uniója szerepel, így nincs értelme komponensr ől beszélni. Hogyan definiáljuk ez

esetben a szelektorokat? Azt fogják visszaadni, hogy egy adott ! -beli elemet melyik eredeti típusértékhalmaz egy eleméhez rendelte hozzá a @ • függvény. Legyen !ºy! " ™ ! % ™™ ! (  egyesítés típus, £  a”!»¹½¼n„¾  . Azt mondjuk, hogy az £  logikai függvények a T egyesítés szelektorai, ha YZ¿UX^  8`„a Y8tU! : £  t [ÁÀ@ •n¶ · "<¸ t ‹UV! ˆÂ  A rekordtípushoz hasonló módon az egyesítés szelektorait is bele szoktuk írni az új típusértékhalmaz jelölésébe. A szelektorokkal felírt típusértékhalmaz jelölése: !3mˆ£ " a! " ™£ % a! % ™™£ ( a! (  Az iterált típuskonstrukciók közül a sorozathoz definiálunk szelektorfüggvényt. A sorozattípusban a közbülső szinten ! › -beli sorozat szerepel, a szelektor ennek a sorozatnak a tagjait adja vissza. Formálisan: Legyen !’㎤#n!8›# . Az £{a!m79ÄX¹Å!8› parciális

függvény a ! "<¸ szelektorfüggvénye, ha YZtGUV!Ma#Y8[U]k^SW @Gœ ¶n· t W ` : £ktc <[3@Gœ ¶n· "<¸ nt <$ A sorozat szelektorát nem szoktuk külön elnevezni, helyette indexelést alkalmazunk, azaz az t<?A£=tc < jelölést használjuk. 90 8. TÍPUSKONSTRUKCIÓK 8.3 Az iterált specifikációs függvényei Ha az iterált típus az előzőekben bevezetett három speciális osztály valamelyikébe tartozik, akkor további függvényeket definiálunk hozzá. Legyen !A–¡tn! ›  , ˆ¦$t ‹UV@  , és tegyük fel, hogy az iterált sorozat, kombináció, vagy halmaz. Ekkor ‰kj#¬µak!3¹-Ä › , ÈÉ ‰kj#¬]nt ÇÆ W ¦‹W Ê ­‚ W QŽ¦” lWË  ¯?" ha !3A£¤#! ›  vagy !ŒAij#¬9! ›  ha !3A£¤Žt!Z›# A ‰=j#¬ függvény tehát a t elemeinek számát adja meg. A függvény jóldefiniált, ugyanis felhasználva a sorozat, kombináció és halmaz típus

definícióját, könnyen látható, hogy a függvényérték független az ¦ választásától. A továbbiakban a sorozattípussal fogunk foglalkozni. Ahol külön nem jelöljük, ott ± !3M£Ž¤#n!8› , ¦G t eUV@Cœ , ¦9 ¦L" ¦”:$¦‹ ­> ³ . ¢ Nem üres sorozat első és utolsó eleme: Ìj#Í¿a!A¹y! › , Î:¡Í¿a!3¹y! › , ˆÌ j#ÍZt Ï   Î>¡ÍZt Ï   ¦L" ¦  ­‚ ‹ ¢ Sorozat kiterjesztése a sorozat elején, vagy végén (legyen ¤IUÃ!8› ): ̈j ¤Žr>t0a !—7!Z›*¹Ð! , Î: ¤Žr>t‹a!—7!Z›¹-! , ± ̈j ¤Žr>tntc¤ Ç @ œ ij#[ ¤ ³c¦”$ ± Î: ¤Žr>ttc$¤ Å @ œ ij#[ˆ¦ ¤ ³ $ ¢ Nem üres sorozat első, vagy utolsó elemének elhagyásával kapott sorozat: Ìj#« ¤Ž¬µa !A¹y! , Î>¡« ¤¬Ña!3¹Ð! , ± Ìj#« ¤Ž¬9t Ç @Cœ= ¦”%k¦G ­‚ ³$ ± Î:¡« ¤Ž¬9t Ç @Cœ= ¦L"¦G ­‚

" ³$ · 8.4 A függvénytípus A gyakorlatban nagyon fontos szerepet játszik egy speciális rekordtípus. Legyen Ò egy tetszőleges (megszámlálható) halmaz, amelyen van egy rákövetkezési reláció. Jelöljük ezt a rákövetkezési relációt £ÓZii -cal, és inverzére vezessük be a ª>« ¤#‰ jelölést. 35. DEFINÍCIÓ : F ÜGGVÉNY TÍPUS Legyen ) egy tetszőleges típus értékhalmaza. Ekkor az Ô»Ñґ£Ž¤Žˆ)„  rekordot függvénytípusnak nevezzük, és ԗMÕZÓZ[ґ)„ -vel jelöljük A függvénytípusra is bevezetünk néhány fontos specifikációs függvényt. A továbbiakban legyen ԗMÕZӂ[ˆÒ‘$)PcG$ˆÎ t Õ&eUV@CB Ekkor 91 8.4 A FÜGGVÉNYTÍPUS ¢ ‰kj#¬¾aԗ¹-Ä?› , ‰=j#¬9dÕ&Œ‰=j#¬]nt  ¢ ÌjTakԍ¹ÐÒ , ÌjT dÕ&LAÎ ¢ Î:<Taԗ¹-Ò , Î> TˆÕ&LA£Ó8iiÖc×$Ø ¶ Ù ¸ · " d΂ ¢ Ìj#Í¿aԍ¹Ð) ,

̈j#ÍZdÕ&[ŒÌˆj#ÍZt  ¢ Î:¡Í¿aԍ¹Ð) , Î>¡ÍZdÕ&[AÎ>¡ÍZt  ¢ Ìj ¤Žr>tcÎ: ¤Žr>tGaԘ7);¹ÐÔ , Ìj ¤Žr‚tˆÕZ$¤ Ç   Î>¡¤Žr‚tˆÕZ$¤ Ç   @”B„˪>« ¤#‰ZˆÎZc$̈j ¤Žr>tntc¤   @”B„ˆÎÎ>¡¤Žr‚tntc$¤ $ ¢ Ìj#« ¤Ž¬fÎ:¡« ¤Ž¬µaԍ¹ÐÔ , Ìj#« ¤Ž¬]ˆÕ&Ï Î>¡«#¤Ž¬]ˆÕ&Ç @”B„ˆ£ÓZiiˆÎZcÌj#« ¤Ž¬9t   @”B„ˆÎÎ>d« ¤Ž¬]nt   A sorozathoz hasonlóan a függvénytípusra is bevezetünk egy szelekciós parciális függvényt. TekintsÜk a fentiekben használt Õ -et Ekkor £ a‹ÒϹÚ) , Û„Ü ÝE Ù Q £Ó8ii  ÌjTˆÕ& ‹WŽ|ÞJ[ߖ‰=j#¬9dÕ&l , és ha à¿U}Û Ü Ý , àxA£Ó8iiá:ÌjTˆÕ&  , akkor: £ n àG–t ácâ " Ù A függvénytípus szelektorfüggvényét nem szoktuk külön elnevezni, helyette a matematikában

– a függvény helyettesítési értékének jelölésére – használt zárójeles hivatkozást használjuk, azaz ÕCnà‹aËA£ S à:c Ù A függvénytípus elnevezés azt a szemléletes képet tükrözi, hogy egy függvénytípusú érték felfogható egy Ò¹½) típusú parciális függvénynek, amelynek értelmezési tartománya a " ÌjT -tól a Î><T -ig tart", és értékeit pedig a sorozat komponens tartalmazza. Az előbbiekben bevezetett ‰=j#¬fÌj#ÍZÎ>¡Í‚ÌjT#Î:<T függvényeket kiterjeszthetjük az egész állapottérre is: komponáljuk a megfelelő változóval. Tehát ha például r egy sorozattípusú változó, akkor ‰kj#¬mDCr egy az egész állapottéren értelmezett függvény Az ilyenfajta függvénykompozíciókra bevezetünk egy újabb jelölést: ha t a fenti függvények valamelyike, és r a neki megfelelő típusú változó, akkor az tGD1r helyett r t -t írunk. 92 8. TÍPUSKONSTRUKCIÓK 8.5 A

típuskonstrukciók típusműveletei A típuskonstrukciók eddigi tárgyalásából még hiányzik valami: nem beszéltünk még a konstruált típusok műveleteiről. Az előbb felsorolt speciális esetekhez – az imént definiált függvények segítségével – bevezetünk néhány típusműveletet. A továbbiakban megengedett feltételnek fogjuk nevezni azokat az ãM¹¾¼ állításokat, amelyek lehetnek elágazás, vagy ciklus feltételei. Legyen !oÁˆ£ " aZ! " £ ( a>! (  rekord, tha‚! , t  a>!  (/UŒk^ 8` ). Mivel t az állapottér változója, t komponálható a szelektorfüggvényekkel, és így az állapotéren értelmezett függvényeket kapunk. A £Ž4D?t függvénykompozíciót a továbbiakban tc´£Ž -vel fogjuk jelölni. Egy rekord típusnál a szelektorfüggvény használatát megengedettnek tekintjük. Ezen kívül bevezetjük a tc £Žuaˍt< jelölést is. Ezen azt a t1aˍt<š értékadást értjük,

amelyben t<šˆ´£Ž*Ãt< és t<š minden más komponense megegyezik t megfelelő komponensével. A fenti típusműveletek arra adnak lehetőséget, hogy egy rekord “mezőinek" az értékét lekérdezhessük, illetve megváltoztathassuk. A fent definiált műveletben zavaró lehet, hogy egy függvény helyettesítési értékének (tc´£Ž ) “adunk értéket". Ezért fontos megjegyezni, hogy ez csupán egy jelölése az értékadásnak. Legyen !’ш£ "a“!"Ž™™£Ž(Ja“!&(: egyesítés, tPa“! , t<ha“!& (PUI^  8` ). Ekkor a rekord típusnál bevezetett jelölést az egyesítés esetén is bevezetjük, tc´£ -n, az £&D+t kompozíciót értjük, és megengedett függvénynek tekintjük. Ezen kívül megengedett művelet a t/aˍ@[•ent<¡ értékadás. Ennek az értékadásnak a jelölését leegyszerűsítjük, a továbbiakban tGaË3t< alakban fogjuk használni. A fenti

értékadást bizonyos ésszerű korlátozások bevezetésével “megfordíthatjuk". Így kapjuk az alábbi parciális értékadást: t<La´Œt . Ez az értékadás csak akkor végezhető el, ha tc £Ž igaz. A sorozat típuskonstrukció nagyon gyakori, és sokféle művelet definiálható vele kapcsolatban. Attól függően, hogy melyeket tekintjük megvalósítottnak, különböz ő konstrukciókról beszélünk. Most előbb megadunk néhány lehetséges műveletet, majd ezután a sorozat típusokat osztályba soroljuk a megengedett műveleteik alapján. Legyen a továbbiakban !ŒI£Ž¤#)„ , tea! , ¤ƒa=) . Ekkor az iménti szelektorokhoz hasonlóan bevezetjük az alábbi jelöléseket: ‰kj#¬KDGtŹ ̈j#Í/DGtŹ Î>¡Í/DGtŹ tc ‰=j#¬ tc ̈j#Í tc Î>¡Í Természtesen tc Ìj#Í és tc Î>¡Í csak parciális függvények. Ezen kívül az alábbi (esetleg 93 8.5 A TÍPUSKONSTRUKCIÓK TÍPUSMŰVELETEI parciális)

értékadásokra a következő jelöléseket fogjuk használni: t a´AÌj#« ¤Ž¬]nt ‹ t‹a´MÎ>d« ¤Ž¬]nt tea´ŒÌj ¤Žr>ttc$¤ t‹a´AÎ: ¤Žr>ttc$¤ ¤= t‹a´ŒÌj#Í8nt cÌj#« ¤Ž¬9t ¤= t‹a´MÎ:¡Í8nt Î>d« ¤Ž¬]nt ǹ  ¹ Ç ǹ ǹ Ϲ ǹ t‹aÌj#« ¤Ž¬ t‹akÎ>d« ¤Ž¬ t‹aÌj ¤Žr‚t¤  t‹akÎ>¡¤Žr‚t¤  ¤= t‹äjª‚jª ¤= t‹akÎ>䪂jª A bevezetett jelölések első látásra zavarba ejtőnek tűnhetnek, hiszen ugyanazt a kulcsszót a baloldalon függvényként, a jobboldalon pedig a művelet neveként használjuk. Lényeges ezért megjegyezni, hogy a jobb oldalon található műveletek csa a baloldali értékadás egyszerűsítő jelölései. Attól függően, hogy a fent definiált műveletek közül melyeket tekintjük megengedettnek, különböz ő konstrukciókról beszélünk. 36. DEFINÍCIÓ : S PECIÁLIS SOROZATTÍPUSOK Legyen

!ŒŒ£Ž¤#)P . Ekkor a ! ¢ szekvenciális input file, ha csak a ÌjªZjª a megengedett művelet, ¢ szekvenciális output file, ha csak a Î> ¤r‚t a megengedett művelet, ¢ verem, ha a megengedett műveletek a ̈j ¤r‚t és a Ìjª‚jª , vagy a Î: ¤Žr>t és a Î>䪂jª , ¢ sor, ha a megengedett műveletek a Î: ¤Žr>t és a Ìjª‚jª , vagy a Ìj ¤Žr‚t és a Î>䪂jª . Ahhoz, hogy a szekvenciális input file a ÌjªZjª művelettel használható legyen, tudnunk kell, hogy mikor olvastuk ki az utolsó elemet a file-ból. Ezt a problémát úgy szoktuk megoldani, hogy bevezetünk egy extremális elemet, és kikötjük, hogy a fileban ez az utolsó elem (tehát még az üres file is tartalmazza). Ez a technika valósul meg azokban az operációs rendszerekben, ahol a szövegfile-ok végét file-vége (EOF) karakter jelzi. Mivel a ̈jª‚jª művelet bizonyos esetekben kényelmetlen lehet – gondoljunk

arra, amikor nehézkes extremális elemet találni –, bevezetünk egy másik olvasóműveletet is. Használjuk az olvasás sikerességének jelzésére a Q“j#«#¬9$€T“j#«#¬fl halmaz elemeit Ekkor az £r?$‰kr$r{a« ¤#€=‰ műveleten az alábbi értékadásokat értjük: £r‰r? r{a«#¤#€4‰¹æå £r‰r? rfa´3“j#«Ž¬9$̈j#ÍZrZ$Ìj#« ¤Ž¬]nrZ £r{aËŒ€T“j#«#¬9 ha ‰kj#¬]nr8/Œ z | ha ‰kj#¬]nr8Œ| Ha egy szekvenciális file-ra a « ¤Ž€4‰ művelet van megengedve, akkor nincs szükség extremális elemre, helyette az £r változó értéke alapján lehet eldönteni, hogy végére értünk-e a file-nak. 94 8. TÍPUSKONSTRUKCIÓK Legyen Ôm—ÕZӂ[ˆÒ‘$)„ , Õ9a4Ô , ¤a4) , ea4Ò . Ekkor a sorozat típushoz hasonlóan bevezetjük az alábbi jelöléseket: ‰=j#¬XDeÕ Ìj#Í/DeÕ Î:¡Í/DeÕ ÌˆjTCDeÕ Î><TCDeÕ ¹ ¹ ¹ ¹ ¹ ÕZ ‰kj#¬ ÕZ Ìj#Í ÕZ´Î:¡Í ÕZ ÌjT

ÕZ´Î:<T A fenti függvényeken kívül a függvény típus szelektorfüggvényét ÕC< -t is megengedettnek tekintjük. A rekord típusnál bevezetett szelektorra (mezőre) vonatkozó értékadásnak jelen esetben is van megfelelője: az ÕCn<‹aË3¤ parciális értékadás Az értékadás azért parciális, mert csak akkor végzhető el, ha ÕZ ÌjT0ÞÑ‘Þ¾ÕZ Î><T . Ekkor a fenti jelölésen azt az Õ{a´MÕ8š értékadást értjük, amelyre: Õ8š ÌjTeMÕZ ̈jT”gÕ8šˆ Î><TeAÕZ Î><TCgÕ8šˆn<Œ¤+g Y:çxU] ÕZ ÌjT# ´ÕZ Î><T`“açVŒ z ”¹-Õ š ^ç4AÕC^ç4c A sorozatokra bevezetett kiterjesztő és elhagyó műveleteket függvény típusra is definiáljuk: Õ aËAÌj#« ¤Ž¬9dÕ&ǹ { Õ{aËMÎ:¡« ¤Ž¬9dÕ&ǹ Ցaˌ̈j ¤Žr>tˆÕZ¤ ǹ ՑaËAÎ> ¤Žr>tˆÕZ¤ ǹ Ցa=Ìj#« ¤Ž¬ Ցa4Î:¡« ¤Ž¬

Ցa=Ìj ¤Žr>tˆ¤# Ցa4Î: ¤Žr>tˆ¤# Ha ezen utolsó csoportban felsorolt műveleteket egy függvénytípusra nem engedjük meg, akkor egy speciális függvénytípushoz, a vektorhoz jutunk. Az általános függvénytípustól megkülönböztetend ő a vektortípusra külön jelölést vezetünk be: è½ Í=¤ 4tˆÒ‘$)P . Ha azt is jelölni kívánjuk, hogy mik a vektor indexhatárai, akkor a típust èy»Í=¤ 4t$ €Î^´Õ&Î`ha[)„ -vel jelöljük. További jelölésbeli eltérés az általános függvénytípustól: a szelektorfüggvény jelölésére nem a kerek, hanem a szögletes zárójelet használjuk. II. rész Programozási módszertan 95 Alapvető programozási tételek Legelőször – a levezetési szabályok használatát is ismertetve – néhány egyszerű feladatra keresünk megoldóprogramot. 9.1 Összegzés
  
       " $#%   &!()   !()+*,.-0/21

3 4# " &  56
:#<;=1>1 7 8!9 Az előfeltételben szereplő +*,?-,/ feltétel azt fogalmazza meg, hogy az és  Legyen adott az függvény. Feladatunk az, hogy egy adott intervallumban összegezzük az függvény értékeit. Specifikáljuk először a feladatot számok egy – legfeljebb üres – intervallumot határoznak meg. (Az intervallum akkor lesz üres, ha a kezdőpontja eggyel nagyobb mint a végpontja.) Próbáljuk a feladatot ciklussal megoldani: ehhez a ciklus levezetési szabálya alapján keresnünk kell egy invariáns tulajdonságot ( ), ami a ciklus futásának egy közbülső állapotát írja le. Fogalmazza meg ez az invariáns azt a tulajdonságot, hogy az @ 97 98 9. ALAPVETŐ PROGRAMOZÁSI TÉTELEK A összegzést az intervallum egy kezdőszeletére már elvégeztük. Ennek formális leírásához bővítsük ki az állapotteret egy újabb egész típusú komponenssel ( ), amely azt fogja mutatni, hogy hol tartunk az

összegzésben. Az új állapottér tehát legyen:  B     A Ekkor az invariáns tulajdonság: @C$# " &AEDF HGI/JK L&  7 8!M6 9
:#<;=1>1 Vizsgáljuk meg most a ciklus levezetési szabálya feltételeit: "CN @ : Ez a feltétel jól láthatóan nem teljesül (sőt fordítva áll fenn). Mit lehet 1) " " ilyenkor tenni? Vagy a -t, vagy a @ -t meg kell változtatni. A azonban a feladatot definiálja, azt nem változtathatjuk meg, a @ -t pedig mi választottuk úgy, hogy egy közbülső állapotot írjon le, ezért azt sem lenne szerencsés Van "  állítást, eldobni. azonban egy harmadik lehetőség is: keressünk egy olyan amelyre már "  N @ teljesül, és oldjuk meg a feladatot egy olyan szekvenciával, amelynek " második része egy olyan ciklus" lesz, " melynek előfeltétele a  , az utófeltétele 3 pedig , első fele pedig egy a -ból  -be képez " ő program (azaz alkalmazzuk a

szekvencia levezetési szabályát). Legyen ez a  állítás: " !4# " &A  GI/  PO 1 " N @ fennáll. Most még keresnünk kell egy Könnyen látható, hogy" ekkor"   O olyan programot, ami -ból  -be jut. A ARQS  TG0/(Q értékadás megfelel ennek a kritériumnak, hiszen az értékadás leggyengébb előfeltételéről szóló tétel alapján: " NVU
:#WAQXY  HG,/(Q O Q " K1  # " )G,/  HG,/ OZPO 1  " .  N 3 : Ebből a feltételből meghatározhatjuk, hogy mi lesz a ciklusunk 2) @P [] feltétele. Ehhez azt kell megnézni, hogy mikor következik az invariáns tulajdon  ságból az utófeltétel. A kettőt összehasonlítva észrevehetjük, hogy ez A esetén van így. Tehát []  #WA  ^1 , azaz  #WA  ^1 . Nbadc O : A feltétel teljesítéséhez keresnünk kell egy olyan – az ál3) @C` lapottéren értelmezett – egészértékű függvényt, amely az invariáns és a ciklusfeltétel fennállása

esetén pozitív. Mivel a változók is az állapottér függvényei, a terminálófüggvényt rajtuk keresztül fogjuk kifejezni. Vegyük észre, hogy ha ( miatt) és ( miatt), akkor értéke pozitív lesz. Legyen tehát: AeDf GP/(  @ Ag   GIA a   G`A . a  alkmNnU
:#Wo k Q aqpralk 1 : Mivel már van terminálófüggvényünk, vegyük 5) @hij előre a levezetési szabály utolsó feltételét, ami azt kívánja meg, hogy a ciklusmag csökkentse a terminálófüggvényt. Mivel az utófeltétel szerint  értékét meg kell tartanunk, a terminálófüggvényt A növelésével tudjuk csökkenteni. Mennyivel 99 9.2 SZÁMLÁLÁS A növeljük -t? Legalább 1-gyel. Ha egy kicsit előre tekintünk, és figyelembe vesszük, hogy a ciklusmagnak az invariánst meg kell tartania (ez a 4. pont), akkor látható, hogy -t legfeljebb 1-gyel növelhetjük meg. Tehát a értékadás csökkenti a terminálófüggvény értékét, ui: sA   At-f/ @,)u))G`A  a k NVU
:#WAE 

AZ-v/JQ> GFA pIa k 1  )Gg#WAZ-0/21 p,a k . NxU
:#Wo k Qy@1 : Meg kell még vizsgálnunk, hogy a As  A?-f/ értékadás 4) @Pw jó lesz-e ciklusmagnak, azaz megtartja-e az invariánst. Írjuk fel a @ -hez tartozó leggyengébb előfeltételét: U
:#WAE  AZ-0/(Qy@1  # " &AZ-v/ZDF HGI/JK L&  M{6 z]|
:#<;=1>1 7 8!9 " Látható, hogy ez @`? -ből nem következik. Jelöljük hát a fenti feltételt "   -vel, és legyen a ciklusmag amelynek közbülső feltétele   és  egy olyan szekvencia,már második tagja a A) A:-w/ értékadás. Ekkor dolgunk, mint találni " képeznincsés más a értékét egy olyan programot, ami @d -ből   -be változtatja "   -ben: mivel AdDg Gnem v ( /  (@ ) és meg. Nézzük meg, hogy mi nem teljesül AF  ( ), A}-P/?D, Gg/(  fennáll.  értéke @ szerint viszont nem jó, mert " csak A -ig tartalmazza
értékeinek összegét,   szerint pedig már AZ-g/ -ig kell. A

fenti meggondolás alapján tehát  növelése
:#~A-v/1 -gyel jó lesz, azaz: @,) NVU
:#~Y  q-r
:#~AY-0/21€Q "  1   # " A-v/YD` GI/JK L&‚-I
:#WAZ-0/21 ƒM{6 z„|
:#%;=1y1 . 7K8!9 A A fenti levezetés alapján kimondható az alábbi tétel: Tétel: Az alábbi struktogram formában megadott program megoldása a fent specifikált feladatnak: " " 3 ARQSZ   GI/JQ O  Ad‚ -I
:#WAZ-0/21 A)  A-v/ @g" )  @ Bizonyítás: A tétel a szekvencia és a ciklus levezetési szabályából, a specifikáció tételéből és a fenti levezetésből következik. 9.2 Számlálás s ^g Legyen egy az egész számokon értelmezett logikai függvény. A feladat az, hogy számoljuk meg, hány helyen igaz az intervallumban.    † k     ‡  ! 100 9. ALAPVETŐ PROGRAMOZÁSI TÉTELEK " 4 #<  L )  !JE+*Iu-0/21 3 $# " )‡  56 <# #%;=1y1y1 7 8!9 ˆ O  / és #~“$L ;l1 

fenti specifikációban ˆ ]‰‹Š QŒ/( , amelyre ˆ #<;WŽ’‘L1 ˆ O AAfeladat megoldása analóg az összegzés tételénél leírtakkal. A ciklus invariáns tulajdonságát itt is az utófeltétel gyengítésével kapjuk (az intervallum egy tetszőleges kezdőszeletére írjuk fel): @C$# " &AEDF HGI/JK L ‡  K7 8^M6 9 ˆ #%#<;l1y1y1 A továbbiakban a ciklus levezetési szabályában szereplő feltételekhez címszószerűen felsoroljuk a levezetés során előforduló elemeket. " !4# " &A  GI/)‡ 0O 1 ,  #~A  ^1 , 2) a   G`A , 3)  5) a A) AZ-v/ értékadás csökkenti a terminálófüggvény értékét, "  # " qAR-./ZD` eG?/JK ~‚‡  M{6 z„| #<#%;=1y1y1 Itt azt kell megvizsgálni, hogy 4)   7K8!9)ˆ " @0& -ből következik-e   . Vegyük észre, hogy []#WA?-f/21 esetén következik, míg #WA!-)/1 esetén " – az összegzéshez hasonlóan – meg kell növelnünk ‡

értékét. Ezért a @sZ -ből   -be jutó program az ”J•.#<#WA–-`/21q(‡E ‡-F/(QX[]#WA–-`/21q o˜— ”J@1 elágazás lesz, ugyanis az elágazás levezetési szabályát alkalmazva: @vE.)#~A-v/1 NN UU
:#W‡™  ‡i-0" /(Q "   1 @g).&[]#~A-v/1
:#~o˜—d”L@šQ   1 NVU
:#W”J•šQ "   1 teljesül. miatt @,) 1) A fenti meggondolások alapján nyilvánvaló az alábbi tétel: Tétel: Az alábbi struktogram formában megadott program megoldása a fent specifikált feladatnak: " " 3 › AQy‡.   HGI/JQ O Ad  #WA-0/21  ˜o — ”J@ .‡  ‡i-0/  A) A-v/ @,) "  / @ Bizonyítás: A tétel a levezetési szabályokból, és a specifikáció tételéből a fenti meggondolások (levezetés) alapján következik. 101 9.3 MAXIMUMKERESÉS 9.3 Maximumkeresés œ mƒ
g!œ
Legyen egy tetszőleges rendezett halmaz és egy adott függvény. Feladatunk az, hogy egy adott intervallumban

keressük meg az függvény maximumát és egy olyan helyét, ahol ezt a maximumértéket felveszi.     œ     ; &Jž " $#%   ! )     )+*,^1 3 4# " );DF u&Lž 
:#<;=1!™Ÿ¡™D` s ^L
:#K’1q*g
:#<;=1>1 Vegyük észre, hogy az előbbiekkel ellentétben ebben a specifikációban nem engedtük meg az üres intervallumot. Ennek oka rendkívül egyszerű: üres intervallumon nincs értelme megkérdezni, hogy hol van a maximum. A feladatot ciklussal oldjuk meg, amelynek invariánsa: @¢$# " &A)DF sK L);£D` s AL’E&Lž 
:#<;=1R.Ÿ¡™D` s AL„J
:#K’1q*v
:#%;=1>1 A feladatot megoldó program levezetése hasonlatos az előzőhöz, ezért itt is csak címszavakban soroljuk fel a lépéseket: "   # " &A  ƒ);  ¢) Lž 
:#%w1>1 ,  #WAd ^1 , 2) a  )G`A , 3)  5) a A) A-0/ értékadás csökkenti a terminálófüggvény értékét, "  # "

dAt-/uDP sK $&;YDP s At-/€¡w&Lž 
:#%;=1] Ÿ¡hD0 ¤A?4)   elágazás lesz: /€™š
:# L1h*c
: #%;=1>1 A @¦F -ből "   -be jutó program itt isp egy ”J•.#~
:#WA-™/21 Lžh(;SQy Lžw A-™/JQS
:#WA-™/1{QX
:#WA-™/21  LžhJo£—d”L@1 , ui. @g)u
:#~AZ-v/1 cp  &Jž NN UU
:#%;XQy Lž& "  AZ-v/JQS
:#~AY-0/21€Q "   1 @g)u
:#~AZ-v/1 &Jž
:#Wo£—d”L@šQ   1 NVU
:#<”L•šQ "  1 teljesül. miatt @gE 1) Tétel: Az alábbi struktogram formában megadott program megoldása a fent specifikált feladatnak: " 3 " ;XQSAQy L žw   sQ>sQS
:#<&1 Ad  ›
:#WAZ-v/1q§I&Lž ›
:#WAZ-v/1q*I&Lž o˜— ”J@ ;XQ>&Jž&  AZ-0/(QX
:#WAZ-v /1 A) A-v/ @ @,) "  102 9. ALAPVETŐ PROGRAMOZÁSI TÉTELEK Bizonyítás: A tétel a levezetési szabályokból, és a specifikáció tételéből a fenti meggondolások

(levezetés) alapján következik. 9.4 Feltételes maximumkeresés œ
d(`¨œ ªR«$¬ sK 

 ­ œ P‰ U     ; Lž " 4#< & L!)   !JE+*Iu-0/21 3 $# " U  #~®’;DF s ^(#%;=1>1^ U ¯#%;DF u‚#%;=1!) Lž  :
#%;=1> Ÿ¡™Ds sK ^°# ’1±#W
:# ’1š*,
:#<;l1y1>1y1 Legyen egy tetszőleges rendezett halmaz és egy adott függvény. Legyen egy az egész számokon értelmezett logikai függvény. Határozzuk meg a halmaz felett az függvény maximumát és a halmaz egy olyan elemét, amelyen a maximumértékét felveszi. Vegyük észre, hogy itt újra megengedhet ő az üres intervallum, és hogy ekkor az a válasz, hogy az intervallumban nincs tulajdonságú elem. A levezetés az előzőkhöz hasonlóan: @C$# " &AE DF HGI/JK L U  #~®’;D` ¤AL^°#<;=1>1! U ±#%;‚D` sK¤ALL)#<;=1> &Jž
:#%;=1RuŸ.Ds ¤AL^°# ’1±#W
:#

’1š*,
:#<;l1y1>1y1 "  # " &A  HGI/ U  “$L ;l1 , 1)   #~A  ^1 , 2) a   G`A , 3)  5) a A) AZ-v/ értékadás csökkenti a terminálófüggvény értékét, 4) Írjuk fel a ciklusmag közbülső feltételét: "  ^$# " &AZ-v/ZDF GI/JK L U  #~®’;‚DF AZ-0/€^(#%;=1>1y U ¯#<;£D` s AZ-0/€L)#<;l1^E&Lž 
:#<;=1> Ÿ¡™D` sK¤AZ-v/Œ^°# ’1±#W
:# ’1q*g
:#<;l1y1>1y1>1 @v) és "   összehasonlításával látható, hogy három fő lehetőség van: – []#WA-0/21 : ekkor SKIP,  U U – #WAš-s/1J[ : ez az első tulajdonságú elem, tehát Qy;XQ>&Jž& ;~Ž’‘$QXA/(QX
:#WAZ-v/1 ,U – #WA-0/21R : ekkor a maximumkeresésnél megismert két eset lehetséges: ²
:#WA-0/21 c  Lž : ekkor ;XQ>&Lž   AY-0/(QX
:#WAZ-0/21 , ²
:#WA-0/21 p  Lž : ekkor o˜— ”J@ . 103 9.5 LINEÁRIS KERESÉS " Tétel: Az alábbi struktogram

formában megadott program megoldása a fent specifikált feladatnak: 3 " AQ U   HGg/JQ>³ Ad  ,@ ) › []‚#WAZ-v/1 › #~A-v/1R [ U › #~A-v/1! U ›
:#WAY-v/1q§r&Jž ›
:#WAY-v/1q*r&Lž  U  o˜—d”L@ Qy;XQ>&Jž& S ; y Q L  w ž  o˜—d”L@ ´ QSAZ-0/(QX
:#WAY-v/1 AZ-v/JQS
:#WAZ-0/21 "  A)  A-v/ @ Bizonyítás: A tétel a levezetési szabályokból, és a specifikáció tételéből a fenti meggondolások (levezetés) alapján következik. 9.5 Lineáris keresés `(e¨‰ +Dw        ; " $#%   &(&®°.§,+°‚#K’1>1 3 4# " );§Iƒ)#<;l1RuŸ¡™D` sK ;^G,/€„J[]#K’1y1 A feladatot ciklussal oldjuk meg. Az invariánshoz gyengítjük az utófeltételt, elhagyjuk belőle ‚#%;=1 -t: @¢$# " );§,¢uŸ™DF ;„GI/Œ^J[]# ’1>1 "  # " );  w1 , 1)   []#%;=1 , 2) Legyen adott tulajdonság. A feladat az, hogy keressük meg azt a legkisebb

tulajdonságú egész számot, amely nem kisebb, mint az adott szám. µ¨§g a  µ¶Gs; 3) Legyen tetszőlegesen rögzített olyan szám, amelyre előfeltétel miatt létezik). Ekkor . #Wµd1 igaz(ilyen az £;   ; -0/ értékadás csökkenti a terminálófüggvény értékét, NVU :
#<;£  ;-0/(QS@1 . 4) @,) 5) az 104 9. ALAPVETŐ PROGRAMOZÁSI TÉTELEK Tétel: Az alábbi struktogram formában megadott program megoldása a fent specifikált feladatnak: " " 3 ;£  []# <;l1 ; ;-0/ @gE @ Bizonyítás: A tétel a levezetési szabályokból, és a specifikáció tételéből a fentiek szerint következik. A fenti program csak akkor megoldása a feladatnak, ha a tulajdonság megengedett feltétel. Ha ez nem így van, akkor másik megoldást kell keresnünk Válasszuk az alábbi invariánst (a feladat marad ugyanaz!): @C$# " );£§IGI/s#Ÿ¡™D` sQ>;„GI/Œ!L[]# ’1>1! U  (® .D` sQ>;~!J#K’1>1 Ekkor:

"   # " ) ;  HG,/ U  “4L);=1 ,  [ U, 2) 3) Legyen µV§, tetszőlegesen rögzített szám, amelyre #<µ 1 igaz(ilyen az a  µG olyan ;. előfeltétel miatt létezik). Ekkor  5) az ;‚ ;-0/ értékadás csökkenti a terminálófüggvény értékét, 1) "  ^$# " );-0/Z§rHGg/£s#Ÿ¡.DF sQ>;~^J[]‚#K’1>1„ U  ®°DF Qy;-0/€^°‚#K’1>1 U  és így a ciklusmag első fele az  ‚#%;!-v/1 értékadás lesz. 4) A ciklusmag szekvencia lesz, melynek közbülső feltétele: " Tétel: Ekkor az alábbi program is megoldása a specifikált feladatnak. ;XQ U   HGU ,/(Qy³ U   [ #%;R-v/1 @g" E  ;  ;-0/ 3 ·.¸&¹ és létezik ;º§0 , hogy @ #%;=1 Keressük meg a legelső ¹ " ;§I+ · #%;=1 elemet (ha van olyan), amely előtt ( -től kezdve) nem volt igaz ! Ennek a változatnak már a specifikációja is más lesz, hiszen a feladat is megváltozott.  ­P‰    ; » &

Tegyük fel, hogy 9.5 LINEÁRIS KERESÉS 105 " $ #%  &(&®°.§,+°‚#K’1>1 3 4# " ) »  #W®°E§r+ · # L1^.Ÿ!AuDF }G,/€!J[ ¹ #~A¡1>1y »&±#%;‚§rƒ · #%;=1RuŸ™DF ;„GI/Œ^J[]# ’1>1 A feladatot megoldó ciklus invariánsa: @¢$# " );§,HG,/E»  #W®(.D` s ;~^ · #K’1y1!u¼  #~®°uDF ;~^ ¹ #K’1>1y Ÿ¡.DF sQ>;„GI/Œ^J[]# L1y1 Ekkor: "  # " );  GI/E»  “$L ;=£)¼  “4L);=1 , 1)   []»?&[]¼ , 2) szám, amelyre #Wµd1 igaz (ilyen az 3) Legyen µ¨§r tetszőlegesen rögzített a  µ¶olyan előfeltétel miatt létezik). Ekkor Gs; .  5) az ;£ ;-0/ értékadás csökkenti a terminálófüggvény értékét, U  4) A ciklusmag szekvencia lesz, melynek közbülső feltétele (
:#<;˜ ;-0/(QS@1 ): "  R$# " );R-v/Y§,HGI/)»  #W®°EDF sK ;-0/€„ · # ’1>1> ¼  #~®°.DF ;!-0/€! ¹ # L1y1^ŸuDs Qy;~^J[]# L1y1 v·

#%;-0/21€Q ¹ #<;-0/21 értékadás lesz. és így a ciklusmag első fele az »„Qy¼. Tétel: Az alábbi struktogram formában megadott program megoldása a fent specifikált feladatnak: " X; Qy»„Qy¼.  HG,/(Q>³4Q>³ []· »?&[]¼ ¹ ,  »]Q>¼u #%;R-v/1{Q #<;-0/21 @g"  ) ;‚ ;R-0/ 3 ¹ @ A fenti feladatnak van egy speciális esete, amikor tulajdonság azt mondja ki, hogy még nem értünk el egy  számot, azaz egy intervallumon kell keresni. Erre a speciális esetre adunk egy másik megoldást is.  f‰ U     ; " $#%   &!()   !()+*,.-0/21 3 4# " U  #~®°EDs ^°# L1y1^ U ±#%;‚Ds sK ’)#<;l1y Ÿ¡™D` s ;„GI/Œ^J[]# L1y1>1 Legyen a ciklus invariáns tulajdonsága: @¢$# " );DF GI/JK L U  #~®°.DF ;~^(#K’1>1„uŸ™DF s ;„GI/Œ^J[]# L1y1 " Ekkor: 106 9. ALAPVETŐ PROGRAMOZÁSI TÉTELEK "   # " );  HG,/ U 

“4L);=1 ,  [ U u;j  , 2) a   Gs; , 3)  5) az ;‚ ;-0/ értékadás csökkenti a terminálófüggvény értékét, U  4) A ciklusmag szekvencia lesz, melynek közbülső feltétele (
:#%;£ ;R-v/JQy@1 ): "  ^$# " );-0/ZDs HG,/( ’ U  #W®°EDF sK ;-0/€„°#K’1y1^.Ÿ™D` ;~^L[]#K’1>1 U  és így a ciklusmag első fele az  ‚#%;!-v/1 értékadás lesz. 1) Tétel: Az alábbi struktogram formában megadott program megoldása a fent specifikált feladatnak: " " 3 ;XQ U  U  HG ,/(Qy³ [ U  );–    #%;R-v/1 ; ;-0/ @v" u  @ 9.6 Logaritmikus keresés F¨œ Legyen œ

I egy olyan halmaz, amin értelmezve van egy rendezési reláció. Legyen monoton növekedő függvény. A feladat az, hogy döntsük el az függvényről, intervallumon felveszi-e a adott értéket, és ha igen, hogy az adott akkor adjuk meg az intervallum egy olyan pontját, ahol a függvényérték . sK ‚ “eDFœ “

 ­Pœ½f‰ U  “ ;   Bfœ " 4#< & L!)   “$ !J “  “4JE+*,.-0/uŸRAQ¾™DF sK ^ p ’1±#W
:#~A¡1q*v
:#K’1>1y1 ~ # A 3 $# " U  #~®°.DF s ^L
:#K’1  “¿1! U ±#%;‚D` sK L&
:#%;=1  “41y1 A monotonitást felhasználva az intervallumot mindkét végéről szűkítjük az invariánsban: " @C$# U s »]K ¼J^Àf ’uŸ ™DF  › »]K ¼J^L
:# L1m “™ ±#%;‚D` »]K ¼JL&
:#%;=1 “¿1>1 Ekkor "  # " )»  ƒ)¼  ™ U  “$L ;l1 , 1)   [ U u»h*,¼ , 2) 107 9.6 LOGARITMIKUS KERESÉS a 3) Informálisan fogalmazva jelölje a még megvizsgálandó elemek számát. Ezt egy esetszétválasztással adhatjuk meg: a ÂÁ ?¼O G »™-v/JQ Q ha ha U[ U "  R$# " s »„ ¼(^À s ™Ÿ¡.DF sK  › »„ ¼(^’
:#K’1m “™ [ U #<;DF »] ¼Jª1y1 Ekkor a szekvencia első fele lehetne az ;YKD0 »]K ¼( értékkiválasztás.

Hatékonysági szempotokat  is figyelembe véve azonban válasszuk az intervallum középső elemét: ; >#%»t-e¼’1SðÄÅ« . A ciklusmag második felében három eset lehetséges: p “ : ekkor az »h  ;R-v/ értékadás az invariánst megtartja, –
:#<;l1  “ : ekkor megtaláltuk a keresett elemet, tehát U   ;~Ž’‘ , –
:#<;l1 c “ : ekkor az ¼E  ;„GI/ értékadás az invariánst megtartja. –
:#<;l1 4) A ciklusmag legyen egy szekvencia, melynek közbülső feltétele: 5) Egyszerűen ellenőrizhető, hogy a fenti elágazás mindhárom ága csökkenti a termináló függvényt. Tétel: Az alábbi struktogram formában megadott program megoldása a fent specifikált feladatnak: " " 3 »]Q>¼¿Q U U   sQ>˜Q>³ [  )»h*r¼ ;‚ =#%». -`¼1yÃ(Ä« p ›
:#%;=1 “ ›
:#%;=1 “ › :
#%;=1 c “ U  ´ »w  ; -0/ ¼E  ^; G,/ Bizonyítás: A tétel a fenti levezetés következménye. @ @," ) 

Függvényérték kiszámítása A továbbiakban bizonyos speciális függvények helyettesítési értékének kiszámításával fogunk foglalkozni. Tegyük fel, hogy van egy függvényünk, ahol és tetszőleges halmazok. A feladat specifikációja tehát:
                  
   Természetesen ha semmi mást nem tudunk a függvényről, akkor a fenti specifikációhoz nem tudunk igazi megoldóprogramot adni. Ezért az elkövetkezőkben további feltételezésekkel fogunk élni. 10.1 Függvénykompozícióval adott függvény kiszámítása
"!$# # %&  ()* Tegyük fel, hogy , ahol és függvények. Tétel: Ekkor a feladat megoldható az alábbi szekvenciával: +  ,#       +  109 110 10. FÜGGVÉNYÉRTÉK KISZÁMÍTÁSA + Bizonyítás: Kibővítjük az állapotteret egy újabb ( típusú) komponenssel, melynek változója legyen . A szekvencia közbülső feltétele legyen    + ,# 

 -.0/ Ekkor a szekvencia levezetési szabálya alapján a megoldás triviálisan teljesül. 10.2 Esetszétválasztással adott függvény kiszámítása 13254.1674 /8/9/ 41:;<= > feltételek és # 254 # 674 /8/9/ 4 # :;(?@ függvények, 1A feltételek lefedik az  halmazt. Legyen
;7&? az alábbi BCC # 2    4 ha 1 2    D C # 6    4 ha 1 6     
 . CE . # :    4 .ha 1 :    Tétel: Ekkor az
függvény értéke kiszámolható az alábbi elágazással: F 1G27   F 16   F /8/9/ F 1:H   /8/8/   )# 2      )# 6      )# :    Legyenek és tegyük fel, hogy a módon definiálva: Bizonyítás: Az elágazás levezetési szabálya alapján a megoldás triviálisan teljesül. 10.3 Rekurzív formulával adott függvény kiszámítása I JLKNM VXW4VZY 2 4 9/ /8/ 4 VZY S [ 2^] I
`M 
acb  OP<Q,RITSU I
R(Q ?I függvényt az Legyen egy tetszőleges halmaz, egy egész szám, továbbá függvény,

rögzített, és definiáljuk az alábbi módon:
daeJgf)b  VXW4 VZY 2 4 . . . . V Y S0[ 2 továbbá hGikjlM :
mi3f)b  On`iGfNb74o
`i  4 /-/-/ 4Z
miHapJUf)b  Feladatunk az, hogy meghatározzuk az
függvény qrjlM helyen felvett értékét. Q I  q 111 10.3 REKURZÍV FORMULÁVAL ADOTT FÜGGVÉNY KISZÁMÍTÁSA  Q q   mq q 7 s      s 
q mq j,.  M Tétel: Az alábbi struktogrammal adott program megoldása a specifikált feladatnak:  iZ4  4  Y 2 4 -/ / 4  Y 0S [ 2  M4VXW74.VZY 2 4 /-/ 4VZY S0[ 2 iet q  4  Y 2 4 /-/ 4  Y 2  Onmi3f)b4  4 /-/-/ 4  Y 2  4  4 -/ / 4  Y 6 S[ S0[ 0S [ iu i3fNb    v s 1   v Bizonyítás: A tétel bizonyításához elegendő, ha a fenti programot levezetjük, hiszen ekkor az állítás a specifikáció tételéből és a levezetési szabályokból következik. Legyen tehát a megoldóprogram egy ciklus, melynek invariánsa: v   s i ] w M x/ / Gq y s 
mi  4  Y 2
miza{b

 4 /8/8/ 4  Y S0[ 2
mi|apJcf)b  Vizsgáljuk meg a ciklus levezetési szabályának feltételrendszerét: 1) Mivel az eredeti  ~} v nem áll fenn, a ciklus előfeltétele az alábbi V W 4  Y 2 V Y 2%4 8/ /9/ 4  Y 0S [ 2 V Y S[ 2  feltételre     s i M s  állítás lesz. Egyszer  űen látható, hogy a fenti program elején található szimultán értékadás -ból  -be jut. 2) 1 miet q  , V q ari , 5) a ik iGfNb 3) értékadás csökkenti a terminálófüggvény értékét, $i  iGfNb értékadás v -re vonatkozó leggyengébb előfeltételét:      s i3f)b ]pw M /x/ qGy s 
mi3f)b  4  Y 2
`i  4 /9/8/ 4  Y 2
`i|apJUf€  S[ akkor az értékadás leggyengébb előfeltételére vonatkozó szabály alapján egy v szerű behelyettesítéssel verifikálható, hogy a ciklusmag első fele s 1 -ből   - 4) Ha felírjuk az be jut. Megjegyezzük még, hogy a 0 kezdőpont választása önkényes, bármilyen tetszőleges

egész számtól kezdve definiálható egy függvény, és akkor értelemszerűen a program ciklusváltozója is arról az értékről indítandó. 112 10. FÜGGVÉNYÉRTÉK KISZÁMÍTÁSA 10.4 Elemenként feldolgozható függvény I‚2 A továbbiakban legyenek és formában felírható halmazok: Iƒ6 tetszőleges halmazok,  és  pedig az alábbi ‚2^ /-/x/ n:  G2„ /-/x/ L †  ] €%‡kˆ‚Š‰  ‰Š‹Œ,Ži ]w b /x/ qGy és A †  ] €%‡‘$‰  ‰z‹Œ)Ž’i ] ahol nA w b /x/ “ y . Amint az a fenti leírásból kiderül az  az összes olyan halmaz q -est tartalmazza, amelyeknek minden komponense az adott I‚2 halmaz véges részhalmaza Hasonlóan az  elemei pedig az olyan halmaz “ -esek, amelyek I”6 -beli véges részhal mazokból állnak. Definíció: T ELJESEN DISZJUNKT FELBONTÁS Azt mondjuk, hogy teljesen diszjunkt felbontása  4 ]   ]  -nek, ha  A•  A és i) hi ] w b /-/ qGy|  A ›š . ii) hiZ4—– ]rw b /-/ qGyz

 A˜ ™ Vegyük észre, hogy ha  egydimenziós, akkor a teljesen diszjunkt felbontás mege- gyezik a diszjunkt felbontással, de többdimenziós esetben a teljesen diszjunkt felbontás egy jóval erősebb feltételt jelent. Definíció: E LEMENKÉNT FELDOLGOZHATÓ FÜGGVÉNY . Ha minden minden teljesen diszjunkt felbontáLegyen sára  ] 
R7&?  4 hi ] w b /-/ “ y|
A    •L
A   
š A    és ii) hi ] w b /-/ “ y|
5A.   ˜
5A   , akkor
-et elemenként feldolgozhatónak nevezzük. †  ] €%‡œ$‰  ‰‹žŒ,Ž , 6 Példa: Legyen I egy teszőleges halmaz,  2  
,3 2 T 6 Ÿ ,
.  2 4  6   2 •  6 Ekkor
elemenként feldolgozható, ui: tekintsük az   2%4  6  halmazpár egy tetszőleges   2%4  6  ,   254  6  teljesen diszjunkt i) felbontását. Ekkor a teljesen diszjunkt felbontás definíciója alapján: 2• 2  2Š˜  2  2Š˜  6 24 6 • 6 š 4  k6 ˜  6 š 4  6k˜  2 6 š š

Vizsgáljuk most meg az elemenként feldolgozhatóság két kritériumát:   .    
2k  • %2  4 6 6
• 
 2% 4  256 4  ,6  2.
   2 4  6  ˜
   2 4  6 ›š  6$˜  2  •r  6k˜  6  . 1.   2•  6  •T  2 •  6    2k•  2  •r  k6 •  6    2 •  6  ˜   2 •  6    2k˜  2   •   2k˜  6  • 113 10.4 ELEMENKÉNT FELDOLGOZHATÓ FÜGGVÉNY Tehát a – kétváltozós – unió elemenként feldolgozható halmazfüggvény. A továbbiakban tehát egy elemenként feldolgozható függvény helyettesítési értékének kiszámításával fogunk foglalkozni. Mielőtt belekezdenénk a feladat specifikálásába és megoldásába bevezetünk két olyan halmazokra vonatkozó parciális értékadást, amelyeket aztán a megoldó programokban primitív műveletnek tekintünk. ¡ I
7£¢ ( €%‡ ^I¤?€7‡ parciális
£¢   4o  Iž• † Ž4 ] ¦ I /   A fenti függvényt kiszámító 
£¢

 4.  parciális értékadást a továbbiakban   ¨•§ -vel fogjuk jelölni. ¡ Hasonlóan legyen I egy tetszőleges halmaz, és definiáljuk az
%Nª€7‡«RI= €%‡ parciális függvényt:
%¬  4o  I F † Ž(4 ha ] I /   A kiszámító 
%­ 4.  parciális értékadást a továbbiakban   fenti¨® függvényt -vel fogjuk jelölni. Legyen egy tetszőleges halmaz, és definiáljuk az függvényt: ha 10.41 Egyváltozós-egyértékű eset “   Először vizsgáljuk meg azt az esetet, amikor mind , mind egykomponens ű, azaz . Ekkor az függvény egy halmazhoz egy másik halmazt rendel q b
              
    Oldjuk meg a feladatot ciklussal: az invariánsban azt fogalmazzuk meg, hogy az halmaz a még feldolgozandó elemeket, az halmaz pedig a már feldolgozott elemek szerinti képeinek unióját tartalmazza, azaz v   •
  
  -|s  ˜
   š  Vizsgáljuk meg a ciklus levezetési szabályának

feltételeit: 1)   š -ból az fennállása esetén következik értékadás kerül.
   ›š v , ezért a ciklus elé az 
  š 2) Az invariánsból esetén következik az utófeltétel, ám ez jó eséllyel nem egy megengedett feltétel (hiszen éppen -et akarjuk kiszámítani). Vegyük észre azonban, hogy elemenkénti feldolgozhatósága miatt esetén is teljesűl (az üres halmaznak két üres halmaz egy teljesen diszjunkt felbontása). Tehát a ciklusfeltétel: .
1
 ›š t  ¯š
   °š 114 10. FÜGGVÉNYÉRTÉK KISZÁMÍTÁSA  V ‰ ‰  3) Ha (a ciklusfeltétel szerint) nem üres, akkor termináló függvénynek válaszható számossága, azaz . 5)     ® számosságát úgy tudjuk csökkenteni, ha elhagyunk belőle egy – benne levő – elemet. Ezt megtehetjük az imént bevezetett parciális értékadással: . v       •
  F † Ž 
  |s  ˜
  F † Ž  š s ]   v Jól látható, hogy

ez s 1 † -ből nemF következik. Vegyük azonban észre, hogy ha egy  -beli elem, akkor 7Ž és  † 7Ž  -nek egy teljesen diszjunkt felbontása, tehát
elemenkénti feldolgozhatósága miatt:
 †† 7Ž  •
  FF †† Ž 
š   
 7Ž  ˜
  Ž  § † Így az    •r
 Ž  értékadás már majdnem elegendő, hiszen ±
    •§
 † Ž  4   -   •ƒ
 † Ž  •ƒ
  F † Ž 
  ²s   •ƒ
 † Ž . ˜
  F † Ž  š s ]   .v Ezt a feltételt összevetve s 1 -vel látható, hogy már csak az ]  állítást kell teljesítenünk. Ezt viszont megtehetjük az " ]  értékkiválasztással, amelynek a v fenti állításra vonatkozó leggyengébb előfeltétele s 1 . 4) Írjuk fel a fenti parciális értékadás -re vonatkozó leggyengébb előfeltételét: Tétel: Ekkor az alábbi program megoldása a specifikált feladatnak:       š  ›š t " ]     • §
 † Ž     ® v

s 1     v Bizonyítás: A tétel a fenti levezetésből következik. 10.42 Kétváltozós-egyértékű eset
T%*L³ @m;4o$40 ´,€7‡    µ  ~ +         (s      +
   4   Legyen elemenként feldolgozható függvény. Tétel: Ekkor az alábbi program megoldása a specifikált feladatnak: 10.4 ELEMENKÉNT FELDOLGOZHATÓ FÜGGVÉNY 115 +  š  ›š t ­¶  t š c ]   •   F ]  s ] ¦  F ]  s ]  F ] ¦  s ]  +  + •§
 † Ž4 š  +  + •r§
 † 7Ž(4 † 7Ž  +  + •§
 š 4 † Ž     ®    ®    ®    ® Bizonyítás: A tétel az egyváltozós esettel analóg módon levezethető, ha invariáns tulajdonságnak az alábbi állítást: v  + L•
  4   
   4  Hs + ˜    F   ˜  ›š s    F   ˜ termináló függvénynek pedig V ‰ •
›š 4   Nš s    ‰ -t választjuk. 10.43 Egyváltozós kétértékű eset


@·¯r@`;4.u4Zž´³€%‡U4Z
72ƒ@·$4Z
56n¸·¹4o
Legyen elemenként feldolgozható függvény. º
2»4o
%6    µ   +           
2»  m3s + 5
6  . Tétel: Ekkor az alábbi program megoldása a specifikált feladatnak:  4 +  ›š 4 š  ›š t c ]   4 +   •§
2  † 7Ž  4 + •§
6  † 7Ž     ®~† Ž Bizonyítás: A tétel levezetése az egyértékű esettől csak az invariáns tulajdonság megválasztásában tér el: v   •
2   
2   Hs + •L
6   
6   |s  ˜
2   š s + ˜
6    ›š  A termináló függvény marad, és a levezetés lépései is megegyeznek. 116 10. FÜGGVÉNYÉRTÉK KISZÁMÍTÁSA 10.44 Általános változat qŠ4 “ rögzített természetes számok,
e¨2¨N¼9¼8¼Š½n:«¾32¨›¼8¼9¼Š ™ ”mnA.4 ] ™ €7‡"4 mi ]³w b /-/ qGy—4¿– ]À™ w b /x/ “ y  elemenként feldolgozható függvény, és /x/

“ y  függvények p ] w legyenek az
% 2 ¼8¼8¼»Á : * x  – b az
komponensfüggvényei, azaz
º
2 4 /9/8/ 4Z
 .   2 /8/9/   :  2 /8/8/   :  ¨2 2 /8/9/ ›n: : 2  2  :   s s      2 2
7252   2 ¼84 ¼8/9¼ /8/ 4  : : Hs ¼9: ¼8¼ s 
5”  2 4 /9/8/ 4  : .  2 4 /x/-/ 4   Nš 4 /-/x/ 4 š Â:  A t š A-Ãz2 : U ] A-ÂÃz2  A F . F F . ]  A ˆ s/8/9/ ]  AÄ s ] ¦  AÄÅ ˆ s ] ¦  A-Æ  2 4 /9/8/ 4   . . § § † † ± ±  2 •r
72%ºÇ  i2 /8/9/ i Ž4o . 4 /8/8/ 4  •
5”ºÇ  i2 /9/8/ i Ž(4   A 4 /8/9/ 4 S  A-ÄÁ  A ® (4 /9/8/ 4  AÄ ® S ˆ ˆ ± 8 / 9 / / 9 / 8 / / ahol i 2 4 4.i : az b4 4q permutációja, Ç (€È 2ZÉËÊËÊËÊËÉ :(Ì I&= 2 r¼8¼8¼ : , † i ] †† i 2 4 /8/8/9/9// 4i S Ž Ç ±  † i 2 4 /x/ 4i S Ž(4.  A žÍ š 4 Ž4 ha ha i„] ¦ i 2 4 4i S Ž : Az elágazás "ágainak" száma € a{b . Legyenek Bizonyítás: A

tétel az alábbi invariáns tulajdonsággal és termináló függvénnyel formálisan levezethető (a levezetést annak bonyolultsága miatt elhagyjuk): v mhª– ]rw b /-/ “ y| »™ •
™   2 4 /9/8/ 4  : 
™   2 4 /8/9/ 4  : s »™ ˜
™   2 4 /9/8/ 4  :  Nš |s hGio4ZJ ] w b /-/ qGy| A F  A  ˜  š  S :  Î Â °Î V ÎÎ A-Ãz2 A ÎÎ Î Î Visszalépéses keresés

 
 tetszőleges véges, nem üres  "! #! %$  &)(+*,-.(/ 0 1325476 1 2547689" .:
 tulajdonságok 1. 1<; >= ; 2. ?@AB C
EDF,GH2I?JK2L1 :M &NOJA4P1 JQ ; 3. ?@AB
R2I?J S#TUK2CG?LVW+X: YR2XJZ  T<Z<A4[1]JQ  1^OT  ; 4. 1  1 A feladat annak eldöntése, hogy létezik-e olyan elem -ban, amelyre teljesül a 1 feltétel, és ha igen, adjunk meg egy ilyen elemet. `  (a6 c eJdIfEg b h 2= i 2jOb lk Tm/n2.1 OT poEbR4qOJrFor1LJQ^# Számozzuk meg

elemeit az alábbi módon: Minden halmaz elemeit számozzuk meg nullától  D9 -ig. Ezután minden J eleméhez van egy ^&S,,-,S#s0L rendezett
-es, amelyre J  J ut S,-,vS#J :w  , ahol 9xy^&)%&S-,,,S#Uxz0m%j0 . Ezen megszámozás egy lexikografikus rendezést definiál -n   .: &|D8v}(l*,- (~ .: C0D8, Ekkor a fenti megszámozás egy Legyen { bijekciót létesít { és között. Jelölje ezt az {4 leképezést € Legyen , és . Legyenek halmazok ( ). Legyen , amely felbontható sorozatára az alábbi módon: 117 118 11. VISSZALÉPÉSES KERESÉS { E9{‚
ƒ Y.  „ 0  j† h S ahol:  0& h ‡ ˆ  Z OB
 Z#pM & Vegyük észre, hogy az halmaz elemei felfoghatók vegyesalapú számrendszerben felírt számként is. Ez alapján egy -es számértéke: A bevezetett jelölésekkel a feladatot újra specifikáljuk, és most már megkövetelhetjük azt is, hogy ha létezik keresett

tulajdonságú elem, akkor az első ilyet adjuk meg: `  { (a6 c ‰d fEg b h 2= i 2CYb ~k Š 9{‡2.1 ‹€H Š ^#^o bp4qz1LO€}‹C^Œo9? Š 9{2 ƒ Š } ƒ ‹.4Ž1 ‹€H Š ^# Ha nem használjuk ki a 1 speciális tulajdonságait, akkor a fenti feldat megoldható lineáris kereséssel, a  .: ! { ! Dlv intervallumon Vizsgáljuk meg, hogy hogyan használhatnánk ki 1 specialitását! Ha 1 O€}‹.# igaz és 1 M &NO€}‹C^ pedig hamis, akkor minden olyan LW8{ -re, amelynek első ‘ komponense megegyezik  első I‘/ komponensével, 1 M &XO€}YL^ is hamis lesz. Ezért ha az Q‘a -edik pozíció után a  csak nullákat tartalmaz, akkor a keresésben nagyobbat léphetünk, és növelhetjük  -t az Q‘% -edik pozíción. Az algoritmus még egyszerűbbé tehető, ha a  -t kiegészítjük egy túlcsordulás bittel, amelynek 1 értéke azt jelzi, hogy  értéke már nem növelhető. ƒ Terjesszük ki az

függvényt az alábbi módon: ƒ 2 d .S- g ({’4“ ; , ƒ O”S•.  ” † h ; ‘ „ 0  j† h S ahol: :& 0 ˆ h ;–  Z Z# & ` 0j˜]— ™všs›  { (œ ; ( d .S- g c 0j˜#— ™všs›  {  (œ  ; ” h 0j˜#— ™všs› 2CY L    žom     oW  BX:
ŸoW?A+   ‘lX:
p2  R Ÿ i 0j˜#— ™všs› 2C ƒ ‹”S]C  ƒ YL: ‘ h¡}¢ o£53 C ž¤Co ? 3 ‘lX:
R2   119 ¦
ª« TŸ¬Ib#O”S•LS^ §¨ ”)2   ”  om‚ ­  ®    DF / +S] 2  ¯DyXS] ”S• 2  CS] ‘% ° 0C˜^— ™všz› 2C ƒ Y.R‘±” † h  ƒ YLuR‘ h ¢ o£53 : ž¤Co ?A+ ²‘lX:
p2  ³o9?A3 ¯Dyvp2N     A fenti meggondolások másik következménye, hogy célszerű egy olyan művelet bevezetése is amely amellett, hogy 1LO€}‹C^ -t eldönti, azt a legkisebb indexet is megadja, amelyre 1 O€}‹C^ hamis.

`>´ šzµ]š^¶  { (œR;a(~6 c ´ šzµ•š·¶  {  (œ  ; b h ´ š·µ]š·¶ 2j‹ .    o£     o£  3
Ÿo/1 ¢O¸ &NO€}‹# i ´ šzµ•š·¶ 2C·  .oEb  1LO€}‹C^¹o Ž¹bR4qO53 žO:
Ÿor1 ¸ & O€}‹C^RožŽ1 ‹€}‹.#^ Ez a feladat visszavezethető lineáris keresés 2.8-ra ¦ º ¬-»¬¼Ÿ‹.S^+S#b‹ ¨§ +S#bŒ2  ¯DyXS = b.om‚ ­
bŒ2  1 M & O€}Y.^ 52  ²‘l A program levezetéséhez a már bemutatott specifikációt használjuk. Legyen az invariáns tulajdonság: ° 2Cu? Š 9{2Ÿx ƒ ‹.S Š  ƒ O”S•A4‚Ž1LO€} Š # o£b  1 ‹€HY^#o Ž¹bR4q‹”  ½£5B
ŸožŽ1 ‹€}‹.#Ror1 ¸ &IO€}‹C^^o ?A3 ‘lX:
R2 R  120 11. VISSZALÉPÉSES KERESÉS .S#º ”S#e2 %¾ ;XS#CS, ¬<»¬¼YLS#¿S]b‹ Ž¹b.oE”  
ª« T ¬Ib^O”NS]LS#ž ® º

¬<»¬¼Ÿ‹LS#¿” S]b‹   À Á¿Â ° / Megjegyezzük, hogy a visszalépéses kereséshez hasonlóan több visszalépéses technikát alkalmazó algoritmus is levezethető, például a visszalépéses számlálás: .S#”S#¿S]ÃU2 %¾ ;NS#CS,S# º ¬<»” ¬I ¼ŸYLS^+S#bY ® b ÃU2  à « ‘% À Á¿Â °
ª T ¬Ib^O”NS]LS#ž / Programtranszformációk A továbbiakban olyan esetekkel fogunk foglalkozni, amelyekben a feladat állapotterét kell megváltoztatnunk. Vegyük észre: eddig is csináltunk már ilyet: bevezethetünk új változókat, vagy akár el is hagyhatunk komponenseket. Az összetettebb esetekben az eredeti állapottér bizonyos komponenseit újakkal helyettesítjük. 12.1 Koordináta transzformációk Gyakran előfordul, hogy az állapottér egy komponensének típusát egy kapcsolódó másik típusra kell cserélnünk. Az ilyen transzformációk úgy általánosíthatók, hogy egy leképezést definiálunk a két

állapottér egymásnak megfelelő komponensei között. 12.11 Típustranszformációk Típustranszformációról akkor beszélhetünk, ha az állapottér bizonyos komponenseit valami kapcsolódó típusra cseréljük. A programozási tételek – és általában véve a (feladat, megoldó program) párok – az alábbiakban bemutatásra kerülő transzformációkon keresztül általánosíthatók, ha az állapotterek közötti transzformáció tulajdonképpen típustranszformáció. Ekkor az ábrán látható valamely típuson megoldott program egyszerű szabályok segítségével átvihető egy kapcsolódó típusra. 121 122 12. PROGRAMTRANSZFORMÁCIÓK függvény halmaz függvény-típus sorozat vektor input file 12.1 ábra Típusok közötti kapcsolatok A programozási tételek átírása más típusra Az alábbi sémák a programozási tételek típusok közötti transzformációjakor elvégzendő helyettesítéseket definiálják. A transzformáció úgy

történik, hogy az első típus adott műveletét a második típus megfelelő (azonos sorban levő) műveletére cseréljük.
Halmazról ( ) sorozatra ( ) (egy input halmaz/sorozat esetén) A két típus közötti megfeleltetés: az  és sorozatok tagjai felsorolják az  és  halmazok elemeit.          "!$#%&   ()!$* +",.-  /0 1"()!$2  # A fenti megfeleltetésben szereplő ,.-  /0 művelet a ,-  3/ művelet olyan kiterjesztése, amely megengedi, hogy egy legfeljebb egy elemű halmazzal terjesszük ki a sorozatot. Ha a halmaz egy elemű, akkor azzal az elemmel terjeszti ki a sorozatot, míg ha üres, akkor a sorozatot helyben hagyja. Ennek megfelelően az elemenként feldolgozható 4 függvényről is feltesszük, hogy egy egy elemű halmazhoz legfeljebb egy elemű halmazt rendel hozzá. Az  65 művelet helyett az  változónak feleltettük meg az 3 ()!$* értéket, mert a ()!$ függvény

mindig a sorozat első elemét adja vissza ellentétben az eredeti értékkiválasztással. Példa (egyváltozós egyértékű elemenkénti feldolgozás): 123 12.1 KOORDINÁTA TRANSZFORMÁCIÓK   7   65  9  4;:=< " >$? 8 @98  +9AB 3 C!$#D&   +",.- 3/E:B4;:=<$ (B!$* >F?G? 1H(B!$2  #
Sorozatról (  ) szekvenciális input file-ra (lopop,ext) ( ) vagy (read) ( ): (előreolvasási technika) A két típus közötti megfeleltetés: ha az  sorozat nem üres, akkor megegyezik a (B!  ./E:IJ" ? és (B!  3/E:IK" ? sorozatokkal, míg üres sorozat esetén az  és  sorozatokkal. P K HKG Q2  R " P K HKG Q2  R P ST!$2$# "GL"()!NM!NM " "GL"()!NM!NM HO  ./=2 3  ()!$* 1C()!$2  # 3 C!$#D&  A transzformált program egy plusz ()!NM!NM (vagy 2  R ) művelettel kezdődik. Példa (egyváltozós egyértékű elemenkénti

feldolgozás): UV  "!$#D&   9 (B!$* C,W-  ./E:4;:=< ">F?G?  H()!$2  # V P J"GXQ2  C P 8ST!$2$#  " +",.-  /E:B4;:Y< ">$?? P  HJGZQ2  R
Halmazról ( ) vektorra (*"[$QQ]-^5` "[Q (B!Q$G"[$ ,.-Y acb5 *QH (B!Q$GQH ,.-Y a ) Feleltessük meg az  (és  ) halmaznak a :)*"[F- ? (ill. :)*QHcb ? ) párt oly módon, hogy az  (ill.  ) halmaz elemei a *"[ vektor "[F (B!Q$d - (ill. a *Q vektor QH ()!QF6 b ) indexű elemeivel egyeznek meg. `7   @98  11 897 -*  "[F (B!Q^egf *"[F -Ba -h9-egf * bjifkacbl3bmif bln*  ()!Qheof Példa (egyváltozós egyértékű elemenkénti feldolgozás): 124 12. PROGRAMTRANSZFORMÁCIÓK 89 7   65    4;:Y< " >$? L9p< H> bl*  (B!Qheof -q*  [  (B!Qregf * bjifEacbl974;:=<s [ -Ba >$?  bjif -r-Jeof


Sorozatról (N ) vektorra (*"[$QHJ-^5 "[F (B!Q$G"[F ,.-Y aKbl5` *QH ()!Q$QF9,W-Y a ) Sorozatok esetén a sorozat és vektor típusokra megengedett műveletek korlátozzák a két típus közötti megfeleltetés szabad választását: nem használható ugyanaz a leképezés, mint halmazoknál. Válasszunk hát a típusműveletekhez illeszkedő megfeleltetést! Feleltessük meg az  sorozatnak a :)* [ - ? párt oly módon, hogy az  sorozat tagjai rendre a * [ vektor -N6 [ 9,.-= indexű elemeivel egyeznek meg A sorozatnak viszont a :I* b ? párt úgy feleltessük meg, hogy a sorozat elemei rendre a vektor *  ()!Q$d b indexű elemeivel egyeznek meg.  "!$#t&  ()!$* 1H(B!$2  # ",W-  ./E: F?  -]* [ 9,.-=;if *"[H -a -^-Kif *Q" bmifkacb  bjif bl*  (B!Q^egf Példa (egyváltozós egyértékű elemenkénti feldolgozás): AB 3 C!$#u&   ",W- ./E:4;:=<$3

()!$* >$??  H()!$2  # bl*  (B!Qheof -q*  "[Q ,.-Y]if *QH bjifEacbl974;:=<s"[F -Ba >$? bjif -r-vif
Intervallum felett definiált függvényről ( #XSKawj-@5x #yGSKa és a függvény argumentuma -vif ) sorozatra (  ) Első ránézésre úgy tűnhet, hogy kihagytunk egy lépést, a függvénytípust. De vegyük észre, hogy a függvény típusra való áttérés nem igényel transzformációt! Itt tulajdonképpen a sorozatot az intervallumnak feleltetjük meg az alábbi módon: tekintsük az  sorozatot egy az zf"6  C!$#8a intervallumon értelmezett függvénynek, ahol a függvényértékek a sorozat megfelelő elemei. Ekkor a tételben szereplő függvénynek tulajdonképpen az 4|{w függvényt tekinthetjük. 125 12.2 ÁLLAPOTTÉR TRANSZFORMÁCIÓ - nS   4;:I-vif ? -r-vif  "!$#u&  4;:) (B!$* ? 1H(B!$2  # Példa (számlálás tétele): } l#~egfH& } S   € : } if ? lmif

r‚LƒC„ } } 9 if / l&  "!$#%&   € :B3 ()!$* ? lmif  ‚Xƒ"„  1H(B!$2 # /
Halmazokról ( † ) szigorúan monoton növő sorozatokra ( $ ‡ ) a kétváltozós elemenkénti feldolgozás esetén. A kétváltozós elemenkénti feldolgozásnál az okozhat gondot, hogy el kell tudnunk dönteni, hogy egy adott elem melyik sorozatban van benne. Ezért tettük fel, hogy a sorozatok növekvően rendezettek, mert így mindkét sorozat legelső eleme a legkisebb, és ha ezek közül a kisebbiket választjuk, akkor a tartalmazás egyszerűen eldönthető. Egyébként a transzformáció többi része megegyezik az egyváltozós esetnél leírtakkal (itt is szükséges, hogy a függvényérték legfeljebb egyelemű legyen). Természetesen az elem kiválasztása itt is elhagyható, hiszen a (B!$* művelet a sorozatnak mindig ugyanazt az elemét adja vissza. ˆ ‰ ŠZ‹Œ ] ŽF E‘ ’”Š– “ •J—˜  E‘ ’Š8 “ • š ŽF

E‘ ’VŠ– š ŽQ E‘ ’Š– “ •›U˜  k‘’VŠ “ •J› “ •J›U˜  E‘ ’VŠ8 “ •]› ŽQ E‘ ’Š “ •›+˜  E‘ ’”Š– “ •]› F Ž  6 œ ‘ U  1 ž ˜  z œ ‘  R Ÿ + — ˜  E  ‘ g ’  Š • F Ž  6 œ ‘ q  ¡ ˜  z œ ‘  C Ÿ  — Q Ž  E  ‘ n ’ Š• ŽQ œz‘ hŠ–˜  œz‘  ™ ™ ™ ˆ]‰E¢F£¤GF¦ š§Cš¨ ŽQ œz‘ skªY«EŸ)Ÿ ˆ]‰­¢Q£®¤F¦ š®§Rš¨ ŽF œ6‘ skª ˆ ‰E¢F£¤F¦ š®§Cš «sª ¨ ˜  œ6‘ sNŸ)Ÿ ] ¨ ˜  œ6‘ sNŸ)Ÿ ŽU‰Eœ6‘¬­¤’ ˜]‰Eœz‘ ¬­¤’ ŽU‰­œ6‘ ¬N¤’ ˜J‰kœz‘ ¬­¤G’ 12.2 Állapottér transzformáció Az alábbiakban egy olyan példát mutatunk be, amelyben az állapottér transzformáció nem egyszerű típustranszformáció. A feladatot úgy fogjuk megoldani, hogy eredeti állapottér helyett egy új (absztrakt) állapotteret választunk, azon megoldjuk a feladatot, majd a megoldásban

szereplő műveleteket megvalósítjuk az eredeti téren. Tegyük fel, hogy van egy karakterekb ől álló szekvenciális file-unk, ami egy szöveget tartalmaz. A feladat az, hogy számoljuk meg, hogy hány olyan szó van a szövegben, 126 12. PROGRAMTRANSZFORMÁCIÓK } amelynek hossza nagyobb, mint a megadott érték! A szövegben a szavakat elválasztó jelek (egy vagy több) választják el egymástól. Az elválasztó jelek halmazát jelölje  Így első ránézésre a feladat nem vezethető vissza egyetlen ismert programozási tételre sem. A feladatot ezért úgy általánosítjuk, hogy bevezetünk egy új állapotteret: tegyük fel, hogy a szövegfile helyett egy olyan file-unk van, amiben az eredeti file szavainak hossza szerepel. Legyen ez az absztrakt file ¯ R° , míg az eredeti szövegfile 4Z"± . A feladat specifikációja az új téren: ² ³°µ´”¶ ¯ · ³° ¯¹¸ º 3:I¯|¯½­¾G¸ ?¿+ÀzÁ­Â à } » .:=¼ ÄdÅ : ¯ Ä;È ?G? [ÇÆ Ez

a feladat visszavezethető a számlálás tételének szekvenciális file-ra felírt változatára: N! M  Sr:¯ ? P ¯KH¯G¯1Q2  C 19& P ¯|ST!$2$# }  H¯ È / l+if  ‚Xƒ"„ P ¯KH¯G¯1Q2  R Hátra van még az absztrakt !NM  S és 2  R műveletek megvalósítása. Az absztrakt ¯ file-nak pontosan akkor van még eleme, ha az eredeti 4 file-ban van még szó. Ezért van szükség az !NM  S műveletre, amely arra hivatott, hogy biztosítsa a 2  R művelet elején megkívánt invariáns tulajdonságot: vagy P 4ɹNST!$2$# vagy =4 a következő szó első karakterét tartalmazza. Ezen invariáns tulajdonság segítségével a 2  R műveletben könnyen el lehet dönteni, hogy lesz-e visszaadott érték, vagy már az absztrakt file is kiürült. Az absztrakt file-ok kezelésének általában is ez a technikája: egy !NM  S művelettel biztosítjuk a 2  R elején megkívánt invariáns tulajdonságot, és gondoskodunk róla, hogy a 2 

R művelet ezt az invariáns tulajdonságot megtartsa. Általában is igaz az, hogy az invariánsból egyszerűen eldönthető, hogy lesz-e még visszaadott elem, ezért az absztrakt 2  R mindig elágazással kezdődik! Nézzük tehát az absztrakt műveletek megvalósítását az eredeti állapottéren: ezek mint látható szintén programozási tételek egyszerű konstrukciói. 127 12.3 EGYSZERŰ PROGRAMTRANSZFORMÁCIÓK ÊË !NM  Sr:¯ ? ÌÍ P 4 =4 4ZQ2  C P 4ST!$2$#ÏÎ8=4L5  P 4 c4N4@"2  R ÊË P ÌÍ ¯ Q¯KY¯lQ2  R  P 4 ST!$2$# P ¯ ST!$2$# H¯ 9& P 4ST!$2$#ÐÎ8=4O5   Q¯1Q¯mif P 4=4 4ZQ2  C P 4ST!$2$#ÐÎ8=4L5  P 4=4 4ZQ2  C P ¯ ¹NST!$2$# / 12.3 Egyszerű programtranszformációk Azt mondjuk, hogy az komponensét ől, ha ²  program M]:  ? programfüggvénye nem függ az állapottér Ä  Ñv} 3NU58ÒjÓ ÀdÔC 3: 5`:G 6fHGSKa < - > H¹Õm7EÕ ?^Ö MJ:  ? :) ?

OMJ:  ? : ?  ² Ä Azt mondjuk, hogy az  program  Ä változója konstans, ha ² Ñ ÑK× ÑT} × Ä l5 5  :B ? .: 58Òٖ Ø Õ  Ä ?  ² Ä Azt mondjuk, hogy az  program végrehajtása nem változtatja meg az  Ä változót, Ñ Ñ ha Ñ l5ÒjÓ ÀdÔC 5¼M]:  ? :) ? " Ä  Ä Nem megengedett feltétel kitranszformálása elágazásból ² ² ƒ ±l:IÛv[j  [Fkd6dGÛÜ  Ü ? , ² ´ N0 0 0N0F  ¸ programot az alábbi módon: ² ² [ ´É kU´ ¿ ´ÝÞ´Ék U´ÏÝ  [  ¿ ([ (Ü Legyen o ² Ú ¸´ az  ¸ Ú ² ¸ ² ² [´Ùd6­´ ( [ kk k ( Ü nÛ [ :B [ kd6d ¿ ?  kk GÛ Ü :) [  6dd ¿ ? ƒ ±l:B( [  [  6dd( Ü  Ü ? ² Ekkor az  ¸ program ekvivalens  -sel -n. ² ¿ . Konstruáljuk 128 12. PROGRAMTRANSZFORMÁCIÓK Nem megengedett ciklusfeltétel kitranszformálása ß² Ú Let ² ¸´ ² ² ² ´ ² 0 0Q  xà á:IÛV Kâ ? , ² ¸ 0N0

programot az alábbi módon: ² ² [ ´Ak ´ ¿ ´7Ý ¸w  [  ¿ ( [ ´g6dT´ Ekkor az  ² ¿ . Konstruáljuk az  ¸ Ú (JÛr:) [  6dd ¿ ? ( Kâ (;nÛr:) [ kd6d ¿ ? ² ¸ program ekvivalens  -sel -n. Szimultán értékadás helyettesítése egyszerű értékadásokkal ² ´ 0N0 , a következő szimultán értékadás: ² ² ² [ É ´  kU´ ¿ ã  [  ¿ ä  åæ  [  6dd ¿ 4 [ :) [  6dd ¿ ? kd6d 4 ¿ :B [ kd6d ¿ ? ² ² Konstruáljuk az  ¸ Ú ¸´ ¸ 0N0 programot az alábbi módon: ² ² ² ² ² ¸ [ ´Ak ´ ¿ ´ [ ´Ðk U´ ¿ ¿ ã [  [  ¿ Legyen oÚ ² ä  ¸ åæ [ 74 [ :) [ kd6d ¿ ? . . ¿ 74 ¿ B:  [ kdd6  ¿ ?  [  [ . . Ekkor az   ¿  ¿ ² ¸ program ekvivalens  -sel -n. Szekvencia sorrendjének felcserélése  Y[ Ï:  [$ç  ?   ­[ Ð:  "ç  [ ? és az állapottér azon komponenseit amelyektől az  [ függ 

nem változtatja meg és viszont, akkor  [Y ekvivalens  ­[ -el. Ha 129 12.3 EGYSZERŰ PROGRAMTRANSZFORMÁCIÓK ÊË ÌÍ  [Y ÊË ÌÍ  [   ­[   [ Ciklusmag-beli szekvencia sorrendjének felcserélése Legyen  Ïà8á:IÛp  â ? ,   â [ -ben. Legyen továbbá  ¸ 㠁 ä ? 9Ðâ t:)-èÄ®éè Ä6ê ;[ ipf ç  â [ és? tegyük fel, hogy az - konstans ç -^-vif . ã :  â [ ä åæ  ¸ åæ Û Û -^-vif Kâ [ Ä®éèÄdê  â[ [ - 9-Kif ^ Ekkor  ekvivalens  ¸ -vel. Függvény helyettesítése változóval ² ² ² ² ² ² ² [ ´¼6d­´ ¿ . és legyen 4 egy az Ä®ë ´¼6d­´ Ädì altér felett Legyen oÚ ´ 0N0 , Äë Ä®ì definiált függvény, melynek értékkészlete í . Tegyük ²fel továbbá, ² 0N0 hogy az  kd6d ¸^´ ¸ programot az alábbi változók konstansok  -ben, és készítsük el az  ¸ Ú módon: ² ² ¸î Ekkor  W[ [X´É kU´ ² ¿  ¿

´7í ² ¸ ekvivalens  -sel -n. † †l4;:B čë  6dd Ädì ? ÀdðEñ ësò9ó9ó9ó9ò ðEñ ì  éèô rï Rekurzívan definiált függvény helyettesítése } Õ Ö í Legyen í egy tetszőleges halmaz, È & egy egész szám, továbbá ±³C¶g´@í Ö í függvényt az függvény, / â /Nõv[Fkk k/Nõ Õ ê [è5Z¶ rögzített, és definiáljuk az 4LC¶ alábbi módon: 4 :B& ? ; 4;:Yeèf ? továbbá Ñ 4;:Ye -rög& : } if ? /â  / õv[  . . . . /Nõ Õ ê [ } 4;:)-Kif ? ±l:I-KifHN4;:I- ?  6dd 4;:I-e if ?G? 130 12. PROGRAMTRANSZFORMÁCIÓK Tekintsük az alábbi  programot: -^&  [ Û Kâ -h9-Kif ahol - mind  â -ban, mind  [ -ben konstans, és  â -ban hivatkozás történik értékére. Ekkor  ekvivalens az alábbi programmal: -N†3†"õT[skd6 †"õ Õ ê + [ &WG/ â G/Nõv[Fkd6/Nõ Õ ê [  [ Û } †3† õv[  6d† õ Õ ê [ ±l:)-KifH 4;:)-

? kdd6N4;:I-Te if ?G?  .†  6d† õ Õ ê À Ädê  éèô Kâ ï [ -h9-Kif 4;:I-riÉf ? Szekvenciális megfelelő Egy feladat megoldása során sokszor szembesülünk azzal a problémával, hogy különböző típusértékhalmazokba eső értékek közötti kapcsolatot kell leírnunk, vagy ilyen értékeket kell összehasonlítanunk. Erre leggyakrabban akkor kerül sor, ha valamilyen állapottértranszformációt végzünk, és meg kell adnunk az eredeti és az absztrakt tér közötti kapcsolatot. Az ilyen megfeleltetések formális megadása általában elég nehézkes A szekvenciális megfelelő fogalmának felhasználásával azonban ezek a kapcsolatok is egyszerűbben írhatók fel. Legyenek

 
elemi típusok (egy típus akkor elemi, ha önmagával van reprezentálva, azaz a hozzátartozó reprezentációs függvény az identikus leképezés). Az elemi értékek halmaza legyen 
  
  Tegyük fel hogy a  típus reprezentációs

függvényére igazak az alábbi megszorítások:  
 ,  kölcsönösen egyértelmű (bijektív),  megengedett típuskonstrukció (azaz direktszorzat, unió és iterált konstrukciókból épül fel) Legyen továbbá  "!#$# %& az úgynevezett bázishalmaz, ahol   *  +-,/. tetszőleges típusértékhalmaz, és jelölje az elemi típusok halmazát 131 )(  01 132 !#
2
3 lelője: ahol 13. SZEKVENCIÁLIS MEGFELEL Ő 4
5& . Ekkor a 687 elem  bázisra vonatkoztatott szekvenciális megfe@AAA D ha G7H A D 6-EF F E  J7H I LKM7N0 B 9#:<; 6 = >.? AA O 6 = >F ha ha J  H 7 I LKJ7N I 0 és  rekord AAC P ha J  H 7 I L   K J  N 7 I 0 és  egyesítés 6 = >  + .  Q 6 = >.+ ha J7H I LKJ7N I 0 és  sorozat O 6 = .1 P 6 = .1 Q 6 = .1 RTS<U 9#:<; RTS<U 9#:<; 6F 9 3= .F  9#:<; 6F 9<V = - XWZ[Y  6-. =  9#:<; 6  = >.+  #9

:#; 6-F] %^` )a = > A jelölés egyszerűsítése végett, ha a bázis egyelemű, akkor a bázishalmaz helyett az elem is írható, azaz bc!#$#& esetén 9#:<; 6 =   8. dde #9 :#; 6 = F Tekintsük a következő példát: f    9#:<; Xf .F U :#g dihj
kl 9#m3npo diqlrsutZ.+ 9#:<; wvuxjyf .+ wz :<o){ d x
|tl}Z (~ S|d3€ y s$‚.+ 9#:<; wvuxjyf .+ :#g di
k? z S>d x„ƒ U†#‡/d3h yˆ .+ ‰‹Š ‰‹Š ‰‹Š hj
>k  qlrsut  x
|tZ}  € y s$ 
k  x„ƒ  h yˆ  Legyen 0‚‚! vuxjyf 4‰ Š & , 6Z7N . Ekkor 9 :<; 6 = hj
>k. a 6 sorozatbeli rekordok névrészeinek sorozata ( 7 h
k ) j 9 :<; 6 = vuxjyf . a 6 sorozatbeli rekordok névrészének és születési hely részének egymás után fűzésével kapott karaktersorozat 9 :<; 6 =e! x
|tl}Z
>k&<. a 6 sorozatbeli rekordok születési hely és év részének egymás után fűzésével kapott sorozat ( 7 Xx


tl}ŒN
k|.  ) 9 :<; 9 :<; 6 = hj
>k. = vuxjyf a 6 sorozatbeli rekordok névrészeiből képzett karaktersorozat 9 :<; 6 = Ž. üres sorozat Hogyan használható a szekvenciális megfelelő az állapottértranszformáció leírására? Tekintsük a 12.2 fejezetben bemutatott példát Ott egy szövegfile-t a benne levő 133 szavak hosszainak file-jával helyettesítettük. Tegyük fel, hogy vuxjyf  wy hs|’‘4q
unió típus, ahol y hs$ a szavakat alkotó betűk típusa, q
ˆ pedig az elválasztó jelek típusa. Ekkor az “”d•0– 9#:<; wvuxjyf eredeti file és a —Nd•˜– 9#:<; ‰ absztrakt file között kell a kapcsolatot definiálnunk. Ehhez vezessünk be még két absztrakt filetípust: legyen s‚ 9#:<; 9#m Sd•qlr ƒ ‘ 9#m3n d™qlrsuhj
| , ahol qlr ƒ  9#:#; wy hs|‚ és qlrsuhj
|š 9#:<; q?
ˆ . , továbbá legyen k 9 :<; qlr ƒ Ekkor:  az “/d30 és az n  ag d›k és a —œd3˜

d™s közötti kapcsolat: #9 :<; n =e! y hs|M4q
ˆ &2.‹ #9 :#; “=e! y  h s|M4q
ˆ &2.F  az n d›s és a g dik közötti kapcsolat: 9#:<; g = qlr ƒ .l 9 :<; n = qlr ƒ F közötti kapcsolat: ~ S<, —•.l ~ S<, g KŸž ( 7¡ *  ~ S<, —T.£¢d—   ~ S<, g  F Fel kell még tennünk azt, hogy n a lehető leghosszabb azonos típusú részsorozatokból áll, vagyis az s típus invariáns tulajdonsága: ¤ n .?šž ( 7¡ *  ~ S<, n .¦ * ¢†d n  9 m S§ n ¨  9#min K n  9#m3n § n ¨  9#m S A fenti leírás matematikai egzaktsággal definiálja azt az állapottértranszformációt, amit a 12.2 fejezetben csak szavakkal írtunk le Természetesen másképp is formalizálható egy állapottértranszformáció, de a szekvenciális megfelelő használata sokszor leegyszerűsíti a leírást. ˆ . Programinverzió 14.1 Egyváltozós eset  
  
   !" #

$"    
%
) &( * +)-
, . / )  )0,  1 2 * #435!635 ) , 7 
%
) &8 9 +)
, . 1 2/ 9) :),! ) , ; Legyenek , , és tetszőleges típusok. Legyen továbbá , valamint , és függvények. Tekintsük az alábbi specifikációval adott feladatot: Tegyük fel, hogy az és függvény értékét kiszámító program az alábbi alakban írható fel: 135 136 < = )  9 >?@ A < ; )CB  9 EDGFH 9/I  < ;# )  < = < ; < J# 14. PROGRAMINVERZIÓ Ha az , és programok végrehajtása nem változtatja meg az értékét, akkor a fenti programot elemenként előállító programnak nevezzük, Hasonlóan, tegyük fel, hogy az alábbi formában írható fel: # 9 változó függvény értékét kiszámító program pedig az
% KL &( * M%L , . 2 L  L ,  1 / *  # L, 7 < #N < #= < #=# < #N *  LCO *-PQSUR T < #7 *2B;LVO WPX  L< 

WPY Q #7#E *  L Ha az , és programok végrehajtása nem változtatja meg az változó értékét, akkor a fenti programot elemenként felhasználó programnak nevezzük, ! függvény elemenként feldolgozható, és minden Tegyük fel továbbá, hogy az egyelemű halmazra a függvényérték egyelemű. Ekkor a függvénykompozíció helyettesítési értékének kiszámítására vonatkozó programozási tétel alapján a feladat megoldható a fenti elemenként előállító, egy elemenként feldolgozó és az imént bemutatott elemenként felhasználó program szekvenciájaként. A feladatra azonban egy hatékonyabb megoldást is adhatunk a programinverzió segítségével: ekkor a közbülső két sorozat típust kihagyhatjuk és a három ciklust egybeírhatjuk az alábbi módon: 14.2 KÉTVÁLTOZÓS ESET < 7! )  < #N *  A < J )CB  Z >8J[ E < #7E *2B Z  < J# )  < #7#E *  137 14.2 Kétváltozós eset 
      


`8ab   
   
   !c& d" ]^ #  E$ " 
%
)   &e
)   &( * +)
  , &`)
  , . ,Ef , 1 2/ )*   )#4 35!)     ) ) ,  B    )  , ;     < 7  )   < =  )   9  g?@ 9  g ?@ A A < ;  )  B   < J  )  B   9  EDGFH 9/I    9  ED/FH 9/I   < J # )   < ; # )   9 9 #  Legyenek , , , , valamint és tetszőleges típusok. Legyen továbbá , , és és függvények. Tekintsük az alábbi specifikációval adott feladatot: Legyenek az alábbiak: és függvényeket kiszámító elemenként előállító programok az és tegyük fel, hogy az előállított és sorozatok rendezettek. Legyen mint korábban, továbbá tegyük fel, hogy egy olyan kétváltozós egyértékű elemenként feldolgozható függvény, amely minden olyan halmazpárhoz, amelynek tagjai legfeljebb egy elemet tartalmaznak, pontosan egy

elemű halmazt rendel hozzá. Ekkor a függvénykompozíció helyettesítési értékének kiszámítására vonatkozó programozási tétel alapján a feladat megoldható a fenti két elemenként előállító, a kétváltozós egyértékű elemenként feldolgozó és az -at kiszámító elemenként felhasználó # 138 14. PROGRAMINVERZIÓ program szekvenciájaként. Vajon ebben az esetben is összeinvertálhatóak a fenti programok? A válasz természetesen: igen, de a megoldás itt nem olyan egyszerű, mint az egyváltozós esetben volt. A probléma a szekvenciális file-oknál felmerülttel analóg: az elemet előállító program ( ill. ) az egyes elemeket ugyanúgy szolgáltatja mintha file-ból olvasnánk őket: csak akkor nézhetjük meg a következő elemet ha legeneráltatjuk. Ez sugallja azt a megoldást, hogy az és sorozatokat tekintsük az elemenként feldolgozásban absztrakt file-oknak. Az elemenként felhasználó program beinvertálása nem okoz

gondot, ugyanúgy történik mint az egyváltozós esetben. < ;  < ;  9 9 jh i!k7l/mon0p;qjrbhji!k7l2msntNq u;n0pNrvwn0pwr n0pyxwzwk7}E{a~Hv~ rju;nt|rvwntar nt4xwzwk7{av mov|q uJn p€ l-h=zNƒ‚„u;n t  l0h=z= u;n ty {a‹ ‡jl-vwh=n zNpˆŒ ‚ vwm‰n uJt n q pŠ u;n t ‹ uJvŽn0n p p   uJnvwn t t uJn p€ {|‹ ‡jl0vwh=n z=pˆ ‚vwmn u;t n q p€ u;n t † † † kx ’‘ t m‰“=vwn0p=”|rj•Žq k–x ’‘ t m‰“=vwn0p=”|rJ“=vwntŽ”Nq kx ’‘ t mo• rJ“=vwntŽ”Nq u;n p rjvwn p rn p xwzNk={|v uJn p rvwn p rn p xŽzwk={|v u;n t rvwn t r n t xwzwk7{av uJnt|rvw}En~ tarnt–xŽzwk={|v movrjk=q } pp ~ mt { p q } pt ~ m{ t q }E~H~ mov|q —˜ PN› œ– 9   ™š < 7  )   —˜  9  B=*9  B79   Y )0 ™š A   < 9   >: œ PY Q  9  g )ž œ PYQ ; ) B=*9  ahol az absztrakt műveletek megvalósításai: / —˜ PN› œ– 9   ™š < 7  )   —˜  9  B=*9  B79   Y )0

š™ A   < 9   >: œ PY Q  9  g )ž œ PYQ ; ) B=*9  / Időszerűsítés 15.1 Az időszerűsítés definíciója
Legyen adott továbbá egy olyan file, amely transzformációk sorozatát tartalmazza. Ezt   leképezés  , a file-t fogjuk módosítófile-nak nevezni. Legyen  ekkor    A feladat az, hogy időszerűsítsük a törzsfile-t a módosítófile-ban leírt transzformációk$&%  és kal. Jelölje ! az időszerűsítés transzformációt Ekkor "# "# )(+*-, .,0/+1-24352768:9;9;9<8=,?>@8=,BA<)( Induljunk ki egy olyan adatfile-ból amelyben azonos típusú elemek találhatóak. Ezt a file-t törzsfile-nak fogjuk nevezni. Legyen az elemek típusa , ekkor 
 Ahhoz, hogy a feladatra megoldást adjunk ez a leírás még mindig túl általános, ezért további kikötéseket teszünk a file-okra.
CEDGFH* GI 1. Az időszerűsítés kulcsos  JEDKLI FH*-MNPO D

F O Legyen és , ahol egy tetszőleges rendezett halmaz, a rekordok kulcsrésze; a törzsrekord adatrésze; pedig az elvégzendő transzformációt definiáló típus. Feltesszük továbbá, hogy mind a tözsfile, mind a módosítófile a kulcsmező ( ) szerint rendezett, azaz a és típusok invariáns tulajdonságára: SQ R@)( UT #V W@XZY5[]^  ,`a( cbK[Sd ](fe DhgN(fe^iGA D Q;j`a, kT #V W@XZY5[]^  ,`a, cbl[;d $,me Dngl,me5iLA D 139   140 15. IDŐSZERŰSÍTÉS 2. A törzsfile a kulcsmező szerint egyértelmű Q R )( @TCV#W *po XZY5[]^ " ,`a( qd Wslr ot$( e D . r (Eu D 3. A transzformáció csak az alábbi három féle lehet O  a(7"v`A<wyxs"vz>"wEotvH{ v`A| }  vz>~ " I vz{~ €n] * ahol &‚;ƒz ƒH]I„ I  Ahol a jelölés nem rontja el a szelektorfüggvények egyértelműségét, ott az egymás után következő szelektorfüggvény-sorozatból a közbülső elemek – a jelölést

egyszerűsítendő – kihagyhatók, ezért pl. ha , akkor helyett csak -t írunk. ,  ,†  , M  Hátra van még annak leírása, hogy hogyan hatnak a fenti transzformációk a törzsfile-ra. Kényelmi okokból a transzformációk eredményét halmazként adjuk meg (ez elegendő, mert a törzsfile kulcs szerint egyértelmű). Ehhez bevezetünk , ahol rendezett halmaz, pedig néhány jelölést: legyen tetszőleges típus, valamint . Ekkor F Š ‡ " D ˆDF h]FH*-‰h]Š X  ‡‹   ‡ eŒ W@X`Y["5  ,Z ‡#pdE  D   e D? ,`  ‡ ‡G*y D    ‡‡ e  W@X`W@X`Y["5Y[" 5 " ,Z ‡#pd‡Ž‘pdhE ‡ e Dt’D  “•– ), e *-( ha , e ( ” , e a( y  — a, e *-( ha , e x ˜B), e *-( ha , e o ahol (Euš$(Eu X (  (Eu D .r , e D  * ha , e D X ›( D  a, * (  ™ e (  * – különben ? ,   (   a, m e Ž D * m , e M * — ),?e-*-(  ™ ( @ œ y ha e D Xr ›( D  “”• ›(Eu (Eu X (  (Eu D

r , e D žkülönben a,me DŽ*Ÿ,?e   )(+-,me D -Ÿy œ ha ,me D X ( D  0˜ a, e *-(  ›(  * különben 4. A javítás művelet csere Q;jZa, ŒTJVŽWPX`Y5[]^ " ,`a, pd *-,me M o T ,?e  konstans vz{ lc mező helyére Ebben az esetben a szoktuk felírni, hogy a ]I -t írunk és a ,me Ž  típust )(+* D Ÿ úgyfüggvényalkalkalmazást a módosítórekord adat,me részére ( ) cseréljük. 141 15.2 IDŐSZERŰSÍTÉS EGYÉRTELMŰ MÓDOSÍTÓFILE-LAL A feladat specifikációja tehát: ¡   ¢%  %’ (q£ , ( ¤C¢%  (f£¦ ,m¦ § ¨a( £ (f£¦  ,.,?¦ ª!ˆ(Œ "# )( £¦ *-, ¦ - és az Ha a fenti specifikációban időszerűsítésről beszélünk. []^ ‡ pontok teljesülnek ‡  « , akkor közönséges, ha ‡ ¬ akkor egyszerű 15.2 Időszerűsítés egyértelmű módosítófile-lal Mivel a közönséges és az egyszerű időszerűsítés között tulajdonképpen csak a javítás

elvégzésében van különbség, mi a továbbiakban az egyszerű időszerűsítéssel fogunk foglalkozni. Közönséges időszerűsítés esetén az adatrész cseréjének helyére a javító ) elvégzése írható. függvény ( ,me  A feladatot három irányból is megpróbáljuk megoldani: visszavezetjük halmazok uniójára, egyváltozós egyértékű illetve kétváltozós egyértékű elemenkénti feldolgozásra. 15.21 Visszavezetés halmazok uniójára Tekintsük a file-okat halmaznak, és próbáljuk meg halmazokon megoldani a feladatot. Milyen kulcsértékek fordulhatnak elő az új törzsfile-ban? Természetesen csak olyanok, amelyek vagy -ban, vagy -ben, esetleg mindkettőben szerepeltek. (q£ I , I­¦Ž.I œ  ®­¨ ¯ ° <"±  I­¦ Terjesszük ki a halmazt az üres értékkel: A segítségével az egyes transzformációk értelmezési tartománya és értékkészlete az alábbiak szerint alakul: v`A4CI²¢®t¨¯ ° <]±  v

> †®­¨¯ ° <]±  †I v { CI² I ®­¯ <]± értéket veszi fel, akkor az azt jelzi, hogy vaHa egy elem adatrésze az ¨° lójában nem létezik, és ezért nem kerül bele az új törzsfile-ba. Idézzük fel az unió programját: 142 15. IDŐSZERŰSÍTÉS ³´ · ¸  ¹‡ œ ‰ µ¶ · º» ‡¼r »ž ½h‰ r ‰ » X ‡¾œ ¿  Xm‡¾  X ‰ · ¸ ·¹œÁ  ‡ ¸ ‡m  ‰­¸.‰    mX ‡¾ hX À ‰ · º ·¾œÁ  ‡ º ‡?  ¿ ¿ hXmÀ ‡¾  · º ·¾œÁ ‰hº.‰  X ‰   A feladat a következő megfeleltetéssel visszavezethető a fenti programra: ‡‰  ·  ‡¼r »ž½h‰ r »  š X ‡¾œ ‰   Xh‡  X ‰  (£ , ( (q£ r »ž½h, r » Dh X q(q£ D =œ ›, D < D X (q£ D  D X , D  A megfelelő program: (=¸» q( £ r »ž½n, ’r » Dh X f›(q£ D =œ ›, D  ¿ D X ›( £ D = D`X À › , D  ¿ D X ›( £ D = D X ›, D

 ¿ D Xr › ( £ D = D X › , D  ÃA Ã> Ã{ Vizsgáljuk meg most, hogy mit kell tenni az elágazás egyes ágaiban: D (£  a( £ * D 1. Ha a kulcs csak a eredeti törzsfile-ban szerepelt, akkor a elemre nem vonatkozott módosítás, változtatás nélkül kell kiírni az új törzsfile-ba. ÅÄ Ã A ÆÇ (=¸( œÁ  a( £ * D ( £ ¸( £   a( £ * D 15.2 IDŐSZERŰSÍTÉS EGYÉRTELMŰ MÓDOSÍTÓFILE-LAL 143 D 2. Ha a kulcsérték mind az eredeti törzsfile-ban, mind pedig a módosítófile-ban szerepelt, akkor a törlés és a javítás műveletek végezhetők el. Ebben az ágban a kulcsú elemet mindkét file-ból el kell hagyni. D D ÄÅ Ã > ÆÇ  ),z*yD + o ¿  ),z*yD + ( ¿  a,Z D S x ¿ à HF QÈ ÉBQ¤ ¡ (ʺ( œÁ EDŽ*  a,Z D +  ,Cº,   ),z*yD (q£¸(q£   a(q£* D D 3. Ha a kulcs csak a módosítófile-ban szerepelt, akkor csak a beszúrás műveletet lehet elvégezni, és a kulcsú elemet

ki kell törölni a módosítófile-ból. ÄÅ Ã { ÇÆ  ),z*yD + x ¿  ),z*yD + ( ¿ ¿  ),z*yD + o ÉBQ¤ ¡ (ʺ( œÁ EDŽ*  a,Z D +  BÉ Q"¤ ¡ ,Cº,   ),z*yD a programnak hibajelzést is kell adnia, akkor azt a fenti struktogramokban ÉBQ¤Ha¡ -val jelzett helyeken kell megtennie. Térjünk most vissza az eredeti feladatra, ahol halmazok helyett szekvenciális file Ë művelet értelmezve. Ekkor a program ok szerepelnek. Legyen az inputfile-okon a ° az alábbiak szerint alakul: Ì-ÍaÎÏEÐSÍaÎÏ)ÍaÎÊÑ+ÒyÓ Ô;Ð<ÕpÌ-ÖψÐ+ÖψÖÑSÒyÓ Ô;Ð ÍŽÑ ×HØÚÙ Ì-Í ×?ÛÜ ÒyÖ`Ý4ÌfÖ×?ÛÜ ÒyÖ Ì-ÍaΌ×mÌfÖáà4Ð+ÍaÎâ ãsä­Ð+Öâ ã<å Ì-ÍaΌ×mÌfÖ¼à Ì-ÍaΌ×?Ì-Öáà:Ð+ÍaÎâ ã:ç­Ð+Öâ ã<å Ý!ÌfÖK×mÔ;æp۝ܟÒyÖ Ð+ÍaÎ<â ã=×mÐ+Öâ ã Ý!ÌfÍaÎP×mÔ;æpÛÜ ÒyÖ Þsß ÍŽÑSè<é€Ó-ê<Í Ð+ÍaÎSå Þ Þsß

Ì-ÍaÎψÐ+ÍaÎ<Ï)ÍaÎÊÑ+ÒyÓ Ô;Ð ë!íì ë!î ì ß ahol ÄÅ Ã@> ï ÇÆ , o ¿ , ( ¿ , x ¿ à FHQÈ ÉBQ"¤ ¡ (Ê"ð W  ‡ (S , DŽ* ,  ;( £ * ( £ Ÿ( £  °  Ë ›,z* ,Z-,ñ ° Ë 144 15. IDŐSZERŰSÍTÉS ÄÅ @à { ï ÆÇ , x ¿ , ( ¿ ¿ , o ÉBQ"¤ ¡ (Ê"ð W  ‡ (S , DŽ* ,  ÉBQ¤ ¡ ;,Z* ,Z-,ò °  Ë 15.22 Visszavezetés egyváltozós elemenkénti feldolgozásra Az időszerűsítés állapottere felfogható úgy is, mint a törzsfile és a módosítófile összefésülése – tegyük fel, hogy egy file-unk van az alábbi szerkezettel: kulcsérték -ból vagy -ből adatrész -ból vagy transzformáció rész -ből vagy Természetesen az adatrész és a transzformáció rész mindegyike nem lehet . Formálisan: (q£ q( £ , , ó ó ‡NX Legyen elemét. Ekkor: ó  I  I ¦  O¦  ®­!¯ °  "± ®­#¯ ° <]± ó  )I EDh"FB* ]I ¦ -Mn"O ¦ I œ

®ô!¯ °  "±  O œ ®­#¯ ° <]±   ‡G D  „(q£ D žœ  , D  . Jelölje ]‡ az ‡ ®­#¯ °  "±š* DáÀ ( £ D  ™  ha "‡õ X  £ )( * D * D ( £ D  "‡õ ha "‡õ X ]‡ G S ®­#¯ °  "±š* DáÀ ›, D M  ™ ha "‡õ D X ›, D   ), z * D # M * "‡õ ]‡G S ha "‡õ X  . Ekkor ®­¨¯ ° <]± egy tetszőleges Az állapottértranszformációt alkalmazva így eljutottunk az cq   &) D*Ÿ MŽ) Ÿy elemenként feldolgozható függvényre felírt egyváltozós elemenkénti feldolgozáshoz, ahol a transzformációs rész alkalmazása az adatrészre: ¡  ó “ö  *  MŽ)   ” •ö ®­M¨¯ ° <]±  \ M \ %÷ A specifikáció: ‡ ( ha ha ha ha  M¹ª®­!¯ ° <"±  M (   mrª®­¨¯ ° <"±  M x   ‚®­#¯ ° <"±  M o   mrª®­¨¯ ° <"± ó

145 15.2 IDŐSZERŰSÍTÉS EGYÉRTELMŰ MÓDOSÍTÓFILE-LAL ¤C ‡¦ § ¨ ‡  ‡ ¦ és az ["5 ¬ ª!ˆ(Œ’c ‡ ¦ Ÿ pontok teljesülnek A halmazokra felírt megoldóprogram:  ?r‚®­¨¯ ° <"±  ¿  M¹&®­#¯ ° <]± ¸ªˆ DŽ*   ahol  ( ¸’» ¿ ¿  ( ÉBQ"¤ ¡ ¿ (ʺ’» ‡`r  »  ?r‚®­Xh#¯ ° ‡  "±   ‚®­¨¯ ° <"±  ¿  M ªr ®­!¯ ° <"± ¿  M &r ®­#¯ ° <]± Ã> Ã{ (=¸( œzÁ ‡ ¸ ‡h  ÄÅ Ã > ÆÇ  o  x ¿ ÉBQ"¤ ¡ ¸‚ˆ DŽ*  ) - ÄÅ Ã { ÆÇ  x ¿ ¿  o ¸ªˆ DŽ*  M  ÉBQ¤ ¡ Térjünk vissza most az eredeti állapottérre:  mrª®­!¯ ° <"±   ª®­!¯ ° <"±   mrª®­!¯ ° <"±  ¼‡ r »  Xm‡  Mô‚®t#¯ ° <"±  M ‚r ®t#¯ ° <"±  M ‚r ®t#¯ °

<"± T T T T T (q£ ’  r »ž½n, r » Dn X q›(q£ D =œ , D < D X ›(q£ D = DáX À , D`X À ›(q£ D = D X , D X ›(q£ D = D X , D  D  D  146 15. IDŐSZERŰSÍTÉS ‡ º ‡?  ‡ º  ?‡   (ʺ( Á œH mr’» ã:øúùŸÍaÎ â ã$û ã:øšùŸÍaÎâ ã$û ãøšü ùŸÍaÎ â ã$û : à T ÍaÎÊã¾Ñ ×høšü ùŸÍaÖÎPý â ã$û à:ÍaÎÊã:Ñ ×høšùŸÍaΌÖý â ã<û à4ÖãsÑ ×?øùŸÖKÖý â ã$û Þ Þ Þ ÍaÎÏEã<å ÍaÎ ÏEã å ÖÏqã å þ Öþ Ñ ×hÖKý þ ß ß ÖÏpã<å ß þ ß º’cq  < értékadást kiszámító programokban Használjuk fel azt a tényt, hogy a és az értékadás megfelelőjében szereplő elágazások feltételrendszere megegyezik, továbbá a értékadást csak azokba az ágakba írjuk bele, amelyekben . Ekkor ugyanazt a programot kapjuk, mint az első megoldásban 15.23 Visszavezetés kétváltozós

elemenkénti feldolgozásra A feladat megoldásának talán legegyszerűbb módja az, ha kétváltozós egyértékű – hibakezelés esetén kétértékű – elemenkénti feldolgozásra vezetjük vissza. Tekintsük a feladat eredeti specifikációját. Ha a módosítófile kulcs szerint egyértelmű, akkor az időszerűsítés függvénye ( ) a kulcsokra nézve elemenként feldolgozható. A kulcsértékekre felírt függvény: ! ˆDŽ*y»   “ )(q» £" yD ” • ˆDŽ*  ),zyD ha  ),),zzyyDD + (x ˆ» ‘ * D  +  ha  ),z*yD + o ! »* ha +  ),z*yD ( “”• » * ha   )(q£"*yD ),z*yD ++ x ha ! ˆD* D  ˆDŽ*  ), D S   a(q£yD + Ÿ ha  ),zyD + o "# Ha ezt a fenti függvényt behelyettesítjük a kétváltozós elemenkénti feldolgozás tételébe, akkor ugyanahhoz a megoldóprogramhoz jutunk – csak sokkal rövidebb úton –, mint az első megoldásban. 15.3 Időszerűsítés nem egyértelmű módosítófilelal

Vajon miben változik a feladat, ha a módosítófile kulcs szerint nem egyértelmű? Ebben az esetben a feladat nem elemenként feldolgozható. Erre a problémára kétféle megoldási módot is megvizsgálunk: az adatabsztrakciós és a függvényabsztrakciós megközelítést. 15.31 Megoldás adatabsztrakcióval Mint az előbb már megállapítást nyert, ha a módosító file kulcs szerint nem egyértelmű, akkor a feladat nem elemenként feldolgozható. Hát akkor tegyük azzá! Ehhez arra van 147 15.3 IDŐSZERŰSÍTÉS NEM EGYÉRTELMŰ MÓDOSÍTÓFILE-LAL szükség, hogy a módosító file-t kulcs szerint egyértelművé tegyük. Ezt egy állapottértranszformáció segítségével könnyen megtehetjük, ugyanis csak annyit kell tennünk, hogy az azonos kulcsú módosító rekordokat egy új rekordba fogjuk össze. így az új módosító rekord a következőképpen fog kinézni: (kulcs, transzformációsorozat) v  ˆO w  s¦ JˆDPFB*ŸMlPv ó ’ 

¦ w Azaz definiáljuk az új módosítófile típusát az alábbi módon: és . Ezekkel a típusdefiníciókkal a Legyen módosítófile így írható le: Ezzel a módosítófile-lal tehát eljutottunk a kétváltozós egyértékű (hibafile használata esetén kétértékű) elemenkénti feldolgozáshoz. Az egyetlen különbség csak az, hogy az adott transzformáció-sorozat végrehajtását meg kell valósítanunk az eredeti állapottéren. Ehhez szükségünk lesz az szibólumra, amely értéket hozzávesszük az adatrész típusához: . Az, hogy egy törzsrekord azt jelenti, hogy a rekordot nem kell kiírni az eredményfile-ba. adatrésze Az elemenként feldolgozható függvényünk: ®­¯ <"± I­¦tÿI œ ¨ °  ®ô! ¯ °  "±  ®­¨¯ ° <"± " # EDE»Ž* D»   ˆDa( q £" D "# EDŽ* D  ˆD  ‡ "# ‡ * D S MŽf®n!¯ °  "± Ÿ * D S MŽ  a(q£yD + Ÿ A transzformációsorozat

elvégzése csak a transzformációk megfelelő sorrendje esetén lehetséges. Ha egy transzformációsorozat egy tagját nem lehet elvégezni, akkor azt a függvény egyértelsorozatból ki kell hagyni (esetleg hibát kell jelezni). Ezzel az műen definiált. Írjuk fel tehát a fenti megfontolások alapján a kétváltozós elemenkénti feldolgozás programját a megfelelő behelyettesítésekkel: "# Î 
Î Î  Î     "!    #  $ %&(  $ %*)  .
0/*12  !  )    
  Î Î Î Î  Î Î    
      
         +!       # #   $ %,&( $ %-)    $%   $%   %
   $%  %
   $%  
   $ 3 !  $ 4)  
   $ 3 ! &BC A  D ) .
65879;:=<>!? @  %-) .
8 5 79E:<F!? @  %*)    
       
0        
00  Î Î Î Î Î Î Î Î Î 148 15. IDŐSZERŰSÍTÉS 0 £  I­¦ ]‡G MŽ

Ž ’c "‡õ M " , Definiálnunk kell még, hogy mit jelent a fenti struktogramban a transzformációso-G rozat elvégzése. Ehhez bevezetjük az rekurzívan definiált függvényt: ahol cIH   c WKJ[  ]‡G M e^iGA ˆc WfŸ M$e^iGA művelet elvégzésén az alábbi függvényértékeket A fenti definícióban szereplő "‡õ ­ I ¦ értjük: Legyen tX , ekkor: “öö ®­#¯ ° <"±š* ha "‡õ M ( nBr&®­!¯ ° <"± ö * M ( &®­!¯ ° <"± ha "‡õ n * M x ‚®­¯  "± ” "‡õ M e5iLA   öö•ö "‡õ M * haha "‡"‡õõ\ M \ x ??mr‚®­##¯ °°  "± ®­¨¯ ° <"± "‡õ* M ha "‡õ MM oo ?Br& &  ®­¨¯ ° <"± ha "‡õ ?  Az függvényt kiszámító – a módosítássorozatot elvégző – program: ÄÅ Ë º M# ÆÇ "‡õ # º  M  ,  r H "‡ õ ¿ ¿ ¿ ]‡G

M L) M o ]‡G M L) M ( "‡õ M L) M x ¿ Ë ª®­¨¯ ° <]± / ¿ Ë &®­#¯ ° <"± / ¿ Ë ‚®­¨¯ ° <]± / ÉBQ¤ ¡ Ë ¸‚®­#¯ °  "± Ë ¸ "‡õ M Lˆ M ÉBQ¤ ¡ ÉBQ¤ ¡ Ë ¸ "‡õ M L) M "‡õ Mn Lˆ ° ›, ®­¯ <"± is, a ð W  ‡ ( művelet helyett az alábbi Mivel az aktuális adat értéke lehet !° ó programot használjuk: ÄÅ (Ê]ÉBQ ¾)Ë DŽ*ŸË ÇÆ
 Ë ª®­¨¯ ° <"± ¿ / à FHQÈ (="ð W  ‡ (S-ˆË DŽ*ŸË Térjünk most vissza az eredeti állapottérre. Ekkor a főprogram: 149 15.3 IDŐSZERŰSÍTÉS NEM EGYÉRTELMŰ MÓDOSÍTÓFILE-LAL Î 
Î Î  Î  P  "!  Q  #  $ %&(  $ %-)  .
0/*12  !  )    
  Î Î Î Ë ¸’:ô  *ŸË D Î  Î Î    
       M
00     NO     "!  Q   P  # #   $

%R&S $ %*)    $%   $%   %
   $%  %
   $%  
<UTV!  $ @  %-)  
W<XTF! &BC A 0D   %-) .
65879;:=<>!? @  %-) .
5879E:<F!? @  %*)    
  Î Î Î Î Î Î Î Î Î Az a már korábban definiált rekurzív függvényt kiszámító program megvalósítása az eredeti állapottéren: ÄÅ Ë º:ô *ŸË D ÆÇ  Ë ¸  ›,Z  Y ° ,  Ë Dô , , ( , x ¿ ¿ ¿ Ë ‚®­#¯ °  "± ¿ Ë ª®ô#¯ ° <]± / ÉBQ¤ ¡ Ë º‚®­!¯ ° <"± Ë º , ÉBQ¤ ›,z* ,Z-,C ° Ë D , o ¿ Ë ‚®­¨¯ ° <]± / ¡ ÉBQ¤ ¡ Ë º , ¿ / 15.32 Kulcsok egyértelműsítése A gyakorlatban sokszor találkozhatunk olyan file-okkal, amelyek rekordjaiban van valamilyen kulcsmező ami szerint a file rendezett, ám de a file mégsem egyértelmű kulcs szerint, és így a file a kulcsmezőre vonatkoztatva nem elemenként feldolgozható. A következőkben

egy olyan technikát fogunk bemutatni, amelyben egy új kulcsot definiálunk a file-ra, és ezen új kulcs szerint a file @ már egyértelmű. Tegyük fel, hogy a file [ típusú rekordokból áll. Az új kulcsot úgy kapjuk, hogy az egymás után levő azonos kulcsokat megsorszámozzuk. Legyen tehát * -G [ , ahol . Legyen továbbá : ªEDn"FB* ·  Éò ˆDh]FH* š Oªªˆðm]ÉB* ·  h" š † ˆO  , L " , i) +   A   [ és #V WŒX`Y5[]^ L  , bK[Sd : ii)    e^iGA   ™ Ž[ * e  ha  ee DDt r  e5e5iLiLAA DD Ž J[ ha   , iii) VŽWŒXáY["5 L  d :   e Dt  e D és Ž Ž e ·   e · 150 15. IDŐSZERŰSÍTÉS Ž Ž ð ’X ›  š  D Ekkor tetszőleges [ esetén – feltéve, hogy a kulcs szerint rendezett – a kulcs szerint rendezett és egyértelmű. Természetesen a fenti megszámozást általában csak az absztrakció leírására használjuk, és csak ritkán fordul

elő, hogy a függvény által definiált absztrakciót meg is valósítjuk.  15.33 Megoldás függvényabsztrakcióval Egy adott feladat megoldását mindig elkerülhetetlenül befolyásolja a specifikáció módja. A függvényabsztrakció lényege abban rejlik, hogy a megoldást egy alkalmasan választott függvény helyettesítési értékének kiszámítására vezetjük vissza. Induljunk ki egy olyan absztrakt file-ból, mint amilyet az egyváltozós elemenkénti feldolgozásra való visszavezetésben használtunk. Természetesen, mivel most a módosítófile nem egyértelmű kulcs szerint, az absztrakt file definíciója kissé módosul: ha egy kulcs mindkét file-ban szerepel, akkor a törzsrekordot az első rá vonatkozó módosítórekorddal vonjuk össze, és az esetlegesen előforduló további azonos kulcsú módosítórekordokból pedig egy-egy olyan absztrakt rekordot képezünk, amelynek adatrésze . Ez az absztrakció az imént bemutatott egyértelműsítő

leképezésen keresztül implicit módon írható le: legyen , és . Ekkor ó ®­!¯ ° <"± és (£ X  ; ‡Ž+ ð  ó  , X ‡0X &;a(q£ S ð =œ ;a, + ð  V#WŒX`Y5[]^ ‡G  , d : Ž ‡# e  ™ ­® €¯ a(<q"£ ±š*- Ž ‡# e ð S # ° Ž ‡# e M  ™ ®­€¯ a,< "±š*- Ž ‡# e ð + M! #°  ‡Ž e ð  e ð ha ‡Ž ha különben különben X ; a(q£ + ð  X ›Ž), S ð  Megoldás függvénykompozícióval Először egy olyan megoldást adunk a feladatra, amelynek specifikációjában az utófeltétel egy kompozícióval adott függvény kiszámítása, ahol a kompozíció egy rekurzív módon megadott függvényből és egy esetszétválasztással definiált függvényből áll. ó ¡  %÷ ó‡ ( ¤  J ¦ ‡ § ! ‡  ‡ ¦ ó ª¨p(Œ.ÉBQ
¾ˆ]A ‡ ¦ " , *ˆ<>" ‡ ¦ " , y <{ ‡ ¦ " , -Ÿ- 15.3 IDŐSZERŰSÍTÉS NEM

EGYÉRTELMŰ MÓDOSÍTÓFILE-LAL 151 B-G £ &%?F %mI­¦ , ó c2H  ^]I +*
:¹›®¹#¯ °  "± “ö E]A< Wq * ó <>" Wf ‡ e^iGA MŽˆ<{ WfŸ- ha ‡ e^iGA Dt’<>$ Wq ” c `W J.[  •ö ˆÉBQ ˆ A *ˆ > y {
Wf Wf Wf-e^iGA D ’r  > Wq ‡ e^iGA DŽ* ‡ e^iGA MŽ ‡ e^iGA Ÿ ha ‡ ó ÉBQ
÷$÷%ZˆF†%?In¦  , és ó ®­#¯ ° <]± ÉHQ
a(+*yDŽ   ™ (+ð W  ‡ (S)(+›EDŽ - ha mrª ª  ®­#¯ ° <]± ha ó  4 kulcsérték egy tetszőAz függvény kezdőértékének definíciójában szereplő
leges olyan kulcsérték lehet, amely egyik file-ban sem fordul elő. ó Mivel az utófeltétel függvénykompozícióval adott, a megoldás egy szekvencia lesz,  ÉBQ  függvényt számítja ki. Az amelynek része az , második része pedig aD*ŸË
 függvényelsőegyes + ( *  Ë komponenseinek rendre a változók felelnek meg.  YŒ ‡# y   ‡ * ]‡ ‡ ó  °

Ë (+* Ë DŽŸË ¸Q  ]a +*
:¹;®ô!¯ ° <"± ‡ Z  Y °, Ë Dô "‡õ D ó ¿ Ë º ]‡G MŽ)Ë  (Ê]ÉBQ
ˆËD*ŸË  / Ë º "‡õ M# ]‡G  Ë Dh¸ "‡õ D  ‡ * ]‡ó ‡  °  Ë (="ÉBQ
)Ë DŽ* Ë  Az ‡ absztrakt file műveleteinek megvalósítása: ÄÅ  ŒY ÆÇ y ‡# ;,Z* ,Z-,ò °  Ë ›( £ * ( £ -( £  °  Ë ahol 152 ÄÅ       15. IDŐSZERŰSÍTÉS ÆÇ
   P     
O   P  +!  Q   ^Zb!  P   Q  #  # #  $ % D   $ %-)    $%    $%   $ %&( $ %*)   $%
  $%   $%
   $%   $%
   $%   $
  $   $
  $   $ 
 &RC A 0 0D   $3
 B & C A 0D   $3
   $3   $3
   $3    
0    
0         c
0         M
0  Î Î Î Î Î Î Î Î Î Î 
    / Î Î Î Î Î Î Î Hátra van még a

transzformáció elvégzésének megvalósítása: ÄÅ      $3     $ @3 $  
fd  d, R 0 C 0  D  & A / 587hFi  
 R 0 & C A 0D   ÆÇ
   $ 3 !ed )  &RC A 0 0D    $ 3@$  d, &RC A 0 0D d,  / 5 7h>i
   $ 3@$  587h>i 8   $ 3@$ g &RC A 0 0 D  
   $ 3@$  / / Megoldás extremális elemmel Az előző megodás szépséghibája, hogy a feladatot nem egy függvény helyettesítési értékének kiszámításaként specifikáltuk. Ezért adunk most egy másik megoldást is, amely egy a gyakorlatban sokszor hasznos eszközt használ. Ez az utolsó utáni elem bevezetése ( extremális elemmel). Egészítsük ki az előző megoldásban szereplő file-t – ha nem üres – egy olyan elemmel, amelynek kulcsa minden lehetséges kulcsértéktől eltér. Jelöljük ezt a típust -sal. Ekkor a két típus közötti megfeleltetés: j , ó ó ° Ë ó   ð W  ‡ (S ‡ *›
:¹;®ô#¯ °

<"±ú;®­!¯ ° <"± - ™  ‡Ž ‡ * ó j ó ha ha r H  ‡õ  ,, ‡õ  H A kiszámolandó rekurzív függvény majdnem teljesen megegyezik az előzővel. A jobb áttekinthetőség érdekében a függvényt most komponensenként fogjuk felírni. Ahhoz, hogy a függvényt egyszerűbben írhassuk fel, tegyük fel, hogy az üres sorozatra alkalmazott L függvény nem definiált értéket ad vissza (így akL G nem csak parciális függvény, hiszen minden sorozatra alkalmazható). Ekkor , ) M M ª ) £   %áF %áI­¦ 153 15.3 IDŐSZERŰSÍTÉS NEM EGYÉRTELMŰ MÓDOSÍTÓFILE-LAL ?ªE]A *y<>$y<{ l m!  )  l6q !?1rWs )  î l !?1rWs ) í  l !?1rWs )  ! n2o   $ p  3@$ %  $ p  3@$ 4) t l q ?! 1 ^)  l !?1 )  * wyx q $ %  ha uv ! l !?1   wyx q # l !?1 )  R C D ) z &R& C A A  D ) /*12  ! l q !?1 )^ ! l !?1 )^ l !?1 ) ) )^ ha l !?1 ){); z z  wyx q $ % $ % # l ?! 1 X |  w}x qq $

3 !! l !?1 q ) )^ ha ll !?!?11 )   w}x qq $ %  w}x $ 3  wyx $ 4)^ ha )Xz  w}x $ % | l !?1 q )^ ha ll !?!?11 )   w}x qq $ % @w}x $ %~ ha );z @w}x $ % í î í í í î í í í í í î î ó ¡  %÷ ó‡ ( ¤C ¦ ‡ § ¨ ‡  ‡ ¦ ª!ˆ(Œ’]A< ‡ ¦  , - Ezt a függvényt használva a feladat specifikációja: Ez a feladat visszavezethető file-ra felírt rekurzívan megadott függvény helyettesítési értékének kiszámítására:  YŒ ‡Ž y   ‡ * ‡ ‡  ° Ë (+*ŸË DŽŸË ¸P]a + ‡c DŽ ‡õ ‡ Z  Y °, Ë Dt ‡G D ¿ / ¿ Ë ‚®­¨¯ ° <]± Ë º ‡G MŽ)Ë  à FHQÈ (="ð W  ‡ (S)Ë DŽ* Ë  / Ë Dh¸ ‡õ D Ë º ‡G M# ‡L   ‡ * ‡ ‡  ° Ë Az ‡ absztrakt file műveleteinek megvalósítása: ÄÅ  YŒ ÆÇ y ‡Ž ›,z* ,Z-,ñ ° Ë ;(q£"* (q£"Ÿ(q£š °  Ë  Y ° , ¿ ›( £  Y ° , ¿ ›( £ ›,ó Ë x Y ° , ¿ ›,Z ‡L Dn¸


: ‡L Dh¸ , D ‡G Dhº ( £ D 154   
    ÄÅ       15. IDŐSZERŰSÍTÉS ÆÇ
    $ % 9E:<XT  
O   Q      P^€     !  Q  !  Q   N  #  #  $ %,&S  $ %-)   $ %    $ %  #  $ % D   $ %-)   $%
  $%   $%
   $%   $%
   $%   $
  $   $
  $   $ 
 &BC A 0 0D   $ 3
 &RC A 0 0D   $3
   $3   $3
   $3   
0      
00       M
0       c
  Î Î Î Î Î Î Î Î Î Î Î Î Î Î Î Î Î ‡ / /   $%
 9;:=<UT A transzformáció elvégzésének megvalósítása tulajdonképpen megegyezik az előző esetnél felírttal, csak most az absztrakt file-t használjuk:  ÄÅ     $3     $ @3 $  
fd  d, R  & C A 0 0D / 587hFi  
 R 0  C 0  D & A ÆÇ
   $ 3 !ed )  &RC A 0 0D    $ 3@$  d,

&RC A 0 0D d,  / 5 7h>i
   $ 3@$  587h>i 8   $ 3@$ g &RC A 0 0 D  
   $ 3@$  / / A fenti megoldási módokat összehasonlítva látható, hogy minél magasabb absztrakciós szintű fogalmakat használunk, annál egyszerűbben tudjuk kezelni a feladatot. Nagyon sok esetben az adat- és függvényabsztrakció is alkalmazható egy feladat megoldásakor, sőt mint azt az iménti példa mutatja a kettő kombinációja is egy lehetséges út. Feladatok 2002. szeptember 25 1. Halmazok elemű és egy 1.1 Legalább, illetve legfeljebb hány eleme van egy – metszetének – Descartes szorzatának
elemű halmaz – egyesítésének – különbségének?         , és    halmazok elemeit, ha     !"  #$ ,%" ! , ,  ) esetén 1.3 Bizonyítsd be, hogy &( /00 21  3465 &(78.-  3465 & ,9 :!;<  7=:>?  @7 &  ;  > - +*,.12 Írjuk fel az

- ha H nem üres, akkor K és L egyértelmű. 2. Relációk 2.1 Az AB ! CDE!@F! CDE! . A B G H C"G IJ0 KC4G 0 DEG CDLEHL a) Mi a reláció értelmezési tartománya és értékkészlete? A J DC MNLE4 MO QP J0M hatványa? halmaz inverz képe, ill. ősképe? d) Mi a e) Hány eleme van A értékkészlete hatványhalmazának? 2.2 Milyen összefüggés van egy & halmaz A reláció szerinti inverz képe és ősképe között? És ha A függvény?  ) . Mivel egyenlő A8SUT @ ? 2.3 a) AR b) Megadható-e valamilyen összefüggés egy & halmaz inverz képének képe, és a & halmaz között? c) Megadható-e valamilyen összefüggés egy & halmaz ősképe képe és a & halmaz között? V K2W KX0 YW[Z XKXK^] W KX 5a`b . Mi a & V - /0] - /c5F`ed -cZ /cfE4 halmaz inverz képe, 2.4 a) A ill. ősképe?   K2W  X!0 2WgZ Xh XK6] W KX5i`b=jk YW KXG YW[P

XKXK] W KX5)`b . b) A   2- /0b] - L/l5i`md -=Z /nfoE4 halmaz inverz képe, ill. ősképe? Mi a & B K2W  X!0 qp,YW  XGKX b] W  X5i`r , ahol p 7 `)`?st` . 2.5 A   2- /0b] - L/l5i`md -=Z /nfoE4 halmaz ősképe ill. inverz képe? Mi a & u  . Van-e valamilyen összefüggés az AgSUT wvbux halmaz és az ev A8SyTz uxK halmaz 2.6 AR b) Determinisztikus-e, ill. függvény-e a reláció? c) Mi között? 2.7 Készíts olyan nem üres relációt, amelyre igaz, hogy értékkészlete minden valódi részhalmazának ősképe üres halmaz! 1 A
 a
uuc  . Hogyan lehetne jellemezni az ASyTz
jmuc és az A8SyT
 uc A SUT és A SyT halmaz segítségével?  `)`6 B4 B L/0r] /H] - d / R rd /   -  . 2.9 Legyen B  2-  /0b] D] - d -  ^/J .              SyT  SyT  SyT  SUT 8b   SUTH   SUT     ) . Igaz-e, hogy 2.10     SyT   

SUT   SUT a)   7x   SUTH  SyT  SUTH x b) *     SUT    SyT   SUT c)   7x    SyT 8 SUT  SUT K d) *  Igazak-e az a)–d) állítások, ha vagy  függvény? 2.8 halmazt az 2.11 Mi az összefüggés két reláció kompozíciójának értelmezési tartománya és ugyanezen két reláció szigorú értelemben vett kompozíciójának értelmezési tartománya között? .p A 2.12 Legyen A a 2.1 feladatban adott reláció igazsághalmaza? p logikai függvényt, hogy p A igazsághalmaza üres legyen! Lu B) . Igaz-e, hogy 2A  cu  SyT u  SUT A  SyT ? 2.14 A    . Igaz-e, hogy 2A  SUT @ 2A   SyT ? 2.15 AR    . Igaz-e, hogy *&  7@ASyTz2A8SyTz2& Kr 2A  SUTH2& ? 2.16 AR
u `)` . uB - /0b]J ] - d)/] - d# ! /0L 2.17
  2- L/0b]J/] - d)/ B d)/   -  a)
 2- /Ib]J/] -  b) u Lu"
és u
-t relációt! Add meg a  SyT  )[  )= 

V$# . Igazak-e az alábbi állítások? 2.18 & 5$% " & 2-    &e2- . % a) Ha , akkor   &)% (* . +&-,* % b)  +&-,.5* % ]4] &e&).-(* I]BJ0/1 &   & . c) +*\% w2 /1 & 3  & . d) & e) Asszociativitás: 4 cc55 &       & 6 &  & ug A 7 R  . u AR 798:/ u  SUT ;7 A ; f) u  A 7 B) . u A 798:/ u  SyT  7 ; A ; g)   <=/ >  A  >  > , ahol > B) h) A i) Monotonitás: AR 7?79/t/ u"A  ^u 7>u^u7 AR AR 2.13 Készíts olyan nem üres A pm  . p V QG !QG  0 CDhG EQL Mi p , ill relációt és 2 A u u 2.19 Legyen és két reláció a természetes számok halmazán! és a kétszeresét, egy páros természetes számhoz a felét. A egy természetes számhoz rendeli önmagát Au reláció . hatványát (
 ) és ennek az értelmezési tartományát! c) Írd fel a A relációt és

az értelmezési tartományát! w   u  A ! Írd fel az  relációt és az értelmezési tartományát! d)       i . Igaz-e, hogy: 2.20  , %  SUTz % a)  +  & ,   %  SUT % & b) & +&-(   a) Írd fel a két relációt, és add meg az értelmezési tartományukat! b) Írd fel az 3. Reláció lezártja A " H DKCDLE4g "HL! DKC E4 . A < G H C"G IJ0 KC4G 0 DEG CDLEHL Mi lesz A lezártja és korlátos lezártja?
` [)` .
B - L/0r] /H] - d / B rd /   -  Mi lesz
lezártja? 3.2 3.1 3.3 Mutassunk példát olyan relációra, aminek lezártja és korlátos lezártja különböz ő!
  3.4 Mi
  -cP " z/] /l5)`b
2- r . ha ha - f? - lezártja és korlátos lezártja?  " H DKCDLE4" A  ) . A  H0 HEG !LEH0 DG  C"G EHG  B  C . Írjuk fel

a reláció feltételre vonatkozó lezártját! `o[` . A B - /0b]a/H] - d / R ,d/=  -   B W ] W kettőhatvány  Írjuk fel az A ] 3.6 AR 3.5 lezártját és korlátos lezártját! relációt,  3.7 Adjunk példát olyan nem üres relációra, amelynek lezártja üres halmaz és van olyan feltétel, hogy a reláció feltételre vonatkozó lezártjának értelmezési tartománya megegyezik az eredeti reláció értelmezési tartományával! 3.8 A  a A 3.9 Van-e olyan nem üres reláció és lezártja azonos a relációval? 3.10 A A . Tegyük fel, hogy az értelmezési tartománya egyenl ő az -re vonatkozó ősképével. Mit mondhatunk lezártjáról? AR `)` .  A értelmezési tartományának feltétel, hogy a reláció lezártja üres halmaz, és a Ag2-   4" z -ccP ] 5)`r" ha ha - B -  feltételre vonatkozó A reláció lezártja és korlátos lezártja?  ` )` . 3.11 AR    Ag2-  J-x P

] 5i`b haha -- R Mi az A reláció lezártja és korlátos lezártja? `)` . Az A reláció minden összetett számhoz a legnagyobb valódi osztóját rendeli Legyen % 3.12 AR Mi az a) egy rögzített összetett természetes szám! b) egy rögzített prímszám! 3

.- r q: 5 o` ] A `)`  3.13 R   AgYW r  Legyen tartománya? Mi lesz 3.14 A A %  ! Mi lesz az A reláció /l] : 5)` 7 /   W[P  " J!"   " lezártja és korlátos lezártja? legyen a 3.11 feladatban adott reláció és korlátos lezártját!  l
 feltételre vonatkozó lezártjának értelmezési Z " ha ha ha ha W w  ldd W W B
 W W w W páros páratlan páratlan szám). Add meg az A ] relációt, lezártját 3.15 Igazak-e az alábbi állítások? $5 %  % , akkor A.- r Ag2- % % . b)  B) , akkor A  A . * c) Ha az halmaz véges és A B  , és  * d) Ha megszámlálhatóan végtelen, AB *- 5) 7xq:4
2- ^5i`

 7 ] Ag2- I]
.- 0/ A  A `   ` h A értelmezési tartománya ` ! 3.16 Legyen AB /] / ld)/lf W d)D] /J" ha W páratlan r  W[P " A2W ha W páros  YW b YW páros természetes szám). Mi az A reláció  feltételre vonatkozó lezártja és korlátos lezártja? a) Ha 4. Projekció, redukált      .  5  , ahol  ` ,RH "   HII Az  sorozat további elemeit T T úgy kapjuk meg, hogy a pontok koordinátáit az első koordinátával kezdve ciklikusan 1-gyel növeljük. K r ? pr
  red  4.2 Legfeljebb ill legalább milyen hosszú egy és egy
hosszúságú sorozat redukáltjának konkatenációja, 4.1 ill. konkatenációjának redukáltja? 4.3 Igaz-e, hogy egy  sorozat redukáltjának projekciója ugyanolyan hosszú, mint az  sorozat redukáltja? 4.4 Igaz-e, hogy egy  sorozat projekciójának redukáltja ugyanolyan hosszú, mint az  sorozat redukáltja?       !#" V

"c  5%$OHKC&  ` 8f  IHHJT G  !HJG !,JG !!KC"T G, ahol E!L!*  KC"0 E!  7  ! C"G E.  ! C"G()(( r ? a) pr*@ b ? b) red pr*n+ 4.5 Legyen  5. Feladat, program, programfüggvény, megoldás .    !  "H! ,n "HL! DKC E4"M0w )  )- . T   2- / 1 r] 1  - Z /J . Miért hibás az  feladat leírása? T  !   "H! ,n "HL! DKC E4"Uw    )- . 5.2  T   K2- L/ 1 0 3D/. p K ] p  - Z /M  IHJ H H?IHányT olyan pontja van az állapottérnek, amelyekhez 5.1 a feladat ugyanazokat a pontokat rendeli, mint -hez? 4 BHL!KC E!7 B  )  . 7m  soJ HE soIC"EH sw"^MIMM "se s zC "se MIMM C4seCDE!IC C!smC"JE! C4s CDJEC" Es EHzC Es

EHC E"seEC     !J CD C" CDI C  C EHG . # 7 -t! a) Adjuk meg 7 b) Megoldja-e a feladatot? 7 7 5.4 Legyen program,  olyan feladat, hogy megoldása  -nek Igaz-e, hogy 7 a) ha  nem determinisztikus, akkor sem az? 7 b) ha  determinisztikus, akkor is az? # 7 sem az? c) ha  nem determinisztikus, akkor #  7 d) ha determinisztikus, akkor  is az? # 7 is az? e) ha  determinisztikus, akkor 7 # 7r sem az? f) ha nem determinisztikus, akkor 5.3 Legyen 5.5 Igaz-e, hogy programok uniójának programfüggvénye megegyezik a programfüggvények uniójával? 7  )  . Igaz-e, hogy # 7b - /065)B)] :  5i  782-   ^5>7id /^
 L ? 5.8 Legyen  és   egy–egy feladat ugyanazon az állapottéren! Igaz-e, ha minden program, ami megoldása  T -nek, azT megoldása   -nek is, és minden program, ami megoldása   -nek, az megoldása  T -nek is, akkor  és   megegyeznek? T # 7  7 5.9 Igaz-e, hogy értelmezési tartománya

éppen  ősképe -re nézve? 7 % 5 % / 5.10 Mondhatjuk-e, 7 %   d8# hogy 7 % az  program % . megoldja az  feladatot, ha igaz a következő állítás:  7 7 5.11    Az program megoldja   -t Igaz-e, hogy megoldja  -et is? T7 7 7 T 5.12 T  .  megoldja az  feladatot Igaz-e, hogy 7 T megoldja  -et?   `BF`b    K  40 2W KX n] Xy]   ,     K  40 2W KX n] W   d)Xy]   . Ekvivalens-e a két 5.13 T feladat? (Van-e valamilyen összefüggés közöttük?)    7 , 7  programok  -n. Az 7 és az 7  is megoldja az  feladatot Igaz-e, hogy az 5.14 7  7 j 7 T T T  program is megoldja az  feladatot?7 ` `  5.15 Legyen  a 219-es feladat d) pontjának relációja! 7 x 2- If - (()( b] -    C"G . j6 /f / G /Ifo/L/  r]/     C"G j6 21 f 1 L 1 b] 1     C"L j6 3 If 3  3  b]J3     C"G # 7 értelmezési tartományát! Megoldja-e 7 az  feladatot? Add meg 5.6 Fejezzük ki

a programok uniójának programfüggvényét a programok programfüggvényeivel! 5.7 5.16 Tekintsük a következő szövegesen megadott feladatot: Adott egy sakktábla, és két rajta lév ő bástya helyzete Helyezzünk el a táblán egy harmadik bástyát úgy, hogy az mindkett őnek az ütésében álljon! Készítsük el a modellt: írjuk fel az állapotteret és az relációt!  7  5owd 7 2- $   # 7 .-  5.17 Tudjuk, hogy5$% megoldja  -et (az állapottéren). Igaz-e, hogy (K /  2- - Ri  ? 7 i / egy program. Jelöljük 
-vel azt a relációt, amely  egy feladat és 5.18 Legyen #és 7 metszeteként áll elő. Igaz-e, hogy %   % 7 a) ha , akkor megoldja  -et? 7   % "% ? b) ha megoldja  -et, akkor   5 6. Feladat és program kiterjesztése   HL!!c "H  R  ! .  Vk    G HL Mi az  kiterjesztettje  )  -re? w`6 w`)` . V B)cM  B %4 % Z b]%5 `b

b)  -re? Mi az  kiterjesztettje   $     K  G  Kn]  d L feladat, és az   $ c) Adott az állapottéren az  B        !   állapottéren ( ) a következő program: 7   Lks9 LH h!  Q  Q s9 Q!   H   Q s9 Q! h!  L    bs9  hls9h! LH     Lbs LH  h  Qls Q! LH    Qls Q!   H  h  yzs  y   hs  h  7  -re való kiterjesztettjét? Megoldja-e az     m   ()()($  . Mondjunk példát olyan programra, amelynek egyetlen valódi altérre vett 6.2  `b  IMIMM0
. T projekciója sem program.  6.1 a)


           pr^6 , akkor   az  kiterjesztettje? b)  pr  SyT 6 ? ill.  pr SUT 4 ? <        tB ,  #  # , ahol   t , 6.4 Legyen  wFn   # k@ ,  n  , és legyen,      az  kiterjesztése  nm@=# # -re.T rendre #  # T Igaz-e,

hogy  az  kiterjesztése -re? Add meg az  és az  közötti kapcsolatot a projekció és a kiterjesztés fogalmának segítségével! 7  )   altere  -nek, akkor 6.5 Igaz-e, ha %  pr % ? a) pr       kiterjesztése  -re azonos 7 -sel? 7  -ra történő projekciójának b)  és  altere  -nak.    x  < [       az  projekciója  -re  6.6    T T az   kiterjesztése -ra. Igaz-e, hogy az  feladat -ra való kiterjesztettjének -re vett projekciója T megegyezik   -vel? 6.3 Igaz-e? a) ha                  7. Vegyes feladatok `b      !r5i` `]  7 B .- f - I b5iB - / ] - rjk HIf L 7 T B HIf G !f !HL G$j  2-   ^5)?  ]   - d  b 2- legkisebb 1-nél nagyobb L T osztója . 7 ill. 7  a feladatot? a) Megoldja-e 7T és 7  ? b) Ekvivalens-e T   $  &  5i` )! 7.2 Számítsuk (

intervallumon `)`ki a  QP 

wfüggvény B    értékeinek  B)cösszegét   az  azkiterjesztése  ) -re. 7 7  B)   T7   )  . T T  T    L/0G  / T K^]J/ T   d
 .  K
T
T T T QP 7 x 
 W s K 
 W 0 
 QP  G 
 KP J ZwKP J T GMIMIM T MIMM0    ()(( J KG 7  x 
 W
s QP K  Z
 W 0ZQP 
 KKP J ZwKP J  7  x 
 W  s 
 W  G 
 p, .# m# Y
G2# re# Y
K 7.1 Keressük meg egy természetes szám egy osztóját! osztója -nak .          6   # r H ha páros p,   QP    ha különben különben 7 7 a) Megoldja-e és   -et? 7 T b) Megoldja-e  -t?  c) Mely programok ekvivalensek -n?   `  ` m` . 7     M 7 az (1,1,2) pontból kiindulva előállítja a 10 Fibonacci számot az 7.3 ,Y
  2
cP J Z ,Y
cP H rekurzív összefüggés alapján. A7 koordináták rendre  2
cP  -nek,  2
c#P 7 nek,  2
-nek felelnek meg Írd fel azt a sorozatot,

amelyet az (1,1,2) ponthoz rendel! Mit rendel   az (1,1,2) ponthoz?  A ) `   A V     B YW 
 G X  W K6] B . 7 7  B )  T 7 YW 
hKbxf 2W 
hG 2W 
P H  W 0IMMIMI YW    W  7 T YW 
hKbxf .- 0IMIMM0 ] b    yd 3  r <d * 5 T
& 72> .
3  2-2- T  YW  <
d 2- q > 5 >

3 2- 2-  KL SUT SUT . 3  B)
ahol > 
H!  0 ha D]
d
w  . 3      YW >
2W
YW 
)P  W hG ha ^  ]
Ud
w  7 ill. 7  az  feladatot? Ekvivalensek-e  -n? Van-e olyan altere  -nak, ahol 7 és 7  Megoldja-e T T ekvivalens?  7.4 Számítsuk ki egy valós szám természetes kitevőjű hatványát!
, .          8. Leggyengébb előfeltétel 8.1 Tekintsük az 54 feladatban adott programot! A  B!LE4 . Írd fel az  lf 7, A  halmazt! 7,  ill. lf 7,  L ? 8.2 Mivel egyenlő lf 5)` : u Q0/ u  Z J ,

akkor 8.3 Igaz-e, ha * 5i` 7 lf 7,Lu Y
Kr lf 7, q:4
5i` 7 u 2
K ? * .:!
7  A  lf 7   A 08:/ lf 7 j 7   A  lf 7  A  lf 7   A ? 8.4 Igaz-e, hogy lf T  5  7 
JXhK  T 9 5  7 
T XhzK  X  ) 5 8.5 Igaz-e, lf  %  ha"% * W ? (
7nW Xh azlf azT állítás, amelynekW igazsághalmaza JX , )akkor          7   / programra  lf 7, &    lf 7, &   , akkor  &   8.6  &  &  . Igaz-e, ha minden T&  ? T T 7 7    / programok. Igaz-e, ha *  &   7  lf 7  &    lf 7   &  , akkor 7 ekvivalens 8.7 7 T T T -vel? 7, rd ,A K és (igaz d lf 7, A KK között? 8.8 Milyen összefüggés van lf  7,   # 7 SUT  A  ? 8.9 Igaz-e, hogy lf A w` . Legyen 7 az 516 feladat programja! &e2W r YW páros szám)  lf 7, &   ? 8.10
     
   7 9. Specifikáció tétele 9.1 Keressük meg egy természetes szám egy osztóját 9.2 Keressük

meg egy összetett természetes szám egy valódi osztóját 9.3 Keressük meg egy természetes szám egy valódi osztóját 9.4 Keressük meg egy természetes szám összes valódi osztóját 9.5 Keressük meg egy természetes szám legnagyobb prímosztóját 9.6 Állapítsuk meg, hogy hány valódi osztója van egy természetes számnak 9.8 Keressük az 6-tal. 9.9 Az OM M
& intervallumban az első olyan számot, amelyiknek van valódi osztója. MOM
& intervallumban azt a számot, amelyiknek a legtöbb valódi osztója van, de nem osztható $ 9.7 Keressük az $ MNM
& intervallumban melyik számnak van a legtöbb valódi osztója. $ 10. Típus F    .   D    és   egy típusspecifikáció.    .  !7 T  T  B TB T !7            , és 7  7 . T T T T T Igaz-e, ha megfelel -nek, akkor  is? T    G      két típusspecifikáció! 10.2 Legyen  T  T 9 megfelel -nek . 1. állítás: Minden típusra: megfelel  -nek  

    és   . 2. állítás: T 10.1 Legyen   
             
     
              Ekvivalens-e a két állítás?    D egy típusspecifikáció.    és        T T  T T 5            T  és T T   és *  87   T + a) Legyen T feleljen meg -nek!        és  &      &  , és *  5 87   l + b) Legyen  T T T T T feleljen meg -nek! Igaz-e, hogy  is megfelel -nek?    D a következő típusspecifikáció: 10.4 Legyen H w ` h F       .  T  T specifikációja:  `   `  u y 2W  W W g5 W   A q:  7@W ZeW d  W f    specifikációja:  `   `     `   `  X X W W u y 2W  W d XwX A y  YW oX yd W  W dXgwX 10.3 Legyen   
                         
  
                      

  8           , valamint T , valamint T   D L0 R H DKCDLE!    * . 5 =7 4    T . ] !] rd xs ] !]H K
a) T .z ] !] 
b) 7  6  / T * . 5 =7 7 T z  5 5 $ J]  ]  & ]o]  ]H5%$ ] !J]]0d ] * &  5%n $OHJ]   ] & 7 ]  G L]H]  ] P  Z Jd *  7l*    SUT  7     yc    $  * ."3g5  7 * 5$ 7  ." 3  x a5   ]o] b]"  ] !] ] 3] Z rd *  5%$ !] 6] & 7   . " 3"3D Kd  +* %5 $  P  & 7 . @o3"3 Udm] !]H" P rdm] 33] P J d * 5 $OH P  & 78 .  S n S T d 3"3  S @w3 S T KL    feladatot, a relációt, és az 7  7  programfüggvényét! Megfelel-e a típus a Írd le szavakkal az  T T specifikációnak az a) ill. a b) esetben?  
                      
         

           10.5 Adjunk típusspecifikációt, reprezentációs függvényt, és adjuk meg a típusműveleteket megvalósító programok $ elő& és utófeltételeit (a típusspecifikáció tétele szerint) a következő típusra: a lehetséges értékek: . A műveletek a következő és az előző 100000 szerinti maradékkal. Az elemi értékek a deci
  mális számjegyek  . Mutasd meg, hogy a típus megfelel a típusspecifikációnak!  JHL! DKC E!   D    10.6 A típusértékek halmaza legyen a magyar abc magánhangzói! a, á, e, é, i, í, o, ó, ö, ő, u, ú, ü, ű . Szeretnénk tudni, hogy egy adott magánhangzónak melyik a (rövid ill hosszú) párja Legyen egy olyan típusműveletünk, amely erre a kérdésre választ tud adni. Az elemi típusértékek halmaza legyen a  
  halmaz! Add meg a típusspecifikációt és készíts el egy olyan típust (add meg a típusműveleteket

megvalósító programok elő- és utófeltételeit a típusspecifikáció tétele szerint), ami megfelel a specifikációnak! JDI! CDE D   IIHHIJ!0J0C! 10.7 Specifikáld azt a típust, melynek értékei egy 128 elemű halmaz részhalmazai, típusműveletei pedig két rész halmaz metszetének ill. uniójának képzése, ill annak megállapítása, hogy egy elem eleme-e egy részhalmaznak. Adj meg egy reprezentációs függvényt, típust, amely megfelel a specifikációnak! (Az elemi típus a bit típus.) 10.8 Adjunk típusspecifikációt, reprezentációs függvényt, típust (ami megfelel a specifikációnak)! A típusértékek: a síkvektorok halmaza, a műveletek: két vektor összeadása, valamint annak eldöntése, hogy két vektor számszorosa-e egymásnak. 10.9 Adjunk típusspecifikációt, reprezentációs függvényt, típust (ami megfelel a specifikációnak)! A típusértékek a térvektorok halmaza, a műveletek: két vektor

kivonása, valamint egy vektornak egy számmal való szorzása. 10.10 Adj típusspecifikációt, reprezentációs függvényt, típust (ami megfelel a specifikációnak) a komplex számok típusára, ahol a műveletek két komplex szám összeadása és egy komplex szám képzetes részének meghatározása.

5 10.11 Adj típusspecifikációt, reprezentációs függvényt, típust (ami megfelel a specifikációnak) a komplexszá mok típusára, ahol a műveletek két komplex szám összeszorzása és egy komplex szám -dik ( ) hatványának meghatározása. 10.12 Adj típusspecifiációt, reprezentációs függvényt, típust (ami megfelel a specifikációnak) A típusértékek a körlemezek halmaza, a műveletek: egy körlemez eltolása, és annak eldöntése, hogy egy síkbeli pont rajta van-e a körlemezen. 10.13 Adj típusspecifiációt, reprezentációs függvényt, típust (ami megfelel a specifikációnak) A típusértékek a gömbök halmaza, a műveletek: egy gömb

eltolása, és annak eldöntése, hogy egy térbeli pont benne van-e a gömbben. 9 10.14 Adj típusspecifiációt, reprezentációs függvényt, típust (ami megfelel a specifikációnak) A típusértékek a négyzetek halmaza, a műveletek: egy négyzet eltolása, egy négyzet métetének megvátoztatása, egy négyzet területének kiszámítása és annak eldöntése, hogy egy síkbeli pont rajta van-e a négyzeten. 10.15 Adj típusspecifiációt, reprezentációs függvényt, típust (ami megfelel a specifikációnak) A típusértékek a kockák halmaza, a műveletek: egy kocka eltolása, egy kocka métetének megvátoztatása, egy kocka térfogatának kiszámítása és annak eldöntése, hogy egy térbeli pont benne van-e a kockában. 11. Paramétertér, specifikáció     állapottér RB!!z és a   paramétertér, továbbá az  és   T      0 /   /  b]  L  T K2- T -  T  2- -    specifikációja:     V T   -T - u 2-

- T  - - d -   -  T A 
u  T d  2- T -  K Azonosak-e az  és   feladatok! T       11.2  X   T     W W  T 7 u  YWu  d W V] XbXy] A W .     K.- /00 21  34K6] 1  - dm] 3h] r3g 1   Megadható-e valamilyen összefüggés  és  között? T 11.3 Ír d  le szövegesen az alábbi feladatot:     ` V    és adott egy Wi7  s  függvény.
u
 d

A   d

d   QK ahol 7  s J és Q   ha * 5 $ 
& 7nW W Q  11.1 Adott az feladatok.                                     egyébként ?  V  B)  B  G  6]  d  d G 11.5 Igaz-e a specifikáció tételének megfordítása? 7 /l5i 7 u / lf 7, A LK (Ha megoldja  -et, akkor *     V  11.6 # u    d gf A  $  d # ! # d *   7  # ! DIQ0/ ] cP/  0] D
EH] P #,] ahol # ! YW b 2W prímszám). Mit rendel a fent specifikált feladat

az és a pontokhoz? Fogalmazd meg szavakban a feladatot!  `  `  `  `  `      )  specifikációja: 11.7 T W X W X T u  2W  W d XwX A y YW  W dX ?X d W ] nd X ] nd * 5)` 78YW ] dX ] / h] 11.4 Specifikáljuk a következő feladatot: ,  
                           10        B  2- / 1 G 3  ." p r] - 3@d /  6d p ] - ^/ d - ] p d)/] p  Megadható-e valamilyen összefüggés  és   között? T s 11.8 Adott p 7   függvény.  egy          

 T    B)  T specifikációja: u y  d

A y 5  $ L & d

dr%5 $ 
&"d * %5 $ Q 7 p, 6f p, QKd *
7 p, p,   specifikációja: u   d

A  b5 $ 
&4d * 5 $ 
& 7=p, p, Q .                                   Azonos-e a két feladat?  ) ` R
 $ 
& 7 Jz .

V  ) ,  B h G    b]    d     G T       R  $OH
& 7  11.10 Írd le szövegesen az alábbi feladatot: W W u . YW  W A  +* L  5 $ 
& 78 rf / W Q W$ d W 5  YW YW az W vektor permutációinak a halmaza. ahol  11.9 Specifikáljuk a következő feladatot:                       12. Elemi programok  " H  B - /J"wB) . 7 program  -n, 7?V" swf 8swfH ()((  gsof  . Legyen 7 az 7 kiterjeszLegyen   7  T tése -re,  pedig olyan program -n, hogy  ekvivalens -sel -n. 7 a) elemi program-e ? 7 és biztosan elemi program-e  ? b) elemi program-e T  X!  KXG   0  X!wX  X!b    `  ` 12.2   2W W , azaz az X Mi az 2W 7  YW  4 T    T 2W W  #$ %) /m5  ] W$ /0i(%xdmX /0  #y értékadás és az A  2W f X utófeltétel leggyengébb 12.1 előfeltétele? 13. Programkonstrukciók,

levezetési szabályok 13.1  "H DKCDLE! ! .     C     "H DKC E4 7 T B soIC zs?^MIMM s !J "se C4s C  C!smC4E! Es E  "s J  T 7  B soHC zs?! s !J^MMIM "se C4s C  C!smC4E!MMIM Es E  "s MMIM< 7  7  ,   7 7    7 7  , #  7 programokat és a programfüggvényeiket! Add meg az T T T T T
       11  "H DKCDLE! ! ,      C ,     z! DKCD ,    BH CD ! . T 7 B soJ^MMIM s  "seC4E C4s C H Es E "s   T 7  B soJ s zC "se MIMM C4s C Es E "s   7 nB soJ s ^MIMM "se C4s C Es E^MIMM "s H MMIM<   T 7 7 T    7 7     7 7  ? %     ? #   7 13.3 Fejezzük ki a SKIP ill az ABORT programot egy tetszőleges program és a programkonstrukciók
13.2


  
segítségével! 7  7 és  egy-egy program az állapottéren. Igaz-e, hogy  T 7m 7  7  . Igaz-e, hogy 13.5 T   7 
%  % a) lf T !  7  7  G b 7  7     b) tetszőleges A utófeltételre: lf T A lf T lf A ? 13.4 Legyen 7 7 T 7 7  T megegyezik -vel?    13.6 Van-e olyan program, ami felírható szekvenciaként is, elágazásként is, és felírható ciklusként is? 13.7 Igaz-e, hogy minden program felírható szekvenciaként is, elágazásként is, és felírható ciklusként is?   7 7 IMIMMI  7 7 . Igaz-e, hogy %  .1 
  % ? 13.8  T T !    T     7  7  MIMIM7 program  -n!   7 7 MIMIM 7 7  . 7 37 j 7  j (()(0j 7 Keressünk 13.9 Legyen  7 % T T  és %  < ! T T olyan  feltételeket és  programokat, hogy  #    7 I  I M  M I M  7  7  7 j 7 j (()(Jj$7  13.10   része # 7r -nek? . Igaz-e, hogy T 7 T   7 7  . 7 T %         %   % Fj %   13.11 Igaz-e?   v Ha

   K [j % T 7 T    7    v , akkor  K?    T       T T   B  C . 13.12       v v  7   SKIP 7  7    az állapottér egyes pontjaihoz? Milyen sorozatokat rendel T 7  7 7 7 7 7  13.13 T   . T megoldja  T -et és  megoldja   -t Megoldja-e az a)  T     T feladatot? b)  7  7  7  . 7 megoldása az 6    feladatnak 13.14 T 7 az  -et ill. 7  az   -t? T Megoldja-e T IMIMMI T  7   7 7 .   ) feladat * %5 $ 
& 7 7  megoldja az  ]  feladatot. 13.15  T7 T a)  megoldja-e az  feladatot?      ()((    igaz? b)  megoldja-e az  feladatot, ha % T      (()(    ? c)  megoldja-e az  feladatot, ha T                  
        
              12   5  $    T& 7 7 7  T MIMMI  7 7 ] .     feladat  megoldja az  feladatot Igaz-e, hogy *
7 megoldja az 

feladatot?   7 7 T MIMMI   7 7 j .()( (T j MIMMI   ) feladat * 5 $ 
& 7 7  megoldja az   feladatot. 13.17  T T  feladatot? Megoldja-e  az    7 7 IMIMMI  7 7  .  )6 feladat  megoldja az  feladatot és   j-()()( j   % 13.18  T T * T 5 $OH
& 7 7  megoldja az  ]  feladatot.  Igaz-e, hogy    7 7 IMIMMI  7 7 .  IMMIM0  Bi feladat * 5 $OH
& 7 %    és 7  megoldja 13.19  T T   j ()((j T  . Megoldja-e  az  feladatot?  az   feladatot.  T   7  7   7   d  7 j$7   7 13.20 Igaz-e, hogy  T T 7 T  7  és   T 7 T T  7 T   7    13.16                           a) egyenlő? b) ekvivalens? 7   "   13.21 Legyen  " ! Igaz-e, hogy  7 7   " 7 7 " ,  T   T 7 7 T   7   T és     " ,      T 7 7 T  d   7 7   d  " 7 a) egyenlő?

b) ekvivalens?   feladat. 7  program  -n 7  megoldja  -et Megoldja-e a #   7 z program az  feladat V  -re vonatkozó lezártját? #    7 ! Igaz-e, hogy 13.23 Legyen # #  # 7 ? a) # 7 # # ? b)  `   `  13.24  7   7 w  #
   
  D]  7  7  Z Hi ]  7  7 " Z KK 7  7 w  
 ]  ]  v v  7  Z   7  Z  7 KC4 ill. a   ponthoz? Milyen sorozatokat rendel a u 13.25 Tegyük fel, hogy teljesül a ciklus levezetési szabályának mind az öt feltétele, és igazsághalmaza nem üres. Lehet-e üres a 
d A  a) 
d  d A  halmaz? b) u?d  igazsághalmaza 13.26 Tegyük fel, hogy teljesül a ciklus levezetési szabályának mind az öt feltétele, és 7  #     
és lf A igazsághalmazának metszete? nem üres. Lehet-e üres a lf e# 7 J    13.27 Tegyük a ciklus levezetési szabályának mind az öt feltétele. Legyen   teljesül  . Igaz-e, @ és %xfel, 5 
hogy hogy   5

`     %
a) * /n5  % 7    
 / 0 /0 0 % P ? b) U] g # 7 J]  ? c) 13.22         13 : )5 ` 7 0 % d  %   ? 7a 7 7 u u 13.28 Legyen u / lf 7, A GLu T  /  lfés7  , A GLésu A / olyan 7 állítások, u . amelyekre lf  u    A   <@d  u T    u    <@d  u    A    < ? Indokold, ha nem, és írj rá Lehetséges-e, hogy példát, ha igen!    `     `  13.29 X X uB 2W  W d XwX   X dX w" 7 @ A KYW KYWXGf W 2WP  X!0 2WP HKX0 YW P H X P J 6] W 5  Xx5 `bj   "GIf  " b] 5  #x KKYWYW KXGf YW2W  X!0 2WP W HKX 0 YW P H X P J0 YWP KX P J0 2W[P KX P  "GIMMIM0 YW[ P X Z HJ0 YWP XIIJ 2W P X  " r] W 5  dX5!H  E Megjegyzés: Az YW párhoz hosszúságú,#az hosszúságú, YW párhoz hosszúságú  -re.azIgaz-e,  YW   párhoz 7  valamilyen sorozatot rendel a program. Tudjuk, hogy

hogy található olyan
állítás és 7 Vs  függvény, hogy a ciklus levezetési szabályának feltételei teljesülnek, és ha igen, 
adj meg egy megfelelő -t, -t és -t!               13.30  / / 7  7 E  W 2- / 7Wi7  - -xP /z - ?/ 7W 7 w- / Pm-   7   Z JK u   2-  - d /^/ dr5%$ DI)&"dm] -xP /] " A  y 2-  - d)/ wu / / d 7,  W Bizonyítsuk be, hogy lf A ! d)                           14. Típuskonstrukciók    , %x5 .x5 % 1. def: .x5 % 2. def:  14.1


c5  . 9 :  5   87 %x5
9 *  5   78 x% 5
, .


  yd yd : rr5%5%$$ JJ]]  ]] && 7  $.zz . :  7  Ekvivalens-e a két definíció, ha az iterált kombináció, halmaz, sorozat, ill. általában? 14.2   J0 5 . Ekvivalens-e a következő két definició, ha az iterált halmaz, sorozat, ill általában? 0 Mit ad meg p T p ? r     1.

def: p T      T  r      2. def: p  T    


              14