DEUG MASS 1999-2000, 4e semestre Module d'Algorithmique
Exercices de révision

thèmes: Recherche gloutonne, Complexité, Machine de Turing, Récursivité


On désire effectuer le produit de 4 matrices réelles de taille respective 10x20, 20x50, 50x1 et 1x100. On suppose que le produit d'une matrice pxq par une matrice qxr demande pqr opérations scalaires (cas typique d'un algorithme de multiplication matricielle).

  1. Déterminer l'ordre optimal de multiplication permettant de minimiser le nombre total d'opérations scalaires
  2. Comment déterminer cet ordre optimal si le nombre de matrices à multiplier est quelconque?

Corrigé.


Donner, sous forme de programme ou de graphe d'états, une machine de Turing réalisant une soustraction.

Corrigé.


Soient un ensemble de villes et une table des distances entre ces villes.

  1. Proposer une méthode pour trouver un chemin passant par chacune des villes et revenant au point de départ.
  2. Proposer une heuristique efficace pour que ce chemin soit aussi court que possible.

Corrigé.


Soient les algorithmes récursifs quefaisje(n) et etmoidonc(n). Ces algorithmes représentent des fonctions prenant un nombre entier comme argument et renvoyant un autre nombre entier. 
fonction quefaisje(n)
si n < 0
   ^0
sinon
   si n pair
      ^quefaisje(n/2)
   sinon
      ^1 + quefaisje((n-1)/2)
 
fonction etmoidonc(n)
selon (n modulo 4)
   0 : etmoidonc(n/4)
   1 : 1 + etmoidonc((n-1)/4)
   2 : 1 + etmoidonc((n-2)/4)
   3 : 2 + etmoidonc((n-3)/4)

  1. Calculez, pour chacune de ces fonctions, la valeur renvoyée pour n = 0. Que constatez-vous? Proposez des modifications pour corriger le problème.
  2. Calculez, pour chacune de ces fonctions, la valeur renvoyée quand n = 4p, en fonction de la valeur renvoyée pour n = p.
  3. Même question pour n = 4p+1, n=4p+2, n=4p+3. Qu'en concluez vous?
  4. Combien d'étapes de calcul sont nécessaires à chacune de ces fonctions pour calculer leur valeur pour un argument n entier positif?

Question subsidiaire facultative: Calculez la valeur renvoyée par ces fonctions pour n = 2p.q+r, en fonction des valeurs renvoyées pour p, q, et r. Pouvez vous alors expliquer ce que calculent ces fonctions.

Corrigé.