Complexité des algorithmes et notations asymptotiques. Résolution d'équations de récurrence.
Types abstraits et structures de données. Types de données élémentaires: piles, files, listes linéaires. Arbres: arbres binaires de recherche, arbres équilibrés. Tables: fonction de dispersion et adressage dispersé, résolution des collisions. Approche ``Diviser pour régner''. Programmation dynamique. Algorithmes voraces. Introduction à la notion de problème NP-complet.
Note importante: Ce cours est réservé aux
étudiant-e-s de la maîtrise en informatique (cours de
propédeutique ou cours d'appoint, donc hors-programme).