Exercice UML corrigé: Algorithmique diagrammes d’activités

Exercice UML

Les diagrammes d’activités permettent de raisonner sur des algorithmes, au cours de l’activité de spécification détaillée.

Vous allez utiliser les diagrammes d’activités pour décrire des algorithmes de tri.

1. Élaborez une activité swap qui prend trois arguments, un tableau tab et deux indices et b, et échange le contenu de la case tab[a] et tab[b].

2. En utilisant swap, décrivez un tri par bulles d’un tableau tab de taille n. L’algorithme consiste en n – 1 parcours du tableau, chacun amenant (par des appels successifs à swap sur des cases contiguës) le plus grand élément du tableau en dernière position (donc en position n 1 i à l’itération numéro i).

3. L’algorithme glouton du tri par bulles est peu efficace, en raison du grand nombre de copies inutiles réalisées. Écrivez un tri par insertion, qui opère en n itérations : à chaque itération de numéro  i, considérez la plage de valeurs de 0 à i 1 comme triée. L’algo- rithme consiste à chercher le bon endroit où insérer la valeur en position i, afin de trier la plage de valeurs de 0 à i. Copiez la valeur en position i dans une variable temporaire et décalez les valeurs avant cette position vers la droite (une par une) jusqu’à trouver l’endroit ou recopier la valeur de la variable temporaire.

4. L’algorithme précédent a encore une complexité élevée. Les tris les plus efficaces sont fondés sur des appels récursifs qui font chuter la complexité. La fusion de deux tableaux triés en un tableau trié est une opération de complexité linéaire sur la taille du tableau résultant. Pouvez-vous concevoir un algorithme (tri par fusion) qui s’appuie sur cette propriété  et des appels récursifs pour trier plus efficacement un tableau ? Indication : vous pouvez définir une activité tri fusion qui prend un tableau t et deux indices, g et d, et trie la portion du tableau comprise entre les indices g et d.

Notons que les algorithmes présentés ici sont fondés sur le très classique livre Le Langage C, de Kernighan et Ritchie. La lecture comparée des versions en C et en diagrammes d’activités est instructive.

La correction des exercices (voir page 2 en bas)

Télécharger aussi :

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *