Up: Option Algèbre et Calcul Formel, Préparation à l'Agrégation de Mathématiques d'OrsayOption Algèbre et Calcul Formel, Préparation à l'Agrégation de Mathématiques d'Orsay Next: TP: rudiments de cryptographieTP: rudiments de cryptographie
Document aussi disponible au format PDF, Postscript, DVI, Text, LaTeX, LyX.

Tris et Complexité


Problem 1   Quelle est le meilleur algorithme pour trouver un nom dans un annuaire ?

Quel est le meilleur méthode pour calculer le déterminant d'une matrice ?

Comment prédire le temps que va mettre un programme pour s'exécuter ?

Comment savoir, entre deux algorithmes, lequel est le plus rapide ?

Comment savoir si un algorithme est optimal ?








Exemple 2   Je recherche le nom «Zorro» dans un annuaire en utilisant la méthode suivante:
  1. Je pars du début de l'annuaire;
  2. Je compare le nom avec «Zorro»;
  3. Si oui, j'ai terminé;
  4. Si non, je recommence en 2 avec le nom suivant;
Combien est-ce que cela va me prendre de temps?









Analyse:

On s'est donné un problème (rechercher un mot dans un dictionnaire), un algorithme pour le résoudre (recherche exhaustive). Puis on a introduit un modèle de calcul:
  1. Choix de la mesure de la taille d'une instance problème (le nombre de mots d'un dictionnaire donné)
  2. Choix des opérations élémentaires (comparer deux mots)
Dans ce modèle, on a cherché le nombre d'opérations élémentaires effectuées par l'algorithme pour un problème de taille n. C'est ce que l'on appelle la complexité de l'algorithme. En fait, on a vu deux variations:
  1. Complexité au pire (n opérations)
  2. Complexité en moyenne (n/2 opérations)
À partir de cette information, et en connaissant le temps nécessaire pour de petites instances du problème on peut évaluer le temps nécessaire pour résoudre n'importe quelle instance du problème.
Exemple 3   Évaluons la complexité de la recherche dichotomique.









Analyse:

La plupart du temps, il suffit d'avoir un ordre de grandeur du nombre d'opérations: les constantes sont sans grande importance. Un algorithme en 1000log2n+50 sera meilleur qu'un algorithme en n/1000 dès que l'on s'intéressera à des instances suffisament grandes.
Définition 4   Soient f et g deux fonctions de N dans N (par exemple les complexités de deux algorithmes).

On note f=O(g) si, asymptotiquement, f est au plus du même ordre de grandeur que g, i.e. s'il existe une constante a et un entier N tels que f(n)<= ag(n) pour n>= N.

On note f=o(g) si, assymptotiquement, f est négligeable devant g, i.e. si pour toute constante a il existe N tel que f(n)<= ag(n) pour n>= N.

En gros: f
Remarque 5   Quelques règles de calculs sur les O():
  1. O(4n+3)=O(n)
  2. O(logn)+O(logn)=O(logn)
  3. O(n2)+O(n)=O(n2)
  4. O(n3)O(n2logn)=O(n5logn)
Et de même pour les o().
Exercice 1   Donner un algorithme pour chercher le plus grand élément d'une liste de nombres. Évaluer la complexité de cet algorithme. Existe-t'il un meilleur algorithme ?








Définition 6   La complexité d'un problème est la complexité du meilleur algorithme pour le résoudre.

On dit qu'un algorithme est optimal si sa complexité coïncide avec celle du problème.
Exercice 2   Donner un algorithme pour calculer la somme de deux matrices carrées, et évaluer sa complexité. Est-il optimal ?

Donner un algorithme pour calculer le produit de deux matrices carrées, et évaluer sa complexité. Est-il optimal ?
Theorem 7   Rechercher un élément dans une liste triée de taille n est un problème de complexité O(logn).
Exercice 3   On dispose d'un ordinateur pouvant exécuter 109 opérations élémentaires par seconde (1GHz). On a un problème (par exemple, chercher un mot dans une liste, calculer le déterminant d'une matrice), et des instances de taille 1,10,100,1000 de ce problème. Enfin, on a plusieurs algorithmes pour résoudre ce problème, dont on connaît les complexités respectives: O(logn), O(n), O(nlogn), O(n2), O(n3), O(n10), O(2n), O(n!), O(nn). Évaluer dans chacun des cas le temps nécessaire.








Exercice 4   Comparaison de la complexité de quelques algorithmes de tri.

On a une liste que l'on veut trier, mettons 7,8,4,2,5,9,3,5.
Tri sélection
 
  1. On échange le premier élément avec le plus petit des éléments: 2,8,4,7,5,9,3,5
  2. On échange le deuxième élément avec le plus petit des éléments restants: 2,3,4,7,5,9,8,5
  3. ...
  4. Au bout de k étapes, les k premiers éléments sont triés; on échange alors le k+1ème élément avec le plus petit des éléments restants.
  5. À la fin, la liste est triée: 2,3,4,5,5,7,8,9.
