Acquis d'apprentissage

L'étudiant sera capable de :
  • formaliser (spécifier) un problème à partir d'un énoncé ;
  • résoudre le problème de façon systématique pour proposer un programme correct et efficace, y compris ses structures de 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. Nous voyons d'une part des structures de données récursives: arbres, arbres rouges-noirs, listes, etc.; d'autre part, des méthodes systématiques de construction de programmes efficaces :
  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 et ses optimisations.
 
 
 
 
 

Table des matières

Partie 0. Rappels :

  1. Spécification par pré et et post-conditions, preuves par invariants et variants.
  2. Evaluation du temps d'éxécution.
  3. 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 et ses améliorations (propagation, branch-and-bound, ...)
 
 

Méthodes d'enseignement

Un cours magistral illustré de nombreux exemples, plus des travaux pratiques avec des devoirs. Un projet à remettre en fin de semestre.
 
 
 

Méthode d'évaluation

70% Examen écrit à livre fermé, sans ordinateur. La question principale demande de résoudre efficacement un problème nouveau. 
20% Projet à remettre en fin de semestre. Il ne peut pas être repassé en 2nde session.
10% Devoirs lors des TPs. Ne peut pas être repassé en 2nde session.
 
 
 
 
 

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 l'édition française).

 
 

Langue d'instruction

Anglais
Formation Programme d’études Bloc Crédits Obligatoire
Bachelier en sciences informatiques Standard 0 5
Bachelier en sciences informatiques Standard 2 5