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

TCA101 - 1er semestre : TD 1

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 ?

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 chacun des programmes pour n=100 ? n=10^{6} ? n=10^{10} ?

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.

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.

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 ?

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 ?

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.