Présentation

Présentation informelle

Considérons les étapes qui interviennent dans la résolution problème quelconque :

1. concevoir une procédure qui une à fois appliquée amènera à une solution du problème ;
2. résoudre effectivement le problème en appliquant cette méthode.

Le résultat du premier point sera nommé un algorithme. Quant au deuxième point, c'est-à-dire la mise en pratique de l'algorithme, nous l'appellerons un processus.

Ces notions sont très répandues dans la vie courante. Un algorithme peut par exemple y prendre la forme :

• d'une recette de cuisine,
• d'un mode d'emploi,
• d'une notice de montage,
• d'une partition musicale,
• d'un texte de loi,
• d'un itinéraire routier.

Dans le cas particulier de l'informatique, une étape supplémentaire vient se glisser entre la conception de l'algorithme et sa réalisation à travers un processus : l'algorithme doit être rendu compréhensible par la machine que nous allons utiliser pour résoudre effectivement le problème. Le résultat de la traduction de l'algorithme dans un langage connu de la machine est appelé un programme.

Rapide historique

C'est un mathématicien perse du 8ème siècle, Al-Khawarizmi, qui a donné son nom à la notion d'algorithme. Son besoin était de traduire un livre de mathématiques venu d'Inde pour que les résultats et les méthodes exposés dans ce livre se répandent dans le monde arabe puis en Europe. Les résultats devaient donc être compréhensibles par tout autre mathématicien et les méthodes applicables, sans ambiguïté.

En particulier, ce livre utilisait une numérotation de position, ainsi que le chiffre zéro que ce type de représentation des nombres rend nécessaire. Par ailleurs, le titre de ce livre devait être repris pour désigner une branche des mathématiques, l'algèbre.

Si l'origine du mot algorithme est très ancienne, la notion même d'algorithme l'est plus encore : on la sait présente chez les babyloniens, 1800 ans avant JC.

Une tablette assyrienne provenant de la bibliothèque d'Assurbanipal et datée de -640 expose une recette pour obtenir des pigments bleus (notons que pour avoir un algorithme satisfaisant, il faudrait préciser ici les temps de cuisson !) :

En résumé, il doit être bien clair que cette notion d'algorithme dépasse, de loin, l'informatique et les ordinateurs. Nécessite un vocabulaire partagé, des opérations de base maîtrisées par tous et de la précision.

Langage de description

Premiers éléments

Instructions de sorties

On se donne une instruction Écrire pour afficher du texte, ainsi qu'une instruction ALaLigne pour poursuivre l'affichage à la ligne suivante.

Patron d'un algorithme

Le patron général est le suivant :

Algorithme NomAlgorithme
Début
  ... actions
Fin

La première ligne, appelée profil donne essentiellement le nom de l'algorithme. On trouve ensuite un délimiteur de début puis les différentes actions composant l'algorithme et enfin un délimiteur de fin.

Ainsi, l'algorithme suivant est valide :

Algorithme Bonjour
Début
  Écrire('Hello world !!!')
  ALaLigne
Fin

Évoquer l'appel à un tel algorithme dans un algorithme principal.

Variables et types

Une variable est constitué d'un nom et d'un contenu, ce contenu étant d'un certain type. Les types différents : booléen, caractère, chaîne de caractères, nombre entier, nombre réel, etc.

Pour la clarté de l'algorithme, il peut être intéressant de déclarer les variables utilisées et leur type au tout début. Quand l'algorithme sera traduit en programme cette déclaration aura d'autres avantages : réservation de l'espace mémoire correspondant au type, possibilité de vérifier le programme du point de vue de la cohérence des types, etc.

Affectation souvent symbolisée par une flèche vers la gauche (←).

Expressions, évaluation, etc.

Nouveau patron d'un algorithme

Nous allons maintenant préciser les variables utilisées par l'algorithme et leurs types, en distinguant les paramètres externes et les variables internes à l'algorithme. Ainsi, le patron d'un algorithme devient

Algorithme NomAlgorithme (paramètres...)
Variable ...
Début
  ... actions
Fin

Instructions conditionnelles et itératives

