COMPLEXITÉ, mathématique
Carte mentale
Élargissez votre recherche dans Universalis
Au cœur de l'informatique théorique, la théorie du calcul – ou théorie de la calculabilité – née dans la décennie 1930 des travaux de Kurt Gödel (1906-1978), Alan Turing (1912-1954) et Alonzo Church (1903-1995), répond à des questions sur ce qui est faisable dans l'absolu par le calcul avec un ordinateur. Elle énonce des résultats négatifs du type : il est impossible d'écrire un programme – aussi long et complexe soit-il – qui, chargé d'analyser d'autres programmes, repère ceux qui se perdent dans une boucle et ne se terminent jamais (indécidabilité de l'arrêt d'un programme). Ces preuves d'impossibilité sont importantes et une fine répartition entre ce qui est algorithmiquement faisable et ce qui ne l'est pas, est maintenant disponible.
1
2
3
4
5
…
pour nos abonnés,
l’article se compose de 3 pages
Écrit par :
- Jean-Paul DELAHAYE : professeur à l'université des sciences et technologies de Lille
Classification
Autres références
« COMPLEXITÉ, mathématique » est également traité dans :
ALGORITHMIQUE
Dans le chapitre « Échelle de complexité » : […] L' étude précédente permet de situer divers problèmes algorithmiques sur une « échelle de complexité » présentée dans le tableau . Les diverses mesures de coût utilisées (opérations booléennes, opérations élémentaires sur les nombres réels, comparaisonséchanges) n'étant pas strictement équivalentes, la définition d'une telle échelle se précise par l'introduction d'un modèle de la notion de calcula […] Lire la suite
CALCUL, mathématique
Dans le chapitre « Calculabilité et algorithmique » : […] Dans les années 1930 s'élabore, sous l'impulsion notamment du logicien Alan Turing, une théorie abstraite de la calculabilité, ce avant même l'avènement de l'ordinateur. Tout n'est pas calculable en mathématique et, par exemple, il ne saurait exister de procédé systématique permettant de distinguer par calcul, parmi l'infini des assertions mathématiques possibles, celles qui sont vraies : il s'agi […] Lire la suite
KHOT SUBHASH (1978- )
Le mathématicien indien Subhash Khot est un théoricien de l’informatique, spécialiste des problèmes d’optimisation dans ce qu’il est convenu d’appeler la théorie de la complexité. Né le 10 juin 1978 à Ichalkaranji, ville moyenne de l’État du Maharashtra dans l’ouest de l’Inde, Khot est le fils de deux médecins. Classé premier au concours d’entrée de l’Institut indien de technologie (I.T.T.) de Bo […] Lire la suite
KOLMOGOROV THÉORIE DE LA COMPLEXITÉ DE
La théorie de la complexité de Kolmogorov d'une suite numérique S est définie comme la taille, K(S), du plus court programme P qui, confié à une machine universelle (tout ordinateur contemporain en est une), produit la suite S. Cette notion est séduisante car elle synthétise en un seul nombre plusieurs mesures de complexité dont celle que propose la théorie de l'information de l'Américain Claude […] Lire la suite
ONDELETTES
Dans le chapitre « 3. Des algorithmes rapides » : […] L'une des raisons essentielles du succès rencontré par les méthodes fondées sur la transformation de Fourier tient dans l'existence d'algorithmes rapides de calcul qui lui sont associés (la fameuse F.F.T. [Fast Fourier Transform]). Or il s'est avéré que les transformations en ondelettes discrètes, pour peu que l'ondelette soit convenablement choisie, sont naturellement associées à des algorithmes […] Lire la suite
Voir aussi
Pour citer l’article
Jean-Paul DELAHAYE, « COMPLEXITÉ, mathématique », Encyclopædia Universalis [en ligne], consulté le 25 février 2020. URL : http://www.universalis.fr/encyclopedie/complexite-mathematique/