Notions avancées de structures de données, algorithmes et programmation

Département
Informatique théorique

Scolarité
Licence MI
Licence d'informatique

Ce cours aborde les points suivants :

méthodologie de construction de programmes par abstraction ;
types abstraits, profils de fonctions et signatures, constructeurs, sélecteurs, modificateurs et destructeurs, pré et post conditions, expression du comportement mutuel des opérations ;
modules de description, extensions, généricité ;
récursivité et suppression de la récursivité ;
expression des entrées-sorties et itérateurs ;
analyse de la complexité des algorithmes ;
stratégies algorithmiques classiques ;
implantation et programmation en langage impératif (C) ;
représentations concrètes par tableaux et pointeurs, et leur masquage ;
allocation de mémoire statique et dynamique, maîtrise des pointeurs ;
programmation en C ;
import/Export et compilation séparée ;
structures de données classiques ;
définition et représentation des piles, files, listes, listes ordonnées ;
tables, adressage calculé, associatif, indexé, partagé, hachage ;
graphes orientés et non orientés ;
algorithmes classiques de parcours de graphes en profondeur et en largeur ;
fermetures de relations binaires, algorithme de Warshall ;
recherche de plus court chemins, algorithme de Dijkstra ;
arbres binaires et généraux, forêts, dictionnaires, arbres équilibrés, arbres AVL, files de priorité ;
algorithmes sur les arbres, arbres de recouvrement ;
algorithmes de tri interne et externe ;
optimalité et complexité des algorithmes de tri ;
implantations concrètes et programmation en C.