Objectifs pédagogiques

Apprendre quelques techniques algorithmiques de base : recherche exhaustive, algorithmes récursifs, diviser pour régner, programmation dynamique, algorithmes gourmands.

Savoir appliquer ces techniques à un certain nombre de problèmes standard sur des structures de données basiques : listes (tri), graphes (clôture transitive, chemins, plus petit arbre recouvrant), chaînes de caractères (recherche).

Apprendre à analyser la complexité asymptotique dans le pire des cas des programmes, y compris les programmes récursifs à travers l'utilisation de récurrences. Connaître différentes méthodes de résolution des récurrences et savoir quand celles-ci peuvent être appliquées (master theorem, méthode de l'arbre de récurrence, substitution de variables).

Apprendre les bases de la preuve de correction des programmes : triplets de Hoare, logique de Floyd-Hoare, invariants de boucle.