Les supports proposés sur ce site correspondent à l’enseignement APL2: Algorithmes, Langages et Programmation 2 faisant partie de l’UE11 “Bases de l’informatique” du PPN des IUT en informatique. Il propose une introduction aux structures de données et les algorithmes de base qui y sont associés. L’ordre suivi ici reproduit celui suivi en cours. Je ne rends bien évidemment pas disponibles les corrigés des TD et TP, mais vous pouvez me contacter si vous désirez y avoir accès.
TP1 : Tutoriel d’introduction à C
Enoncé du TP1 donnant une introduction rapide au langage C. Le cours repose sur l’hypothèse que vous savez déjà programmer en Python.
CM1 : Rappels sur complexité et tableaux
Supports du cours #1 où sont faits ce qui sont essentiellement des rappels sur la notion de complexité — en particulier complexité poynomiale en temps — et sur les tableaux — en particulier l’impact sur la mémoire de l’utilisation (création, modification, destruction) d’une variable tableau en mémoire.
TD1 : Complexité et tableaux
Enoncé du TD1 portant sur la complexité et les tableaux, avec essentiellement des rappels et des petits exercices d’entrainement.
TP2 : Pointeurs en C
Enoncé du TP2 sur les pointeurs en C, passage par variable, passage d’arguments à un programme, fonctions d’entrée sortie standard et dans les fichiers. Ce TP se base sur un ensemble de fichiers de code source à télécharger.
CM2 : Listes chaînées et Types Abstraits de Données
Supports du cours #2. Les types de données abstraits sont introduits, ainsi que les listes chaînées. Les TAD liste itérative et liste récursive sont présentés. Enfin, les TAD classiques de liste doublement chaînée, liste circulaire, pile et file sont exposés.
TD2 : Listes chaînées
Enoncé du TD2 portant sur l’implantation d’une liste récursive au moyen d’une liste chaînée. Algorithmes de base sur cette structure.
TP3 : listes chaînées
Enoncé du TP3 sur les listes chaînées : après une brève introduction aux structures en C, nous implantons ce que nous avons vu lors du TD2. Les fichiers des codes source mentionnés sont à télécharger.
CM3 : Arbres binaires, arbres binaires de recherche, tables de hachage
Support du CM#3 où sont introduits les arbres binaires, arbres binaires de recherche, arbres équilibrés, et les tables de hachage.
TD6 : arbres binaires
Enoncé du TD6 portant sur les arbres binaires, et les arbres binaires de recherche.
TP7 et 9 : gestion de fichier CSV
Enoncé couvrant les deux dernières sessions de TP (4h) et ayant pour but de lire un fichier au format csv (séparateur ;) et de stocker les informations pertinentes dans une table de hachage. Le fichier est issu des données de l’INSEE sur les prénoms en France (hors Mayotte) en 1900 et 2018. Chaque enregistrement comporte 5 champs (voir la documentation officielle) :
- Le sexe, indiqué sur un caractère par 1 (masculin) ou 2 (féminin).
- Le prénom usuel, indiqué dans une chaîne de 25 caractères au maximum.
- L’année de calcul de la statistique, indiquée sur une chaîne de 4 caractères. Le mot “XXXX” est indiqué lorsque l’année est inconnue.
- Le département, sur deux caractères. “XX” est utilisé si le département est inconnu.
- Le nombre d’occurrences du prénom pour l’année et le département indiqués. Ce nombre tient dans une chaîne de 8 caractères au maximum.
Archives
TP7 et 9 : k-d trees
Enoncé couvrant les deux dernières sessions de TP (4h) ayant pour but d’implanter des k-d trees en 2D, ainsi que la fonction de recherche du point le plus proche. Le TP7 met en place les outils utiles (lecture de fichiers de points, tri en C), et permet de faire un rappel des notions de C. Le TP9 porte sur la programmation effective en C d’un k-d tree et de la recherche du plus proche voisin. Ce TP étendu est l’occasion de passer en revue tout ce qui a été vu en APL2.
