Algo Les problemes problematiques.pdf

(59 KB) Pobierz
Les problèmes «problématiques» (1)
Rappel:
un problème (une tâche) sera dit
formalisable
s’il peut être exprimé sous la forme d’une association
entre les entrées et les sorties d’une machine de Turing.
Exemple:
Calcul de la parité d’un nombre
:
entrée:
le nombre à traiter (sous la forme d’une séquence binaire).
sortie:
1
ou
0
selon que le nombre est ou n’est pas pair.
Informatique II
Algorithmique
– 27 –
Les problèmes «problématiques» (2)
On va distinguer trois grandes familles
de problèmes problématiques:
• Les problèmes
non formalisables
• Les problèmes
non décidables
• Les problèmes
NP-complets
Informatique II
Algorithmique
– 28 –
Les problèmes non formalisables
Ce type de problème est plus fréquent
qu’on pourrait le penser
a priori.
Un problème peut être non formalisable:
parce qu’il est intrinsèquement vague
exemples:
la vie a-t-elle un sens ?
Dieu existe-il ?
parce qu’il est difficile d’obtenir un consensus sur sa
spécification précise (c'est le cas le plus fréquent).
exemple:
déterminer la santé financière d’une entreprise
Cette tâche ne paraît pas problématique
a priori...
mais elle est en fait difficile à formaliser (spécifier) précisément,
car plusieurs approches sont possibles, entre lesquelles les experts sont partagés.
Informatique II
Algorithmique
– 29 –
Les problèmes non décidables
Un des intérêts de l’introduction de la notion de
machine de Turing est qu’elle permet de
démontrer
que
l’on ne peut pas résoudre tous les problèmes
formalisables.
Ceci est important, car cela montre
les limites intrinsèques de l’informatique.
Les problèmes qui ne peuvent être résolus à l’aide d’une machine de Turing
(et donc, si l’on admet l’hypothèse de Church, qui ne peuvent être
résolus par aucune approche algorithmique) sont appelés
des problèmes
non décidables.
Exemple:
Ecrire un programme qui, pour tout programme
P,
accompagné de ses
données d’entrée
D,
permet de déterminer si l’exécution de
P
sur
D
termine
(après un nombre fini d’opérations).
Ce problème est appelé
le problème de la
terminaison des programmes.
Informatique II
Algorithmique
– 30 –
Problème non décidable: la terminaison (1)
Démontrons que le problème de la terminaison
d’une machine de Turing
T
sur des données d’entrée
i
est non décidable;
en d’autre termes, qu’on ne peut construire une machine
de Turing permettant de déterminer, pour toute machine de Turing
t
et toutes données d’entrée
i,
si
t(i)
termine après un nombre fini d’opérations.
(par l’absurde)
Supposons qu’une telle machine
T
existe:
T
est donc telle que:
T(i,j) =
{
1
si
T
i
(j)
termine
0
sinon
A partir de
T,
construisons alors la machine
T’
telle que:
T’(i)
termine
ssi
T(i,i)
=
0
Informatique II
Algorithmique
– 31 –

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin