Acquis d'apprentissage

L'étudiant sera capable de :

  • formaliser un problème (spécifier) à partir d'un énoncé ;
  • résoudre le problème de façon systématique pour proposer un programme correct et efficace.
    • La correction résulte d'une preuve ;
    • L'efficacité s'évalue ici par la complexité asymptotique : le temps de calcul (et la mémoire) pour de grandes données.

Objectifs

Apprendre une démarche rigoureuse de construction de programmes efficaces: l'algorithmique.

Contenu

Toutes les méthodes reposent sur la démarche de spécification formelle, implémentation et preuve. L'évaluation de l'efficacité d'un problème est basée sur un calcul du temps d'éxécution et de consommation de la mémoire (théorie de la complexité) La récursion sert de base à ce cours.

Des méthodes systématiques de construction de programmes efficaces seront présentées:

  1. la méthode "diviser pour régner"
  2. les méthodes de mémorisation, dont la programmation dynamique
  3. la méthode gloutonne
  4. la méthode générer/tester (ou par force brute) et ses améliorations.

Pour mettre en oeuvre ces algorithme, on étudiera les structures de données récursives: arbres, arbres rouges-noirs, B-arbres, etc.

Table des matières

Partie 0. Rappels: Spécification par pré et et post-conditions, preuves par invariants et variants. Evaluation du temps d'éxécution. Récursion. 

Partie I. Méthodes de construction de programmes:

  1. la méthode "diviser pour régner" 
  2. les méthodes de mémorisation, dont la programmation dynamique 
  3. la méthode gloutonne 
  4. la méthode générer/tester (ou par force brute) et ses améliorations.

Partie II. Structures de données récursives:  listes, arbres, arbres rouges-noirs, etc.

 

Exercices

Les séances d'exercices sont organisées selon un triple perspective.

  1. Consolidation des prérequis:
    • écriture de spécifications;
    • construction d'algorithmes par la technique de l'invariant;
    • types abstraits (liste chaînée, liste doublement chaînée, arbre binaire,...).
  2. Appropriation des méthodes vues au cours théorique:
    • construction d'algorithmes par les différentes méthodes;
    • calcul de la complexité des algorithmes construits. 

Méthodes d'enseignement

Un cours magistral illustré de nombreux exemples, plus des travaux pratiques. Les étudiants sont également invités à faire des exercices à domicile. Un mini-projet récapitule la matière et prépare à l'examen.

Méthode d'évaluation

  1. Des interrogations en cours d'année (TP) comptent pour 10%.
  2. Un mini-projet à remettre en fin d'année (dernier jour de cours) compte pour 20%. Ces deux activités se font uniquement en 1ère session.
  3. L'examen écrit compte pour le reste (70%). Il peut être repassé en 2nde session (août) si nécessaire.

Sources, références et supports éventuels

Le cours suit une partie du livre: Introduction à l'algorithmique, de T. Cormen, C. Leiserson, R. Rivest, C. Stein (ed. Dunod pour la version française).

Langue d'instruction

Français
Formation Programme d’études Bloc Crédits Obligatoire
Standard 0 10
Standard 3 10