retour

Novembre 2006

Master 1 - TP Génie Informatique n1

TP1 : tableau de temperatures

Mettez vous à 2 par poste. Vous me rendrez un petit rapport (un seul par binôme) dans une semaine maximum (ceux qui ne savent pas ce qu'est une semaine peuvent utiliser un dictionnaire). Le sujet est long, vous devez essayer d'aller le plus loin possible. Mais vous devez également me montrer l'avancement du TP.

Remarques préliminaires :

Ce TP nous permettra de mettre en oeuvre les notions vues en cours : programmation séquentielle, structures de contrôle, fonctions, variables scalaires et tableaux, objets. Nous supposons vouloir traiter diverses valeurs réelles (des températures) mesurées lors d'un essai thermique, regroupées dans un tableau. Vous allez définir un tableau de températures (nous n'avons jamais plus de 100 mesures) comme un objet contenant le nombre de températures et toutes ces températures. Vous définirez la classe "temp" et ses méthodes dans un fichier nommé "temp.cpp". Vous mettrez votre programme de test dans un autre fichier. Je vous conseille d'utiliser vos notes prises en particulier en TD.

1. Dans un premier temps, créez la classe "temp" avec une méthode nommée "saisir" qui :

et une méthode nommée "afficher" qui affiche les données.

