LI 012 : Algorithmes et Structures de données


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é…


Emploi du temps

Horaires : Mardi, de 14:00 à 16:00
Salle : 3, patio 42-43
Rythme : Semestriel (S2)
Premier cours Mardi 11 Février

Modalités de contrôle

  • Contrôle continu
    Un DST (30%), un DNS (20%), et un partiel en fin de semestre (50%)
  • Contrôle terminal
    Un examen en fin de semestre (100%)

Plan (sommaire et indicatif) du cours

  1. Introduction
  2. Les mots : algorithmes de recherche de facteurs.
  3. Les tris : algorithmes standards, en nlogn, récursifs.
  4. Structures linéaires (1) : listes
    • Exercices
    • Polycopiés : Exemples de code complet pour l'implémentation chaînée par curseur. Version de cette année (PS, PDF) ; voir aussi la version de l'an dernier, un peu différente (PS, PDF, TXT)
  5. Structures linéaires (2) : piles, files, etc.
  6. Structures non linéaires (1) : les arbres.
    • Polycopiés : Définitions des arbres (PS, PDF) ; Implémentations contigües (début) (PS, PDF)
  7. Structures non linéaires (2) : les graphes.

Contrôles

  • Devoir non surveillé n° 1 : distribué le 18 Mars, pour le 06 mai.
  • Devoir sur table n° 1 : mardi 01 avril, horaire et salle habituels
    Sans documents autorisés.
  • Examen final (pour tous les étudiants) : mardi 17 juin, de 14h00 à 17h00, salle 105 îlot Jussieu.

Bibliographie


http://www.linguist.jussieu.fr/~amsili/Ens03/LI012.html mer jun 4, 2003 Ma maison-page