7. fejezet - Programkonstrukciók
Előző I. rész - Bevezetés a programozáshoz (Fóthi Ákos) Következő

7. fejezet - Programkonstrukciók

Tartalom

7.1Megengedett konstrukciók
7.2A programkonstrukciók programfüggvénye
7.3Levezetési szabályok
7.4Példák
7.5Feladatok
7.6A programkonstrukciók és a kiszámíthatóság
7.6.1Parciális rekurzív függvények
7.6.2A parciális rekurzív függvények kiszámítása
7.6.3Következmény
7.6.4Relációk

Ebben a fejezetben azzal foglakozunk, hogy hogyan lehet meglevő programokból új programokat készíteni. Természetesen sokféleképpen konstruálhatunk meglevő programjainkból új programokat, de most csak háromféle konstrukciós műveletet fogunk megengedni: a szekvencia-, elágazás- és ciklusképzést. Később megmutatjuk, hogy ez a három konstrukciós művelet elegendő is. Nemcsak definiáljuk ezeket a konsrukciókat, de megvizsgáljuk programfüggvényüket és leggyengébb előfeltételüket is.

7.1Megengedett konstrukciók

Az első definíció arról szól, hogy egy programot közvetlenül egy másik után végezzünk el. A definícióban használni fogjuk a következő jelölést: legyen , ,

7.1. Definíció (SZEKVENCIA).

Legyenek programok. Az relációt az és szekvenciájának nevezzük, és -vel jelöljük, ha :

7.1. ábra -

7.1. ábra. Szekvencia

Vegyük észre, hogy ha két olyan program szekvenciáját képezzük, amelyek értékkészlete csak véges sorozatokat tartalmaz, akkor a szekvencia is csak véges sorozatokat rendel az állapottér pontjaihoz.

Hasonlóan egyszerűen ellenőrizhető az is, hogy determinisztikus programok szekvenciája is determinisztikus reláció (függvény).

A programkonstrukciókat szerkezeti ábrákkal, úgynevezett struktogramokkal szoktuk ábrázolni.

Legyenek , programok -n. Ekkor az szekvencia struktogramja:

A második konstrukciós lehetőségünk az, hogy más-más meglevő programot hajtsunk végre bizonyos feltételektől függően.

7.2. Definíció (ELáGAZáS).

Legyenek feltételek, programok -n. Ekkor az relációt az -kből képzett -k által meghatározott elágazásnak nevezzük és -nel jelöljük, ha :

ahol :

Az elágazás definíciójában nem kötöttük ki, hogy a feltételek diszjunktak, tehát az állapottér egy pontjában több feltétel is igaz lehet, ebben az esetben az elágazás az összes olyan sorozatot hozzárendeli ehhez a ponthoz, amit legalább egy olyan program, aminek a feltételrésze ebben a pontban igaz. Ezért haa a feltételek nem diszjunktak, akkor a determinisztikus programokból képzett elágazás lehet nem determinisztikus is.

Ha csak olyan programokból képzünk elágazást, amik csak véges sorozatokat rendelnek az állapottér minden pontjához, az elágazás akkor is rendelhet (azonos elemekből álló) végtelen sorozatot, ha a feltételek igazsághalmazai nem fedik le az egész állapotteret.

Megjegyezzük, hogy a definíció szerint, ha egy pontban egyik feltétel sem teljesül, az elágazás "elszáll", ellentétben a legtöbb gyakorlatilag használt programnyelvvel.

Legyenek programok, feltételek -n. Ekkor az elágazás struktogramja:

A harmadik konstrukciós lehetőségünk az, hogy egy meglevő programot egy feltételtől függően valahányszor egymás után végrehajtsunk. A ciklus definálásához szükségünk van további két jelölésre: véges sok, illetve végtelen sok sorozat konkatenációjának redukáltjára.

Legyenek és ,

Legyenek ,

7.3. Definíció (CIKLUS).

Legyen feltétel és program -n. A relációt az -ból a feltétellel képzett ciklusnak nevezzük, és -lal jelöljük, ha

  • :

  • :

Első ránézésre a definíció kissé bonyolult. Nézzük meg alaposabban!

7.2. ábra -

7.2. ábra. Ciklus

A defifícó alapján nyílvánvaló, hogy a determinisztikus programból képzett ciklus is determinisztikus lesz.

Ezzel ellentétben, ha egy csak véges sorozatokat rendelő programot foglalunk ciklusba, akkor a ciklus értékkészlete még tartalmazhat végtelen sorozatot (ha soha nem jutunk ki a feltétel igazsághalmazából).

Legyen program, feltétel -n. Ekkor a ciklus struktogramja:

A fentiekben leírt konstrukciókat programokra lehet alkalmazni. De vajon programokat hoznak-e létre? Az alábbi tétel kimondja, hogy az előzőkben definiált három konstrukciós művelet meglevő programokból valóban programokat hoz létre. 7.1. TéTEL: A SZEKVENCIA, AZ ELáGAZáS éS A CIKLUS PROGRAM. Legyen tetszőleges állapottér, programok, valamint feltételek -n. Ekkor

  1. ,

  2. ,

programok -n.

Bizonyítás:  Mindhárom konstrukció definíciójában explicit szerepel, hogy reláció -on, és , azaz teljesül a program definíciójának első pontja. A továbbiakban esetekre bontva megvizsgáljuk a másik két kritérium teljesülését.

  1. Legyen tetszőleges, és . Ekkor két eset lehetséges:

    • Ha és ebben az esetben és triviálisan teljesül, hiszen program.

    • Ha úgy, hogy és . Ekkor a definíciója miatt redukált. Másrészt , tehát .

  2. Legyen tetszőleges, és . Ekkor

    • Tegyük fel, hogy . Ekkor , tehát teljesíti a program definíciójának kritériumait.

    • Tegyük fel, hogy . Ekkor , így mivel program, teljesíti a definícióban megkívánt tulajdonságokat.

  3. Legyen tetszőleges, és .

    • Tegyük fel, hogy . Ekkor , így az előírt tulajdonságok triviálisan teljesülnek.

    • Tegyük fel, hogy . Ekkor három eset lehetséges:

      1. :

        Ekkor , így – definíciója miatt – redukált. Másrészt felhasználva, hogy és , is teljesül.

      2. : Ekkor a kritériumok teljesülése az előző ponttal analóg módon ellenőrizhető.

      3. :

        Ekkor a definíciója alapján redukált sorozat, és is teljesül.

_

Előző Fel Következő
6. fejezet - Elemi programok Tartalom 7.2A programkonstrukciók programfüggvénye