UCBL, Maîtrise MIM, Recherche Opérationnelle : Travaux dirigés

Chapitre 1 Notions de complexité

Problem 1.0.1 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 1 Évaluer au mieux la complexité des problèmes suivants:

Calcul de n!;

Calcul du n-ième nombre de Fibonacci;

Recherche d'un mot dans un dictionnaire;

Calcul du pgcd de deux nombres;

Calcul du produit de deux matrices;

Calcul du déterminant d'une matrice;

Calcul du rang d'une matrice;

Inversion d'une matrice;

Calcul d'un vecteur x solution de Ax=b, où A est une matrice et b un vecteur;

Recherche du plus court chemin entre deux stations de métro à Paris;

Test de primalité de n.

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 ?

Travaux pratiques

Recherche opérationnelle et Optimisation Discrète

Travaux dirigés, licence