LI043(6) : Algorithmique

2e semestre
CM: Jeudi, 14h00 à 16h00, salle 105 îlot Jussieu (enseignant P. Amsili)
TD: Jeudi, 09h00 à 11h00, salle 11 (enseignante Lucie Barque)
Premier CM 25 janvier 2006
Premier TD 01 février 2006
à partir de la semaine du 26 février, les enseignements auront lieu (CM et TD) à la salle 277F Bât M3 A Halle 2ème Etage
Pas de CM les 8 février, 1er mars, 5 avril

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. Mots et recherche de facteurs.
  3. Les tris
  4. Structures linéaires
    1. Types abstraits
    2. Listes
    3. Piles
    4. Files
  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
  6. Structures non linéaires (2) : les graphes.

Organisation du cours

25/01/07 TD pas de TD la 1ère semaine
25/01/07 CM Ch1. Introduction (poly)
01/02/07 TD Introduction (exos)
01/02/07 CM Ch2. Mots et recherches de facteurs (poly)
08/02/07 TD Rech. de Facteurs (1) (exos)
08/02/07 CM séance annulée
15/02/07 TD Rech. de Facteurs (2) (exos)
15/02/07 CM Ch3. Tris (1)
22/02/07 TD Tris (1) (exos)
22/02/07 CM Ch3. Tris (2)
Distribution devoir non surveillé
01/03/07 TD Tris (2) (exos)
01/03/07 CM séance annulée
08/03/07 TD Tri arborescent et quicksort (exos)
08/03/07 CM Ch4. Structures linéaires (1)
 1. Listes
15/03/07 TD Listes (exos)
15/03/07 CM Ch4. Structures linéaires (2)
 1. Listes (implémentation chaînée)
22/03/07 TD Devoir sur table
22/03/07 CM Ch4. Structures linéaires (3)
 2. Piles
 3. Files
29/03/07 TD Listes, piles, files (exos)
29/03/07 CM Ch5. Structures non linéaires: arbres (1) (poly1, poly2)
05/04/07 TD Les arbres (1) (exos)
05/04/07 CM séance annulée
26/04/07 TD séance annulée
26/04/07 CM Ch5. Structures non linéaires: arbres (2) (poly)
03/05/07 TD+ Les arbres (2) (exos)
 

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é :
    distribué le 22 février, à rendre le 26 avril 2007
    • Enoncé
    • un exemple de code java pour générer des tableaux d'entiers aléatoires
    • Critères de correction :
      • Qualité du code
      • Qualité des résultats obtenus
      • Synthèse des résultats
      • Qualité de la discussion
    • Notes
  • Devoir sur table n° 1 : 22 mars 2007
  • Examen final et DST n° 2 : jeudi 10 mai 2007, salle et horaires habituels.
  • 2e session : mercredi 13 juin 2007, 17h. salle et horaire à confirmer.

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 June 13 2007