Objectifs
Permettre à l'étudiant de s'initier à la conception, à la description et au choix des structures d'information indépendamment d'un langage de programmation. Lui permettre de développer l'habileté à les implanter à l'aide de certains langages typiques.
Contenu
Introduction aux types abstraits, à leur formalisation axiomatique et à leur implantation. Critères d'évaluation des structures de l'information et de leurs implantations: tableau, enregistrement, chaîne de caractères, ensemble, pile, file, liste, arbres simples et équilibrés, graphe, adressage dispersé. Étude de la complexité de différents algorithmes de tri et de recherche avec l'accent mis sur le choix de la structure de données. Compromis espace versus temps. Ce cours comporte des séances obligatoires de travaux dirigés (TD) de deux heures par semaine.