//img.uscri.be/pth/f215409ddf89089a9821c3b9fe7c5502d30a3dc5
Cette publication ne fait pas partie de la bibliothèque YouScribe
Elle est disponible uniquement à l'achat (la librairie de YouScribe)
Achetez pour : 24,99 € Lire un extrait

Téléchargement

Format(s) : PDF

avec DRM

Algorithmes et structures de données génériques - 2ème édition

De
352 pages

Ce livre s'adresse aux lecteurs ayant déjà acquis les concepts de base de la programmation. Les algorithmes sont écrits en C et présentés de manière complète et concrète sur de nombreux exemples. La programmation en C utilise cependant les concepts de la programmation objet. Le passage à C++ ou Java peut se faire sans problème. Plus de 160 figures et de nombreux exercices corrigés complètent les diverses notions présentées. Enfin, des compléments sont proposés sur le Web.

Voir plus Voir moins
Avantpropos
Ce livre suppose acquis les concepts de base de la programmation tels que les notions de constantes, de types, de variables, de tableaux, de structures, de fichiers et de découpage en fonctions d’un programme. Il présente des notions plus complexes très utilisées en conception de programmes performants sur ordinateur. Le chapitre 1 introduit la notion de récursivité des procédures et de récursivité des données conduisant à la notion d’allocation dynamique et de pointeurs. Il introduit ensuite la notion de découpage d’une application en modules communiquant grâce à des interfaces basées sur des appels de fonction. Le module devient un nouveau type de données: l’utilisateur du module n’accède pas directement aux données du module qui sont masquées et internes au module. On parle alors d’encapsulation des données qui sont invisibles de l’extérieur du module. Le type ainsi défini est un type abstrait de données (TAD) pour l’utilisateur qui communique uniquement par un jeu de fonctions de l’interface du module. Cette notion est constamment mise en appli-cation dans les programmes de ce livre. Le chapitre 2 présente la notion de listes, très utilisée en informatique dès lors que l’information à gérer est sujette à ajouts ou retraits en cours de traitement. Un module est défini avec des opérations de base sur les listes indépendantes des applications. Des exemples de mise en œuvre sont présentés, ainsi que des variantes des listes (circu-laires, symétriques) et des mémorisations en mémoire centrale ou secondaire (fichiers). Le chapitre 3 définit la notion d’arbres (informations arborescentes). La plupart des algorithmes utilisent la récursivité qui s’impose pleinement pour le traitement
X
Avantpropos
des arbres. Les algorithmes sont concis, naturels, faciles à concevoir et à comprendre dès lors que le concept de récursivité est maîtrisé. De nombreux exem-ples concrets sont donnés dans ce but. La fin du chapitre présente les arbres ordonnés (les éléments sont placés dans l’arbre suivant un critère d’ordre) pouvant servir d’index pour retrouver rapidement des informations à partir d’une clé. En cas d’ajouts ou de retraits, on peut être amené à réorganiser la structure d’un arbre (le rééquilibrer) pour que les performances ne se dégradent pas trop. Le chapitre 4 traite de la notion de tables : retrouver une information à partir d’une clé l’identifiant de manière unique. Plusieurs possibilités sont passées en revue en précisant leurs avantages et leurs inconvénients. Plusieurs techniques de hachage (hash-coding) sont analysées sur des exemples simples. Le chapitre 5 est consacré à la notion de graphes et à leurs mémorisations sous forme de matrices ou de listes d’adjacence. Il donne plusieurs algorithmes permet-tant de parcourir un graphe ou de trouver le plus court chemin pour aller d’un point à un autre. Là également récursivité et allocation dynamique sont nécessaires.
Les algorithmes présentés sont écrits en C et souvent de manière complète, ce qui permet au lecteur de tester personnellement les programmes et dejouer avecpour en comprendre toutes les finesses. Jouer avec le programme signifie être en mesure de le comprendre, de faire des sorties intermédiaires pour vérifier ou expliciter certains points et éventuellement être en mesure de l’améliorer en fonction de l’application envisagée. Les programmes présentés font un minimum de contrôles de validité de façon à bien mettre en évidence l’essentiel des algorithmes. Les algorithmes pourraient facilement être réécrits dans tout autre langage autorisant la modularité, la récursivité et l’allocation dynamique. Le codage est secondaire ; par contre la définition des fonc-tions de base pour chaque type de structures de données est fondamentale. Chaque structure de données se traduit par la création d’un nouveau type (Liste, Nœud, Table, Graphe) et de son interface sous la forme d’un jeu de fonctions d’initialisation, d’ajout, de retrait, de parcours de la structure ou de fonctions plus spécifiques de la structure de données. Des menus de tests et de visualisation permettent de voir évoluer la structure. Ils donnent de plus des exemples de mise en œuvre des nouveaux types créés.
Les programmes sontgénériquesdans la mesure où chaque structure de données (liste, arbre, table, etc.) peut gérer (sans modification) des objets de types différents (une liste de personnes, une liste de cartes, etc.). L’ensemble des notions et des programmes présentés constitue une boîte à outils que le concepteur de logiciels peut utiliser ou adapter pour résoudre ses problèmes.
Certains des programmes présentés dans ce livre peuvent être consultés à l’adresse suivante : www.iut-lannion.fr/MD/MDLIVRES/LivreSDD. Vous pouvez adresser vos remarques à l’adresse électronique suivante :
Michel.Divay@univ-rennes1.fr
D’avance merci.
Michel Divay
1