LI0436 : Algorithmique

2e semestre
CM: Jeudi, 14h00 à 16h00, salle 065E, Halle aux farines (enseignant P. Amsili)
TD: Jeudi, 16h30 à 18h30, salle 065E (enseignant Grégoire Winterstein)
Premier CM 22 janvier 2009, premier TD 22 janvier 2009
CM (et TD) du 29 janvier supprimés en raison de la grève
Pas de CM le 05 mars (TD à la place)
Pas de CM ni de TD le 09 avril
CM et TD du 19 février supprimés en raison de la grève
CM et TD du 19 mars supprimés en raison de la fermeture de la Halle aux Farines
CM de rattrapage prévus les lundi 23/03 et 06/04, de 9h00 à 11h00, salle 270F, Halle aux farines
Séances de rattrapage après les vacances de printemps: Mercredi 29 avril : cours de 10h - 12h en salle 471 E Jeudi 30 avril, cours de 10h à 12h en salle 380 F ;
Jeudi 30 avril : TD de 16h - 18h en salle 472F ;
Jeudi 7 mai, cours et TD aux heures et salle habituelles.

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. 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 : les arbres

Organisation (indicative) du cours

     
22/01/09 CM Ch1. Introduction (poly)
22/01/09 TD Feuille d'exercices
29/01/09 CM Pas de séance (grève)
29/01/09 TD Pas de séance (grève)
05/02/09 CM Ch2. Tris (1)
   Algorithmes quadratiques (poly)
05/02/09 TD Feuille d'exercices
12/02/09 CM Ch2. Tris (2)
   Algorithmes efficaces : heapsort
12/02/09 TD Feuille d'exercices
19/02/09 CM

Pas de séance (grève)
19/02/09 TD Pas de séance (grève)
26/02/09 CM Ch2. Tris (3)
   Algorithmes efficaces : quicksort
Ch3. Structures linéaires
   Type de données abstrait
   Le type liste (définition fonctionnelle)
26/02/09 TD Feuille d'exercices
05/03/09 CM TD Feuille d'exercices (révision)
05/03/09 TD Devoir sur table
12/03/09 CM Ch3. Structures linéaires
   Le type liste (implémentation)
12/03/09 TD Feuille d'exercices
19/03/09 CM

Séance annulée (grève)
19/03/09 TD Séance annulée (grève)
23/03/09 CM Séance annulée (mauvaise information)
26/03/09 CM Ch3. Structures linéaires
   Le type pile (définition & implémentation)
   Le type file (définition & implémentation)
26/03/09 TD Feuille d'exercices
02/04/09 CM Ch4. Recherche de facteurs poly1 poly2
Ch5. Les arbres binaires
02/04/09 TD Feuille d'exercices
06/04/09 CM Séance de rattrapage annulée (voir après les vacances)
09/04/09 CM Pas de séance
09/04/09 TD Pas de séance
2930/04/09 CM Séance de rattrapage, salle 471E380 F, 10h-12h
Ch6. Les arbres
   Définition (poly)
   Parcours (poly)
30/04/09 TD Séance de rattrapage, salle 472F, 16h-18h Feuille d'exercices
07/05/09 CM Séance de rattrapage, salle 65E, 14h-16h
Ch6. Les arbres
   Arbres comme structure de contrôle
   Arbres comme structure de données
07/05/09 TD Séance de rattrapage, salle 65E, 16h30-18h30
 

Contrôles

Modalités
  • Contrôle continu : un devoir sur table (mi-semestre, 30%), un devoir non surveillé facultatif (20%) et une épreuve écrite (session d'examen de mai, 50%). Sans le devoir non surveillé, les pourcentages sont de 40% pour le DST et 60% pour l'examen final.
  • 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 sur table n° 1
    Jeudi 05 mars 2009, 16h30-18h30, salle habituelle
  • Devoir non surveillé facultatif:
    distribué (tardivement) le 19 mars, à rendre le 15 mai 2009 29 mai 2009
    • 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
  • Examen final et DST n° 2 : mardi 26 mai 2009, 9h00 à 11h00, salle 65E.
  • Deuxième session : lundi 15 juin 2009, 16h30 à 18h30, salle 65E.

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

    Liens
Ma maison-page June 16 2009