Structures de données, algorithmes et objets
Cours de tronc commun du ``Pôle informatique ''

Responsables : Olivier Boissier , Jean Michel Moreau

Durée : 72 heures

Objectifs :

L'objectif principal de ce cours est d'apprendre à analyser un problème en le décrivant en termes algorithmiques et à maîtriser correctement les difficultés inhérentes à la programmation en un langage à objets. Les élèves doivent être capables à l'issue de ce cours de modéliser et d'analyser un problème, de programmer une solution et de la valider. Ceci suppose d'une part l'acquisition d'une méthodologie de programmation efficace et d'autre part la pratique d'au moins un langage. Le langage C++ a été retenu. Ce cours s'organise autour de deux axes :

Mise en oeuvre d'une démarche raisonnée pour l'analyse, la conception et la réalisation de logiciels,
Etude des structures de données et des algorithmes fondamentaux qui sont à la base d'une grande partie des réalisations informatiques actuelles.

Ce cours ne nécessite aucun prérequis en informatique autre que les enseignements suivis en classes préparatoires. Il vise à donner à un ingénieur généraliste la base de connaissances et de savoir-faire indispensable pour utiliser efficacement l'informatique dans le cadre de son futur métier. Ce cours constitue également la base de connaissances indispensable pour l'ingénieur voulant se spécialiser en informatique soit dans le cadre des cours de 2ème et 3ème années de l'école, soit à l'issue de sa formation.

Contrôle

contrôle continu sur les TPs réalisés individuellement
prise en compte de la participation aux TDs,
projet d'analyse et de programmation en langage C++

Travaux dirigés, Corrigés

TP 9 : ``Implantation de TDAs par tableaux''.
TP 12 : ``Implantation de TDAs par pointeurs''.
.rcpp
.log

Lectures conseillées

Algorithmes et langages C/C++

A. Aho, J. Hopcroft, J. Ullman, Data Structures and Algorithms, Addison-Wesley, 1983. En français : Structures de données et Algorithmes. trad. par J.M. Moreau, InterEditions, 1987.
T. Budd, Classic Data Structures in C++, Addison-Wesley 1994.
T. Cormen, C. Leiserson, R. Rivest, Introduction to Algorithms, MIT Press, 1990, en Français "Introduction à l'algorithmique", traduction de X. Cazin, Dunod, 1994.
C. Froidevaux, M.C. Gaudel, M. Soria, Types de données et algorithmiques, EDISCIENCE International, 1994.
E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of data structures in C, Computer Science Press, 1993
Robert Sedgewick, Algorithms in C, Addison-Wesley, 1990. En Français : Algorithmes en langage C. trad. par J.M. Moreau, InterEditions, 1990.
Niklaus Wirth, Algorithms and Data Structures, Prentice-Hall, 1986.

Le langage C

S.P. Harbison, G.L. Steele Jr, C A Reference Manual 2nd Ed, Tartan Laboratories, Prentice-Hall Software series, 1987.
B.W. Kernighan, D. M. Ritchie, The C Programming Language 2nd Ed, Prentice-Hall, 1988.
Peter Van Der Linden, Expert C Programming, Deep C Secrets, Prentice Hall, 1994.

Le langage C++ et les objets.

James O. Coplien, Advanced C++ Programming Styles and Idioms, Addison Wesley, 1992.
S.L. Lippman, C++ primer, 2nd Edition. Addison Wesley, 1992. En français : L'essentiel du C++. trad. par K. Zizi, Addison Wesley, 1992.
G. Masini, A. Napoli, D. Cobret, D. Léonard, K, Tombre, Les langages à objets, InterEditions, 1989.
Bjarne Stroustrup, The C++ Programming Language, 2nd Ed., Addison Wesley, 1991.

Retour au début

Pour aller plus loin

Structures de données et algorithmes

Binary Search Tree Applets
Cours d'algorithmique de l'ISIA
Cours informatique de l'INSA,
Cours d'algorithmique de l'école polytechnique,
Design and Analysis of Algorithms of UC Irvine,
Exercices du livre de T. Cormen, C. Leiserson, R. Rivest, Introduction to Algorithms, MIT Press, 1990, en Français "Introduction à l'algorithmique", traduction de X. Cazin, Dunod, 1994.

Langage C

Langage C++ et programmation par objets