Cours 1 : Qu'est-ce que l'informatique ?
Calculabilité
Il existe des choses que l'on sait spécifier sans savoir les calculer. Définir une machine (les formules à radicaux, la règle et le compas) permet de définir une calculabilité.
Turing
Machine de Turing
La machine de Turing (1936) définit une calculabilité. Il s'agit d'un ensemble de 5-uplets (E1,S1,E2,S2,M) signifiant : "Si la machine est dans l'état E1, que le symbole sur la bande, sous la tête de lecture, est S1, alors la machine passe en état E2, écrit S2 sur la bande, et bouge la tête de lecture dans le sens M". Exemple : 
          Bande : ....10110M0100101M1101011....
tête de lecture :       *

( Start,  M, Delete, M, -> )
( Start,  0, Start,  0, -> )
( Start,  1, Start,  1, -> )
( Delete, M, Rewind, M, <- )
( Delete, 0, Delete, 0, -> )
( Delete, 1, Delete, 0, -> )
( Rewind, M, Stop,   M, <- )
( Rewind, 0, Rewind, 0, -> )
( Rewind, 1, Rewind, 1, -> )
( Stop )
Exemple de la multiplication 3x5 en codage unaire 
 Bande : 111x11111
qui se transforme par une machine qui va bien en 
 Bande : 111111111111111
On sent que la machine est plus simple que si le codage avait été décimal...
Machine de Turing Universelle
On peut coder la desciption d'une machine M1 sur une bande... et consrtuire une machine M2 qui travaille là-dessus. M1 est une donnée... alors que c'est aussi la description d'une machine. Si la bande contient un codage de M1, puis
Si la bande contient un codage de M1, suivi du codage D d'une donnée sur laquelle M1 sait travailler :
Church
Church (le directeur de thèse de Turing) a défini en 1930 une calculabilité via le λ-calcul. Ils 'agit de réécriture, et non de modifier une bande par une suite d'instructions. Exemple:
Thèse de Church-Turing
La λ-calculabilité et la Turing-calculabilité sont les mêmes.
L'ordinateur
Calcule ce qui est Turing-calculable. Attention aux limitation de taille de bande (mémoire) et au nombre d'opération requis (temps de calcul). Ils définissent la complexité d'un algorithme.
La bande contient la descriptions de machines (i.e. programmes, i.e. logiciels), mais aussi les données sur lesquelles ces machines vont travailler. L'un de ces programmes à le statut particulier de système d'exploitation, il gère les ressources de l'ordinateur.
Les langages de programmation
L'idée est que la description de la machine de turing que comprend le processeur est illisible... On utilise un compilateur (un programme aussi) qui transforme du texte lisible par un humain en code binaire pour le processeur. Le texte lisible est assez formatté, c'est ce qui définit un langage de programmation.
Syntaxe et sémantique
La première ligne est du langage C, l'autre non. 
i=3*i++;
i=3*+i+;
... pourquoi ? C'est ce que définit la syntaxe. Qu'est-ce que fait le texte bien formé ? C'est ce que définit la sémantique.
Les langages impératifs
C'est le langage des recettes de cuisine. Une séquence d'ordres qui modifient l'état de quelque chose.
Les langages fonctionnels
Ils se basent sur la réécriture de formules, comme la calcul mathématique.
Les langages logiques
C'est bien plus utilisé qu'on ne le croit... C'est fait pour les systèmes experts de diagnostique, les systèmes de résolution de contrainte (faire un emploi du temps par exemple), mais surtout les makefile.
Exemple classique : 
Homme(Socrate)
Mortel(X) <= Homme(X)
On demande alors 
Mortel(Socrates) ?
                    true
Mortel(x) ?
                    x=Socrates
Exemple contemporain : Vous recevez des amis. Vous savez ce qu'ils aiment, et vous voulez préparer un plat qui contente tout le monde. 
Aime(Paul,  Puree)
Aime(Paul,  Crepes)
Aime(Pierre,Pizza)
Aime(Pierre,Rognons)
Aime(Pierre,Crepes)
Aime(Jean,  Pizza)
Aime(Jean,  Rognons)
Aime(Jean,  Crepes)

Repas(X) <= Aime(Jean,X) et Aime(Pierre,X) et Aime(Paul,x)

Repas(plat) ?
              plat = Crepes
Programmation Objet
Notion transversale aux types de langage, introduite pour ce cours dans le cadre de la programmation impérative.