Informatique théorique

Articles

• PRIX ABEL 2021

  • Écrit par Bernard PIRE
  • 1 014 mots
  • 2 médias

  Le prix Abel, qui distingue chaque année un ou plusieurs mathématiciens pour leurs contributions exceptionnelles au développement des mathématiques, a été décerné en 2021 au Hongrois László Lovász et à l’Israélien Avi Wigderson. Dix-neuf ans après la création de ce « prix Nobel des...

• 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é....

• 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...

• 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...

• 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 ...

• 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...

• 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...

• 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...

Médias