IntroductionIntroduction
Ce livre est le fruit d'une quinzaine d’années d'expérience dans le domaine de l'enseignement du cours d'algorithmique et de structures de données. C'est le cours tel qu'il est assuré à l'Institut National d'Informatique d'Alger (Ex C.E.R.I) pour les étudiants de deuxième année du cycle "ingénieur d'état en informatique".
Il constitue ainsi un support de cours pour des étudiants ayant déjà une première expérience dans le domaine de la programmation. Il est aussi destiné pour des professionnels qui veulent connaître plus aussi bien sur les structures de données en mémoire centrale que sur celles sur les mémoires externes, nommées par la suite structures de fichiers.
Objectif
du cours
Le cours couvre deux parties : les structures de données en mémoire centrale et les structures de fichiers.
Il
est clair qu'on ne peut entamer la seconde partie sans bien connaître la
première.
Deux aspects sont généralement traités : on écrit des algorithmes abstraits, c'est à dire on définit des modèles sur chaque structure de données. Ensuite, chaque modèle est implémenté par le choix d'une représentation mémoire et la traduction des opérations du modèle dans cette représentation.
Un mode de conception d'algorithmes est introduit : la récursivité. Sans ce mode de pensée on ne peut introduire certaines structures de données.
Contenu
La première partie présente les cours de structures de données. On y trouvera principalement les listes linéaires chaînées, les arbres et les techniques de hachage.
La deuxième partie présente les cours de structures de fichiers. On y trouvera principalement les structures de fichiers, les méthodes d'accés et les méthodes d'arbres.
La troisième et quatrième parties sont consacrées à la présentation d'un grand nombre d'exercices programmés dans les langages procéduraux PASCAL et C. Ces programmes constituent une sorte de manuel de référence pour les langages en question. En plus, la plupart des programmes existent en PASCAL et en C, ce qui permet de voir comment passer d'un langage à un autre. Nous avons bien commenté les programmes afin de les rendre plus clairs. Nous avons également présenté pour chaque programme les données et les résultats. Ces derniers sont parfois très détaillés pour permettre de suivre la trace, le plus souvent pour montrer la construction de la structure de données en question.Enfin, nous avons jugé utile de rajouter un ensemble d'annexes permettant de compléter le cours. Aussi, nous avons présenté le fomalisme algorithmique utilisé dans cet ouvrage et donné une brève présentation des langages de programmation PASCAL et C. Nous avons aussi présenté la O-notation qui est universelle et qui permet de mesurer des algorithmes.
Remerciements
Nous exprimons nos remerciements les plus chaleureux à nos collègues W.K Hidouci et A. Benhouhou pour leur apport et efficacité dans la lecture de certaines parties de ce manuscrit.