Structures
de données A2 (NFA006 jour et soir) Structures
de données A2 (NFA006 jour et soir)NOUVEAU : SUJETS DES ED (C. Picouleau) : ED5, ED6, ED7, ED8, ED9, ED10
ainsi que des corrigés succincts :
Corrigé février 2004 partie 1 et Corrigé février 2004 partie 2et Corrigé février 2005 partie 3
Corrigé février 2005 partie 1 et Corrigé février 2005 partie 2
Vous pouvez consulter le sujet d'examen de la première session de l'année 2003, ainsi que son corrigé. Il existe également une version pdf du sujet (160 Ko), comme du corrigé (200 Ko).
Vous pouvez consulter le sujet d'examen de la première session de l'année 2002, ainsi que son corrigé.
Trois exercices ne sont pas dans le livre et sont disponibles ici en version pdf: Simulation de pointeurs, arbres binaires de recherche et arbres AVL.
Il est également possible de télécharger un fichier contenant l'ensemble des fichiers sources de ces démonstrations, en version zippé. Il suffit ensuite de le dézipper pour retrouver les sources dans un répertoire S_Demos, ainsi que ses sous répertoires. Un script (compile.sh) permet ensuite de les compiler sous Unix, Linux ou sous MacOS X.
Cette démonstration a surtout pour but de présenter un type abstrait en tant que boîte noire, sur laquelle on effectue des opérations. Les effets d'une opération de modification du type n'est visible que par les opérations spécifiques d'observation du type.
Cette démonstration montre le fonctionnement de 6 tris, parmi les plus importants. Elle tente de montrer pour chacun d'eux la complexité en terme de comparaisons ou en terme de transferts. Dans le cas du tri par tas, l'animation permet de suivre l'évolution de la structure arborescente qui est cachée dans l'algorithme.
Nous trouvons ici de façon classique la recherche séquentielle et la recherche dichotomique. De plus une animation particulière montre l'ensemble des opérations d'adjonction et de suppression dans un tas, complétant ainsi ce qui a été vu dans le tri par tas.
Cette démonstration présente le fonctionnement des arbres AVL, en dessinant en permanence l'arbre avec les déséquilibres en tout nœud. Les trois opérations fondamentales sont montrées: positionnement, adjonction et suppression.
Cette démonstration est analogue à celle sur les arbres AVL, mais pour des arbres balancés d'ordre 2 ou 3.Ici encore, on s'intéresse aux trois opérations fondamentales: positionnement, adjonction et suppression
Le support de cours de cette demi-valeur est le livre de Christian Carrez, "Structures de données en Java, C++ et Ada95", paru chez Masson en 1997. Ce livre est associé à un CD-Rom qui contient les sources des modules présentés dans le livre, ainsi qu'une démonstration interactive des algorithmes de tri principaux. Cette démonstration est reprise ici avec quelques modifications. Elle est complétée par des démonstrations interactives de la recherche dans une liste contiguë, ainsi que des opérations sur les arbres AVL ou sur les arbres balancés.
Ces démonstrations nécessitent une machine virtuelle Java. Certains navigateurs anciens ne permettent pas de les exécuter correctement.
Il est également possible de télécharger un fichier contenant l'ensemble des classes de ces démonstrations, et de le désarchiver. Vous pouvez ensuite ouvrir l'un des fichiers "Tables.html", "Tri.html", "Recherche.html", "AVL.html" ou "B-Arbre.html" avec votre navigateur favori.
La bibliothèque des modules Ada décrits dans le livre peut être téléchargée.