Upload
lianne-alix
View
115
Download
0
Embed Size (px)
Citation preview
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
Programmation procéduraleLes différents schémas
� 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.
Programmation procéduraleLes différents schémas
� 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.
Programmation procéduraleLes différents schémas
� 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
Programmation procéduraleLes différents schémas
� 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|.....
Programmation procéduraleLes différents schémas
� 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
Programmation procéduraleLes différents schémas
� Schéma récursif
• Une seule structure de contrôle: alternative avec des appels récursifs.
Programmation procéduraleLes différents schémas
� 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].
Programmation procéduraleLes différents schémas
� 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.
Programmation procéduraleLes différents schémas
� 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().
Programmation procéduraleLes différents schémas
� 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).
Programmation procéduraleLes différents schémas
� 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.
Programmation procéduraleLes différents schémas
� 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.
Programmation procéduraleLes différents schémas
� 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.
Programmation procéduraleLes différents schémas
� 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
Programmation procéduraleLes différents schémas
� 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).
Programmation procéduraleLes différents schémas
� Quelques résultats
• D <SE B
• D =FN B (Théorème de Bohm et Jaccopini)
Programmation procéduraleLes différents schémas
� 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 <=)
Programmation procéduraleLes différents schémas
� 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.