Contenu du cours

1.

Notions mathématiques de base: taux de croissance des fonctions et notations asymptotiques; équations de récurrence et techniques de résolution.

2.

Rappels sur les types abstraits de données et types de données élémentaires: piles et files, listes linéaires.

3.

Arbres: représentations; arbres binaires de recherche (fouilles, insertions, suppressions); arbres équilibrés (propriétés, rotations, insertions, suppressions).

4.

Tables: adressage direct vs. adressage dispersé; résolution des collisions (chaînage externe vs. adressage ouvert); fonctions de dispersion.

5.

Approche ``Diviser pour régner'': concepts de base; applications (fouille binaire, tri par fusion et/ou tri quicksort, sélection).

6.

Programmation dynamique: concepts de base; applications (multiplication de matrices, sous-séquence la plus longue).

7.

Algorithmes voraces: concepts de base; applications (ordonnancement, codes de Huffman, arbre de recouvrement minimal et/ou algorithmes sur les graphes).

8.

Introduction à la NP-complétude (si le temps le permet): temps polynomial vs. non-polynomial; classes de complexité; NP-complétude et réductibilité.