Mots-cles :
•  Algorithme
•  Début
•  Fin

Instructions :
•  Afficher qui prend un paramètre (ou argument) noté entre parenthèses

Constante litérales (ici du texte, une «chaîne de caractère») :
•  "bonjour le monde !"

• On affiche un calcul, mais on n'a rien calculé

• On ne se rappelle rien d'une ligne à l'autre
• Comment retenir le résultat de l'opération ?

Solution : les variables

• En certains langages, il faut toujours déclarer les variables, ainsi que leur type
Mnémonique : comme les ingrédients d'une recette
• En PHP, on ne déclare pas ni les variables, ni leur type
• En JavaScript, on déclare les variables, mas pas leur type

• Valeurs nécessaires dès le début d'un algorithme ; ces entrées : Entrée : type nom_de_variable_1, type nom_de_variable_2,...
• Déclaration dans le corps de l'algorithme, variable temporaire (locale)
  type nom_de_variable_3,...
• Valeur que l'algorithme calcule et fournit à la fin de son exécution : ces sorties : Sortie : type nom_de_variable_1, type nom_de_variable_2,...
  • Si l'algorithme ne retourne qu'une seule valeur on peut ne déclarer que son type en Sortie et utiliser l'instruction retourner (exemples plus loin...)
• Lorsque une variable est créée, elle n'a pas aucune valeur (« undefined »)

• Pour affecter une valeur à une variable, on utilise l'opérateur « ← »
• Exemples pour la variable a déclarée comme entier :
  • a ← 2;
    la variable a reçoit la valeur 2
  • b ← a;
    la variable b reçoit la valeur de la variable a, c'est à dire 2
  • a ← a + b;
    la variable a reçoit la somme de sa propre valeur et de celle de b, donc...?
  • a ← b + a;
    la variable a reçoit la somme des valeurs de b et de sa propre... donc...??

• Ici, l'algorithme est court, et la variable c ne sert pas à grand chose. Mais dans des exemples plus longs, l'utilisation de variables dans l'algorithme s'avère nécessaire
• L'instruction retourner renvoie la valeur contenue dans la variable c, elle renvoie une seule valeur
• Si l'algorithme ne doit rien retourner ( Sortie :), si besoin est, on utilise l'instruction retourner sans argument

• Selon le type d'information à stocker, nous utiliserons le types suivants :
  • entier : pour les valeurs entières
  • réel : pour les valeurs réelles
  • car : pour un caractère unique
  • chaîne : pour un ensemble de caractères
  • booléen : pour les valeurs booléennes
• Une fois déclarée, en algorithmique, une variable ne peut pas changer de type (ce sera différent en javascript et en php)
• Les noms des types de données sont des mots réservés, ils ne doivent être utilisés comme identificateurs de variables

• Comment manipuler les variables ?
• On a déjà vu l'affectation « ← »
• On a déjà « retournée » une variable
• Ces opérations sont communes à tous les types
• pour chaque nouvelle « fonction » ou « opération », on précisera à quels types elle s'applique, ainsi que le type du résultat
• On va maintenant voir les premières opérations associées à chaque type

Opérations relatives aux entiers :

• Lorsque plusieurs opérations apparaissent dans une expression, il y a un ordre d'évaluation, suivant la priorité des opérateurs (du plus prioritaire au moins prioritaire)
  • niveau 1 : - unaire (changement signe) et parenthèses
  • niveau 2 : * ÷ % (binaire)
  • niveau 3 : +,- (binaire)
• Quand deux opérateurs sont de même priorité, le calcul se fait de gauche à droite (associativité gauche)

Opérations relatives aux réels :

• Opérations mixtes avec les entiers, résultat généralement converti en réel

Opérations relatives aux caractères :

• Ils permettent de représenter un caractère alphanumérique, ponctuation, caractères de contrôle...
• On entoure le caractère avec une paire d'apostrophes ('a') ou une paire de guillemets ("a")

Opérations relatives aux chaînes de caractères

