Objectif

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.

Contenu

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é.

Formules pédagogiques

Leçons magistrales, travaux pratiques, exercices.

Préalable(s)

INF11207