MP, PSI et la TSI

Introduction à l'algorithmique avancée

I. Qu’est-ce que l’algorithmique ?

1. Définition (Algorithme).

Un algorithme est une suite finie d’opérations élémentaires constituant un schéma de calcul ou de résolution d’un problème.

2. Définition (Algorithmique)

L’algorithmique désigne le processus de recherche d’algorithme :

3. Différences entre algorithmes et programmes

Un programme est la réalisation (l’implémentation) d’un algorithme au moyen d’un langage donné (sur une architecture donnée). Il s’agit de la mise en oeuvre du principe. Par exemple, lors de la programmation on s’occupera parfois, explicitement de la gestion de la mémoire (allocation dynamique en C) qui est un problème d’implémentation ignoré au niveau algorithmique.

4. Qualités exigées d’un bon algorithme

Un bon algorithme doit satisfaire les qualités suivantes :

  • Correct : Il faut que le programme exécute correctement les tâches pour lesquelles il a été conçu
  • Complet : Il faut que le programme considère tous les cas possibles et donne un résultat dans chaque cas.
  • Efficace : Il faut que le programme exécute sa tâche avec efficacité c’est à dire avec un coût minimal. Le coût pour un ordinateur se mesure en termes de temps de calcul et d’espace mémoire nécessaire.

II. Problème 1 : Valeur d’un polynôme

On voudrait élaborer un algorithme permettant de calculer pour une valeur X donnée de type REAL la valeur numérique d'un polynôme de degré n:

Données : n et les coefficients an, ... , a0 et x

Objectif : calcul de P(X)

1. Algorithme 1 ( trivial) :

def algo1(a):         
         P=0
         for i in range(n) :
                  P = P+ a[i]*(X**i)
         return P

Coût de l’algorithme :

  • (n+1) additions 

  • (n+1) multiplications 

  •  (n+1) puissances 


2. Algorithme 2 (sans puissance) :

def algo2(a):         
         XP=1
         P =0
         for k in range(N) :
                  P = P+ XP*a[k]
                  XP = XP * X
         return P

Coût de l’algorithme :

  • (n+1) additions 

  • 2(n+1) multiplications 


3. Algorithme 3 (Schéma de Horner):

Le schéma de Horner est illustré par la figure ci-contre :

def horner(a,x) :
          p=a[-1]
          for k in range(len(a)-2,-1,-1) :
                      p=p*x+a[k]
          return p

 Coût de l’algorithme:

  • (n) additions 

  • (n) multiplications 


III. Problème 2 : La plus grande somme contiguë

Le but est d’élaborer un algorithme permettant de calculer la plus grande somme contiguë d'une séquence d'entiers placés dans un tableau.

Étant donné un tableau A[0..n-1] de n nombres entiers positifs ou négatifs, comment déterminer la valeur maximale des sommes correspondantes aux sections de la forme A[i..j[. On notera que 0 est la somme de n'importe quelle section vide A[i..i[.

Par exemple, si le tableau contient les dix éléments :


la somme maximale est A[2..7[= A[2..6] = 187.

1. Algorithme 1 (naïf) :

L'idée la plus simple est de calculer toutes les sommes et de rechercher la plus grande, par un algorithme du style:

def somme1(a) :
          maximum=0
          for i in range(n-1) :
                      for j in range(i,n) :
                                  somme=0
                                  for k in range(i,j) :
                                              somme+=a[k]
                                  if somme>maximum :
                                              maximum=somme
          return maximum

Il est facile de voir que la comparaison entre Maximum et Somme est effectuée O(n^3) fois.

2. Algorithme 2 :

Une meilleure idée consiste à ne pas recalculer systématiquement les sommes mais à utiliser la relation:


D’ou la fonction :

def algorithme2(a) :
          max=0
          for i in range(len(a)-1) :
                      somme=0
                      for j in range(i,len(a)) :
                                  somme+=a[j]
                                  if somme>max :
                                              max=somme
          return max

Cette version n'effectue plus que O(n^2) additions.

Peut-on  mieux faire ? 

3. Algorithme 3 :

On peut essayer une approche dichotomique en coupant le tableau en deux parties de tailles équivalentes et en disant que la somme maximale est réalisée soit totalement dans la partie droite, soit totalement dans la partie gauche, soit à cheval. La valeur recherchée est nécessairement la plus grande des trois sommes. Cette idée nous conduit à l’algorithme récursif suivant :

def algorithme3(a,g,d) :
          if g>d :
                      return 0
          if g==d :
                      if a[g]>0 :
                                  return a[g]
                      else :
                                  return 0
          m=(g+d)//2
          max1=0
          somme=0
          for i in range(m,g-1,-1) :
                      somme+=a[i]
                      if somme>max1 :
                                  max1=somme
          max2=0
          somme=0
          for i in range(m+1,d+1) :
                      somme+=a[i]
                      if somme>max2 :
                                  max2=somme
          maximum=max1+max2
          somme= algorithme3(a,g,m)
          if somme>maximum :
                      maximum=somme
          somme= algorithme3(a,m+1,d)
          if somme>maximum :
                      maximum=somme
          return maximum

On invoque cette fonction par l'appel algorithme3 (a, 0, len(a)).

Complexité de l’algorithme : 

Cet algorithme est de type « diviser pour régner ». Le nombre de comparaisons effectuées à l’intérieur de la fonction récursive est égal à (d-g) fois. Il est donc O(n). L’équation récurrente de sa complexité est donc:

On démontrera plus loin en utilisant le théorème qui sera présenté au chapitre suivant que : T(n) = O(n log(n))

Car : T(n) = 2T(n/2) + O(n)

4. Algorithme 4 :

Mais on peut encore mieux faire. L'idée cette fois est de parcourir une seule fois le tableau et de maintenir simultanément deux maximums : la plus grande somme « max1 » et un « max2 » qui est remis à zéro chaque fois qu’il devient négatif. La plus grande somme recherchée est égale soit à « max1 » soit à « max2 » d'où l'algorithme :

def algorithme4(a) :
          max1=0
          max2=0
          for i in range(n) :
                      max2+=a[i]
                      if max2<0 :
                                  max2=0
                      if max2>max1 :
                                  max1=max2
          return max1  

Il est clair que cet algorithme est en O(n).

Peut-on  mieux faire ? 

La réponse est non car tout algorithme résolvant ce problème est obligé de parcourir l'intégralité des données, donc a complexité au moins linéaire.

Sur un PC à 400MHz, pour un tableau de taille 107 Jon Bentley, (Programming Pearls, Addison-Wesley, 2000) ) donne l'estimation suivante des temps d'exécution :


VI. Conclusion

  • Existence de plusieurs solutions pour un problème donné 

  • Ces solutions peuvent être correctes mais n’ont pas la même efficacité (coût) 

  • Avant de proposer un algorithme, il faut estimer son coût 

  • Et se poser la question de l’existence d’une autre solution moins coûteuse 

Partager ce cours avec tes amis :
Rédigé par Mostafa Sedoki
Professeur d'Informatique dans les CPGE

Cours Similaires :