Qu'est-ce que l'algorithmique ?

Qu’est-ce que l’algorithmique ?

On s’intéresse à l’activité de programmation d’un ordinateur qui permet de résoudre des problèmes d’une façon automatique. On se place à un niveau conceptuel dans lequel un problème quelconque, informatique ou non, est caractérisé par un ensemble de données d’entrée et des résultats attendus. On peut donc représenter ce niveau d’analyse par le schéma de la figure ci-dessous.

Exemple

On donne les ingrédients suivants :

Thym - laurier - persil - ail - huile - vinaigre - sel - poivre - citron et un brochet de trois livres. Préparer une marinade de brochet.

Dans cet exemple, le problème est représenté par les données : le thym, le laurier, ..., le brochet dont on connaît le poids et par le résultat attendu qui est un plat cuisiné : une marinade de brochet. Ce n’est pas (pas encore) un problème qui se pose habituellement en informatique, mais il se pose dans les mêmes termes.

Exemple

On demande de calculer, pour une année dont on donne le millésime, le jour de la semaine où tombe le premier mai.

Ici, les données sont constituées d’un millésime, comme 2005 par exemple. Le résultat attendu est un jour de la semaine, comme dimanche par exemple.

Dans ces exemples, le problème est constitué d’un jeu de données. Le résultat attendu doit être obtenu par des transformations à faire subir aux données ; c’est ce que représente la figure précédente.

Les problèmes auxquels on s’intéresse dans ce livre sont résolus à...

Structure du livre

Ce livre ne s’intéresse qu’à la machine abstraite, dans l’espace du problème, pour laquelle il étudie une algorithmique particulière : l’algorithmique impérative ou procédurale. Il est divisé en deux parties. La première regroupe les chapitres « Programmes directs » à « Récursivité ou itération ? ». C’est dans cette partie que sont abordées les notions d’algorithmique de base et la méthode de construction raisonnée d’un algorithme impératif. La deuxième partie s’étend des chapitres « Trier » à « Crypter ». On y cherche, cette fois, des solutions à des problèmes plus élaborés dans divers domaines du calcul automatique.

Le chapitre « Programmes directs » montre quelques exemples d’algorithmes empruntés au quotidien et tente de définir la nature des algorithmes étudiés dans cet ouvrage. On y précise, notamment, la distinction entre la spécification et la réalisation d’un algorithme et on montre que l’algorithmique proprement dite s’arrête là où commence la programmation. En particulier, résoudre un problème consiste à passer des données aux résultats attendus par la suite séquentielle des transformations à faire subir aux données. Cependant, la description de ces opérations peut s’exprimer de différentes façons et, en ce sens, l’algorithmique n’est pas la programmation. On aborde les notations qui seront utilisées pour exprimer des transformations sans contrôle du flot d’instructions. 

Le chapitre « L’alternative » étudie l’une des constructions fondamentales de l’algorithmique....

Public visé

Ce livre s’adresse d’abord aux débutants en programmation. À ce titre, il est plutôt destiné aux filières qui enseignent encore la programmation impérative procédurale, comme les Sections de Techniciens Supérieurs en informatique (STS) ou les formations aux Diplômes Universitaires de Technologie (DUT). Cependant, les méthodes abordées et les exemples étudiés peuvent intéresser tout étudiant qui a à connaître ou à pratiquer la programmation en général. Les élèves ingénieurs trouveront certainement de multiples sujets d’analyse à leur niveau, peut-être en étendant certains des exercices proposés.

Les étudiants déjà avancés pourront aborder ce livre en piochant, ici ou là, des exercices à résoudre. Cependant, ils devront commencer par rafraîchir leurs connaissances en revoyant d’abord attentivement le chapitre « Programmes directs » qui traite de la spécification et le chapitre « Itération » qui traite de la construction raisonnée d’une itération. Les débutants devront probablement étudier le livre linéairement, en suivant l’ordre des chapitres, au moins dans la première partie qui s’étend des chapitres...

Préface à la troisième édition

Cette troisième édition reprend les sujets étudiés dans les éditions précédentes ; ils restent les mêmes et le sont dans le même esprit, avec les mêmes objectifs et les mêmes méthodes.

Pour cette édition, certains des exercices dont l’édition précédente ne donnait que l’énoncé ont été résolus dans le texte. De nombreuses autres solutions d’exercices non résolus dans le texte sont dès à présent disponibles dans les éléments en téléchargement associés à cet ouvrage et proposés depuis la page Informations générales.

Tous les exercices résolus, dont les solutions étaient disponibles en libre téléchargement depuis la page Informations générales, ont été revus et modifiés. Ces modifications sont parfois cosmétiques : corrections des fautes d’orthographes, corrections de présentation... Cependant, beaucoup d’entre eux ont été modifiés plus profondément dans leur énoncé ou dans la présentation de la solution proposée. Enfin, des exercices sans solution dans l’édition précédente ont été résolus...