Upload
algernon-norman-onyme
View
70
Download
5
Embed Size (px)
Citation preview
Rappel de cours
Algorithmique 2 et structures de données avancées
Lebbah Fatima Zohra
Ecole Préparatoire en Sciences et Techniques d'OranEPSTO
2me année, Semestre 3 (S3)
September 27, 2011
1 / 18
Rappel de cours
Contenu du cours
1 Rappel de coursLes types standardsL'algorithmeLes types structurésLes procédures et les fonctions
2 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Dé�nition des types standards
type domaine présentation représentation opérateurs fonctionsde valeurs externe interne
booléen faux, vrai faux, vrai 0,1 et,ou,non, ord,pred,<,>,=, succ6=, ≤,≥
entier minentier..maxentier Décimal complément à 2 +,-,*, ord,pred,(15 ou -25) (16/32 bits) <,>,=, 6=, succ
≤,≥,div,mod
réel sous ensemble Décimal virgule �ottante +,-,*,/, sin,cos,abs,des réels (3.5 ou -2.3) (32 bits) <,>,=, sqrt,trunc,
6=, ≤,≥ round, ...
caractère jeu �ni ('x', '?', code ASCII <,>, ord,pred,et ordonné '9', ' " ') (1 octet) 6=, ≤,≥ succ,chr
de caractères
chaîne suite de '1 chaîne' suite de <,>, length,caractères du 'aujourd'hui' code ASCII =,6=, concatcode ASCII ≤,≥
énuméré liste ordonnée constante du type 0,1, etc. <,>, ord,de constantes selon =,6=, pred,
du type énumération ≤,≥ succ
3 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Dé�nition des types standards
type domaine présentation représentation opérateurs fonctionsde valeurs externe interne
booléen faux, vrai faux, vrai 0,1 et,ou,non, ord,pred,<,>,=, succ6=, ≤,≥
entier minentier..maxentier Décimal complément à 2 +,-,*, ord,pred,(15 ou -25) (16/32 bits) <,>,=, 6=, succ
≤,≥,div,mod
réel sous ensemble Décimal virgule �ottante +,-,*,/, sin,cos,abs,des réels (3.5 ou -2.3) (32 bits) <,>,=, sqrt,trunc,
6=, ≤,≥ round, ...
caractère jeu �ni ('x', '?', code ASCII <,>, ord,pred,et ordonné '9', ' " ') (1 octet) 6=, ≤,≥ succ,chr
de caractères
chaîne suite de '1 chaîne' suite de <,>, length,caractères du 'aujourd'hui' code ASCII =,6=, concatcode ASCII ≤,≥
énuméré liste ordonnée constante du type 0,1, etc. <,>, ord,de constantes selon =,6=, pred,
du type énumération ≤,≥ succ
3 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Dé�nition des types standards
type domaine présentation représentation opérateurs fonctionsde valeurs externe interne
booléen faux, vrai faux, vrai 0,1 et,ou,non, ord,pred,<,>,=, succ6=, ≤,≥
entier minentier..maxentier Décimal complément à 2 +,-,*, ord,pred,(15 ou -25) (16/32 bits) <,>,=, 6=, succ
≤,≥,div,mod
réel sous ensemble Décimal virgule �ottante +,-,*,/, sin,cos,abs,des réels (3.5 ou -2.3) (32 bits) <,>,=, sqrt,trunc,
6=, ≤,≥ round, ...
caractère jeu �ni ('x', '?', code ASCII <,>, ord,pred,et ordonné '9', ' " ') (1 octet) 6=, ≤,≥ succ,chr
de caractères
chaîne suite de '1 chaîne' suite de <,>, length,caractères du 'aujourd'hui' code ASCII =,6=, concatcode ASCII ≤,≥
énuméré liste ordonnée constante du type 0,1, etc. <,>, ord,de constantes selon =,6=, pred,
du type énumération ≤,≥ succ
3 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Dé�nition des types standards
type domaine présentation représentation opérateurs fonctionsde valeurs externe interne
booléen faux, vrai faux, vrai 0,1 et,ou,non, ord,pred,<,>,=, succ6=, ≤,≥
entier minentier..maxentier Décimal complément à 2 +,-,*, ord,pred,(15 ou -25) (16/32 bits) <,>,=, 6=, succ
≤,≥,div,mod
réel sous ensemble Décimal virgule �ottante +,-,*,/, sin,cos,abs,des réels (3.5 ou -2.3) (32 bits) <,>,=, sqrt,trunc,
6=, ≤,≥ round, ...
caractère jeu �ni ('x', '?', code ASCII <,>, ord,pred,et ordonné '9', ' " ') (1 octet) 6=, ≤,≥ succ,chr
de caractères
chaîne suite de '1 chaîne' suite de <,>, length,caractères du 'aujourd'hui' code ASCII =,6=, concatcode ASCII ≤,≥
énuméré liste ordonnée constante du type 0,1, etc. <,>, ord,de constantes selon =,6=, pred,
du type énumération ≤,≥ succ
3 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Dé�nition des types standards
type domaine présentation représentation opérateurs fonctionsde valeurs externe interne
booléen faux, vrai faux, vrai 0,1 et,ou,non, ord,pred,<,>,=, succ6=, ≤,≥
entier minentier..maxentier Décimal complément à 2 +,-,*, ord,pred,(15 ou -25) (16/32 bits) <,>,=, 6=, succ
≤,≥,div,mod
réel sous ensemble Décimal virgule �ottante +,-,*,/, sin,cos,abs,des réels (3.5 ou -2.3) (32 bits) <,>,=, sqrt,trunc,
6=, ≤,≥ round, ...
caractère jeu �ni ('x', '?', code ASCII <,>, ord,pred,et ordonné '9', ' " ') (1 octet) 6=, ≤,≥ succ,chr
de caractères
chaîne suite de '1 chaîne' suite de <,>, length,caractères du 'aujourd'hui' code ASCII =,6=, concatcode ASCII ≤,≥
énuméré liste ordonnée constante du type 0,1, etc. <,>, ord,de constantes selon =,6=, pred,
du type énumération ≤,≥ succ
3 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Dé�nition des types standards
type domaine présentation représentation opérateurs fonctionsde valeurs externe interne
booléen faux, vrai faux, vrai 0,1 et,ou,non, ord,pred,<,>,=, succ6=, ≤,≥
entier minentier..maxentier Décimal complément à 2 +,-,*, ord,pred,(15 ou -25) (16/32 bits) <,>,=, 6=, succ
≤,≥,div,mod
réel sous ensemble Décimal virgule �ottante +,-,*,/, sin,cos,abs,des réels (3.5 ou -2.3) (32 bits) <,>,=, sqrt,trunc,
6=, ≤,≥ round, ...
caractère jeu �ni ('x', '?', code ASCII <,>, ord,pred,et ordonné '9', ' " ') (1 octet) 6=, ≤,≥ succ,chr
de caractères
chaîne suite de '1 chaîne' suite de <,>, length,caractères du 'aujourd'hui' code ASCII =,6=, concatcode ASCII ≤,≥
énuméré liste ordonnée constante du type 0,1, etc. <,>, ord,de constantes selon =,6=, pred,
du type énumération ≤,≥ succ
3 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Dé�nition des types standards
type domaine présentation représentation opérateurs fonctionsde valeurs externe interne
booléen faux, vrai faux, vrai 0,1 et,ou,non, ord,pred,<,>,=, succ6=, ≤,≥
entier minentier..maxentier Décimal complément à 2 +,-,*, ord,pred,(15 ou -25) (16/32 bits) <,>,=, 6=, succ
≤,≥,div,mod
réel sous ensemble Décimal virgule �ottante +,-,*,/, sin,cos,abs,des réels (3.5 ou -2.3) (32 bits) <,>,=, sqrt,trunc,
6=, ≤,≥ round, ...
caractère jeu �ni ('x', '?', code ASCII <,>, ord,pred,et ordonné '9', ' " ') (1 octet) 6=, ≤,≥ succ,chr
de caractères
chaîne suite de '1 chaîne' suite de <,>, length,caractères du 'aujourd'hui' code ASCII =,6=, concatcode ASCII ≤,≥
énuméré liste ordonnée constante du type 0,1, etc. <,>, ord,de constantes selon =,6=, pred,
du type énumération ≤,≥ succ
3 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Classi�cation des types standards
Type ordinal
Un type ordinal est un type dont toute constante est codée, enmachine, par un entier qui dé�nit son rang dans le type
Figure: le type ordinal
4 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Classi�cation des types standards
Type ordinal
Un type ordinal est un type dont toute constante est codée, enmachine, par un entier qui dé�nit son rang dans le type
Figure: le type ordinal4 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Traitement de l'information : l'algorithme et le programme
Traitement de l'information
Le traitement de l'information consiste à faire élaborer, par cettemachine, des informations appelées résultats, à partird'informations connues appelées données.
Informations/données−→ Traitement −→Informations/résultats
5 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Traitement de l'information : l'algorithme et le programme
Traitement de l'information
Le traitement de l'information consiste à faire élaborer, par cettemachine, des informations appelées résultats, à partird'informations connues appelées données.
Informations/données−→ Traitement −→Informations/résultats
5 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Structure générale de l'algorithme
1 L'en-tête de l'algorithme : Algorithme-principal Nom-algo
2 La description des données : variables, constantes, les types
personnels,...etc.
3 Le corps de l'algorithme :
début...instruction i-1;instruction i;instruction i+1;...�n.
6 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Les types structurés
Type Dé�nition Nom des Accès aux composants
composants
vecteur tableau[typeindice] de T[expression]tableau à1 type de base variable T[2 ∗ 3]dimension T : tableau [−2 · · · 10] de indicée composant de
array entier rang 9tableau à n tableau
[ti,1, ti,2, , ti,n
]variable T[exp1, exp2, , expn]
dimensions de type base indicéeenregistrement article
article {i1 : t1; i2 : t2; ...; in : tn} Par selecteurstructure champs de champsrecord Date : article {j : 1..31 ;
m : 1..12; a : 2000..2010} Date .j
7 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Implémentation des vecteurs
Algorithme-principal température
variables T : tableau[1..31] de entier;
S,i : entier;
moyenne : réel;
début
S ← 0;
pour i de 1 à 31
faire
écrire('tempéture du jour', i, ':'); lire(T [i ]); S ← S + T [i ];
�nfaire
moyenne← S/31; écrire('Moyenne des températures :', moyenne);
�n
8 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Implémentation des matrices
Algorithme-principal matrice
variables M:tableau [1..10, 1..20] de entier;
S1,i,j : entier; moyenne, S2 : réel;
début
S2← 0;
pour i de 1 à 10 faire
S1← 0;
pour j de 1 à 20 faire
écrire('M[', i, ',', j ' ]='); lire(M [i , j]); S ← S +M [i , j];
�nfaire
moyenne1← S1/10; écrire('La moyenne de la ligne ', i, ':',moyenne);
S2← S2+moyenne;
�nfaire
moyenne ← S2/20; écrire('Moyenne des moyennes des lignes :',moyenne);
�n 9 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Implémentation des enregistrements/ articles
Algorithme-principal enregistrement
variable client : article
{nom : chaîne de caractères;age : entier naturel;taille : réel;}
début
écrire('Donner le nom, l'age et la taille du client :');
lire(client.nom); lire(client.age);lire(client.taille);
si (client.age > 50) alors écrire(client.nom, "est vieux") sinonécrire(client.nom, "est jeune");
�n
10 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Les procédures et les fonctions
La programmetion structurée
La programmation structurée o�re des outils procédures etfonctions qui facilitent la maîtrise de la complexité des algorithmes.
Les procédure et les fonctions
Les procédures et les fonctions permettent de décomposer lasolution d'un problème en sous-problèmes plus facilementmaîtrisables.
11 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Les procédures et les fonctions
La programmetion structurée
La programmation structurée o�re des outils procédures etfonctions qui facilitent la maîtrise de la complexité des algorithmes.
Les procédure et les fonctions
Les procédures et les fonctions permettent de décomposer lasolution d'un problème en sous-problèmes plus facilementmaîtrisables.
11 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Les paramètres de communication
Les paramètres données :formalisés par ↓,
Les paramètres résultats :formalisés par ↑,Les paramètresdonnées/résultats :formalisés par ↓↑.
12 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Les paramètres de communication
Les paramètres données :formalisés par ↓,
Les paramètres résultats :formalisés par ↑,Les paramètresdonnées/résultats :formalisés par ↓↑.
12 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Les paramètres de communication
Les paramètres données :formalisés par ↓,Les paramètres résultats :formalisés par ↑,
Les paramètresdonnées/résultats :formalisés par ↓↑.
12 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Les paramètres de communication
Les paramètres données :formalisés par ↓,Les paramètres résultats :formalisés par ↑,
Les paramètresdonnées/résultats :formalisés par ↓↑.
12 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Les paramètres de communication
Les paramètres données :formalisés par ↓,Les paramètres résultats :formalisés par ↑,Les paramètresdonnées/résultats :formalisés par ↓↑.
12 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Les paramètres de communication
Les paramètres données :formalisés par ↓,Les paramètres résultats :formalisés par ↑,Les paramètresdonnées/résultats :formalisés par ↓↑.
12 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Les procédures
Les procédures
Une procédure peut être considérée comme une instruction utiliséepour abstraire et nommer une action non primitive.
Comment dé�nir une procédure ?
1 L'en-tête de la procédure : procédure nom-procedure (liste de paramètres
formels). Tout paramètre formel est décrit par :
un mode de transmission,un nom (identi�cateur),un type.
2 La description de l'environnement local,
3 Le corps de l'algorithme de la procedure :
début...instruction i;...�n.
13 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Les procédures
Les procédures
Une procédure peut être considérée comme une instruction utiliséepour abstraire et nommer une action non primitive.
Comment dé�nir une procédure ?
1 L'en-tête de la procédure : procédure nom-procedure (liste de paramètres
formels). Tout paramètre formel est décrit par :
un mode de transmission,un nom (identi�cateur),un type.
2 La description de l'environnement local,
3 Le corps de l'algorithme de la procedure :
début...instruction i;...�n. 13 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Implémentation des procédures
procédure permut(↓↑x,y:réel)variable z : réel
début
z ← x ; x ← y ; y ← z;
�n
14 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Les fonctions
Les fonctions
Une fonction peut être considérée comme un opérateur utilisé pourabstraireet nommerle calcul d'une expression.
Comment dé�nir une fonction ?1 L'en-tête de la fonction : fonction nom-fonction (liste de paramètres formels) :
type. Tout paramètre formel est décrit par :
le mode de transmission ↓ (optionnel),un nom (identi�cateur),un type.
2 Le corps de l'algorithme de la fonction:
début...instruction i;...nom-fonction = exp;�n.
15 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Les fonctions
Les fonctions
Une fonction peut être considérée comme un opérateur utilisé pourabstraireet nommerle calcul d'une expression.
Comment dé�nir une fonction ?1 L'en-tête de la fonction : fonction nom-fonction (liste de paramètres formels) :
type. Tout paramètre formel est décrit par :
le mode de transmission ↓ (optionnel),un nom (identi�cateur),un type.
2 Le corps de l'algorithme de la fonction:
début...instruction i;...nom-fonction = exp;�n.
15 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
Implémentation des fonctions
fonction somme((↓ n : 0..maxentier) : 0..maxentier
variable S, i : entier
début
S ← 0;
pour i de 1 à n
faire
S ← S + i ;
�nfaire
somme ← S;
�n
16 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
La programmation structurée et les types de paramètres
Les types de paramètres
En PS, la solution d'un problème fait intervenir plusieursalgorithmes structurés en blocs (de procédure ou de fonction)imbriqués ou disjoints pour un bloc B, un objet est dit :
Local : s'il est dé�ni dans B,
Global : s'il estdé�ni dans un bloc englobant B.
17 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
La programmation structurée et les types de paramètres
global et local
Un objet global est visible à partir d'un bloc s'il n'est pas masquépar la dé�nition d'un objet homonyme. Dans un bloc B, on peutaccéder à :
tous les objets locaux à B,
tous les objets globaux visibles.
Figure: Exemple de la programmation structurée
18 / 18
Rappel de cours
Les types standardsL'algorithmeLes types structurésLes procédures et les fonctions
La programmation structurée et les types de paramètres
global et local
Un objet global est visible à partir d'un bloc s'il n'est pas masquépar la dé�nition d'un objet homonyme. Dans un bloc B, on peutaccéder à :
tous les objets locaux à B,
tous les objets globaux visibles.
Figure: Exemple de la programmation structurée18 / 18