LI043(6) : Algorithmique

2e semestre
CM: Jeudi, 14h0013h30 à 16h00, salle 270F, Halle aux farines (enseignant P. Amsili)
TD: Jeudi, 09h00 à 11h00, salle 270F (enseignant Sylvain Caillou)
Premier CM 24 janvier 2008
Premier TD 31 janvier 2006
Pas de travaux dirigés la première semaine
Pas de CM les 28 février, et 13 mars, pas de TD le 14 février
Fin des cours: semaine du 14 avril
Les CM commencent à 13h30 à partir du 1er février.
Le CM du 6 mars est remplacé par un TD.

La conception de programmes informatiques de qualité nécessite aussi bien un travail sur l'organisation des actions, leur contrôle (algorithmique) qu'un travail sur les données : leur mode de codage, de stockage, représentation, etc. (structures de données).

L'objectif du cours est d'aborder ces deux aspects de la conception, en étudiant quelques grandes classes de problèmes identifiés et leurs solutions.

On s'intéressera dans chaque cas aux différentes méthodes de résolution de problème, en évaluant ces méthodes selon différents point de vue : efficacité (coût de stockage et de calcul), lisibilité, généralité, ré-utilisabilité...



 

Plan indicatif

  1. Introduction.
  2. Les tris
  3. Structures linéaires
    1. Types abstraits
    2. Listes
    3. Piles
    4. Files
  4. Mots et recherche de facteurs.
  5. Structures non linéaires (1) : les arbres.
    1. Terminologie et primitives
    2. Arbres comme structures de données
    3. Parcours
    4. Arbres comme structures de contrôle
    5. Le cas particulier des arbres binaires

Organisation (indicative) du cours

24/01/08 TD pas de TD la 1ère semaine
24/01/08 CM Ch1. Introduction (poly)
31/01/08 TD introduction
31/01/08 CM Ch2. Tris (1)
07/02/08 TD tris (1)
07/02/08 CM Ch2. Tris (2)
14/02/08 TD pas de séance
14/02/08 CM Ch3. Structures linéaires (1)
21/02/08 TD tris (2)
21/02/08 CM Ch3. Structures linéaires (2)
28/02/08 TD listes
28/02/08 CM séance annulée
06/03/08 TD listes, piles & files
06/03/08 CMTD TD de révision
13/03/08 TD Devoir sur table
13/03/08 CM séance annulée
20/03/08 TD Mots: premiers contacts
20/03/08 CM Ch4. Mots (1)
27/03/08 TD Mots et recherche de facteurs 1
27/03/08 CM Ch4. Mots (2)
03/04/08 TD Mots et recherche de facteurs 2
03/04/08 CM Ch5. Arbres (1)
10/04/08 TD Arbres 1
10/04/08 CM Ch5. Arbres (2)
17/04/08 TD Arbres 2
17/04/08 CM Cours supplémentaire
 

Contrôles

Modalités
  • Contrôle continu : un devoir sur table (mi-semestre, 30%), un devoir non surveillé (20%) et une épreuve écrite (session d'examen de mai, 50%).
  • Contrôle final : une épreuve écrite pendant la session d'examen de mai (100%). 
  • Session de rattrapage (juin.) : pour tous : une épreuve écrite pendant la session d'examen de septembre (100%). 
  • Aucune note n'est conservée entre les deux sessions
Calendrier
  • Devoir non surveillé facultatif
    Etude de complexité de l'algorithme KMP ou Boyer-Moore. Principe: implémenter l'un de ces algorithmes, en insérant dans le code des mesures du coût (compteurs de tours de boucles, compteurs de comparaisons...). Produire de façon aléatoire (au moins) plusieurs miliers de couples mot+facteur distincts, de façon à mesurer la complexité moyenne ; identifier aussi les cas les plus défavorables et la cas les plus favorables.
    On demande de rendre le code commenté, ainsi qu'une synthèse des mesures de complexité obtenues, et une discussion (1 page).
    Travail à rendre pour le Mardi 13 mai 2008 (possible sous forme electronique, format pdf exigé).
  • Devoir sur table n° 1
    Jeudi 13 mars 2008, 9h00-11h00, salle habituelle
  • Examen final et DST n° 2 : session de mai 2008
    Jeudi 22 mai 2008, 14h00-16h00, salle 470E
  • 2e session : juin 2008
    Jeudi 26 juin, 14h00-16h00, salle 124 (CdR)

Annales : voir ma page d'archives

 
 

    Bibliographie

    Il y a de nombreux excellents livres d'algorithmique, que nous ne listons pas ici. Comme point de départ, on peut proposer les ouvrages suivants (qui contiennent à leur tour les références nécessaires en la matière), qui nous servent de base à la préparation de ce cours.
    • Aho Alfred V. et Jeffrey D. Ullman : Concepts fondamentaux de l'informatique, Dunod, 1992.
    • Christine Froidevaux, Marie-Claude Gaudel et Michèle Soria : Types de données et algorithmes. McGraw-Hill, 1990.
    • Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest: Introduction to Algorithms. MIT Press, 1990. Traduction française disponible
Ma maison-page November 18 2008