Examen et corrigé d'algorithmes et structures de données M1
Introduction à l'épreuve d'algorithmes et structures de données
Ce document propose un sujet d'examen accompagné de son corrigé détaillé pour l'unité d'enseignement d'algorithmes et structures de données. Destiné aux étudiants en Master 1 de bioinformatique, il a été conçu et évalué par M. Alain Griffault à l'Université de Bordeaux 1. L'épreuve s'est déroulée en décembre 2011 dans le cadre de la session de décembre de l'année universitaire 2011/2012.
Présentation générale du sujet et de son barème
Le barème total de l'épreuve est fixé à 22 points, répartis sur trois exercices indépendants. Les exercices couvrent des aspects fondamentaux de l'informatique fondamentale et de l'algorithmique avancée, notamment l'utilisation de piles pour implémenter des files, l'algorithme de tri par base appliqué à des structures complexes, ainsi que l'analyse de la récursivité et de la complexité de fonctions mathématiques.
Exercice 1 : Implémentation de files à l'aide de piles
La première partie de l'examen s'intéresse à la réalisation d'une structure de données de type file de taille N en s'appuyant sur deux piles de taille N. Le sujet détaille l'implémentation de base d'une pile à l'aide d'un tableau borné, incluant les fonctions de création, de test de vacuité et de plénitude, ainsi que les opérations d'empilement et de dépilement. Les étudiants sont ensuite amenés à compléter les primitives d'enfilage et de défilage pour cette file bicéphale, où le sommet de la première pile correspond à l'avant de la file et le sommet de la seconde pile correspond à l'arrière. L'exercice pousse la réflexion sur les limites des capacités de stockage et propose d'ajuster la fonction de test de file pleine pour éviter les incohérences de dépassement de capacité.
Exercice 2 : Le tri par base appliqué aux dates de naissance
Le deuxième exercice explore un algorithme ancien utilisé à l'origine pour le traitement des cartes perforées : le tri par base. L'objectif est de trier un tableau de structures représentant des personnes selon leur date de naissance, décomposée en jour, mois et année. Pour y parvenir, le sujet introduit d'abord une fonction de comparaison chronologique, puis demande de simuler manuellement les étapes successives d'un tri stable sur un jeu de données concret de sept personnes. L'importance de la stabilité des tris successifs est démontrée à travers un contre-exemple. Enfin, l'algorithme général du tri par base est formalisé en combinant des tris stables itératifs sur chaque composante de la date, et sa complexité algorithmique fait l'objet d'une analyse comparative.
Exercice 3 : Récursivité et analyse de complexité
Le dernier exercice aborde la récursivité à travers deux fonctions célèbres. La première partie analyse l'algorithme récursif de calcul de la suite de Fibonacci. Le sujet demande de représenter l'arbre des appels récursifs pour une petite valeur, avant d'évaluer le nombre total d'appels et de lier cette croissance à la structure de l'arbre. La seconde partie présente l'algorithme de la suite de Syracuse et interroge sur sa terminaison et sa complexité, soulignant le caractère ouvert de ce problème mathématique en l'état actuel des connaissances scientifiques.
Utilisation recommandée pour les révisions
Ce document constitue un support de travail idéal pour les étudiants souhaitant s'entraîner aux examens d'algorithmique avancée. Il est conseillé de chercher à résoudre chaque exercice de manière autonome avant de consulter les corrigés rédigés. L'analyse détaillée des manipulations de piles, de l'implémentation des files et des tris non comparatifs offre une excellente préparation pour consolider les acquis en structures de données complexes.
Questions fréquentes
À quel niveau d'études s'adresse ce sujet d'examen ?
Ce sujet s'adresse aux étudiants en première année de Master (Master 1) de bioinformatique à l'Université de Bordeaux 1.
Quels sont les principaux thèmes abordés dans le document ?
Les principaux thèmes sont l'implémentation de files à l'aide de piles, le tri par base appliqué à des enregistrements multidimensionnels, la stabilité des algorithmes de tri, ainsi que l'analyse de fonctions récursives et de leur complexité.
Combien d'exercices comporte l'épreuve ?
L'épreuve est composée de trois exercices indépendants totalisant un barème de 22 points.
Testez vos connaissances
Question 1
Comment est implémentée une pile de base dans le premier exercice du sujet ?
- À l'aide d'une liste chaînée dynamique
- À l'aide d'un tableau borné et d'un indice de sommet
- À l'aide d'une table de hachage
- À l'aide d'une file circulaire
Réponse correcte : À l'aide d'un tableau borné et d'un indice de sommet
Explication : Le texte indique explicitement que la pile est implémentée par un tableau borné de N objets et un indice de sommet représentant la position du dernier objet déposé.
Question 2
Sur combien de critères successifs s'effectue le tri par base des dates de naissance dans l'exercice 2 ?
- Un seul critère global
- Deux critères : le mois et l'année
- Trois critères : le jour, le mois et l'année dans cet ordre
- Quatre critères incluant le siècle
Réponse correcte : Trois critères : le jour, le mois et l'année dans cet ordre
Explication : L'idée du tri par base appliquée aux dates de naissance consiste à effectuer séquentiellement trois tris stables successifs : d'abord suivant le jour, puis suivant le mois, et enfin suivant l'année.
Question 3
Quelle est la condition indispensable pour que le tri par base fonctionne correctement ?
- Les tris utilisés à chaque étape doivent être instables
- Les tris utilisés à chaque étape doivent être stables
- Le tableau doit être préalablement trié par ordre alphabétique
- La taille du tableau doit être une puissance de deux
Réponse correcte : Les tris utilisés à chaque étape doivent être stables
Explication : Le sujet démontre qu'un tri par base perd sa validité si les tris intermédiaires ne sont pas stables, car l'ordre relatif des éléments égaux sur les clés précédentes ne serait pas préservé.
Télécharger Examen et corrigé d'algorithmes et structures de données M1 pdf