• Comme pour les caractères, on entoure la chaîne de caractères avec une paire d'apostrophes ou une paire de guillemets 'abcdefg' ou "bonjour les amis;"
• Si le caractère apostrophe ou le caractère guillemet doit apparaître à l'intérieur de la chaîne de caractères, pour pouvoir l'insérer sans que ce soit considéré comme la fin de la chaîne de caractères, on le préfixe avec le caractère \

Opérations relatives aux booléens

• Les booléens sont des variables logiques. Valeurs possibles: vrai ou faux
• Ils permettent de représenter des états logiques
• Utilité: dans les algorithmes lors de tests, décision dans des choix
• Répondre par vrai ou faux à une question
• Une algèbre leur est consacrée : l'algèbre de Boole
• Opérateur unaire : la négation NOT
  ¬

  a	¬a
  v	f
  f	v

Opérations relatives aux booléens

• D'autres opérateurs s'expriment en fonction des 3 précédents
  Exemple : a ⇒ b ≡ ¬a ∨ b
• Le xor est aussi le « non équivalent »

Plus précisément, elles permettent

• d'exécuter des instructions si une certaine condition (Conditionnelles) et vraie (ou fausse)
• de répéter des instructions un certain nombre de fois (Boucles inconditionnelles)
• de répéter des instructions tant qu'une condition est vérifiée (Boucles conditionnelles)

• Si le nombre donné par un utilisateur (lireEntier()) est égal à 0 modulo 2, alors j'affiche qu'il est pair, Sinon j'affiche qu'il est impair
• Si un utilisateur n'est pas dans l'état connecté, Alors je le redirige vers la page d'accueil, Sinon je lui donne accès aux informations privées du site
• Si.... Alors.... Sinon....

Pas exactement la même chose que la gestion d'évènemments :

• Si je clique sur le bouton, Alors je change sa couleur, Sinon je ne fais rien
• Quand l'utilisateur clique sur le bouton, Alors je change la couleur du bouton

• L'algorithmique permet de considérer ces cas en utilisant les conditionnelles
  • permettant d'exprimer des conditions basées sur les opérateurs de comparaison et la logique booléenne
  • fixant un cadre syntaxique pour indiquer quelles instructions exécuter si cette même condition n'est pas remplie

• Syntaxe générale

  
  Si (condition) Alors
     Partie instructions 1
  Sinon
     Partie instructions 2
  Fsi
  				    

• La partie 'Sinon Partie instructions 2' est facultative, s'il n'y a pas d'instructions dans la Partie instructions 2
• La condition est une expression booléenne, elle peut contenir des opérations
• La condition contient toujours au moins une variable dans son expression. Sinon la condition va s'évaluer toujours de la même façon, on écrit en fait une constante booléenne.

Algorithme : conditionnelle 1
Entrée :
Sortie :
Début
   entier a
   a ← lireEntier() 
   Si (a % 2 == 0) Alors
      Afficher("la valeur de la variable a est paire")
   Sinon
      Afficher("la valeur de la variable a est impaire")
   fsi
fin
				    

Algorithme : conditionnelle 2
Entrée :
Sortie :
Début
   entier a,b
   a ← lireEntier()
   b ← lireEntier()
   Si (a >b) Alors
      Afficher("le maximum est la première valeur lue : "+a)
   Sinon
      Afficher("le maximum est la seconde valeur lue : "+b)
   fsi
fin

Algorithme : conditionnelle 3
Entrée :
Sortie :
Début
   booleen a
   a ← lireBooleen()
   Si (a) Alors
      Afficher("on est dans le vrai")
   Sinon
      Afficher("On a tout faux")
   Fsi
Fin
				    

Algorithme : conditionnelle 4
Entrée : chaine s
Sortie :
Début
   Si (s=="bonjour") Alors
      Afficher("merci")
   Fsi
Fin
				    

• Les opérateurs permettant de tester des conditions sont
  • == égalité
  • != différent (aussi écrit <>)
  • < inférieur, <= inférieur ou égal, > supérieur, >= supérieur ou égal