Le Si Alors Sinon va permettre de conditionner l'exécution de certaines instructions.

Le rôle des boucles est d'itérer un bloc d'instructions, soit un nombre précis de fois, soit relativement à une condition.

Si Alors Sinon

Algorithme QueFaireCeSoir
Début
  Si Pluie
  Alors
    MangerPlateauTélé
    SeCoucherTot
  Sinon
    MangerAuRestaurant
    AllerAuCinema
  Fin si
Fin

Boucle Fois

  Fois 3 faire
    Avancer
  Fin Fois

Boucle Tant que et Répéter

Algorithme JusquAuMur
Début
  Tant que Non(DevantMur) faire
    Avancer
  Fin tant que
Fin

Algorithme JusquAuMurVersionRépéter
Début
  Répéter
    Avancer
  jusqu'à DevantMur
Fin

À noter que, contrairement à la boucle tant que, on passe toujours au moins une fois dans une boucle répéter. Ainsi, dans l'exemple ci-dessus, on avancera forcément d'une case... il conviendrait donc de tester si l'on n'est pas devant un mur avant d'utiliser cet algorithme.

Boucle Pour

Dotés des variables, nous pouvons maintenant écrire un nouveau type de boucle, la boucle pour :

Algorithme CompteJusqueCent
Variable i : entier
Début
  Pour i ← 1 à 100 faire
    Écrire(i)
    ALaLigne
  Fin Pour
Fin

Lorsque l'on sait exactement combien de fois on doit itérer un traitement, c'est l'utilisation de cette boucle qui doit être privilégiée.

Par exemple,

Algorithme DessineEtoiles (n : entier)
Variable i : entier
Début
  Pour i ← 1 à n faire
    Écrire('*')
  Fin pour
Fin

Comparaisons des boucles pour un problème simple

On reprend l'exemple précédent de la boucle pour

Algorithme CompteJusqueCentVersionPour
Variable i : entier
Début
  Pour i ← 1 à 100 faire
    Écrire(i)
    ALaLigne
  Fin Pour
Fin

et on écrit des algorithmes qui produisent la même sortie (les nombres de 1 à 100) mais en utilisant les différentes boucles.

D'abord, avec la boucle tant que (il faut initialiser i avant la boucle, et l'augmenter de 1 à chaque passage) :

Algorithme CompteJusqueCentVersionTQ
Variable i : entier
Début
  i ← 1
  Tant que (i ≤ 100) faire
    Écrire(i)
    ALaLigne
    i ← i+1
  Fin tant que
Fin

