Rappels de complexité

Chapitre 1 Rappels de complexité (et d'algèbre linéaire)

Problem 1 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 ?

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

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 l'algorithme suivant:

Je pars du début de l'annuaire;
Je compare le nom avec «Zorro»;
Si oui, j'ai terminé;
Si non, je recommence en 2 avec le nom suivant;

Analyse de ce que l'on a fait:

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:

Choix de la mesure de la taille d'une instance problème (le nombre de mots d'un dictionnaire donné)
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:

Complexité au pire (n opérations)
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 1000log₂n+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():

O(4n+3)=O(n)
O(logn)+O(logn)=O(logn)
O(n²)+O(n)=O(n²)
O(n³)O(n²logn)=O(n⁵logn)

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 ?

Rappeller l'algorithme du pivot de Gauss, et donner l'ordre de grandeur de sa complexité.

Exercice 3 On dispose d'un ordinateur pouvant exécuter 10⁹ 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(n²), O(n³), O(n¹⁰), O(2ⁿ), O(n!), O(nⁿ). Évaluer dans chacun des cas le temps nécessaire.

Exercice 4 Comparaison de la complexité de deux méthodes de tri.

On a une liste que l'on veut trier, mettons 7,8,4,2,5,9,3,5.

Méthode 1 (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.
Méthode 2 (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 2^k éléments sont triés; on les regroupe par paquets de 2^k+1 que l'on trie.
5. À la fin, tous les éléments sont dans le même paquet et sont triés: 2,4,7,8,3,5,5,9.

Quelle est la meilleure méthode ?

Exercice 5 Évaluer au mieux la complexité des problèmes suivants:

Calcul du n-ième nombre de Fibonacci;
Calcul du déterminant d'une matrice;
Calcul du rang d'une matrice;
Calcul de l'inverse d'une matrice;
Calcul d'un vecteur x solution de Ax=b, où A est une matrice et b un vecteur;
Calcul du pgcd de deux nombres;
Test de primalité de n;
Recherche du plus court chemin entre deux stations de métro à Paris;
Calcul de la n-ième décimale de (2)^1/2;
Calcul de l'inverse d'un nombre modulo 3;
Recherche d'un échec et mat en 4 coups à partir d'une position donnée aux échecs.
Problème du sac à dos: étant donné un ensemble d'objets d'épaisseur variable, et un sac à dos de hauteur donnée, peut-on remplir le sac à dos à bloc, sans déborder ?

Presentation

Recherche opérationnelle et Optimisation Discrète

Programmation Linéaire
Rappels de complexité / UCBL, Maîtrise MIM, Recherche Opérationnelle / Nicolas M. Thiéry
Last modified: Fri Jan 19 12:26:09 2007