Introduction - Décidabilité, Théorie de la complexité

NB : informatique théorique

l'algorithmique "vue de loin", sans rentrer dans les détails de la programmation ...

"Considérons un algorithme permettant de résoudre ..."

• on obtient des résultats sur ce qu'il est possible programmer (ou pas)

• on obtient des résultats sur ce qu'il est probablement impossible de programmer efficacement

  • (conjecture P $\neq$ NP)

Définitions

• Problème = question qui se pose sur des entrées de certains types

  • ex : le problème SAT, satisfiabilité d'une formule booléenne

Problématique 1

Est-ce que tous les problèmes ont une solution algorithmique ?

(capable de traiter toutes les entrées)

C'est-à-dire sont Décidables

Divulgâchage 1 ...

NON : certains problèmes ne sont pas décidables (indécidable) : le problème de l'arrêt

... et donc inutile d'essayer de les résoudre

Problématique 2

Pour les problèmes décidables ...

Peut-on espérer les résoudre de manière "réaliste" ?

cf complexité d'un algorithme

On considère que les algorithmes de complexité temporelle polynomiale sont utilisables en pratique

Classification des problèmes

classes : P, Exp, NP, NP-difficile, NP-complet : classes un peu mystérieuses ...

Formalisé vers 1970 : Stephen Cook

Divulgâchage 2 ...

Conjecture : $P \neq NP$

• Un des problèmes du millénaire (1 million de dollar de récompense)

• Si c'est bien le cas, de nombreux problèmes ne peuvent pas être résolus en temps polynomial (par exemple SAT)

• Si ce n'est pas le cas, la communauté informatique internationale est d'un niveau pitoyable ...