Université de Limoges Faculté des Sciences et Techniques

Niveau: Supérieur, Master, Bac+4
Université de Limoges Faculté des Sciences et Techniques Année Universitaire 2008-2009 Master Mathématiques première année Algorithmique et programmation Examen du 9 janvier 2009 Durée 2h. Documents manuscrits et distribués durant le semestre autorisés. Les exercices sont indépendants. Le barême est indicatif. Exercice 1. (6 points) Tri par bulles. On s'intéresse à l'algorithme suivant : Algorithme Tri_bulle(var T: tableau d'entiers, n: entier) Entrées : T[0],...,T[n-1], tableau de n entiers distincts. Sortie : Le tableau trié en ordre croissant. Début trié ?? faux m ?? n-1 Tant que non trié faire trié ?? vrai Pour i de 0 à m-1 faire Si T[i] > T[i+1] alors tmp ?? T[i] T[i] ?? T[i+1] T[i+1] ?? tmp trié ?? faux fin fin m ?? m-1 fin Fin. On s'intéresse à la complexité de cet algorithme, en nombre de comparaisons d'éléments du tableau. 1. Vérifier qu'à l'issue de chaque exécution de la boucle «Pour», l'élément T[m] est correctement placé. En déduire que l'algorithme fonctionne. 2. Quelle configuration d'entrée correspond au meilleur des cas de cet algorithme? Expliquez.

• ?ni par expo- nentiation binaire


• décomposition de l'exposant en base


• entier positif


• année algorithmique


• int tete


• typedef struct


• void afficher


• expo