Informatique théorique

Articles

ALGORITHMIQUE

Écrit par :  Philippe COLLARD, Philippe FLAJOLET

L'objet de l'algorithmique est la conception, l'évaluation et l'optimisation des méthodes de calcul en mathématiques et en informatique. Un algorithme consiste en la spécification d'un schéma de calcul, sous forme d'une suite d'opérations élémentaires obéissant à un enchaînement déterminé. Le terme d'algorithme tire lui-même son origine d ...  Lire la suite

COMPLEXITÉ, mathématique

Écrit par :  Jean-Paul DELAHAYE

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 ...  Lire la suite

INFORMATION THÉORIE DE L'

Écrit par :  Henri ATLAN, Jean-Paul DELAHAYE, Étienne KLEIN

Quand on parle d'information, on pense souvent « information ayant une certaine valeur », ou « information pouvant servir à... ». Existe-t-il une théorie générale de l'information ? La théorie de l'information de Shannon (1949) a souvent été présentée comme cette théorie attendue. On admet aujourd'hui que les résultats qui en ont été tirés en biol ...  Lire la suite

INFORMATIQUE - Principes

Écrit par :  Jacques HEBENSTREIT

Le traitement de l'information, au sens large, forme une part importante de l'activité humaine et elle est aussi ancienne que l'homme lui-même. L'analyse de cette activité, qui est l'objet de l'informatique, a conduit à distinguer la manipulation des connaissances, ou syntaxe, du contenu des connaissances, ou sémantique, et a permis de montrer qu' ...  Lire la suite

ITÉRATION, mathématique

Écrit par :  Jean-Paul DELAHAYE, Universalis

Itérer signifie recommencer, faire à nouveau. Construire les nombres entiers peut être vu comme l'opération consistant à partir de zéro à itérer indéfiniment l'ajout d'une unité. Plus généralement, en mathématiques, lorsqu'une fonction ou opération est disponible, il est fréquent d'en envisager l'itération, celle-ci conduisant soit à de nouvelles ...  Lire la suite

KOLMOGOROV THÉORIE DE LA COMPLEXITÉ DE

Écrit par :  Jean-Paul DELAHAYE

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 ...  Lire la suite

TURING MACHINE DE

Écrit par :  Bernard PIRE

Dans l'article « On computable numbers, with an application to the Entscheidungsproblem », publié en 1936 dans les Proceedings of the Mathematical Society, Alan Mathison Turing (1912-1954) montre qu'il existe des nombres définissables qui ne sont pas calculables. Cela implique qu'il n'existe pas de solution au célèbre problème de la décis ...  Lire la suite