Programmation procédurale Les différents schémas A. Introduction B. Les différents schémas B-schémas D-schémas R-schémas BJn-schémas REn-schémas RECn-schémas

Programmation procéduraleLes différents schémas

A. Introduction B. Les différents schémas B-schémas D-schémas R-schémas BJn-schémas REn-schémas RECn-schémas Variantes Comparaison des structures Relation entre schémas Relation entre structures Quelques résultats


� IntroductionCalculateurs câblés :A l'origine de l'informatique, toutes les opérations étaient câblées.

Machine de Von NeumannLe programme est stocké en mémoire centrale.

• Existence d'un canal de communication entre la mémoire et l'unité de traitement (UC)

• Donc deux opérations de base :- traitement (UC)- mouvement d'informations( Canal de communication)

• L'opération de base est l'affectation.

• Ne sont pas basés sur des systèmes formels.


� Schéma avec Branchement (B-schémas)• Syntaxe sous forme étendue de Backus-Naur.

B-language

<b-algo> => <Inst>{; <Inst> }*<Inst> => <InstSimple> |

Etiq: InstSimple><InstSimple>=><saut>|

<SautCond> | stop | a | b | c | d

<Saut> => Allera Etiq<SautCond> => SI<exp> Allera Etiq<Exp> => T1|T2|T3|.....

Les seules structures de contrôle sont les branchements inconditionnel et conditionnel.


� Schéma avec Branchement (B-schémas)

• Une instruction peut être :- une action - un "si » - un "allera » - un arret

• Le schéma de programme devient un programme lorsqu'on donne un sens aux symboles de fonctions et de prédicats. C'est ce qu'on

• appelle une interprétation.

• Le langage des B-schéma est solution de l'équation à point fixe :

B = A UEt : B UB ; B USi P allera et UAllera et


� Schéma itératif ( D-schéma )

<d-algo> => <Inst> {; <Inst>}*<Inst> => <Tantque>| <Sisinon>|a|b|c|d|....<Tantque> => TANTQUE <exp> :

<Inst>{;<Inst>}* FTANTQUE

<Sisinon> => SI <exp>: <Inst> {; <Inst>}*[SINON

<Inst>{; <Inst>}* ] FSI<Exp> => T1|T2|T3|.....


� Schéma itératif ( D-schéma )

• Les seules structures de contrôle sont la répétitive et l'alternative

• Le langage des D-schémas est solution de l'équation à point fixe :

D = A UD ; D UTantque P : D FintantqueSi P : D Sinon D Finsi


� Schéma récursif

• Une seule structure de contrôle: alternative avec des appels récursifs.


� BJn-schémas• B pour Bohm et J pour Jaccopini

Séquentielle : a ; bConditionnelle : si p alors a sinon b fsiK-itération :

faire p1 --> a1 ; p2 --> a2 ; ....pk --> ak

faitavec K dans l'intervalle [1, n].


� BJn-schémas

• Sens de la K-itération :Si p1 est vrai on effectue a1, puis si p2 est vrai on effectue a2, ....Après ak, on revient en p1.L'itération est arrêtée dés qu'un pi est faux.

• Syntaxiquement le langage BJ est solution de :BJ = A U

BJ ; BJ USi (P U !P) alors BJ sinon BJ fsi UFaire P --> BJ ;

P --> BJ ... ; P --> BJ FaitA désigne l'ensemble des actions.


� REn-schémas • Schéma Répétitif avec Exit.

C'est le cas où on a plusieurs boucles imbriquées et on veut sortir directement des i boucles englobant. On introduit un nouveau type de d'instruction : EXIT(i), 1<= i <= n.

Composante sérielle : a ; bConditionnelle : si p alors a sinon b fsiRépétitive : Faire a fait

où a comporte éventuellement des instructions Exit().


� REn-schémas

• Schéma Répétitif avec Exit.

• Syntaxiquement le langage RE est solution de :

RE = A URE ; RE USi ( P U !P) alors RE Sinon RE fsi UFaire RE fait

F contient des actions et des instructions Exit(i).


� RECn-shémas

• C'est RE auquel on ajoute l'instruction Entrée(i) qui réalise un saut au début de la i-ème itération.


� Variantes

• Dans les REn et RECn on ne retrouve pas la construction Tantque p faire a fait des D-schémas.

• On appelle DREn ( respectivement DRECn) schémas l'ensemble des schémas REn et RECn étendus par ce mode de construction. Les instructions Entrée et Exit ne portent pas sur l'instruction Tantque.


� Comparaison des structures ( Relation entre schémas )

• R1 : Pour toute interprétation I de &1 et &2 on a : I(&1) = I(&2).

• R2 : Les ensembles d'actions et de prédicats ayant une occurrence dans &1 ou dans &2 sont les mêmes.

• Remarques :

1. R1 et R2 sont des relations d'équivalence.

2. Si deux schémas sont reliés par la relation R2, le passage de l'un à l'autre se fait sans introduction de nouvelles actions ou tests.


� Comparaison des structures ( Relations entre structures )

• Soient S1 et S2 deux structures et R une relation• S1 est dit réductible en S2 pour la relation R si quelque soit &1 de S1, il existe

&2 de S2 tel que &1 R &2.notation : S1 <=R S2

• S1 est dit équivalent à S2 pour R si :S1 <=R S2 et S2 <=R S1notation : S1 =R S2

• S1 et dit strictement réductible en S2 pour R si :S1 <=R S2 et non (S2 <=R S1)notation : S1 <R S2


� Comparaison des structures (Relations courantes entre structures)

• Conversion fonctionnelle (FN)Elle correspond à R1 : S1 <=FN S2.Sens : Pour toute interprétation I, et tout schéma &1 de S1, il existe un schéma &2 de S2 tel que I(&1) = I(&2).

• Conversion sémantique (SE)Elle correspond à R1 et R2. S1 <=SE S2.Sens : Pour toute interprétation I, et tout schéma &1 de S1, il existe un schéma &2 de S2 construit sans introduction de nouvelles actions et tel que I(&1) = i(&2).


� Quelques résultats

• D <SE B

• D =FN B (Théorème de Bohm et Jaccopini)


� Quelques résultats • Les comparaisons entre structures sont les résultats des travaux de RAO-

KOSARAJU (1974). <, <=, = désigne <SE, <=SE, =SE.RE = REC = DRE = DREC = B V VREn = RECn <= DREn = DRECn

V VIRE2 = REC2 <= DRE2 = DREC2

V VIRE1 = REC1 <= DRE1 = DREC1

VBJ VBJn

VBJ2

VBJ1 = D (V désigne < et VI <=)


� Conclusion • Soit S une structure quelconque parmi celles que nous venons de

définir. D'après le tableau ci-dessus nous avonsD <=SE S <=SE B

D'où a fortioriD <=FN S <=FN B

Comme B =FN D ( Théorème de Bohm et Jaccopini), on en déduit :S =FN B

Théorème : Toutes les structures présentées sont fonctionnellement équivalentes.

Documents

Programmation procédurale Les différents schémas A. Introduction B. Les différents schémas B-schémas D-schémas R-schémas BJn-schémas REn-schémas RECn-schémas