Cours Algorithmique pour réviser ensemble
...
- Définition nom masculin (d'Al Khârezmi, médecin arabe).
Suite de raisonnements ou d'opérations qui fournit la solution de certains problèmes.
- Objectifs
Un algorithme sert à transmettre un savoir faire.
Il décrit les étapes à suivre pour réaliser un travail.
Il permet d'expliciter clairement les idées de solution d'un problème indépendamment d'un langage de programmation.
L'utilisateur d'un algorithme n'aura qu'à suivre toutes les instructions, dans l'ordre pour arriver au résultat que doit donner l'algorithme.
Algorithme
- Le "langage algorithmique" que nous utilisons est un compromis entre un langage naturel et un langage de programmation.
- Nous présentons les algorithmes comme une suite d'instructions dans l'ordre des traitements. Ils sont toujours accompagnés d'un lexique qui indique, pour chaque variable, son type et son rôle.
- Nous manipulerons les types couramment rencontrés dans les langages de programmation : entier, réel, booléen, caractère, chaîne, tableau et type composite.
- Un algorithme doit être lisible et compréhensible par plusieurs personnes.
- Il doit donc suivre des règles. Il est composé d'une entête et d'un corps.
- L'entête comprend :
- Nom : le nom de l'algorithme
- Rôle : ce que fait l'algorithme
- Données : les données fournies à l'algorithme
- Résultat : ce que l'on obtient à la fin du traitement
- Principe : le principe utilisé dans l'algorithme
- Le corps :
- il est délimité par les mots clés début et fin.
- il se termine par un lexique, décrivant les variables utilisées
Formalisme
- Par convention, tous les identifiants de variables seront notés en minuscule et auront un nom mnémonique
- Il en va de même pour les fonctions, dont l'identifiant doit être le plus explicite sur son rôle. Ce dernier peut être une contraction de plusieurs mots, par conséquent pour rendre la lecture plus facile, la première lettre de chaque mot est mis en majuscule (exemple : CalculerAireRectangle).
Formalisme
- Exemple d'algorithme :
Nom : AddDeuxEntiers.
Rôle : additionner deux entier et mémoriser le résultat
Données : les valeurs à additionner.
Résultat : la somme des deux valeurs.
Principe : Additionner deux entiers a et b et mettre le résultat dans
c.
début
c ← a + b
fin
Lexique :
a : entier
b : entier
c : entier
Les variables
- Une variable est une entité qui contient une information, elle possède :
- un nom, on parle d’identifiant
- une valeur
- un type qui caractérise l’ensemble des valeurs que peut prendre la variable
- L’ensemble des variables est stocké dans la mémoire de l’ordinateur
Les variables
- Type de variable
- entier pour manipuler des entiers
- réel pour manipuler des nombres réels
- booléen pour manipuler des valeurs booléennes
- caractère pour manipuler des caractères alphabétiques et numériques
- chaîne pour manipuler des chaînes de caractères permettant de représenter des mots ou des phrases.
Les variables
- A un type donné, correspond un ensemble d'opérations définies pour ce type.
- Une variable est l'association d'un nom avec un type, permettant de mémoriser une valeur de ce type.
Opérateur, opérande et expression
- Un opérateur est un symbole d’opération qui permet d’agir sur des variables ou de faire des “calculs”
- Une opérande est une entité (variable, constante ou expression) utilisée par un opérateur
- Une expression est une combinaison d’opérateur(s) et d’opérande(s), elle est évaluée durant l’exécution de l’algorithme, et possède une valeur (son interprétation) et un type
Opérateur, opérande et expression
Exemple dans a + b :
a est l’opérande gauche
+ est l’opérateur
b est l’opérande droite
a + b est appelé une expression
Si par exemple a vaut 2 et b 3, l’expression a + b vaut 5
Si par exemple a et b sont des entiers, l’expression a + b est un entier
Les opérateurs
- Un opérateur peut être Unaire ou binaire :
- Unaire s’il n’admet qu’une seule opérande, par exemple l’opérateur non
- Binaire s’il admet deux opérandes, par exemple l’opérateur +
- Un opérateur est associé à un type de donnée et ne peut être utilisé qu’avec des variables, des constantes, ou des expressions de ce type
- Par exemple l’opérateur + ne peut être utilisé qu’avec les types arithmétiques (naturel, entier et réel) ou (exclusif) le type chaîne de caractères
Les opérateurs
- On ne peut pas additionner un entier et un caractère
- Toutefois exceptionnellement dans certains cas on accepte d’utiliser un opérateur avec deux opérandes de types différents, c’est par exemple le cas avec les types arithmétiques (2 + 3.5)
- La signification d’un opérateur peut changer en fonction du type des opérandes
- l’opérateur + avec des entiers aura pour sens l’addition, 2+3 vaut 5
- avec des chaînes de caractères il aura pour sens la concaténation "bonjour" + " tout le monde" vaut "bonjour tout le monde"
Les opérateurs booléens
- Pour les booléens nous avons les opérateurs non, et, ou, Exclusif
- Non
- Et
Les opérateurs booléens
- Ou
- Ou exclusif
Les opérateurs booléens
- Rappels sur la logique booléenne...
Valeurs possibles : Vrai ou Faux
- Associativité des opérateurs et et ou a et (b et c) = (a et b) et c
- Commutativité des opérateurs et et ou
a et b = b et a
a ou b = b ou a
- Distributivité des opérateurs et et ou
a ou (b et c) = (a ou b) et (a ou c)
a et (b ou c) = (a et b) ou (a et c)
- Involution (homographie réciproque) (homos semblable et graphein écrire)
non non a = a
- Loi de Morgan
non (a ou b) = non a et non b
non (a et b) = non a ou non b
Les opérateurs booléens
Les opérateurs sur les numériques
- On retrouve tout naturellemment +, -, *, /
- Avec en plus pour les entiers div et mod, qui permettent respectivement de calculer une division entière et le reste de cette division, par exemple :
11 div 2 vaut 5
11 mod 2 vaut 1
Les opérateurs sur les numériques
- L’opérateur d’égalité :
C’est l’opérateur que l’on retrouve chez tous les types simples qui permet de savoir si les deux opérandes sont égales
Il est représenté par le caractère =
Le résultat d'une expression contenant cet opérateur est un booléen
- On a aussi l’opérateur d’inégalité : ≠
- Et pour les types possédant un ordre les opérateurs de comparaison
<, ≤, >, ≥
Priorités des opérateurs
- Tout comme en arithmétique les opérateurs ont des priorités
Par exemple * et / sont prioritaires sur + et -
Pour les booléens, la priorité des opérateurs est non, et, ouExclusif et ou
- Pour clarifier les choses (ou pour dans certains cas supprimer toutes ambiguïtés) on peut utiliser des parenthèses
Manipulation de variables
- On ne peut faire que deux choses avec une variable :
Cela s’effectue simplement en nommant la variable
Cela s’effectue en utilisant l’opérateur d’affectation représenter par le symbole ←
La syntaxe de cet opérateur est :
identifiant de la variable ← expression
Manipulation de variables
- Par exemple l’expression c ← a + b se comprend de la façon suivante :
On prend la valeur contenue dans la variable a
On prend la valeur contenue dans la variable b
On additionne ces deux valeurs
On met ce résultat dans la variable c
- Si c avait auparavant une valeur, cette dernière est perdue !
Les entrées / sorties
- Un algorithme peut avoir des interactions avec l’utilisateur
- Il peut afficher un résultat (du texte ou le contenu d’une variable)
- demander à l’utilisateur de saisir une information afin de la stocker dans une variable
- En tant qu’informaticien on raisonne en se mettant “à la place de la machine”, donc :
Les entrées / sorties
- Instruction d'écriture
L'instruction de restitution de résultats sur le périphérique de
sortie (en général l'écran) est :
écrire(liste d'expressions)
Cette instruction réalise simplement l'affichage des valeurs des expressions décrites dans la liste.
Ces instructions peuvent être simplement des variables ayant des valeurs ou même des nombres ou des commentaires écrits sous forme de chaînes de caractères.
- Exemple d'utilisation : écrire(x, y+2, "bonjour") 23
Les entrées / sorties
- Instructions de lecture
L'instruction de prise de données sur le périphérique d'entrée (en général le clavier) est :
variable
L'exécution de cette instruction consiste à affecter une valeur à la variable en prenant cette valeur sur le périphérique d'entrée.
Avant l'exécution de cette instruction, la variable avait ou n'avait pas de valeur. Après, elle a la valeur prise sur le périphérique d'entrée.
Les entrées / sorties
- Exemple
On désire écrire un algorithme qui lit sur l'entrée standard une valeur représentant une somme d'argent et qui calcule et affiche le nombre de billets de 100 Euros, 50 Euros et 10 Euros, et de pièces de 2 Euros et 1 Euro qu'elle représente.
Nom : DécompSomme.
Rôle : Décomposition d'une somme
Données : la somme à décomposée.
Résultat : les nombres de billets et de pièces.
Principe : on commence par lire sur l'entrée standard l'entier qui représente la somme d'argent et affecte la valeur à une variable somme.
Pour obtenir la décomposition en nombre de billets et de pièces de la somme d'argent, on procède par divisions successives en conservant chaque fois le reste.
Les entrées / sorties
début
somme
billet100
reste100
billet50
reste50
billet10
reste10
piece2
reste2
piece1
écrire (billet100, billet50, billet10, piece2, piece1)
fin
- Lexique
- somme : entier, la somme d'argent à décomposer
- billet100 : entier, le nombre de billets de 100 Euros
- billet50 : entier, le nombre de billets de 50 Euros
- billet10 : entier, le nombre de billets de 10 Euros
- piece2 : entier, le nombre de pièces de 2 Euros
- piece1 : entier, le nombre de pièces de 1 Euro
- reste100 : entier, reste de la division entière de somme par 100
- reste50 : entier, reste de la division entière de reste100 par 50
- reste10 : entier, reste de la division entière de reste50 par 10
- reste2 : entier, reste de la division entière de reste10 par 2
Les entrées / sorties
Instruction conditionnelle
- L’instruction si alors sinon permet de conditionner l’exécution d’un algorithme à la valeur d’une expression booléenne.
Syntaxe :
si expression booléenne alors
suite d’instructions exécutées si l’expression est vrai
sinon
suite d’instructions exécutées si l’expression est
fausse
finsi
Instruction conditionnelle
- La deuxième partie de l’instruction est optionnelle, on peut
avoir la syntaxe suivante :
si expression booléenne alors
suite d’instructions exécutées si l’expression est vrai
finsi
Instruction conditionnelle
- Exemple
Nom : ValeurAbs
Rôle : Calcule la valeur absolue d’un entier
Données : La valeur à calculer
Résultat : La valeur Absolue
Principe : Si valeur < 0, on la multiplie par -1
début
si valeur ≥ 0 alors
valeurabsolue ← valeur
sinon
valeurabsolue ← valeur * -1
finsi
fin
Lexique
- valeur : entier, la valeur à tester
- valeurabsolue : la valeur absolue
31
L'instruction cas
- Lorsque l’on doit comparer une même variable avec plusieurs valeurs, comme par exemple :
si a=1 alors
faire une chose
sinon
si a=2 alors
faire une autre chose
sinon
si a=4 alors
faire une autre chose
sinon
. . .
finsi
finsi
finsi
- On peut remplacer cette suite de si par l’instruction cas
32
L'instruction cas
- Sa syntaxe est :
cas où v vaut
v1 : action1
v2 : action2
. . .
vn : actionn
autre : action autre
fincas
v1,. . . ,vn sont des constantes de type scalaire (entier, naturel,
enuméré, ou caractère)
action i est exécutée si v = vi (on quitte ensuite l’instruction cas)
action autre est exécutée si quelque soit i, v ≠ vi
u Il arrive souvent dans un algorithme qu'une même action soit répétée plusieurs fois, avec éventuellement quelques variantes. Il est alors fastidieux d'écrire un algorithme qui contient de nombreuses fois la même instruction. De plus, ce nombre peut dépendre du déroulement de l'algorithme. Il est alors impossible de savoir à l'avance combien de fois la même instruction doit être décrite. Pour gérer ces cas, on fait appel à des instructions en boucle qui ont pour effet de répéter plusieurs fois une même instruction. Deux formes existent : la première, si le nombre de répétitions est connu avant l'exécution de l'instruction de répétition, la seconde s'il n'est pas connu. L'exécution de la liste des instructions se nomme itération.
Répétitions inconditionnelles
- Il est fréquent que le nombre de répétitions soit connu à l'avance, et que l'on ait besoin d'utiliser le numéro de l'itération afin d'effectuer des calculs ou des tests. Le mécanisme permettant cela est la boucle Pour.
- Forme de la boucle Pour :
Pour variable de valeur initiale à valeur finale faire
liste d'instructions
fpour
Répétitions inconditionnelles
- La variable dont on donne le nom va prendre successivement toutes les valeurs entières entre valeur initiale et valeur finale. Pour chaque valeur prise par la variable, la liste des instructions est exécutée.
- La valeur utilisée pour énumérer les itérations est appelée valeur d'itération, indice d'itération ou compteur.
L'incrémentation par 1 de la variable est implicite.
Répétitions inconditionnelles
- Autre forme de la boucle Pour :
Pour variable décroissante de valeur initiale à valeur finale
faire
liste d'instructions
fpour
La variable d'itération est décrémentée de 1 après chaque itération.
Les répétitions conditionnelles
- L'utilisation d'une "boucle pour" nécessite de connaître à l'avance le nombre d'itérations désiré, c'est-à-dire la valeur finale du compteur. Dans beaucoup de cas, on souhaite répéter une instruction tant qu'une certaine condition est remplie, alors qu'il est à priori impossible de savoir à l'avance au bout de combien d'itérations cette condition cessera d'être satisfaite. Dans ce cas, on a deux possibilités :
- la boucle Tant que
- la boucle Répéter jusqu'à
- Syntaxe de la boucle Tant que :
tant que condition faire
liste d'instructions
ftant
Les répétitions conditionnelles
- Cette instruction a une condition de poursuite dont la valeur est de type booléen et une liste d'instructions qui est répétée si la valeur de la condition de poursuite est vraie : la liste d'instructions est répétée autant de fois que la condition de poursuite a la valeur vraie. Le déroulement pas à pas de cette instruction équivaut à :
si condition
alors liste d'instructions
si condition
alors liste d'instructions
si condition
alors liste d'instructions
...
Les répétitions conditionnelles
- Etant donné que la condition est évaluée avant l'exécution des instructions à répéter, il est possible que celles-ci ne soient jamais exécutées.
- Il faut que la liste des instructions ait une incidence sur la condition afin qu'elle puisse être évaluée à faux et que la boucle se termine.
- Il faut toujours s'assurer que la condition devient fausse au bout d'un temps fini.
- Exemple
Un utilisateur peut construire des rectangles de taille quelconque, à condition que les largeurs qu'il saisit soient supérieures à 1 pixel.
Les répétitions conditionnelles
Nom : saisirLargeurRectangle
Rôle : Vérification validité largeur saisie
Données : La largeur
Résultat :
Principe : Tant que la largeur est < 1, on demande de resaisir la largeur
début
écrire ("indiquez la largeur du rectangle :")
largeur
tant que largeur < 1 faire
écrire ("erreur : indiquez une valeur strictement positive")
écrire ("indiquez la largeur du rectangle :")
largeur
ftant
fin
Lexique
- largeur : entier, largeur courante saisie
Les répétitions conditionnelles
- Syntaxe de la boucle Répéter jusqu'à :
Répéter
liste d'instructions
jusqu'à condition
La séquence d'instructions est exécutée au moins une fois et jusqu'à ce que l'expression soit vraie. Dès que la condition est vrai, la répétitivité s'arrête.
Les répétitions conditionnelles
Nom : saisirLargeurRectangle
Rôle : Vérification validité largeur saisie
Données : La largeur
Résultat :
Principe : Tant que la largeur est < 1, on demande de resaisir la largeur
début
Répéter
écrire ("indiquez la largeur du rectangle :")
largeur
si largeur < 1 alors
écrire ("erreur : indiquez une valeur strictement positive")
fin si
jusqu'à largeur >= 1
fin
Lexique
- largeur : entier, largeur courante saisie
Les répétitions conditionnelles
- Différences entre les boucles Tant que et Répéter jusqu'à :
- la séquence d'instructions est exécuter au moins une fois dans la boucle Répéter jusqu'à, alors qu'elle peut ne pas être exécuter dans le cas du Tant que.
- la séquence d'instructions est exécuter si la condition est vrai pour le Tant que et si la condition est fausse pour le Répéter jusqu'à.
- Dans les deux cas, la séquence d'instructions doit nécessairement faire évoluer la condition, faute de quoi on obtient une boucle infinie.
Les tableaux
- Lorsque les données sont nombreuses et de même type, afin d'éviter de multiplier le nombre des variables, on les regroupe dans un tableau
- Le type d'un tableau précise le type (commun) de tous les éléments.
- Syntaxe :
tableau type_des_éléments[borne_inf ... borne_sup]
- En général, nous choisirons toujours la valeur 0 pour la borne inférieure dans le but de faciliter la traduction de l'algorithme vers les autres langages (C, Java, ...). Pour un tableau de 10 entiers, on aura :
tab : tableau entier[0..9]
…
Les tableaux
- Les instructions de lecture, écriture et affectation s'appliquent aux tableaux comme aux variables.
x ← Tab[0]
La variable x prend la valeur du premier élément du tableau, c'est à dire : 45
Tab[6] ← 43
Cette instruction a modifiée le contenu du tableau
Les tableaux
- Parcours complet d'un tableau
La plupart des algorithmes basés sur les tableaux utilisent des itérations permettant de faire un parcours complet ou partiel des différents éléments du tableau. De tels algorithmes établissent le résultat recherché par récurrence en fonction des éléments successivement rencontrés.
Les répétitions inconditionnelles sont le moyen le plus simple de parcourir complètement un tableau.
Les tableaux
Dans l'exemple suivant, le programme initialise un à un tous
les éléments d'un tableau de n éléments :
InitTableau
début
pour i de 0 à n-1 faire
tab[i] ← 0
fpour
fin
Lexique :
- i : entier, indice d'itération
- n : entier, taille du tableau
- tab : tableau entier[0..n-1]
Les tableaux
- Les tableaux à deux dimensions ou matrices
Lorsque les données sont nombreuses et de même nature, mais dépendent de deux critères différents, elles sont rangées dans un tableau à deux entrées.
Ce tableau a 3 lignes et 7 colonnes. Les éléments du tableau sont repérés par leur numéro de ligne et leur numéro de colonne.
Tab[1, 4] = 38
0 1 2 3 4 5 6
0 12 28 44 2 76 77 32
1 23 36 51 11 38 54 25
2 43 21 55 67 83 41 69
Les tableaux
- La variable T[L, C] s'appelle l'élément d'indice L et C du tableau T.
Tableau T à 3 lignes et 5 colonnes.
- Les tableaux peuvent avoir n dimensions.
T[0, 0] T[0, 1] T[0, 2] T[0, 3] T[0, 4]
T[1, 0] T[1, 1] T[1, 2] T[1, 3] T[1, 4]
T[2, 0] T[2, 1] T[2, 2] T[2, 3] T[2, 4]
Les procédures et les fonctions
- La méthodologie de base de l’informatique est :
Retarder le plus longtemps possible l’instant du codage
"...diviser chacune des difficultés que j’examinerai en autant de parties qu’il se pourrait et qu’il serait requis pour les mieux résoudre." Descartes
Résoudre le problème par combinaison d’abstractions
Les procédures et les fonctions
- Par exemple, résoudre le problème suivant :
Ecrire un programme qui affiche en ordre croissant les notes d’une promotion suivies de la note la plus faible, de la note la plus élevée et de la moyenne, revient à résoudre les problèmes suivants :
- Remplir un tableau de naturels avec des notes saisies par l’utilisateur
- Afficher un tableau de naturels
- Trier un tableau de naturel en ordre croissant
- Trouver le plus petit naturel d’un tableau
- Trouver le plus grand naturel d’un tableau
- Calculer la moyenne d’un tableau de naturels
Les procédures et les fonctions
Chacun de ces sous-problèmes devient un nouveau problème à résoudre.
Si on considère que l’on sait résoudre ces sousproblèmes, alors on sait “quasiment” résoudre le problème initial.
Donc écrire un programme qui résout un problème revient toujours à écrire des sous-programmes qui résolvent des sous parties du problème initial.
En algorithmique il existe deux types de sousprogrammes :
- Les fonctions
- Les procédures
Les fonctions récursives
- Une fonction récursive est une fonction qui pour fournir un résultat, s’appelle elle-même un certain nombre de fois.
- Exemple : la formule de calcul de la factorielle d’un nombre n s’écrit :
n ! = 1 x 2 x 3 x … x n
Ce qui peut se programmer avec une boucle Pour.
Les fonctions récursives
Une autre manière de voir les choses, serait de dire que :
n ! = n x (n-1) !
D’où, la factorielle d’un nombre, c’est ce nombre multiplié par la factorielle du nombre précédent.
- Pour programmer cela, il faut une fonction Facto, chargée de calculer la factorielle. Cette fonction effectue la multiplication du nombre passé en argument par la factorielle du nombre précédent.
Et cette factorielle du nombre précédent va bien entendu être elle-même calculée par la fonction Fact.
Les fonctions récursives
- Pour terminer, il nous manque la condition d'arrêt de ces auto-appels de la fonction Facto.
Dans le cas d'un calcul de factorielle, on s’arrête quand on arrive au nombre 1, pour lequel la factorielle est par définition 1.
Fonction Facto (n : Entier)
Début
Si n = 1 alors
Renvoyer 1
Sinon
Renvoyer Facto(n - 1) * n
Finsi
Fin
Les fonctions récursives
- Le processus récursif remplace en quelque sorte la boucle, c’est-à-dire un processus itératif.
- Il est à noter que l'on traite le problème à l’envers : on part du nombre, et on remonte à rebours jusqu’à 1, pour pouvoir calculer la factorielle.
- Cet effet de rebours est caractéristique de la programmation récursive.
Les fonctions récursives
- Pour conclure sur la récursivité, trois remarques fondamentales.
- la programmation récursive, pour traiter certains problèmes, peut être très économique, elle permet de faire les choses correctement, en très peu de lignes de programmation.
- en revanche, elle est très dispendieuse de ressources machine. Car il faut créer autant de variable temporaires que de " tours " de fonction en attente.
- toute fonction récursives peut également être formulée en termes itératifs ! Donc, si elles facilitent la vie du programmeur, elle ne sont pas indispensable.
Les algorithmes de tri
- Les algorithmes de tri, sont utilisés principalement pour les tableaux et les listes, ils peuvent aller du plus simple au plus compliquer.
- Le tri à bulle
C’est un des algorithmes le plus connu. Bien qu’il soit rarement efficace en terme de temps de calcul, il est néanmoins correcte.
Le principe consiste à balayer tout le tableau, en comparant les éléments adjacents et en les échangeant s’ils ne sont pas dans le bon ordre.
Les algorithmes de tri
Un seul passage ne déplacera un élément donné que d’une position, mais en répétant le processus jusqu’à ce que plus aucun échange ne soit nécessaire, le tri sera effectué.
Ce tri va nécessiter un grand nombre de déplacements d’éléments, il est donc inutilisable dans les cas où ces déplacements sont coûteux en temps.
Il peut par contre être intéressant quand le tableau initial est pré-trié, les éléments n’étant pas disposés trop loin de leur position finale, par exemple lors d’un classement alphabétique, où les éléments sont déjà triés par leur première lettre.
