Questions introductives

 


Maintenant reste plusieurs points qu'ils demandent des explications.

Comment calcule t-on la compléxité d'un algorithme ?
On évalue les performances (aspect quantitatif de la complexité) d'un algorithme, mais ces performances ne dépendent-elles pas de la machine ?
Mise à part la notion quantitative de la compléxité, existe t-il des notions qualitatives ? si oui lesquel ?
Qu'entend-on par machine ?
Peut-on modéliser une machine 'universelle' abstraite de manière à rendre compte des problèmes calculables indépendante des performances des machines à une époque donnée?
Un problème calculable par une machine est-il faisable (tractable) ?


Dans le schéma ci-dessous on a voulu grap^hiquement distinguer quelques un des domaines connexes à la complexité.

Dans celui-ci MT désigne une Machine de Turing. C'est ce type de machine universelle que nous étudierons.

D'autre part on rappelle que la définition d'un problème est constituée de 2 parties:

1. La description de la représentation finie des éléments d'un ensemble fini ou infini dénombrable (un ensemble infini est dénombrable si est il existe une bijection entre lui est l'ensemble des entiers naturels N).

2.Un énoncé portant sur les éléments de cet ensemble.


Plus précisement:

La notion de calculabilité s'applique aux fonctions; ie une fonction est calculable ou pas.

La notion de décidabilité s'applique à des problèmes; ie un problème est décidable ou pas.