À la fin de ce cours, l’étudiant sera en mesure : de faire des choix judicieux de structures de données et d’algorithmes basés sur une analyse de leur complexité; de concevoir et d’implémenter des algorithmes pour résoudre des problèmes tels la recherche, le tri et la compression de données; de résoudre des problèmes d’analyse d’algorithmes, de représentation et de compression de contenu multimédia.
Rôle des algorithmes et analyse asymptotique. Rappel des types abstraits de données et des structures de données de base : listes, piles, files, arborescences. Techniques de programmation telles la récursivité, et le retour-arrière. Introduction aux arbres binaires. Représentation des structures de données (listes générales et multilistes, arborescences, graphes). Algorithmes de tri (tri rapide, par monceau, pigeonnier) et de recherche (hachage, arbre de recherche). Représentation de données graphiques et d’images. Numérisation des signaux (quantification, échantillonnage, théorème de Nyquist). Algorithmes de compression sans perte (RLE, Huffman, LZW, codage arithmétique) et avec perte. Normes de compression d’images et de séquences vidéo.
Séances de laboratoire : analyser des contenus multimédias à l’aide d’outils logiciels. Concevoir et implémenter des applications permettant de solutionner des problèmes d’optimisation, de tri, de recherche et de codage.
- Enseignant: Stéphane Coulombe