2. Ajoutez une méthode qui calcule la température moyenne (elle la retourne mais ne l'affiche pas !) mais affichez la dans le programme principal.

3. Créez les accesseurs en lecture et écriture qui vous semblent utiles.

4. Dans le programme principal, créez une boucle qui permette de répéter ce menu :

        que voulez vous faire ?
        1 -> saisir le tableau
        2 -> l'afficher
        3 -> moyenne
        0 -> quitter le programme

L'utilisateur peut choisir l'ordre et le nombre d'actions (au début le tableau est vide)

5. Rajoutez une méthode permettant d'ajouter une température (à la suite des autres).

6. Maintenant, nous aimerions trier le tableau. Il existe pour cela différents algorithmes, décrits plus bas. Demandez-moi lequel vous devrez implanter (toujours via une méthode).

7. Rajoutez la possibilité de supprimer une valeur(demander sa position, passé en argument).

8. Modifiez l'ajout d'une température en permettant de l'insérer à un endroit précis.

9.Rajoutez la possibilité d'exécuter une rotation, dans les deux sens : le premier passe en dernier et tous les autres se décalent; le dernier passe en premier et tous les autres se décalent. (2 méthodes).

Algorithmes de tri de tableaux (question 4) :

le tri bulle : Cet algorithme est relativement connu, bien qu'il soit rarement efficace (en termes de temps de calcul, le tri est néanmoins correct, bien évidement). Il consiste à balayer tout le tableau, en comparant les éléments adjacents et les échangeant s'ils ne sont pas dans le bon ordre. Plus précisément : on parcourt tout le tableau. dès qu'un élément est plus grand que son suivant, on échange les deux. Arrivé au bout du tableau, il faut recommencer. En effet, un seul passage ne déplacera un élément donné que d'une position. Mais en répétant le processus jusqu'à ce plus aucun échange ne soit nécessaire, le tableau sera trié. Il vous faudra donc utiliser un "truc" pour vérifier s'il y a eu un changement : au début, on met une variable à 0. A chaque changement, on la met à 1. Si l'on arrive à la fin du tableau et que la variable est restée à 0, on n'a donc plus rien à échanger, le tableau est trié. Je vous conseille de prévoir une fonction qui échange deux températures adjacentes.

le tri par insertion : On prend un élément après l'autre, dans l'ordre initial, et on le place correctement dans les éléments précédents déjà triés, comme on le fait lorsque l'on classe ses cartes à jouer après la donne. Plus précisément : la première (seule) est évidement triée. On regarde la seconde. Si elle est plus grande, on la laisse, sinon on la place devant l'autre. Puis on regarde la troisième, et on va la placer au bon endroit dans les deux précédentes (en premier, au milieu ou laissée à la fin). Puis on teste la quatrième, etc... jusqu'à avoir complètement balayé le tableau. Je vous conseille de prévoir une fonction qui permet d'avancer une carte depuis une position i vers une position j (j<i), en décalant toutes celles entre j et i d'un cran.

le tri par sélection : On recherche l'élément le plus petit. Il faut donc le placer en premier. Or cette position est déjà occupée, on se propose donc d'échanger les deux éléments. Il ne reste plus qu'à répéter l'opération N fois (N étant la taille du tableau). C'est à dire qu'on recherche ensuite le plus petit dans ceux qui restent (N-1), on le met en seconde position, on recommence pour chercher le troisième, et ainsi de suite jusqu'à l'avant dernier (le dernier sera automatiquement classé). Je vous conseille de prévoir une fonction qui permet de chercher la position (et pas la valeur) du plus petit élément du tableau, à partir d'une position donnée en argument. Une autre qui permet d'échanger deux températures (dont on donne la position en argument).

le tri shell : C'est une amélioration du tri par insertion : au lieu d'effectuer une rotation de tous les éléments entre la position initiale et finale (ou du moins meilleure) d'un élément, on peut faire des rotations par pas de P, ce qui rendra le fichier presque trié (chaque élément sera à moins de P positions de sa position exacte). On répète ce tri pour P diminuant jusqu'à 1. Une suite possible pour P est de finir par 1, les pas précédents étant de 4, 13, 40, 121, 364, 1093... (Pi=3*Pi-1 +1). D'autres suites sont évidement possibles, à condition de prendre des valeurs qui ne soient pas multiples entre elles (pour ne pas toujours traiter les mêmes éléments et laisser de côté les autres, par exemple les puissances successives de 2 ne traiteraient que les positions paires, sauf au dernier passage.

le tri rapide (Quick Sort) : Ce tri est récursif. L'idée est de prendre une valeur du tableau (appelée pivot), de mettre toutes les valeurs plus petites devant (sans les trier, bien sûr), toutes les plus grandes derrière. Il ne reste plus qu'à trier les deux demi tableaux. On utilise pour cela la récursivité, c'est à dire qu'on utilise la même méthode pour traiter chaque demi tableau, et ce jusqu'à ce que la taille soit petite pour être évidente à trier (taille 1). En pratique, on cherche à trier la partie du tableau délimitée par les indices gauche et droite. On choisit une valeur de ce sous-tableau (une valeur médiane serait idéale, mais sa recherche ralentit plus le tri que de prendre aléatoirement une valeur, par exemple la dernière), que l'on appelle pivot. Puis on cherche la position définitive de ce pivot, c'est à dire qu'on effectue des déplacements de valeurs de telle sorte que tous les éléments avant le pivot soient plus petits que lui, et que toutes celles après lui soient supérieures, mais sans chercher à les classer pour accélérer le processus. Puis on rappelle récursivement le tri de la partie avant le pivot, et de celle après le pivot. On arrête la récursivité sur les parties à un seul élément, qui est donc nécessairement triée.

le tri par création : Lorsqu'il est nécessaire de disposer simultanément du tableau initial et du tableau trié,on peut recopier le tableau initial puis effectuer un tri sur la copie, ou adapter un des algorithmes précédents. Par exemple, à partir du tri par sélection, l'algorithme consiste à rechercher l'élément le plus petit, le copier en première position du tableau final, rechercher le suivant, le placer en seconde position, etc... En cas d'éléments identiques, il est nécessaire de prendre certaines précautions. Une solution consiste à marquer les éléments déjà choisis, par exemple à l'aide d'un troisième tableau d'indicateurs (le tri est alors stable), ceci n'est qu'un exemple, d'autres possibilités existent, peut-être avez-vous une idée ?

Tri par comptage: Suivant les données à trier, il peut être plus efficace de construire un algorithme de tri spécifique. Par exemple, si le tableau contient un grand nombre de valeurs similaires (exemple : gestion annuelle d'un stock où la plupart des articles entrent et sortent plusieurs fois par jour), on peut utiliser l'algorithme simple (par création) consistant à rechercher l'élément le plus petit, compter le nombre de ces éléments, les mettre dans le tableau destination, et répéter l'opération jusqu'à la fin du fichier destination.
Si vous êtes forts, vous pouvez également prévoir le cas où le nombre de valeurs différentes est suffisamment faible pour pouvoir utiliser un tableau de compteurs, ce qui permet d'effectuer le comptage en un seul balayage du fichier.

Tri basique : Dans la cas où les valeurs sont bornées (c'est à dire comprises entre un minimum et un maximum connus à l'avance) et en nombre fini, on peut utiliser ce tri. Par exemple si toutes les clefs sont des entiers entre 000 et 999, on peut séparer le tableau en 10 parties en fonction des centaines, puis récursivement traiter les dizaines puis les unités (tri en base 10). Evidemment, un tri en base 2 sera plus efficace sur ordinateur : du début du tableau,on avance jusqu'à trouver un nombre commençant par 1, puis depuis la fin jusqu'à trouver un nombre commençant par 0. On les échange et l'on continue jusqu'à croisement des deux côtés. Puis on recommence (récursivement par exemple) sur le bit suivant, jusqu'à tri complet. Pour trier des valeurs alphabétiques, on peut effectuer un tri en base 26, sur les N premiers caractères (N pouvant valoir 2 ou 3 par exemple), le fichier est alors presque trié. Il est alors plus efficace d'effectuer un tri par insertion (passe de finition) plutôt que de répéter le tri basique jusqu'à tri complet.


Pour ceux qui ont du mal, une correction simple des premières questions (celles dont j'attendais une réponse pour avoir une note moyenne).

retour

(c) P. TRAU IPST - ULP