Informatique théorique



ALGORITHMIQUE

  • Écrit par 
  • Philippe COLLARD, 
  • Philippe FLAJOLET
  •  • 6 652 mots
  •  • 3 médias

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 du nom du mathématicien persan Al Khwārizm […] Lire la suite

COMPLEXITÉ, mathématique

  • Écrit par 
  • Jean-Paul DELAHAYE
  •  • 1 626 mots

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 es […] Lire la suite

INFORMATION THÉORIE DE L'

  • Écrit par 
  • Henri ATLAN, 
  • Jean-Paul DELAHAYE, 
  • Étienne KLEIN
  •  • 3 063 mots

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 biologie ou en informatique ne sont pas à la mesure des […] Lire la suite

INFORMATIQUE - Principes

  • Écrit par 
  • Jacques HEBENSTREIT
  •  • 3 060 mots
  •  • 2 médias

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 […] Lire la suite

ITÉRATION, mathématique

  • Écrit par 
  • Jean-Paul DELAHAYE, 
  • Universalis
  •  • 830 mots

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 fonctions ou opérations, soit à des structures ou pr […] Lire la suite

KOLMOGOROV THÉORIE DE LA COMPLEXITÉ DE

  • Écrit par 
  • Jean-Paul DELAHAYE
  •  • 563 mots

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 […] Lire la suite

TURING MACHINE DE

  • Écrit par 
  • Bernard PIRE
  •  • 197 mots

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èm […] Lire la suite


Affichage 

Échelle de complexité

tableau : Échelle de complexité

tableau

Échelle de complexité. 

Crédits : Encyclopædia Universalis France

Afficher

Automate à nombre fini d'états

dessin : Automate à nombre fini d'états

dessin

Automate à nombre fini d'états. 

Crédits : Encyclopædia Universalis France

Afficher

Automate à pile de mémoire

dessin : Automate à pile de mémoire

dessin

Automate à pile de mémoire. 

Crédits : Encyclopædia Universalis France

Afficher

Échelle de complexité

Échelle de complexité
Crédits : Encyclopædia Universalis France

tableau

Automate à nombre fini d'états

Automate à nombre fini d'états
Crédits : Encyclopædia Universalis France

dessin

Automate à pile de mémoire

Automate à pile de mémoire
Crédits : Encyclopædia Universalis France

dessin