• Si la condition est complexe, la priorité des opérateurs (comparaisons, logiques ou arithmétiques) peut être assez subtile.
  Parenthésez vos expressions.

• n != p : évaluée à vrai si, au moment de l'évaluation, la valeur contenue dans la variable n est différente de la valeur contenue dans la variable p
• p == p + 3 : évaluée à vrai si, au moment de l'évaluation, la valeur contenue dans la variable p est égale à celle contenue dans la variable n, incrémentée par 3. BONUS : Est-ce que ça peut être vrai ?
• a == b et n != p : évaluée à vrai si, au moment de l'évaluation, la valeur contenue dans la variable a est égale à celle contenue dans la variable b et au même temps la valeur contenue dans la variable n est différente de celle contenue dans la variable p
• On peut aussi écrire (a == b) et (n!=p)
• Essayez : (a>b et n!=p) ou (a<b et n==p)

• Exercice : établissez les tables de vérité des expressions booléennes suivantes pour a et b deux variables entières ; n, p deux variables quelconques ; x,y,z trois variables booléennes :
  • (x ou y) et non (x ou z)
  • (a>b et n!=p) ou (a<b et n==p)
  • a>b et (n!=p ou a<b) et n==p
  • a>b et n!=p ou a<b et n==p
• Autre Exemple (c variable de caractère) : c < 'E' évaluée à vrai si le caractère contenue dans la variable c (de type caractère) est situé avant le 'E' dans le codage ASCII des caractères
• Remarque : les caractères sont ordonnés comme suit
  'a' < 'b' < ... < 'z' < 'A' < ... < 'Z'

Algorithme : ordre début
Entrée :
Sortie
Début

entier a, b;
a ← lireEntier();
b ← lireEntier();
Si (a < b) alors
   afficher("a plus petit que b");
Sinon  
   Si (a > b) Alors
      afficher("a plus grand que b");
   Sinon
      afficher("a et b sont égaux");
   Fsi
Fsi

• Il y a toujours autant de Si que de Fsi dans un algorithme
• Les mots-clés Si, Sinon et Fsi qui appartiennent à la même conditionnelle doivent être alignés verticalement
• Les instructions se trouvant dans les parties Alors et Sinon sont indentées par rapport aux mots-clés de la conditionnelle
• L'exécution d'une conditionnelle est séquentielle, mais seule une des deux séries d'instructions (de la partie Alors ou de la partie Sinon) est exécutée
• S'il n'y a pas de partie Sinon dans une conditionnelle, et si la condition est évaluée à faux, alors aucune instruction n'est exécutée, et on passe à la suite de l'algorithme

• Aussi appelées itérations
• Il arrive très fréquemment qu'une partie d'un algorithme doive être exécutée plusieurs fois, parfois avec quelques nuances dans l'exécution
• Exemples :
  • afficher 500 fois la chaîne de caractères "Bonjour !"
  • afficher la table de multiplication du 7
• L'algorithmique permet de considérer ces cas en utilisant les boucles

• Structure permettant d'effectuer un nombre fini d'itérations. Syntaxe

  
  Pour compteur de m à n pas de p faire
     Partie instructions
  Fpour
  					

