online kép - Fájl  tube fájl feltöltés file feltöltés - adja hozzá a fájlokat online fedezze fel a legújabb online dokumentumok Kapcsolat
   
 

Letöltheto dokumentumok, programok, törvények, tervezetek, javaslatok, egyéb hasznos információk, receptek - Fájl kiterjesztések - fajltube.com

 

Online dokumentumok - kep
   
kategória
 

Biológia állatok Fizikai Földrajz Kémia Matematika Növénytan Számítógépes
Filozófia
Gazdaság
Gyógyszer
Irodalom
Menedzsment
Receptek
Vegyes

 
 
 
 













































 
 

Programgraf. Valódi program, strukturalt program fogalma. Strukturalt és nemstrukturalt alapformak. Böhm-Jacopini tétele.

számítógépes

Fájl küldése e-mail Esszé Projekt


egyéb tételek

 
Funkcionalis függőségek, normalformak
Fajlrendszerek
Megoldasi módszerek
Hattértarak, tömegtarolók
A központi egység
A MagicDVDRipper kezelése
Operaciós rendszerek
A Graph unit fontosabb beépített konstansai, függvényei, eljarasai; hasznalata
Artistic Media
A CLIPPER relaciós adatbaziskezelö nyelv
 
 

Programgráf. Valódi program, strukturált program fogalma. Strukturált és nemstrukturált alapformák. Böhm-Jacopini tétele.

Valódi program: olyan gyengén öf. irányított gráf, amely:

1.,        véges számú nem zérus bemenő éllel és kijövő éllel rendelkezik

2.,        csp.-jai prédikátum csp.-ok és fv.csp.-ok és gyűjtő csp.-ok.

3.,        csp.-on át vezet legalább egy bemenő éllel kezdődő és kijövő éllel végződő út

Példa Nem valódi pr.:



Azt a pr.-ot, melynek gráfja lebontható az önmagában álló ir. élre, struktúrált pr.-nak nevezzük.

Struktúrált programozás

 

1., if p then f else g  -  I-T-E (p,f,g)

g

 
                     545f59f                      545f59f                      545f59f                      545f59f                      545f59f                     ha p akkor f

          ­            p             ¯                     545f59f                      545f59f                      545f59f                      545f59f            kül. g

                     545f59f                      545f59f                      545f59f             p                     545f59f                      545f59f       ha vége

f

 
                 f           g                     545f59f         

2., while p do f  -  W-D(p,f)


                     545f59f     p                     545f59f                      545f59f       p                     545f59f                      545f59f       ciklus amíg p

f

 
                     545f59f                      545f59f                      545f59f                      545f59f                      545f59f                      545f59f             f

                     545f59f                      545f59f                      545f59f                      545f59f                      545f59f                     ciklus vége

                     545f59f     f                     545f59f                      545f59f                      545f59f           


3., begin f g end  - B(f,g)

f

 

f

 

g

 


                     545f59f                      545f59f                      545f59f                      545f59f                      545f59f                     f

g

 
                     545f59f                      545f59f                      545f59f                      545f59f                      545f59f                     g

Definíció:  Egy pr. gráf lebontása az az eljárás, melynek során a fenti 3 alapszerkezet valamelyikét egy fv.csp.-tal helyettesítjük, és ezt addig folytatjuk, amíg lehetséges.

Egy fv.csp.-ot tartalmazó gráf ® önmagában álló ir. él.

Példa

                     545f59f                 p2

f2

 
1.,

            p1


W-D(p2, f2)

 
2.,


            p1


3.,

I-T-E(p1, f1, W-D(p2, f2))

 
           


4.,


Definíció: Azt a pr.-ot, melynek gráfja lebontható az önmagában álló ir. élre, struktúrált pr.-nak nevezzük.

Megjegyzés: Lehet a do f while p - DU(p,f) formát is struktúrált alapformának tekinteni.

f

 


f

 
                     545f59f                      545f59f         p

                     545f59f                      545f59f                      545f59f                      545f59f                      545f59f         p




f

 
                     545f59f                 ciklus

                     545f59f                     f      

                     545f59f                 amíg p

Példa

h

 

h

 
                     545f59f     nem strukt.                     545f59f                      545f59f               strukt.


                     545f59f                 q                     545f59f                      545f59f                      545f59f           q


                     545f59f     p                     545f59f                      545f59f                      545f59f           p

f

 

g

 


Nem strukturáltság jellemzői

Tétel: Egy pr. nem struktúrált Û részgráfjaként előfordul nem struktúrált alapforma.

Tétel: A nem struktúrált pr. a nem struktúrált alapformák közül legalább 2-t tartalmaz.

Nem struktúrált alapformák:


több kilépő élű ciklus                     545f59f                      545f59f          több belépő élű ciklus


több kilépő élű döntés                     545f59f                      545f59f                     több belépő élű döntés

 

(Böhm-Jacopini)

valódi pr.-hoz  vele ekvivalens struktúrált program.

Bizonyítás: (vázlat)

1. Lemma: Adott egy pr. gráf:

élek száma:     n

pred.csp.:        p

gyűjtő csp.:     g

fv.csp.:            j

Ekkor: n = 3p + j + 1 és p = g

Ui.: Csp.-ba mutató élek száma:

fv.csp.-ba:       j                     545f59f   Összesen:

pred.csp.-ba:   p                     545f59f   j + p  + 2g +1 = n

gyűjtő csp.-ba:2g                     545f59f                      545f59f     kimenő él

Csoportból kimutató élek:

fv.csp.-ba:       j                     545f59f   Összesen:

pred.csp.-ba:   2p                    j + 2p + g +1 = n

gyűjtő csp.-ba: g                     545f59f                      545f59f      bemenő él


Þ j + p  + 2g +1 = j + 2p + g +1

                     545f59f     g   =   p                     545f59f                      545f59f         n=3p+j+1

2. Lemma: Egy pr. struktúrált Û felírható B(g,h) , vagy I-T-E(p,g,h) , vagy W-D(p,g) alakban, ahol p predikátum, g,h struktúrált pr., vagy fv., vagy üres pr.

Ui.: Egyszerű meggondolással látható a pr. lebontásánál mutatott módszerrel.

Bizonyítás: (tétel) Konstruktív

Belátjuk: valódi pr. felírható B(g,h), I-T-E(p,g,h), W-D(p,g) alakban, ahol g,h valódi pr.-ok és gráfjukban az élek száma kisebb, mint ez eredeti pr. éleinek száma.

Találat: 910