Tri fusion
 
  1. On groupe les éléments par paquets de deux, et on trie chacun de ces paquets: (7,8),(2,4),(5,9),(3,5).
  2. On groupe les éléments par paquets de quatres, et on trie chacun de ces paquets: (2,4,7,8),(3,5,5,9).
  3. ...
  4. Au bout de k étapes, les paquets de 2k éléments sont triés; on les regroupe par paquets de 2k+1 que l'on trie.
  5. À la fin, tous les éléments sont dans le même paquet et sont triés: (2,3,4,5,5,7,8,9).
Tri rapide
 
Tri insertion, tri par arbre binaire de recherche
 
Quelle est la meilleure méthode ?
Problem 8   Les algorithmes de tris en O(nlogn) sont ils optimaux?








Theorem 9   Le tri d'une liste de taille n est un problème de complexité O(nlogn).








Exercice 5   Évaluer au mieux la complexité des problèmes suivants:
  1. Calcul du n-ième nombre de Fibonacci;
  2. Calcul du déterminant d'une matrice;
  3. Calcul du rang d'une matrice;
  4. Calcul de l'inverse d'une matrice;
  5. Calcul d'un vecteur x solution de Ax=b, où A est une matrice et b un vecteur;
  6. Calcul du pgcd de deux nombres;
  7. Test de primalité de n;
  8. Recherche du plus court chemin entre deux stations de métro à Paris;
  9. Calcul de la n-ième décimale de (2)1/2;
  10. Calcul de l'inverse d'un nombre modulo 3;
  11. Recherche d'un échec et mat en 4 coups à partir d'une position donnée aux échecs.
  12. Problème du sac-à-dos: étant donné un ensemble d'objets de hauteur et de poids variables, et un sac à dos de hauteur donnée, charger au maximum le sac-à-dos?

1  TP


Exercice 6   Implantez une fonction recherche(liste, valeur) renvoyant la position de valeur dans la liste. Par exemple:

recherche([9,20,3,40,37,42,69,65,21,66,1,74,50], 21) renvoie 9

recherche([9,20,3,40,37,42,69,65,21,66,1,74,50], 69) renvoie 7

recherche([9,20,3,40,37,42,69,65,21,66,1,74,50], 5) renvoie FAIL

Indications: ?proc, ?for, ?if, et utilisez les tests suivants:

prog::test(recherche([],1), FAIL):

prog::test(recherche([2],1), FAIL):

prog::test(recherche([2],2), 1):

prog::test(recherche([9,20,3,40,37,42,69,65,21,66,1,74,50],21), 9):

prog::test(recherche([9,20,3,40,37,42,69,65,21,66,1,74,50],69), 7):

prog::test(recherche([9,20,3,40,37,42,69,65,21,66,1,74,50],5), FAIL):

prog::test(recherche([1,3,9,20,21,37,40,42,50,65,66,69,74],21), 5):

prog::test(recherche([1,3,9,20,21,37,40,42,50,65,66,69,74],69), 13):

prog::test(recherche([1,3,9,20,21,37,40,42,50,65,66,69,74],5), FAIL):

Insérer un compteur dans la fonction pour compter le nombre de comparaisons effectuées lors d'un appel. Faire quelques statistiques et tracer une courbe donnant le nombre de comparaisons en moyenne et au pire en fonction de la taille de la liste (Indications: ?plot et essayez r:=random(): [ r() $ i=1..10]).

Même chose dans le cas où l'on suppose que la liste est triée, en utilisant une recherche dichotomique.

Indications: ?while, ?sort, et utiliser deux bornes inf et sup, vérifiant à chaque étape l'invariant «inf <= i < sup», où i est la position (éventuelle) de valeur dans la liste.

Comparer les deux courbes. Évaluer la taille maximale d'une liste dans laquelle on peut faire une recherche en moins d'une heure et d'une semaine.

Exercice 7   Écrire quelques tests pour une fonction de tri de liste d'entiers.

Implanter des fonctions de tri utilisant chacun des algorithmes suivants. Pour chacune tracer des courbes statistiques de complexité au pire et en moyenne. Comparer avec les courbes théoriques.
  1. Tri à bulle en place (Indication: choisir au préalable le bon invariant!);
  2. Tri fusion (Indication: utiliser une fonction recursive; le cas échéant, s'entrainer en implantant au préalable une fonction récursive pour calculer n!);
  3. Tri rapide en place;
  4. Tri insertion dans un arbre binaire de recherche (équilibré ou non). Indication: utiliser une fonction récursive, et essayer les commandes suivantes: 
    t := combinat::binaryTrees([ 4, [1], [6, [4],[7]]]); 
    op(t,0), op(t,1), op(t,2); 
    subsop(t, 1=combinat::binaryTrees([0,[],[1]])) );

2  Quelques références

Valid HTML 4.0! Up: Option Algèbre et Calcul Formel, Préparation à l'Agrégation de Mathématiques d'OrsayOption Algèbre et Calcul Formel, Préparation à l'Agrégation de Mathématiques d'Orsay Next: TP: rudiments de cryptographieTP: rudiments de cryptographie
Tris et Complexité / Option Algèbre et Calcul Formel / Nicolas M. Thiéry
Last modified: Mer 20 Sep 2006 14:39:10