LI012 : Algorithmique

Mardi 14h30-16h30, salle J5, patio 14/25
Premier cours : mardi 8 février 2005, dernier cours le 18 mai.
Pas de séance les 1er mars, 15 mars, 12 avril, ainsi que 26 avril et 3 mai (vacances scolaires)
Séances supplémentaires : certains mercredis, 16h00-18h00, salle machine :
30 mars, 6 avril, 20 avril (DST), 18 mai

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. Ch1. Introduction. Poly, exos
  2. Ch2. Mots et recherche de facteurs. Poly, exos
    Voir aussi un exemple d'implémentation de KMP ICI
  3. Ch3. Les tris
    1. Introduction
    2. Tris élémentaires exos
    3. Tris efficaces poly 1, poly 2
    4. Cas particuliers
  4. Ch4. Structures linéaires
    1. Types abstraits
    2. Listes poly (curseur en Pascal)
      tp1, rliste.c, rliste.h, corrigé 1, tp2
    3. Piles poly
    4. Files
  5. Ch5. Structures non linéaires (1) : les arbres.
    1. Terminologie et primitives poly
    2. Arbres comme structures de données poly, exos
    3. Parcours poly1, poly2
    4. Arbres comme structures de contrôle poly, Exemple en C (n° 3 § 5.5.1), exos
    5. Le cas particulier des arbres binaires code pour TP, version complète
  6. Ch6. Structures non linéaires (2) : les graphes.
 

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 juin, 50%).
  • Contrôle final : une épreuve écrite pendant la session d'examen de juin (100%). 
  • Session de rattrapage (sept.) : pour tous : une épreuve écrite pendant la session d'examen de septembre (100%). 
  • Aucune note n'est conservée entre février et septembre
Calendrier
  • Devoir sur table n° 1 : mercredi 20 avril, 16h00-18h00, salle machine.
  • Devoir non surveillé, à rendre pour le 18 mai 2005.
    • Enoncé
    • Quelques indications pour générer aléatoirement des tableaux, sous la forme de code C.
    • Notes
  • Examen final (pour tous les étudiants) :
    mardi 14 juin, 14h30-16h30, salle J5 patio 14-25
  • Epreuve de septembre
    Vendredi 9 septembre, de 14h00 à 18h00, salle J5 patio 14/25.
Annales : voir ma page d'archives 		 


 

Bibliographie

L'ouvrage principal qui servira de référence à ce cours est (Froidevaux et al, 1990), qui contient le bon niveau de détail pour les calculs de complexité, et des annexes mathématiques utiles. Le plan suivi dans le cours ne correspond pas à l'ouvrage, mais il devrait être facile de s'y retrouver. Seuls les algorithmes de recherche de facteur (ch.2) n'y sont pas présentés, mais ils sont décrits dans de nombreux autres ouvrages, comme (Wirth 1987), et, sauf erreur, dans (Horowitz & Sahni, 1978).

Il y a de nombreux bons livres d'algorithmique, depuis les classiques comme (Wirth 1987), les textes d'Aho et al., jusqu'à des ouvrages français plus récents comme (Froidevaux et al 90, Courtin & Kowarski 1994).

  • Alfred Aho, John Hopcroft, Jeffrey Ullman : Structures de données et algorithmes, InterEditions, 1989.
  • Aho Alfred V. et Jeffrey D. Ullman : Concepts fondamentaux de l'informatique, Dunod, 1992.
  • Danièle Beauquier, Jean Berstel, Philippe Chrétienne : Éléments d'algorithmique, Masson, 1992.
  • Jacques Courtin, Irène Kowarski : Initiation à l'algorithmique et aux structures de données (2 volumes), Dunod, 1994-95.
  • Christine Froidevaux, Marie-Claude Gaudel et Michèle Soria : Types de données et algorithmes. McGraw-Hill, 1990.
  • Ellis Horowitz, Sartag Sahni : Fundamentals of Computer Algorithms, Pitman, 1978.
  • Niklaus Wirth : Algorithmes et Structures de données, Eyrolles, 1987.
  Tue Sep 13, 2005 Ma maison-page