Cours 2020-2021

Algorithmique [INFOB237]

  • 5 crédits
  • 22.5h+22.5h
  • 2e quadrimestre
Langue d'enseignement: Français
Enseignant: Schobbens Pierre

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, ...)

Disciplines

Analyse de systèmes informatiques

Co-requis

Techniques de programmation [INFOB233]

Méthodes d'enseignement

Les modalités d'enseignement et d'évaluation des unités d'enseignement ont été rédigées en fonction de la situation à la rentrée académique 2020-2021. Cependant, ces modalités pourraient faire l'objet de modifications en fonction de l'évolution de la crise sanitaire liée à la covid-19. Les étudiants seront informés de toute modification de la situation générale (passage à l'enseignement à distance partiel ou complet) par les autorités de l'UNamur tandis que les modifications propres à chaque unité d'enseignement leur seront communiquées par les enseignants, via webcampus

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

Mode d'évaluation

Les modalités d'enseignement et d'évaluation des unités d'enseignement ont été rédigées en fonction de la situation à la rentrée académique 2020-2021. Cependant, ces modalités pourraient faire l'objet de modifications en fonction de l'évolution de la crise sanitaire liée à la covid-19. Les étudiants seront informés de toute modification de la situation générale (passage à l'enseignement à distance partiel ou complet) par les autorités de l'UNamur tandis que les modifications propres à chaque unité d'enseignement leur seront communiquées par les enseignants, via webcampus

70% Examen écrit à livre ouvert. La question principale demande de résoudre efficacement un problème nouveau. Si nécessaire à distance sur Webcampus.
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'enseignement

Français

Lieu de l'activité

NAMUR

Faculté organisatrice

Faculté d'informatique
rue Grandgagnage 21
5000 NAMUR
T. 081725252
F. 081724967
secretariat.info@unamur.be

Cycle

Etudes de 1er cycle