De même avec la boucle répéter (noter que la condition d'arrêt est ici la négation de la condition du tant que):

Algorithme CompteJusqueCentVersionRepeter
Variable i : entier
Début
  i ← 1
  Répéter
    Écrire(i)
    ALaLigne
    i ← i+1
  Jusqu'à (i > 100)
Fin

Enfin, en utilisant la récursivité, on obtient :

Algorithme CompteJusqueCentRecursif (n : entier)
Début
  Si (n ≤ 100)
  Alors
    Écrire(n)
    ALaLigne
    CompteJusqueCentRecursif(n+1)
  Fin si
Fin

Algorithmes pour les figures géométriques

Types abstraits

Formalisme

opérations et signature

constructeurs, accesseurs, modifieurs, testeurs, copieurs, afficheurs

pré-conditions et axiomes

opérations complexes

Le type abstrait « Entier »

Type abstrait « Entier »
Utilise « Booléen »

Constructeurs
zero : ∅ → Entier
succ : Entier → Entier
prec : Entier → Entier
pré-condition pour prec(n) : estnul(n) est faux

Testeur
estnul : Entier → Booléen

Afficheur
afficheentier : Entier → ∅

Axiomes
estnul(zero())  = vrai
estnul(succ(n)) = faux
succ(prec(n))   = n
prec(succ(n))   = n

Avec ce type abstrait, nous sommes capables de définir l'addition et la multiplication, indépendamment de l'implémentation de ce type.

Algorithme plus (n,m : entiers)
Début
    Tant que non(est_nul(n))
        m ← succ(m)
        n ← prec(n)
    Fin TQ
    Retourner m


Algorithme fois (n,m : entiers)
Début
    s ← zero()
    Tant que non(est_nul(n))
        s ← plus(s,m)
        n ← prec(n)
    Fin TQ
    Retourner s
Fin

Le type abstrait « Pile »

Type abstrait « Pile »
Utilise « Booléen » et « Élément »

Constructeurs
pilevide : ∅ → Pile
ajoute : Élément × Pile → Pile

Accesseur
sommet : Pile → Élément
pré-condition pour sommet(p) : estvide(p) est faux

Modifieur
depile : Pile → Pile
pré-condition pour depile(p) : estvide(p) est faux

Testeur
estvide : Pile → Booléen

Afficheur
affichepile : Pile → ∅

Copieur
copiepile : Pile → Pile

Axiomes
estvide(pilevide())  = vrai
estvide(ajoute(e,p)) = faux
sommet(ajoute(e,p))  = e
depile(ajoute(e,p))  = p

Un algorithme possible basé sur ce type :

Algorithme inversepile (p : Pile)
Début
    q ← copiepile(p)
    r ← pilevide()
    Tant que non(estvide(q))
        ajoute(sommet(q),r)
        depile(q)
    Fin TQ
    Retourner r
Fin

Type abstrait : le cas des types produits

Forme générale de ces types...

Sur un exemple : le type abstrait « Étudiant ».

Type abstrait « Étudiant »
Utilise « Entier » et « Texte »

Constructeurs
créer_étudiant : Texte × Texte × Texte → Étudiant

Accesseurs
nom_étudiant            : Étudiant         → Texte
prénom_étudiant         : Étudiant         → Texte
naissance_étudiant      : Étudiant         → Texte
noteinfo_étudiant       : Étudiant         → Entier
notemath_étudiant       : Étudiant         → Entier
notediscipline_étudiant : Texte × Étudiant → Entier

Modifieur
modifier_noteinfo : Étudiant × Entier → Étudiant
modifier_notemath : Étudiant × Entier → Étudiant

Afficheur
afficher_étudiant : Étudiant → ∅

Axiomes
nom_étudiant(créer_étudiant(n,p,d))        = n
prénom_étudiant(créer_étudiant(n,p,d))     = p
naissance_étudiant(créer_étudiant(n,p,d))  = d
noteinfo_étudiant(modifier_noteinfo(e,n))  = n
notemath_étudiant(modifier_notemath(e,n))  = n

notediscipline_étudiant('info',modifier_noteinfo(e,n)) = n
notediscipline_étudiant('math',modifier_notemath(e,n)) = n

Le type abstrait « Tableau »

Première version.

Type abstrait « Tableau »
Utilise « Entier » et « Élément »

Constructeurs
créer_tableau : Entier → Tableau

Accesseurs
contenu : Tableau × Entier → Élément
taille  : Tableau → Entier
pré-condition pour contenu(t,n) : 1 ≤ n ≤ taille(t)

Modifieur
fixecase :  Tableau × Entier × Élément → Tableau
pré-condition pour fixecase(t,n,e) : 1 ≤ n ≤ taille(t)

Afficheur
affichetableau : Tableau → ∅

Copieur
copietableau : Tableau → Tableau

Axiomes
taille(créer_tableau(n))   = n
contenu(fixecase(t,n,e),n) = e

Seconde version avec la notation crochets plus proche des langages de programmation.

Type abstrait « Tableau »
Utilise « Entier » et « Élément »

Constructeurs
créer_tableau : Entier → Tableau

Accesseurs
_[_] : Tableau × Entier → Élément
taille  : Tableau → Entier
pré-condition pour contenu(t,n) : 1 ≤ n ≤ taille(t)

Modifieur
_[_] = _ :  Tableau × Entier × Élément → Tableau
pré-condition pour t[n]=e : 1 ≤ n ≤ taille(t)

Afficheur
affichetableau : Tableau → ∅

Copieur
copietableau : Tableau → Tableau

Axiomes
taille(créer_tableau(n))   = n
contenu(fixecase(t,n,e),n) = e

Algorithmes sur les tableaux

Algorithmes de base

Parcours d'un tableau

Algorithme AfficheTableau (t : tableau)
{ Affiche tous les éléments d'un tableau }
Variable i : entier
Début
  Pour i ← 1 à taille(t) faire
    Écrire(t[i])
  Fin Pour
Fin

Recherche des plus petit et grand éléments d'un tableau

Algorithme Maximum (t : tableau d'entiers)
{ Recherche l'élément le plus grand d'un tableau de taille n non nulle }
Variables i, max : entier
Début
  max ← t[1]
  Pour i ← 2 à taille(t) faire
    Si (t[i] > max)
    Alors max ← t[i]
    Fin si
  Fin Pour
  Écrire(max)
Fin

et l'algorithme affiche la valeur 5

Pour mesurer la complexité d'un algorithme, il faut tout d'abord désigner une ou plusieurs opérations élémentaires utilisées par l'algorithme. Dans le cas de la recherche du maximum d'un tableau, ces opérations pourront être :

• la comparaison entre le maximum connu et un élément du tableau (t[i] > max) ;
• l'affectation d'une valeur à la variable contenant le maximum (max ← t[1] et max ← t[i]).

Mesurer la complexité de l'algorithme revient alors à compter le nombre de fois où ces opérations sont effectuées par l'algorithme.

Ainsi, pour un tableau de taille n, l'algorithme Maximum effectue n-1 comparaisons.

Naturellement, nous le voyons avec l'algorithme Maximum et le nombre d'affectations qu'il effectue, la complexité peut varier avec les données fournies en entrée. Nous allons donc distinguer trois notions de complexité : au mieux, au pire et en moyenne.

• Le cas le plus favorable pour notre algorithme Maximum est le cas où le maximum du tableau se trouve en première position : la variable max prend cette valeur au début et n'en change plus ensuite. La complexité au mieux vaut donc 1.
• Au pire, le tableau est trié en ordre croissant et la variable max doit changer de valeur avec chaque case. Le complexité au pire vont donc n.
• La complexité en moyenne est plus difficile à calculer. Il ne s'agit pas comme on pourrait le penser de la moyenne des complexités au mieux et au pire. Nous pouvons observer que si nous choisissons un tableau au hasard, il est beaucoup plus probable d'avoir un tableau dont le maximum est en première place (cas le mieux) qu'un tableau complètement trié (cas le pire). Par conséquent, la complexité en moyenne est plus proche de 1 que de n et, en effet, il est possible de montrer que cette complexité en moyenne vaut log(n).

En résumé, nous avons pour la complexité de l'algorithme Maximum en nombre d'affectations sur un tableau de taille n :

(variation) On cherche la position du minimum dans un tableau et entre deux cases repérées par leurs numéros d (début) et f (fin):

Algorithme PositionMinimum (t : tableau d'entiers ; d,f : entier)
Variable i,imin : entier
Début
  imin ← d
  Pour i ← d+1 à f faire :
    Si t[i] ≤ t[imin] alors
      imin ← i
    Fin si
  Fin pour
  Retourner imin
Fin

Existence d'un élément dans un tableau

Algorithme général :

Algorithme Recherche (e : entier ; t : tableau d'entiers)
{ Indique si l'élément e est présent ou non dans le tableau t }
Variable i : entier
Début
  i ← 1;
  Tant que (i ≤ taille(t)) et (t[i] ≠ e) faire
    i ← i+1
  Fin tant que
  Si (i>taille(t))
  Alors Écrire("l'élément recherché n'est pas présent")
  Sinon Écrire("l'élément recherché a été découvert")
  Fin si
Fin

Mais si les éléments du tableau sont ordonnés, nous pour vous pouvons tirer parti de cette caractéristique.

Algorithme RechercheO (e : entier ; t : tableau d'entiers)
Variable i  : entier
         trouve : booléen
Début
  i ← 1
  Tant que (i ≤ taille(t)) et (t[i] < e) faire:
    i ← i+1
  Fin TQ
  Si (i ≤ taille(t)) et (t[i]=e) alors
    Écrire('oui')
  Sinon
    Écrire('non')
  Fin si
Fin

ou encore mieux avec une recherche dite dichotomique :

Algorithme RechercheDichotomique
(e : entier ; t : tableau d'entiers)
Variable g,d,m  : entier
         trouve : booléen
Début
  g ← 1
  d ← taille(t)
  trouve ← faux
  Tant que (g ≤ d) et NON(trouve) Faire
    m = (g+d) div 2
    Si t[m] = e
    Alors trouve ← vrai
    Sinon Si e < t[m]
          Alors d ← m-1
          Sinon g ← m+1
          Fin si
    Fin si
  Fin Tant que
  Si trouve
  Alors Écrire('Trouvé !')
  Sinon Écrire('Pas trouvé...')
  Fin si
  Écrire(m)
Fin

Pour continuer à bénéficier de ces algorithmes, il faut être capable d'insérer un nouvel élément directement à sa place (ici n indique le numéro de la dernière case):

Algorithme Insertion (t : tableau d'entiers ; n,e : entier)
Variable i : entier
Début
  i ← n
  Tant que (i>0) et (t[i]>e) faire :
    t[i+1] ← t[i]
    i ← i-1
  Fin TQ
  t[i+1] ← e
Fin

Algorithmes de tri de tableaux

Algorithme d'échange

Algorithme Échange (t : tableau d'entiers ; i,j : entiers)
{ Échange le contenu des cases i et j dans le tableau t }
Variable pro : entier
Début
  pro  ← t[i]
  t[i] ← t[j]
  t[j] ← pro
Fin

Tri insertion

Algorithme TriInsertion (t : tableau d'entiers)
{ Trie par ordre croissant le tableau t }
Variable i : entier
Début
  Pour i ← 2 à taille(t) faire
    Insertion(t,i-1,t[i])
  Fin Pour
Fin

Tri extraction

Aussi nommé tri sélection, il utilise l'algorithme PositionMinimum

1. Extraire l'élément le plus petit du tableau à trier.
2. Échanger cette valeur minimale avec la première case du tableau à trier.
3. Trier le reste du tableau (le tableau initial sans la première case) de la même manière.

Algorithme TriExtraction (t : tableau d'entiers)
{ Trie par ordre croissant le tableau t }
Variables i,imin : entier
Début
  Pour i ← 1 à taille(t)-1 faire
    imin ← PositionMinimum(t,i,taille(t))
    Échange(t,i,imin)
  Fin Pour
Fin

Tri à bulles

Algorithme TriBulles (t : tableau d'entiers)
{ Trie par ordre croissant le tableau t contenant n éléments }
Variables i,j : entier
Début
  Pour i ← 1 à taille(t)-1 faire
    Pour j ← 1 à taille(t)-i faire
      Si t[j] > t[j+1]
      Alors Échange(t,j,j+1)
      Fin Si
    Fin Pour
  Fin Pour
Fin

Principe du tri rapide

1. Choisir un élément du tableau, élément que l'on nomme ensuite pivot.
2. Placer le pivot à sa position finale dans le tableau : les éléments plus petits que lui sont à sa gauche, les plus grands à sa droite.
3. Trier, toujours à l'aide de cet algorithme, les sous-tableaux à gauche et à droite du tableau.

Pour que cette méthode soit la plus efficace possible, il faut que le pivot coupe le tableau en deux sous-tableaux de tailles comparables.

Ainsi, si l'on choisit à chaque le plus petit élément du tableau comme pivot, on se retrouve dans le cas de l'algorithme de tri par extraction : la taille du tableau de diminue que d'un à chaque alors que le but est de diviser cette taille par deux.

Cependant, bien choisir le pivot peut être coûteux en terme de complexité.

Aussi on suppose que le tableau arrive dans un ordre aléatoire et on se contente de prendre le premier élément comme pivot.

Algorithme Placer (t,d,f):
Variables l,r : entiers
Début
  l ← d+1
  r ← f
  Tant que l ≤ r:
	Tant que t[r]>t[d]
		r ← r-1
	Fin TQ
	Tant que l ≤ f et t[l] ≤ t[d]
		l ← l+1
	Fin TQ
	Si l<r:
		Échange(t,l,r)
		r ← r-1
		l ← l+1
	Fin si
  Fin TQ
  Échange(t,d,r)
  Renvoyer r
Fin

Algorithme TriRapideBoucle (t,d,f)
Variable k : entier
Début
  Si d<f alors
	k ← Placer(t,d,f)
	TriRapideBoucle(t,d,k-1)
	TriRapideBoucle(t,k+1,f)
  Fin si
Fin

Algorithme TriRapide (t,n)
Début
  TriRapideBoucle(t,1,n)
Fin

Complexité

• le nombre d'échanges effectués,
• le nombre de comparaisons effectuées entre éléments du tableau.

tri à bulles en n².

tri rapide en n.log(n).

Démonstrations en ligne

• Sorting: tris et art,
• VisuTri de Thomas Baudel,
• la page d'insterstices sur les algorithmes de tri.

Complexité exponentielle et indécidabilité

Le problème du voyageur de commerce

http://www-sop.inria.fr/mefisto/java/tutorial1/node18.html

Complexité

complexité en 2ⁿ (exponentielle)

Intuition d'une explosion combinatoire

• tours de Hanoï
• grains de blé sur l'échiquier

Réflexions

Loi de Moore : la rapidité des processeurs double tous les 18 mois. Dans le cas du voyageur de commerce, le fait de doubler la vitesse de calcul ne permet, dans le même temps, que de traiter une ville supplémentaire.

Pourquoi l'algorithme Windows nécessite des machines de plus en plus puissantes ?

Indécidabilité du problème de l'arrêt

Commençons par donner un numéro à tous les algorithmes.

Supposons qu'il existe un algorithme dont la spécification serait la suivante :

Algorithme TestArrêt (a,n : entier)
{ Affiche 1 si l'algorithme de numéro a s'arrête sur l'entrée n,
          0 sinon }

Nous allons montrer en raisonnant par l'absurde qu'un tel algorithme ne peut pas exister.

Pour cela, considérons l'algorithme suivant qui n'est qu'une simple utilisation de l'algorithme TestArrêt.

Algorithme Bizarre (e : entier)
Variable i : entier
Début
  Répéter
    i = TestArrêt(e,e)
  Jusqu'à i = 0
  Écrire(1)
Fin

Nous constatons que cette algorithme Bizarre boucle à l'infini si l'algorithme de numéro e s'arrête ; par contre, Bizarre s'arrête si l'algorithme de numéro e boucle.

Voyons où cela nous mène si nous fournissons à l'algorithme Bizarre son propre numéro :Bizarre boucle si Bizarre s'arrête, et Bizarre s'arrête si Bizarre boucle...

Nous trouvons là une reformulation du paradoxe du barbier : dans une ville où les gens soit se rasent eux-mêmes, soit se font raser par le barbier, qui rase le barbier ? Soit il se rase lui-même et, dans ce cas, il n'est pas rasé par le barbier, soit il ne se rase pas lui même et nous en déduisons qu'il est rasé par le barbier. Reformulé, cela nous donne : soit il se rase lui-même et donc il ne se rase pas lui-même, soit il ne se rase pas lui-même et donc il se rase lui-même.

Nous devons conclure qu'une telle ville avec de tels habitants ne peut exister et, de la même manière, l'algorithme TestArrêt n'existe pas non plus.

L'ensemble des algorithmes est dénombrable, l'ensemble des problèmes ne l'est pas : tout deux sont de taille infinie mais le second est tout de même beaucoup plus grand que le premier.

Conclusion

Nous avons donné des algorithmes pour différents problèmes, en particulier des algorithmes de tri de tableaux.

Nous avons vu des problèmes plus difficiles :

• soit nous avons des algorithmes mais qui ne permettent pas de traitement du problème dans un temps raisonnable (complexité exponentielle) ;
• soit nous avons montré qu'il n'existe aucun algorithme pour certains problèmes (indécidabilité).