Initiation au Développement

Les supports proposés sur ce site correspondent à l’enseignement Initiation au Développement, qui correspond à la ressource R1.01 du PPN des IUT en informatique. La partie du cours que j’enseigne 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: la logique suit une présentation formelle des notions en cours magistral (2h), suivi d’une première manipulation en TD (2h) où les algorithmes sont écrits en pseudo-langage algorithmique, et enfin un ou deux TP (4h) pour les implémenter en C. Les premiers TD et TP correspondent à des cours magistraux donnés par mon collègue Abdel Bourjij.

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. De même, je ne fournis ici que les versions pdf des supports de cours, mais je peux fournir sur demande les versions odp comprenant les animations.

TD1 et 2 : Algorithmes de base

Texte du TD #1 sur les premières écritures d’algorithmes en pseudo-langage avec les fonctions d’entrée-sortie de base, les tests et la manipulation d’entiers.
Texte du TD #2 sur les boucles, et la manipulation de réels. Seule la boucle while est autorisée.

CM4 : Rappels sur complexité, types abstraits de données et tableaux

Supports du cours #4 où sont faits ce qui sont essentiellement des rappels sur la notion de complexité — en particulier complexité poynomiale en temps –, une brève introduction aux types abstraits de données, pour finir 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.

TD5 : Complexité et tableaux

Texte du TD #5 abordant la complexité via des algorithmes de comptage, et proposant quelques exercices de manipulation de tableaux.

TD7 et 8 : Fonctions et récursivité

Texte des TD #7 et 8 introduisant aux fonctions, et proposant quelques exercices sur la récurvisté.

TP13-14 : Pointeurs en C

Enoncé du TP 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.

CM5 : Listes chaînées et consorts

Supports du cours #5. Les listes récursives sont introduits comme type abstrait de données et leur implémentation en tant que listes chaînées, ainsi que les variantes classiques de liste doublement chaînée, liste circulaire, pile et file sont exposés. Les algorithmes fondamentaux qui y sont associés sont décrits et analysés en termes de complexité, ce qui permet une comparaison avec les tableaux. La session se termine sur une activité débranchée sur les listes chaînées réalisée en amphi.

TD9 et 10 : Listes chaînées

Enoncé des TD11 et 12 portant sur l’implantation d’une liste récursive au moyen d’une liste chaînée. Algorithmes de base sur cette structure.

TP18 et 19 : les structures en C

Enoncé des TP sur les structures en C : après une première présentation et manipulation d’une structure encodant un temps, on demande la structure et l’implantation des opérations de la sorte Liste Récurvise vue en cours. Les fichiers des codes source mentionnés sont à télécharger.

TP20 et 21 : listes chaînées

Enoncé des TP sur les listes chaînées : nous nous basons sur l’implantation de la sorte Liste Récurvise faite au TP précédent et implantons tous les algorithmes associés que nous avons vu lors des TD9 et 10. Les fichiers des codes source contiennent une implantation de la sorte Liste Récursive (correction du TP précédent) et sont à télécharger.

CM6 : Arbres binaires, arbres binaires de recherche, tables de hachage

Support du CM#6 où sont introduits les arbres binaires, arbres binaires de recherche, arbres équilibrés, et les tables de hachage.

TD15 : arbres binaires

Enoncé du TD15 portant sur les arbres binaires, et les arbres binaires de recherche.

TP27 et 28 : abres binaires de recherche

Enoncé des TP sur les arbres binaires de recherche. Cette session se fait sous forme de live coding sous VSCode, ce qui permet de présenter une approche analytique pour aborder ce genre de problèmes, mais également quelques trucs permettant de tester rapidement et de manière incrémentale son code, et enfin expliquer par des exemples ce qu’on entend par “bon commentaire”. Le TP a pour objectif de stocker dans un arbre binaire de recherche les données du fichier CSV de noms de prénoms qui est à télécharger.

Situation d’Apprentissage et d’Évaluation (SAÉ)

Deux SAÉ sont attachées à cette ressource: SAÉ1.01 (comparaison d’approches algorithmiques) et SAÉ1.02 (implémentation d’un besoin client). Nous avons choisi de mélanger les deux SAÉ, tout en gardant deux rendus de projets. Je suis donc responsable d’un de ces deux projets pour lequel j’ai imaginés deux sujets que je propose par alternance.

Naissance multiples: l’objectif est de stocker en mémoire les données contenues dans un énorme fichier CSV, le fichier des prénoms des enfants nés depuis 1900 en France, par département (3.9 millions de lignes). Il s’agit de choisir et d’implanter la structure de données la plus adaptée afin de 1) minimiser les informations stockées en mémoire; et 2) permettre des requêtes les plus rapides possibles.
World of IUT: l’objectif est de faire une implémentation sommaire d’un jeu d’aventure textuelle permettant de se déplacer dans un monde fait de cases adjacentes. La manipulation de pointeurs est fortement requise, et une implantation élémentaire d’un graphe est implicitement demandée. Un code source initial est fourni afin pour démarrer le projet et lui donner la bonne dimension.