Introduction

Qu'est-ce que l'algorithmique ?

L'algorithmique est une méthode pour chercher une solution fiable et efficace à un problème.

• Analyser le problème. Le réanalyser le problème si nécessaire.

• Déterminer la méthode de résolution.

• Formuler l'algorithme définitif.

• Traduire l'algorithme dans un langage de programmation adapté.

• Recommencer si nécessaire.

Nous avons de la chance : en français, on traduit computer science par « informatique », et non par « science de l'ordinateur ».

[Computer science] is not really about computers – and it's not about computers in the same sense that physics is not really about particle accelerators, and biology is not about microscopes and Petri dishes...and geometry isn't really about using surveying instruments. — Hal Abelson

Caml

Il faut cependant un langage de programmation pour écrire et essayer nos algorithmes : nous utiliserons Caml.

Classes de langages

Fonctionnel ? Impératif ?

On peut classer les langages en plusieurs « classes ».

1. Programmation impérative : produire une liste d'instructions qui, à partir d'une situation de la machine, définie par les données initiales, détermine les modifications successives des états de la mémoire pour délivrer le résultat demandé.

2. Programmation déclarative : décrire le rapport (les relations) qui existe entre les données et les résultats.

1. Langages fonctionnels : relations assimilées à des fonctions, traitement par combinaison de fonctions intermédiaires. (Lisp, Caml)

2. Langages logiques : relations décrites par des formules logiques, traitement par moteur d'inférence. (Prolog)

Compilation ou interprétation

Le code binaire est le seul que la machine puisse directement comprendre et donc réellement exécuter. Tout programme écrit dans un langage évolué devra par conséquent être d'abord traduit en code-machine avant d'être exécuté.

De ce fait, on peut produire du code exécutable de deux façons :

• La compilation : l'ensemble du programme est globalement traduit par un autre programme appelé compilateur et le code-machine produit est optimisé. Ce code-machine est ensuite exécuté autant de fois que l'on veut.

• L'interprétation : un programme (interpréteur) décode une à une les instructions (ou expressions) du programme source, puis les exécute (les évalue) au fur et à mesure.

Caml peut faire les deux. Dans ce cours, on l'utilise surtout en interprète : on tape une expression, elle est évaluée aussitôt. C'est la façon la plus simple d'essayer ce qu'on écrit. Les mêmes programmes peuvent aussi être compilés, avec ocamlc ou ocamlopt.