• compteur est une variable qui aura automatiquement une nouvelle valeur à chaque itération
• m représentation la valeur de départ (d'initialisation) du compteur
• n représente la dernière valeur que doit prendre le compteur
• p représente la valeur qui sera automatiquement ajoutée à la variable compteur à la fin de chaque itération
• Exemple :

  
  Pour fois de 1 à 500 pas de 1 faire
     afficher("Bonjour !")
  Fpour
  

• Fonctionnement :
  1. Avant d'exécuter la partie instructions, le compteur est initialisé avec la valeur de m
  2. La variable compteur est comparée avec la variable n pour savoir si l'itération continue (si compteur > n on passe à l'instruction située juste après l'instruction Fpour)
  3. La partie instruction est exécutée
  4. La variable p est ajoutée à la variable compteur
  5. Retour à l'étape 2 (on boucle et on tente une nouvelle itération

• Syntaxiquement, modifier la valeur de compteur est possible, mais NOUS L'INTERDISONS FORMELLEMENT
• Si la partie pas de p est omise, alors p prend automatiquement la valeur 1
• On utilise ces boucles statiques quand le nombre d'itérations peut être déterminé numériquement avant le début de la boucle
  • de façon statique par une constante
  • de façon dynamique en se basant sur des expressions dont le résultat est de type entier

Exemples

• Afficher 500 fois le caractère « * »

  
  Algorithme
  Entrée :
  Sortie :
  Début
     Entier compteur
     Pour compteur de 1 à 500 faire                   
        Afficher("*")
     fpour
  fin
  					

• Afficher la table du 7

  
  Algorithme
  Entrée :
  Sortie :
  Début
     entier res,compteur
     Pour compteur de 1 à 10 faire
        res ← 7 * compteur					    
        Afficher("7 * "+compteur+" = "+res)
     Fpour
  Fin
  					

Exemples

• Afficher les nombres impairs de 1 à un nombre donné par l'utilisateur

  
  Algorithme
  Entrée :
  Sortie :
  Début
     entier dernier,compteur
     dernier ← lireEntier()
     Pour compteur de 1 à dernier pas de 2 faire					    
        Afficher(compteur)
     fpour                                                
  fin
  					

• Afficher les nombres impairs de 1 à un nombre donné par l'utilisateur, dans l'ordre inverse

  
  Algorithme
  Entrée :
  Sortie :
  Début
     entier dernier,compteur
     dernier ← lireEntier()
     Pour compteur de dernier à 1 pas de -2 faire					    
        Afficher(compteur)
     Fpour                                                
  Fin
  					

• Cas problématique

  
  Algorithme
  Entrée :
  Sortie :
  Début
     Entier compteur
     Pour compteur de 1 à 10 pas de -2 faire					    
        Afficher(compteur)
     Fpour                                                
  Fin
  					

  ATTENTION ! on peut rapidement faire des erreurs avec les bornes et le pas de la boucle
• Que nous manque-t-il pour parcourir notre jeu de cartes ?

• Autre forme de boucle : la décision de poursuite des itérations se fait en évaluant une condition booléenne et pas seulement en évaluant la valeur d'un entier
• Tant que ... Faire

  
  Tant que (condition) Faire
     Partie instructions
  Fintantque                                  
  					

• La condition est évaluée avant chaque itération
• Si la condition est évaluée à vrai, l'itération est exécutée
• Si la condition est évaluée à faux, l'exécution de l'algorithme reprend après le mot-clé Fintanque

Un exemple qui ressemble à la boucle inconditionnelle

• Boucle Pour

  
  Algorithme
  Entrée :
  Sortie :
  Début
     entier dernier
     dernier ← lireEntier()
     Pour compteur de 1 à 10 pas de 1 faire					    
        Afficher(compteur)
     Fpour                         
  Fin
  				    

• Boucle Tant que

  
  Algorithme
  Entrée :
  Sortie :
  Début
     entier compteur
     compteur ← 1
     Tant que (compteur<=10) Faire
        Afficher(compteur)
        compteur ← compteur + 1
     Fintantque                                         
  Fin
  					

• charAt (caractèreA...)
  

  
  Chaine s                                     
  s ← "bonjour"
  afficher(charAt(s,3))                                                          
  					

• Et longueur:

  
  Chaine s                                     
  s ← "bonjour"
  afficher(longueur(s))                                                          
  					

• Et éventuellement sousChaine :

  
  Chaine s                                     
  s ← "bonjour"
  afficher(sousChaine(s,1,3))                                                          
  					

• ATTENTION : les indices commencent à 0

On se donne une chaîne de caractères...

• Vérifier s'il y a au moins 1 caractère « e »
• Compter le nombre de caractères « e »
• Trouver l'indice du premier caractère « e »

⇒ parcours de chaîne de caractères à l'aide de boucles...

Remarques

Dans ce cas, la partie instruction est répétée indéfiniment

• Autre Syntaxe :

  
  Faire                                     
     Partie instruction
  Tant que (condition)                                                       
  					

• La partie instruction est exécutée au moins une fois

• Il y a toujours autant de « Pour » que de « fpour » dans un algorithme
• Il ya toujours autant de « Tant que » que de « Fintantque »
• La partie instructions est indentée par rapport au début et à la fin de la boucle

• On peut aussi mettre une boucle dans la partie instruction d'une boucle
• On parle alors de boucles imbriquées
• Vous l'avez déjà vu en triant vos cartes !

 entier carte1, ... carte13                                     
 Pour i de 1 a 13 Faire
    utiliser la carte i ?
 fpour                                                     
				      

• Accède-t-on bien à la variable cartei ?
• La situation est-elle gérable pour 1 000 000 de cartes ?
• La situation est-elle gérable si je ne connais pas à l'avance le nombre de cartes ?

Solution : Les tableaux

• Avantages :
  • évite la multiplication des noms de variables
  • résout des problèmes insolubles avec des variables simples
  • permet d'accéder directement à chacune des valeurs contenues dans le tableau
  • permet de ne pas connaître a priori le nombre de variables

• La notion de tableau est à inclure dans une notion plus générale de collection
• La distinction vient de la façon dont la structure de donnée est manipulée en mémoire par le langage
• D'autres structures de données existent, comme les listes chainées, doublement chainées, les arbres (binaires, de recherche, etc ...), les graphes, etc...
• Ici, on utilise pour l'instant des tableaux, car ils sont la première représentation en mémoire des collections
• De façon générale, on choisit telle ou telle structure de données en fonction de l'efficacité de certaines opérations associées à la structure

Manipulation des tableaux

• En algorithmique, il n'existe pas d'instruction pour manipuler un tableau comme un tout
• On ne peut, en particulier, affecter directement un tableau à un autre tableau
• Les tableaux doivent se voir comme un ensemble de variable que l'on manipule « une par une »
• La syntaxe d'accès à un élément d'indice i d'un tableau t est la suivante : t[i]

entier t[n]
t[0] ← 17
t[1] ← 2*3
t[2] ← t[0] + t[1]
				      

Manipulation des tableaux

• De part leur structure répétitive (répétition d'éléments), les tableaux sont souvent manipulés grâce à des boucles
• Exemple :

  
  entier t[10],i
  Pour i de 0 à 9 Faire
     t[i] ← (i+1)*(i+1)
  fpour
  				      

Manipulation des tableaux : exemples

• Compter le nombre d'entiers positifs contenus dans un tableau
• Remplir un tableau
• Vérifier si un tableau contient au moins un entier pair
• Vérifier si un tableau ne contient que des entiers pairs
• Inverser les éléments d'un tableau
• trier un tableau (nécessite des boucles imbriquées)

Elles permettent

• De découper un algorithme en « sous-algorithmes » afin de simplifier et diviser l'algorithme en entités plus petites
• Lorsque qu'un ensemble d'instructions doit être répété à plusieurs endroits dans l'algorithme, cela permet de ne l'écrire qu'une fois. Outre de limiter les erreurs dues aux recopiages, cela rend l'algorithme plus lisible
• Permet d'utiliser des fonctions écrites par d'autres programmeurs. Il ne faut pas ré-inventer la roue (sauf en algorithmique à des fins pédagogiques!)

• Les fonctions en algorithmique sont assez proches de la notion de fonctions en mathématiques
• Les fonctions doivent être définies avant d'être utilisées
• Les fonctions acceptent des paramètres formels (ou encore arguments) et renvoient un résultat
• Les fonctions sont manipulées par leur nom
• Les fonctions peuvent également être appelées sous-programme ou procédure (pour les vieux)

Appel (utilisation) de la fonction au sein d'un algorithme

Algorithme :                                                               
Entrée : chaîne s
Sortie : 
Début
   entier nbe
   nbe ←  NombreDeE(s)
   Si (nbe==0) Alors
      Afficher("Votre chaine de caractères ne contient
                 pas de e")
   Sinon
      Afficher("Il y a "+nbe+" lettres e dans votre 
                chaine de caractères")
   Fsi
Fin
				      

• La représentation du déroulement de l'exécution d'une fonction se fait comme pour un algorithme, séparément de l'algorithme qui appelle la fonction
• La liste des paramètres peut être vide
• Cependant, les parenthèses doivent toujours être présentes

• La fonction renvoie au plus un résultat
• Dans certains langages (python) une fonction peut renvoyer plusieurs résultats
• Quand on aura besoin de renvoyer plusieurs résultats, soit nous utiliserons des tableaux, soit nous utiliserons des « structures de données » (voir plus loin dans le cours)
• Toutes les fonctions sont définies au même niveau : il n'est pas possible de définir une fonction dans une autre fonction
• Le type de retour de la fonction doit être déclaré
• Pour renvoyer une valeur, on utilise le mot-clé retourner. Cette instruction provoque la sortie de la fonction (les instruction suivantes ne sont pas exécutées)

• Lors de l'appel d'une fonction, il est obligatoire de lui fournir tous les paramètres déclarés dans la définition de la fonction
• Il est possible d'ignorer la valeur retournée par la fonction
• Quand le résultat est utilisé (ce qui est la norme), il faut que la variable, ou l'expression qui reçoit la valeur de retour ait un type compatible avec le type de retour de la fonction

• L'exécution de la fonction est indépendante de l'exécution de l'algorithme qui l'appelle
• Le déroulement de son exécution se fait comme celui d'un algorithme
• Quid des variables utilisées pour appeler la fonctions ?

Algorithme :                                                               
Entrée : chaîne s
Sortie : 
Début
   entier nbe
   nbe ← 17
   nbe ←  NombreDeE(s)
   Si (nbe==0) Alors
      Afficher("Votre chaine de caractères ne contient
                 pas de e")
   Sinon
      Afficher("Il y a "+nbe+" lettres e dans votre 
                chaine de caractères")
   Fsi
Fin
				      

• Est-ce que la valeur de s change dans l'algorithme après l'exécution de la fonction ?

• La variable de l'algorithme appelant et celle de la fonction sont stockées à des emplacements mémoire différents
• La variable de l'algorithme appelant et la variable de la fonction peuvent avoir le même nom ou des noms différents
• Dans le cas d'un passage par valeur, on peut donner une simple expression, car c'est la valeur du résultat qui va être passé dans la fonction

• Passage par valeurs : types simples entiers, réels, booléens, caractères,
• Passage par référence : chaînes de caractères, tableaux

• Rien n'interdit qu'une fonction s'appelle elle-même
• Syntaxiquement c'est correct !
• Attention ! c'est dangereux !
• Une condition d'arrêt doit être mise en place afin que la fonction ne s'appelle pas elle-même indéfiniment

• Exemple : Factorielle

Fonction : FactorielleIterative(entier n)
Sortie : entier
Début
   entier f,i
   f ← 1
   Pour i de 1 à n faire
      f ← f * i
   Fpour
   retourner f
FinFonction
				      

Fonction : FactorielleRecursive(entier n)
Sortie : entier
Début
  Si (n<2) Alors
    Retourner 1
  Sinon
    Retourner FactorielleRec(n-1)*n
  Fsi	    
FinFonction
				      

Autres exemples

• Suite de Fibonacci
• Calcul de la puissance d'un nombre
• liens père-fils dans les commentaires d'un site

Conclusion :

• Parfois très utile
• Parfois très coûteux
• Nécessite de bien comprendre la condition d'arrêt
• Ensuite : structures de données récursives (semestre 2 ?)