Structures de données et algorithmes

3,0 credits · Premier cycle

Se familiariser avec diverses stratégies de conception d'algorithmes et développer ses habiletés à évaluer et comparer différentes solutions (algorithmes et structures de données) d'un problème. Analyse de complexité d'algorithmes : analyse asymptotique, notation grand O, theta, omega ; pire cas, cas moyen ; relations de récurrence pour les algorithmes récursifs, théorème Master. Stratégies de conception d'algorithmes : force brute, diviser pour régner, résoudre par réduction ou par transformation du problème, algorithmes gloutons, etc. Étude et analyse comparative d'algorithmes classiques (tri, recherche, graphes). Étude et analyse comparative d'implémentations de types de données abstraits, en particulier le type table ou dictionnaire : arbres, arbres balancés (AVL, rouge-noir), adressage dispersé.