Introduction

$\bullet$ Informatique (mot inventé en 1962) signifie : traitement automatique de l'information.

Bases théoriques issue des mathématiques et dues aux plus grand mathématiciens des années 30.

30 :

Alonzo Church invente le $\lambda$-calcul sur lequel repose le langage LISP.
Alan Turing invente le modèle mathématique des machines de Turing, sur lequel repose le principe des ordinateurs.

39-45 :

Apparition des premiers calculateurs, à des fins militaires principalement pour coder et décoder les messages. Machine ENIGMA utilisée par les allemands pour coder les communications entre sous-marins. Machine BOMBE mise au point par Turing pour ``casser'' le codage d'ENIGMA.

Depuis les années 50 la montée en puissance des ordinateurs a été constante et parallèlement l'informatique s'est développée et présente plusieurs aspects (pas forcément distincts):

• théorique : étude des langages, mathématiques de l'informatique ...;
• machine : le ``hardware'';
• système : gestion des ressources, des réseaux, architecture ...;
• intelligence artificielle;
• infographie;
• internet;
• etc ...
  

$\bullet$ Programmation

Qu'est-ce que programmer ?

C'est écrire des instructions dans un langage particulier, compréhensible par un ordinateur, et à même de faire exécuter à cet ordinateur un certain nombre d'opérations en vue de traiter des informations.

Mais,

la tâche principale de l'élaboration d'un programme n'est pas décrire celui-ci dans un langage informatique donné.

On peut distinguer 5 grandes étapes dont les principales se font avec un papier et un crayon :

1.

compréhension du problème : analyse de celui-ci et décomposition en sous-problèmes plus simples;

2.

choix des structures des données pour représenter les objets que le problème doit traiter;

3.

mise en uvre des algorithmes utiliser pour résoudre les sous-problèmes;

4.

codage des algorithmes dans un langage de programmation donné;

5.

tests, corrections éventuelles, validation.

$\bullet$ Langages

Les premiers programmes étaient écrits dans le langage de la machine sur laquelle ils devaient être exécutés.

Langage machine ou langage de bas niveau = dépendant de la machine, nécessité de bien connaître le fonctionnement de la machine.

Langage de haut niveau = plus facile à programmer, ``indépendant'' de la machine.

50-60 :

Langage de programmation fonctionnelle LISP (LISt Processing), John Mc Carthy, MIT.
Langage de programmation impérative FORTRAN (FORmula TRANslation), John Backus, IBM

70, 80 et + :

Définition des langages :Basic, Pascal, C, Ada, Visual Basic, C++, PROLOG ...

80 :

Standardisation de LISP -> Common LISP

90 :

Java

Langages compilés (Pascal, Ada, C, ...) : une fois le programme écrit, un compilateur le traduit dans un langage compréhensible par la machine et produit un programme exécutable.

Langages interprétés (LISP, PROLOG, ...) : un interprète évalue au fur et a mesure les différentes expressions que vous donnez et renvoie chaque fois la réponse qu'il a calculée.

$\bullet$ SCHEME : langage interprété et fonctionnel.

C'est un dialecte de LISP défini dans un soucis de minimalité et de simplicité, seuls les concepts primordiaux de LISP ont été conservé.

C'est un langage fonctionnel. Programmer en SCHEME, c'est définir et composer des fonctions.

La notion de fonction en Scheme correspond à celle des mathématiques : une fonction prends des paramètres (on dit encore des arguments) en entrée et fournit un résultat en sortie.

Un fonction Scheme peut prendre 0 ou plusieurs paramètres en entrée mais elle renvoie toujours un unique résultat.

Les paramètres et les résultats peuvent être des nombres, mais aussi des chaînes de caractères, des booléens, des listes.

$\bullet$ Objectifs

Aborder la programmation par une approche fonctionnelle au travers du langage Scheme.

Les thèmes abordés seront :

La syntaxe de Scheme

Le mécanisme d'évaluation des expressions

La structure de liste

L'écriture de fonction récursives

La complexité des fonctions

L'abstraction des données

Les fonctions d'ordres supérieures