Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Le Langage Pseudo-Code Cours d’Algorithmique 1er Semestre (Fr´ ed´ eric Koriche

Le Langage Pseudo-Code Cours d’Algorithmique 1er Semestre (Fr´ ed´ eric Koriche) IUT Informatique de Lens Donn´ ees En algorithmique, toute donn´ ee est d´ eﬁnie par ▶son nom: d´ esigne la donn´ ee dans l’algorithme, ▶son type: d´ esigne le domaine de valeurs de la donn´ ee, et ▶sa nature: variable (peut changer de valeur) ou constante (ne peut pas changer de valeur). Types Simples Type Domaine bool´ een {faux, vrai} caract` ere Symboles typographiques entier Z r´ eel R Op´ erateurs Un op´ erateur est une fonction d´ eﬁnie par ▶son arit´ e: d´ esigne le nombre de variables d’entr´ ee, ▶sa position: l’op´ erateur peut ˆ etre pr´ eﬁxe (devant), inﬁxe (milieu) ou postﬁxe (derri` ere), et ▶son type: d´ esigne le type de ses entr´ ees et celui de sa sortie. Exemple: L ’op´ erateur d’addition sur les entiers Op´ erateur binaire, not´ e + (position inﬁxe), dont le type est: + : entier × entier →entier Op´ erateurs sur les types simples ▶Arithm´ etiques (entiers): toutes les entr´ ees sont des entiers et la sortie est un entier. Nom Symbole addition + soustraction − multiplication × division enti` ere / reste mod inversion de signe − ▶Arithm´ etiques (r´ eels): au moins une entr´ ee est un r´ eel et la sortie est un r´ eel. Nom Symbole addition + soustraction − multiplication × division / inversion de signe − ▶Comparaisons: les deux entr´ ees sont des entiers, caract` eres∗ou r´ eels. La sortie est un bool´ een. Nom Symbole est ´ egal ` a = est plus petit que < est plus grand que > est plus petit ou ´ egal ` a ≤ est plus grand ou ´ egal ` a ≥ ▶Logiques: toutes les entr´ ees sont des bool´ eens et la sortie est un bool´ een. Nom Symbole conjonction et disjonction ou n´ egation non Expressions Une expression est une composition d’op´ erations dont l’ordre est sp´ eciﬁ´ e par les parenth` eses. Le type d’une expression est donn´ e par le type de sa valeur de sortie Exemple: Supposons que x, y, z soient des entiers. ▶(x > 0) et (y < 0) est une expression bool´ eenne ▶(x + y)/z est une expression enti` ere Instructions Une instruction est une action ` a accomplir par l’algorithme. Les quatre instructions de base sont la d´ eclaration (m´ emoire), l’assignation (calcul), la lecture (entr´ ees) et l’´ ecriture (sorties). Instruction Sp´ eciﬁcation D´ eclaration type variable Assignation variable ← −expression Lecture lire variable Ecriture ´ ecrire expression Blocs Un bloc est une s´ equence d’instructions identiﬁ´ ee par une barre verticale. Exemple: permutation de valeurs d´ ebut entier a, b, temp lire a, b temp ← −a a ← −b b ← −temp afﬁcher a, b ﬁn L ’instruction de test ”si alors” Dans l’instruction si condition alors bloc, la condition est une expression bool´ eenne, et le bloc n’est ex´ ecut´ e que si la condition est vraie. Exemple: valeur absolue d´ ebut r´ eel x, y lire x y ←x si y < 0 alors y ←−y afﬁcher y ﬁn L ’instruction de test ”si alors sinon” Dans si condition alors bloc 1 sinon bloc 2, la condition est une expression bool´ eenne. Le bloc 1 est ex´ ecut´ e si la condition est vraie ; le bloc 2 est ex´ ecut´ e si la condition est fausse. Exemple: racine carr´ ee d´ ebut r´ eel x, y lire x si x ≥0 alors y ←sqrt(x) afﬁcher y sinon afﬁcher ”Valeur ind´ eﬁnie” ﬁn L ’instruction de test ”suivant cas” Dans l’instruction suivant condition cas o` u v1 bloc 1 cas o` u v2 bloc 2 . . . , la condition est une expression pouvant prendre plusieurs valeurs v1, v2, . . .. Selon la valeur de la condition, le bloc du cas correspondant est ex´ ecut´ e. Exemple: choix de menu d´ ebut entier menu lire menu suivant menu faire cas o` u 1 afﬁcher ”Menu enfants” cas o` u 2 afﬁcher ”Menu v´ eg´ etarien” autres cas afﬁcher ”Menu standard” ﬁn L ’instruction de boucle ”pour” L ’instruction pour est utilis´ ee lorsque le nombre d’it´ erations est connu ` a l’avance: elle initialise un compteur, l’incr´ emente apr` es chaque ex´ ecution du bloc d’instructions, et v´ eriﬁe que le compteur ne d´ epasse pas la borne sup´ erieure. Exemple: Somme des entiers de 1 ` a n d´ ebut entier n, s, i lire n s ←0 pour i de 1 ` a n faire s ←s + i afﬁcher s ﬁn L ’instruction de boucle ”tant que” La boucle tant que est utilis´ ee lorsque le nombre d’it´ erations n’est pas connu ` a l’avance: elle ex´ ecute le bloc d’instructions tant que la condition reste vraie. Exemple: Somme des entr´ ees saisies par l’utilisateur (version ”tant que”) d´ ebut entier n ←1, s ←0 tant que n ̸= 0 faire afﬁcher ”Entrer un entier (0 pour arrˆ eter) : ” lire n s ←s + n afﬁcher s ﬁn L ’instruction de boucle ”r´ ep´ eter jusqu’` a” La boucle r´ ep´ eter jusqu’` a est utilis´ ee lorsque le nombre d’it´ erations n’est pas connu ` a l’avance, et qu’il faut lancer au moins une ex´ ecution du bloc d’instructions. Elle ex´ ecute le bloc jusqu’` a ce que la condition d’arrˆ et devienne vraie. Exemple: Somme des entr´ ees saisies par l’utilisateur (version ”r´ ep´ eter jusqu’` a”) d´ ebut entier n, s ←0 r´ ep´ eter lire n s ←s + n jusqu’` a n = 0 afﬁcher s ﬁn Le Langage Pseudo-Code Cours d’Algorithmique 1er Semestre (Fr´ ed´ eric Koriche) IUT Informatique de Lens Tableaux Statiques Unidimensionnels Un tableau (statique unidimensionnel) est une s´ equence de donn´ ees du mˆ eme type accessibles par leur index. Il est d´ eﬁni par: ▶son nom, ▶le type de ses ´ el´ ements, et ▶sa taille ou le nombre de ses ´ el´ ements. Le premier index d’un tableau de N ´ el´ ements est 0 et le dernier index est N −1. 0 1 2 3 4 5 6 7 12 14 16 09 11 10 13 17 Un tableau de 8 entiers Les seules op´ erations possibles sont la d´ eclaration, l’initialisation (d´ eclaration avec valeurs initiales) et l’acc` es ` a ses ´ el´ ements. Op´ eration Sp´ eciﬁcation Exemple D´ eclaration type nom [taille] entier tab[10] Initialisation type nom [n] ←{v1, · · · , vn} caract` ere voyelles[5] ←{’a’,’e’,’i’,’o’,’u’,’y’} Acc` es nom [index] voyelles[i] Tableaux Statiques Multidimensionnels Un tableau statique de dimension d est une s´ equence de tableaux de dimension d −1. En particulier, une matrice est un tableau de dimension 2. Comme pour tous les tableaux statiques, les seules op´ erations possibles sont la d´ eclaration, l’initialisation et l’acc` es ` a ses ´ el´ ements. Op´ eration Sp´ eciﬁcation Exemple D´ ecl. type nom [rang´ ees][colonnes] r´ eel matrice[4][4] Init. type nom [m][n] ←{{v11, · · · , v1n}, · · · , {vm1, · · · , vmn}} r´ eel unit´ e[2][2] ←{{1, 0}, {0, 1}} Acc` es nom [rang´ ee][colonne] matrice[i][j] Tableaux Dynamiques Un tableau dynamique (unidimensionnel) ou vecteur est une s´ equence de donn´ ees du mˆ eme type ; la taille de la s´ equence est variable (elle peut changer au cours de l’ex´ ecution du programme). En plus des op´ erations de tableaux statiques, les vecteurs permettent des op´ erations de copie et de modiﬁcation. Op´ eration Sp´ eciﬁcation Exemple D´ eclaration vecteur de type nom vecteur de r´ eels v Initialisation vecteur de type nom(quantit´ e,valeur) vecteur de r´ eels v(10,0) Copie nom1 ← −nom2 v ←w Acc` es aux ´ el´ ements nom[index] v[i] Acc` es ` a la taille longueur(nom) longueur(v) Test du vecteur vide vide(nom) si(vide(v)) alors . . . Ajout d’un ´ el´ ement ` a la ﬁn ´ etend ´ etend(v, 10.0) Chaˆ ınes Une chaˆ ıne est un tableau dynamique unidimensionnel compos´ e de caract` eres ascii. En plus des op´ erations de vecteurs, les chaˆ ınes permettent des op´ erations de comparaison lexicographique. Op´ eration Sp´ eciﬁcation Exemple D´ eclaration chaˆ ıne nom chaˆ ıne c Initialisation chaˆ ıne nom ←constante chaˆ ıne chaˆ ıne c ←”Bonjour” Copie nom1 ← −nom2 c ←d Acc` es aux ´ el´ ements nom[index] c[i] Acc` es ` a la taille longueur(nom) longueur(c) Test de la chaˆ ıne vide vide(nom) si(vide(c)) alors . . . Concat´ enation + c ←c + d Comparaisons ≤, <, =, ̸=, >, ≥ si(c ̸= d) alors . . . Typage Il est possible de construire de nouveaux types ` a partir de types pr´ ed´ eﬁnis en utilisant le mot-cl´ e type. En pseudo-code les types apparaissent avant les algorithmes. Exemple: d´ eclaration d’un type et d’une variable de ce type type entier MatriceDeRotation [2][2] d´ ebut MatriceDeRotation m . . . ﬁn Enum´ erations Une ´ enum´ uploads/s3/ algorithmique-2012-synthesepc.pdf