Scribd
Importer
8 vues2 pages

Algorithmes de tri et Tours de Hanoi

Le document présente un travail pratique sur les algorithmes de tri et les tours de Hanoi, demandant d'analyser et d'implémenter différentes méthodes en C. Pour chaque algorithme de tri, il est requis de proposer des versions itératives et récursives, d'estimer leur complexité, de mesurer le temps d'exécution et de comparer les résultats. De même, pour les tours de Hanoi, il faut développer des algorithmes, estimer leur complexité, et analyser les performances en fonction du nombre de disques.

Transféré par

hassani.chaima18
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
8 vues2 pages

Algorithmes de tri et Tours de Hanoi

Le document présente un travail pratique sur les algorithmes de tri et les tours de Hanoi, demandant d'analyser et d'implémenter différentes méthodes en C. Pour chaque algorithme de tri, il est requis de proposer des versions itératives et récursives, d'estimer leur complexité, de mesurer le temps d'exécution et de comparer les résultats. De même, pour les tours de Hanoi, il faut développer des algorithmes, estimer leur complexité, et analyser les performances en fonction du nombre de disques.

Transféré par

hassani.chaima18
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

M1 2024/2025

TP

Partie 1: Algorithmes de tri

Plusieurs algorithmes de tri existent dans la littérature. La problématique du tri de données est très
présente en informatique dans divers domaines applicatifs. Le choix d’un algorithme de tri
approprié est lié, d’une part au contexte d’application, mais aussi aux performances souhaitées. Être
en mesure d’estimer la complexité des différentes méthodes de tri est par conséquent primordial.
Dans ce travail, il vous est demandé de considérer les approches suivantes de tri de valeurs entières:
tri par sélection, tri par insertion, tri à bulle, tri rapide, et tri par fusion.

Pour chaque approche:

1-Proposer deux algorithmes. L’un itératif et l’autre récursif. Pour chaque algorithme :
2-Estimer sa complexité asymptotique.
3-Proposer une implémentation en utilisant le langage C. Considérer une structure de liste chaînée
unidirectionnelle. Les valeurs entières seront générées aléatoirement. En entré du programme (en
ligne de commande), on considère la taille de la liste (nombre d’éléments). En sortie, on considère
les éléments triés ainsi que le temps d’exécution.
4-Effectuer des mesures du temps d’exécution en faisant varier la taille des données.
5-Représenter les mesures prises en utilisant des tableaux et des graphes.
6-Proposer une analyse et une comparaison des différentes méthodes de tri et de leurs versions
respectives itérative et récursives.
7-Proposer une analyse et une comparaison entre les complexités théoriques et expérimentales.

Partie 2: Tours de Hanoi

Les tours de Hanoi sont un jeu de réflexion fréquemment utilisé dans le domaine de la complexité
algorithmique dans un but pédagogique. Le jeu consiste à déplacer des disques de diamètres
différents d'une tour de « départ » à une tour d' « arrivée » en passant par une tour « intermédiaire »,
et ceci en un minimum de coups. Les règles suivantes doivent être respectées :

-On ne peut déplacer plus d'un disque à la fois.


-On ne peut placer un disque que sur un autre disque plus grand que lui ou sur un emplacement
vide.
-On suppose que cette dernière règle est également respectée dans la configuration de départ.

Complexité Mohammed Riyadh ABDMEZIEM


M1 2024/2025

Il vous est demandé de :


1-Proposer deux algorithmes afin de résoudre ce problème. L’un itératif et l’autre récursif. Pour
chaque algorithme proposé :
2-Estimer sa complexité asymptotique.
3-Implémenter les deux algorithmes en utilisant le langage C. En entré du programme (en ligne de
commande), on considère le nombre de disques à déplacer. En sortie, on considère les
déplacements effectués ainsi que le temps d’exécution.
4-Effectuer des mesures du temps d’exécution en faisant varier le nombre de disques à déplacer.
5-A partir de quel nombre de disques à déplacer le programme devient incapable de produire une
solution ?
6-Représenter les mesures prises en utilisant des tableaux et des graphes.
7-Proposer une analyse et une comparaison entre les complexités théoriques et expérimentales des
deux versions itératives et récursives.

Rendus
-Rendu : fichier .zip contenant :

-Un rapport PDF.


-Code source compilable (fichiers .c et éventuellement .h).
-Présentation

Complexité Mohammed Riyadh ABDMEZIEM

Vous aimerez peut-être aussi