Notions avancées de structures de données, algorithmes et programmation/Présentation du cours

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.