Le cours est divisé en trois grandes parties :
1. Analyse de programmes
- propriétés de base des algorithmes : terminaison, correction, complétude, complexité
- preuves inductives et invariants
- modèles de calcul de complexité
- décidabilité et complexité des problèmes algorithmiques
- complexité en pratique : pire cas, meilleur cas, algorithmes récursifs
- complexité en moyenne et algorithmes probabilistes
2. Paradigmes de conception d'algorithmes
- énumération exhaustive
- backtracking
- diviser pour régner
- programmation dynamique
- algorithmes gloutons
- transformations de problèmes
3. Structures de données
- tableaux et listes
- complexité amortie
- files et piles
- files de priorités, tas
- arbres binaires de recherche et arbres AVL
- tables de hachage
Les TPs permettront de mettre tout cela en pratique au travers de la conception et du développement d'un outil de compression de fichiers.
- Gestionnaire: Didier Lime