En 1976, le livre Algorithms + Data Structures = Programs paraît : le postulat posé par ce titre est bien qu'un algorithme n'est rien s'il n'a pas de structure de données appropriée pour stocker ses données. On étudiera, dans cette introduction, tant les algorithmes principaux (tri, graphes – le bien connu Dijkstra mais aussi Bellman-Ford pour la recherche de plus court chemin) que des structures de données très fréquentes sur lesquelles viennent se construire des solutions élaborées à des problèmes complexes (pile, file, dictionnaire, etc.). De même, puisqu'étudier un algorithme ne permet pas de résoudre tous les problèmes, on envisagera quelques techniques fréquentes pour en trouver (chaque technique ayant ses spécificités et sa manière de vivre : certaines sont applicables partout mais avec des temps d'exécution importants, d'autres seront plus rapides mais demanderont un temps d'apprentissage plus élevé ainsi que certaines caractéristiques pour le problème).
On n'utilisera à cette fin aucun langage de programmation précis, plutôt du pseudocode, afin de se focaliser sur les algorithmes, non sur leur implémentation. On développera des outils d'analyse de ces algorithmes (complexité et correction) pour les appliquer dans les parties suivantes.
On suppose que le lecteur a déjà des connaissances en programmation de base (algorithmes et structures de données de base – liste liée, liste doublement liée, tableau, etc.) et souhaite découvrir plus d'algorithmes et de structures de données avec une approche plus théorique que pratique – seul du pseudocode anglais sera présenté.
Introduction aux algorithmes et aux structures de données
Partager