Notions avancées de structures de données, algorithmes et programmation/Présentation du cours
Apparence
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.