Pratique Intensive de la Programmation [ec3] -- Étude d'algorithmes de tri -- Alban Mancheron

Wilhelm .

Sujets

• informatique

Informations

• Publié par: Nesing
• Nombre de lectures: 144
• Langue: Français

Extrait

DÉPARTEMENT SCIENTIFIQUE INTERFACULTAIRE (DSI)
CAMPUS UNIVERSITAIRE DE SCHŒLCHER
BP 7209, 97 275 SCHŒLCHER CEDEX
Licence MIPC, Semestre 2 – /
Mathématiques&Informatique[UEO32]–TravauxPratiques
PratiqueIntensivedelaProgrammation[EC3]–Étuded’algorithmesdetri
Alban MANCHERON
1 Présentation&Objectifs 2 Découpageduprojet
La notion de tri est omniprésente au quotidien; qu’il Pour réaliser cette étude, il est bien évidemment né
s’agisse de vêtements, de compétition, etc. Cette no cessaire de programmer les algorithmes de tri vus en
tion apparaît également en informatique, et plusieurs cours/TD, à savoir le tri bulle, le tri par insertion, le tri
algorithmes permettent de la mettre en œuvre. L’ob sélection, le tri par tas et le tri rapide. Il faut en outre
jectifdecesméthodesestdoncd’ordonnerunecollec programmer un générateur de jeux d’essais, permet
tion d’objets comparables entre eux. Il est possible de tant de créer un tableau de taille donnée et de l’ini
regrouper ces méthodes selon plusieurs critères, afin tialiser selon plusieurs critères (e.g. initialisation avec
de pouvoir plus facilement déterminer quel(s) algo une même valeur, initialisation avec des valeurs crois
rithme(s) est(sont) le(s) plus adapté(s) en fonction des santes/décroissantes ou des valeurs aléatoires com
données à ordonner. Le premier critère généralement prises dans un intervalle donné). De surcroît, il est
considéréestladistinctionentrelesalgorithmesdetris nécessaire de proposer un module permettant l’éva
qui n’utilisent qu’un nombre limité de variables, donc luation des algorithmes de tri (comptage du nombre
qui modifient l’ordre des données directement et ceux d’opérations, du nombre d’affectations, du
quiacontrarioutilisentunnombredevariablesdépen d’accèstableaux,...).Enfin,ilfaudraproposerunmo
dant du nombre d’éléments à trier. Nous nous intéres dule permettant de sauvegarder les résultats des tests
serons dans ce projet uniquement aux algorithmes de dans un fichier.
la première catégorie, les algorithmes de tri dit «sur
Une fois la partie programmation achevée, il vous
place».
est demandé de proposer différents tests et d’analy
Leprojetquevousdevezréaliserconsistedoncàcréer ser les résultats obtenus. L’objectif est de trouver dans
une plate forme de test et de comparaison d’algo quels cas tel ou tel algorithme est le plus performant,
rithmes de tri. Pour cela, il vous faudra réaliser plu quels sont pour chacune des méthodes leurs cas «li
sieurs modules, correspondant aux différents compo mites» (i.e., cas où l’algorithme effectue le plus –le
santsdevotreoutil.Unefoiscetoutilréalisé,vouspro moins– d’opérations, d’affectations, ...), quelles sont
céderez à l’analyse et à la comparaison des méthodes leurs performances dans un cas général, ...
detriimplémentées.Pourplusdecommodité,lesdon
nées à trier seront –à votre convenance– des entiers
naturels ou relatifs (respectivementunsigned int
ouint en C) stockés dans des tableaux.
Objectifsdeceprojet
◦ Programmer intensément en C.◦ Programmer intensément en C.
◦ Se familiariser avec l’environnement Linux.◦ Se f avec
◦ Découvrir la programmation modulaire.◦ la
◦ Appréhender les notions de complexité.◦ les de
1/2UEO32/EC3 – TP DSI – Licence MIPC, Semestre 2
5 Améliorationsproposées3 Échéancier
Les améliorations suivantes sont des propositions.Le calendrier qui suit est indicatif et est susceptible
Néanmoins, celles qui sont suivies du symbole † sontd’être modifié (le cas échéant, vous en seriez informé
lesplusimportantes(donclesplusintéressantesàtoutparvoisd’affichage).Ilpermetnéanmoinsdebiendif
point de vue...). Il s’agit, bien évidemment, d’uneférencier les étapes du projet.
liste non exhaustive.er◦ 1 TP– semaine du 16 au 21 avril
◦ Optimisation du tri bulle, du tri sélection, du tri par• Analyse du projet dans sa globalité.
insertion †.• Implémentation du tri bulle.
e ◦ Intégration d’un mode pas à pas avec trace lors du◦ 2 TP– semaine du 23 au 28 avril
• du tri sélection. déroulement des tris †.
• Implémentation du tri par insertion. ◦ Implémentation et intégration d’algorithmes de tris
e◦ 3 TP– semaine du 23 au 28 avril hors place (tri fusion, tri par base, ...).
• du tri rapide.
◦ Génération automatique de diagrammes en utilisant
• Implémentation du tri par tas.
e par exemplegnuplot.◦ 4 TP– semaine du 30 avril au 5 mai
• du générateur de jeux d’essais.
• Interface de la plate forme de test.
6 Oùsedocumentere◦ 5 TP– semaine du 30 avril au 5 mai
• Implémentation du module de test.
Bien sûr, le projet s’appuie sur les notions vues en• Adaptation des algorithmes.
e cours/TD,maisvouspouvezégalementtrouverdel’in ◦ 6 TP– semaine du 7 au 12 mai
• Réalisation des tests. formation à la bibliothèque universitaire, ou encore
• Analyse des résultats. sur internet. Il vous est d’ailleurs chaudement recom
e◦ 7 TP– semaine du 7 au 12 mai mandé d’aller consulter les pages dédiées aux algo
• Corrections ou améliorations.
rithmes de tri sur wikipedia.
Petit rappel en passant, un anagramme de « pris la
4 Formalités tarte» est «le tri par tas» ...
Letravailestàréaliserenbinômes.Leprojetserapré
senté dans un rapport de 10 à 15 pages (hors annexes
éventuelles).
Ce rapport devra :
◦ pour la forme :
• mentionner vos noms, prénoms et numéro de groupe;
1• être dactylographié, imprimé et relié convenablement ;
• necomporterenannexequelesmorceauxdecodeindispen
sables à la compréhension.
◦ pour le fond :
• décrire la problématique;
• proposer une analyse répondant à ce problème;
• analyser les résultats obtenus à partir de vos jeux d’essais.
Il devra être remis à Alban MANCHERON au plus tard
le vendredi 18 mai à 11h57m41s.
Toutretardentraîneraunepénalitéd’unpointpar
jourentamé.
Bon courage...
1Il sera écrit en français. L’orthographe, la grammaire et le vocabulaire seront pris en compte pour la notation. Les envois par mail
ne seront pas pris en considération.
2/2