Informatique fondamentale 2
Guilhem Jaber
[Link]@[Link]
http ://[Link]
1 / 19
Les premiers algorithmes
Calcul de division et de racine carrée dans la civilisation babylonienne
(2000-1600 av. n. è.)
Crible d’Ératosthène, algorithme d’Euclide dans la Grèce antique (300
av. n. è.) ;
Constructions à la règle et au compas dans la Grèce antique (300 av.
n. è.) ;
Résolution des équations du 2nd degrés (Al-Khwarizmi, 820 n.e.)
Origine du terme ”algorithme” à partir de la traduction latine de son
nom au 12ème siècle n.e. : Algorithmo de Numero Indorum
Un algorithme formalise une méthode de calcul effective
sur des objets mathématiques.
2 / 19
Méthode effective
Une méthode, ou procédure, M, est dite ”effective” (ou ”systématique” ou
”mécanique”) lorsque :
M est définie en termes d’instructions ;
M produira, si elle est exécutée sans erreurs, le résultat souhaité en un
nombre fini d’étapes ;
M peut (en pratique ou en principe) être exécuté par un être humain
sans l’aide d’aucune machine autre qu’un papier et un crayon ;
M n’exige aucune perspicacité, intuition ou ingéniosité de la part de
l’être humain qui applique la méthode.
Source : traduction de
[Link]
3 / 19
Algorithme
Un algorithme est une description finie d’une méthode effective, en
termes d’opérations élémentaires bien définies : des instructions.
On s’attend en général à ce qu’un algorithme soit :
une procédure déterministe : l’étape suivante est définie de manière
unique, s’il y en a une ;
une méthode qui produit toujours un résultat, quelle que soit l’entrée :
le calcul décrit par un algorithme se termine toujours.
4 / 19
Algorithme
Quels objets manipule un algorithme ?
⇝ Des objets mathématiques : nombres, figures géométriques,
expressions algébriques, . . .
Que calcule un algorithme ?
⇝ Une fonction mathématique sur ces objets
5 / 19
Toutes les fonctions mathématiques sont elles calculables
par des algorithmes ?
Question formulée au début du 20ème siècle par David Hilbert.
Nécessite de formaliser les notions d’algorithme et de modèle de
calcul.
6 / 19
Une interlude : automatiser le calcul
Au 17ème siècle de notre ère, les premiers dispositifs physique
permettant d’automatiser le calcul sont inventés :
La Pascaline (1642), conçue par Blaise Pascal pour effectuer
automatiquement des additions et soustractions, avec un système de
roues dentées.
Son amélioration par Gottfried Wilhelm Leibniz pour réaliser des
multiplications et divisions,
Ce sont les précurseurs des calculatrices mécaniques.
7 / 19
Programmer ces machines
Au 18ème siècle de notre ère, on conçoit la possibilité d’adapter ces
machines mécaniques pour réaliser un ensemble varié de taches :
métier à tisser Jacquard en 1804, utilisant des cartes perforées pour
automatiser la fabrication de motifs complexes.
Analytical Engine conçu par Babbage, et dont les premiers programmes
sont écrits par Ada Lovelace (1837).
8 / 19
Analytical Engine
Machine mécanique programmable conçue par Babbage en 1837 ;
Programmes écrits par Ada Lovelace pour calculer les nombres de
Bernoulli :
9 / 19
Modèles de calcul
La notion de modèle de calcul émerge dans la première moitié du 20ème
siècle, pour formaliser les méthodes effectives réalisable par l’être humain,
et par les dispositifs mécaniques conçus depuis deux siècles.
Entre 1930 et 1936 des définitions formelles de modèle de calcul sont
fournis :
Kurt Gödel et Jacques Herbrand introduisent les fonctions
µ-récursives.
Alonzo Church introduit le λ-calcul.
Alan Turing introduit les machines de Turing.
10 / 19
Thèse de Church-Turing
Ces trois modèles définissent la même notion de fonction
calculable !
Thèse de Church-Turing : Chacun de ces modèle peut représenter
n’importe quelle méthode effective définie par un algorithme.
Chacun de ces trois modèles est universel.
11 / 19
Turing-complétude
On dit qu’un modèle de calcul M est Turing-complet si toute
méthode effective peut être décrite dans ce modèle.
La complétude de Turing est généralement prouvée par un encodage
d’un modèle de calcul universel standard dans M.
Par exemple en montrant que M peut représenter n’importe quel
calcul faisable par une machine de Turing.
12 / 19
Des fonctions non calculables
Ces modèles de calcul permettent d’exhiber des fonctions
mathématiques de N dans Bool qui ne sont pas calculables par un
algorithme.
En effet, chaque algorithme a une description finie, il ne peut donc
exister qu’un nombre infini dénombrable de fonctions calculables.
Or d’après un résultat célèbre de George Cantor, il existe un nombre
non dénombrable de fonction de N dans Bool.
Le premier exemple concret de telle fonction non calculable est fourni
par Alan Turing : le problème de l’arrêt.
La fonction qui prend en entrée une description d’une machine de
Turing et qui renvoie vraie si cette machine s’arrête et faux sinon, n’est
pas calculable.
Pour définir cette fonction, on doit fournir une technique d’encodage
d’une machine de Turing sous la forme d’entiers.
13 / 19
La théorie de la calculabilité
Ces premiers travaux vont donner lieu au développement d’une
théorie mathématique de ce qui est calculable.
De nombreux problèmes de décision seront montrés indécidables :
14 / 19
La théorie de la calculabilité
Ces premiers travaux vont donner lieu au développement d’une
théorie mathématique de ce qui est calculable.
De nombreux problèmes de décision seront montrés indécidables :
une formule mathématique est-elle prouvable ?
⇝ “Entscheidungsproblem” (Problème de la décision), formulé en 1928 par
David Hilbert et Wilhelm Ackermann.
⇝ Prouvé comme étant indécidable en 1936 par Alonzo Church et Alan
Turing indépendamment.
15 / 19
La théorie de la calculabilité
Ces premiers travaux vont donner lieu au développement d’une
théorie mathématique de ce qui est calculable.
De nombreux problèmes de décision seront montrés indécidables :
une formule mathématique est-elle prouvable ?
⇝ “Entscheidungsproblem” (Problème de la décision), formulé en 1928 par
David Hilbert et Wilhelm Ackermann.
⇝ Prouvé comme étant indécidable en 1936 par Alonzo Church et Alan
Turing indépendamment.
une équation diophantienne (un polynôme à coefficients entiers)
a-t-elle une solution entière ?
⇝ “10ème problème de Hilbert” lors du congrès de mathématique de Paris
en 1900.
Prouvé comme étant indécidable en 1970 par Yuri Matiyasevich (se
basant sur des travaux de Martin Davis, Hilary Putnam and Julia
Robinson).
16 / 19
Une prolifération de modèles de calcul
Circuits booléens
Fonctions récursives
Systèmes de réécriture
Machines de Turing
Automates cellulaires
λ-calcul
Logique des combinateurs
Réseaux de neurones artificiels
Automates à pile
Grammaires formelles
Langage de programmation
Comment les comparer ?
17 / 19
Théorie de la complexité
La théorie de la complexité étudie les aspects ”pratiques” de la
calculabilité.
Combien de temps et d’espace mémoire seront
nécessaires pour le calcul d’une fonction calculable ?
Classification des problèmes en fonction de leur utilisation des
ressources de temps et d’espace.
Notion de classe de complexité : LOGSPACE, P, NP, PSPACE, PH,
EXPTIME
Problème complet : NP-complétude
18 / 19
Organisation du module
Cinq chapitres :
λ-calcul
Automates à pile
Machines de Turing
Calculabilité
Complexité
Trois intervenants :
Guilhem Jaber
Matthieu Perrin
Guillaume Fertin
19 / 19