Algorithmique et structures de Données

Préface : L’auteur Dr BESSAA Brahim est maître de conférences à l’Université des Sciences et de la Technologie Houari Boumediene. Il enseigne l’algorithmique au département d’informatique depuis plusieurs années. Ce livre d’algorithmique s’adresse principalement aux étudiants de 2ème année licence en informatique, mais aussi à tous ceux qui auront à développer des programmes informatiques au cours de leur scolarité ou dans leur vie professionnelle. L’auteur est un enseignant qui connaît parfaitement les attentes des étudiants et propose ici une approche intéressante. Plutôt que de présenter un cours avec quelques exercices, l’auteur a choisi de résumer le cours en retenant les éléments les plus pertinents suivi de plusieurs exercices avec solutions. La présentation de cet ouvrage est claire, les algorithmes sont décrits dans une notation algorithmique d’une grande simplicité et les exercices sont accompagnés de solutions choisies avec grand soin. Le lecteur peut facilement se familiariser et approfondir les notions rencontrées grâce aux nombreux exercices avec solutions de difficulté graduée. Pour des raisons pédagogiques, certaines solutions ont été traduites en langage C. Le langage C, est encore très utilisé aujourd’hui pour des raisons d’efficacité du code produit, de rapidité et aussi si on a des ressources de calcul limitées. Un enjeu pédagogique particulier est très bien défendu dans ce livre : celui d’écrire des algorithmes efficaces. La conception d’algorithmes est une tâche difficile qui nécessite une grande réflexion, c’est le moment où l’on cherche à trouver l’idée géniale, la structure cachée, celle qui va permettre de résoudre la question. Pour un même problème, il existe bien souvent plusieurs algorithmes qui conduisent à sa solution. Le choix du « meilleur » algorithme est alors généralement guidé par des critères d’efficacité. Ainsi, pour la majorité des exercices l’auteur propose différentes solutions en donnant la complexité théorique de chaque solution suivie d’une analyse permettant de tirer des conclusions sur leur efficacité. L’éventail des algorithmes présentés reposent sur les structures de données des plus simples (les tableaux statiques ou dynamiques et les listes chainées) aux plus sophistiquées (les arbres, les piles et les files et les tables de hachage). Notons aussi l’importance accordée aux différentes mesures de complexité qui permettent. d’approfondir entre autres l’étude de l’efficacité des algorithmes. Aussi, un concept indispensable à maitriser en algorithmique, abordé dans ce livre, est la récursivité. Elle permet de résoudre certains problèmes d’une manière simple et naturelle. Par exemple, indispensable pour parcourir simplement des structures arborescentes. La pensée algorithmique repose de manière forte sur une culture algorithmique, et celle-ci s’acquiert en utilisant des livres comme cet ouvrage qui je pense sera une référence incontournable. Avant propos : Cet ouvrage s’adresse aux étudiants du cycle licence informatique et des écoles d’ingénieurs. Le niveau de maîtrise attendu correspond à la seconde année de licence. Dans ce livre nous supposons que les concepts de base de l’algorithmique sont aquis, en effet, nous présentons ici des structures de données plus complexes. Le livre est organisé en six chapitres couvrant l’ensemble du programme de la deuxième année du cycle licence informatique. Dans chaque chapitre nous présentons un rappel de cours suivi d’une série variée d’exercices avec des corrigés détaillés présentés d’une manière pédagogique aidant l’étudiant à comprendre la solution et par fois nous donnons la traduction de la solution en langage C. Pour les programmes C, nous avons utilisé l’IDE Code::Blocks, donc il se peut que si vous utilisez d’autres compilateurs, on vous signale quelques erreurs de syntaxe. La majorité des programmes C présentés sont des fonctions, donc nous conseillons les étudiants de faire des manipulations avec des programmes utilisant ces fonctions afin de bien comprendre les solutions et éventuellement être en mesure de les améliorer en fonction des applications envisagées. Pour la syntaxe utilisée dans les solutions algorithmiques, nous avons gardé celle utilisé dans notre livre de première année (Exercices Corrigés d’Algorithmique, Edition Pages Bleues Internationales). Suivant les universités ou les écoles, il peut y avoir quelques différences de syntaxe, mais qui ne touchent pas à la logique et au fonds des solutions. Enfin, je tiens à présenter mes sincères remerciements à madame Chahra-zad IGHILAZA, une des spécialistes d’algorithmique à l’USTHB, pour sa profonde lecture du document avant son édition, ses conseils et ses corrections qui ont fait de ce livre ce qu’il est. Pour toutes vos remarques, vous pouvez nous contacter à l’adresse : bbessaa@yahoo.fr.