Université Bordeaux I DEUG Première année 2002/2003

TCA101 - 1er semestre : TD 1 - Corrigé

Algorithmes - Notion de complexité - Types abstraits de données

Exercice 1.1 Quel est le nombre d’anagrammes d’un mot de 10 lettres différentes ? de 20 lettres ? En supposant qu’il faille 1 microseconde pour afficher une lettre à l’écran, combien de temps prendrait l’affichage de tous les anagrammes d’un mot de 10 lettres différentes ? de 20 lettres ?

Le nombre d’anagrammes d’un mot de n lettres différentes est n! Pour afficher tous les anagrammes d’un mot de 10 lettres différentes il faut 10 × 10! microsecondes, soit environ 36 s ; pour afficher tous les anagrammes d’un mot de 20 lettres différentes il faut 20 × 20! microsecondes, soit environ 5 × 10^{13}s, soit encore 1,5 million d’années.

Exercice 1.2 On considère les deux algorithmes suivants :

    Pour i variant de 1 à n             Pour i variant de 1 à \sqrt{n}
       si i divise n alors                si i divise n alors
          afficher i                         afficher i, n/i

En supposant que chacune des opérations “test de divisibilité” et “affichage d’une valeur” dure 2 microsecondes, combien de temps dure le programme pour n=100 ? n=10^{6} ? n=10^{10} ?

Algo 1 : n tests, au maxi n affichages : soit entre n et 2n n=100 : entre 0,2 ms et 0,4 ms n=1 000 000 :entre 2 s et 4 s n=10^{10} : entre 20000 et 40 000 s soit entre 5h et 11h

Algo 2 : \sqrt{n} tests, au maxi 2\sqrt{n} affichages : soit entre \sqrt{n} et 3\sqrt{n} n=100 : entre 0,02 ms et 0,06 ms n=1000000 :entre 2 ms et 6 ms n=10^{10} : entre 0,2s et 0,6 s

Exercice 1.3 La suite de Fibonacci est la suite des nombres 0,1,1,2,3,5,8,13... (les deux premiers sont imposés: 0 et 1, ensuite on obtient chaque nombre en additionnant les deux précédents). Donner un algorithme permettant de calculer le n-ième terme de cette suite.

     calculer f(n) :
          si n=0 alors mettre r à 0
          sinon
               mettre a à 0
               mettre b à 1
               tant que n > 1 faire
                   mettre r à a+b
                   mettre a à b
                   mettre b à r
                   enlever 1 de n

Exercice 1.4 Un joueur A choisit un entier entre 1 et 1000. Le joueur B cherche à deviner ce nombre : il propose des nombres entre 1 et 1000, le joueur A répondant suivant les cas “correct”, “trop petit” ou “trop grand”. Combien le joueur B doit-il poser de questions pour être certain de trouver le nombre choisi ? Formaliser l’algorithme correspondant.

10 questions suffisent.

      mettre min à 1
      mettre max à 1000
      proposer 500
      tant qu'on n'a pas trouvé faire
          proposer moy=( min + max )/2
          si trop grand : mettre max à moy - 1
          si trop petit : mettre min à moy + 1

Exercice 1.5 On vous a laissé un message : “rappeler le 05 56 84 60 84”. Ce numéro vous dit quelque chose, mais vous ne vous rappelez pas de qui il s’agit. Comment faire pour le retrouver dans un répertoire téléphonique ?

On examine les entrées du répertoire, jusqu’à ce qu’on trouve une entrée correspondant au bon numéro. On pourra utiliser un type répertoire, les opérations possibles étant : chercher l’entrée suivante, extraire le numéro d’une entrée, extraire le nom d’une entrée, comparer deux numéros.

Exercice 1.6 Cherchant à acquérir une imprimante, vous consultez le catalogue d’un magasin de matériel informatique. Dans ce catalogue, les produits sont classés par fabricants. Comment faire pour trouver l’imprimante la plus rapide ?

On examine toutes les entrées du catalogue, en gardant en mémoire l’entrée correspondant à l’imprimante la plus rapide examinée. On pourra utiliser un type “catalogue”, les opérations possibles étant : chercher l’entrée suivante, extraire le type d’une entrée (“imprimante”, “scanner”...), extraire les caractéristiques d’une entrée (imprimante, scanner...), extraire la vitesse d’une imprimante, comparer deux vitesses.

Exercice 1.7 Donner plusieurs méthodes pour ranger un paquet de 52 cartes dans l’ordre As, 2, 3,...,10, Valet, Dame, Roi de Trèfle, As, 2, ..., Roi de Carreau, As, 2, ..., Roi de Cœur, As, 2, ..., Roi de Pique. Comparer ces méthodes.