Informatique théorique

L'informatique théorique est l'étude des fondements logiques et mathématiques de l'informatique. C'est une branche de la science informatique et la science formelle. Plus généralement, le terme est utilisé pour désigner des domaines ou sous-domaines de recherche centrés sur des vérités universelles (axiomes) en rapport avec l'informatique. L'informatique théorique se caractérise par une approche par nature plus mathématique et moins empirique de l'informatique et ses objectifs ne sont pas toujours directement reliés à des enjeux technologiques.

Une représentation artistique d'une machine de Turing. Les machines de Turing sont un modèle de calcul.

De nombreuses disciplines peuvent être regroupées sous cette dénomination diffuse dont :

Histoire

Dans cette section, nous donnons une histoire de l'informatique théorique en nous appuyant sur différentes sources :

Années 1940
Alan Turing à l'âge de 16 ans.

Les logiciens Bertrand Russel, David Hilbert et George Boole furent des précurseurs de l'informatique théorique. Mais cette branche de l'informatique a surtout vu le jour à partir des travaux d'Alan Turing et Alonzo Church en 1936, qui ont introduit les modèles formels de calculs (les machines de Turing et le lambda calcul). Ils ont montré l'existence de machines universelles capables de simuler toutes les machines du même type, par exemple les machines de Turing universelles. En 1938, Claude Shannon montre que l'algèbre booléenne explique le comportement des circuits avec des relais électromécaniques. En 1948, Claude Shannon publie A Mathematical Theory of Communication, fondateur de la théorie de l'information. En 1949, il annonce les fondements de la théorie de la complexité des circuits booléens.

Années 1950
L'ENIAC (photo prise entre 1947 et 1955).

La programmation des ordinateurs de l'époque était difficile. Par exemple, il était nécessaire de brancher ou débrancher une centaine de câbles sur l'ordinateur ENIAC afin de réaliser une simple opération.

Une contribution importante des années 1950 est la création de langages de programmation comme FORTRAN, COBOL et LISP, qui offrent des constructions de haut-niveau pour écrire :

La théorie des langages et des automates est un sujet important dans les années 1950, car il permet de comprendre l'expressivité des langages informatiques et leur mise en œuvre. Les machines à états finis et les automates à pile sont formellement définis. Puis Michael Oser Rabin et Dana Stewart Scott étudient mathématiquement le pouvoir expressif et les limites de ces modèles.

Années 1960

En 1964, Noam Chomsky définit la hiérarchie de Chomsky. Plusieurs classes de langages (langages rationnels, langages algébriques, langages avec contextes, langages récursivement énumérables) correspondent à des types de machines théoriques différentes (automates finis, automates à pile, machine de Turing à mémoire linéaire, machine de Turing). Différentes variantes de ces classes de langages et machines sont étudiés.

Hartmanis, Lewis et Stearns et d'autres classifient les langages selon le temps et/ou la mémoire qu'il faut pour les calculer. Ce sont les balbutiements de la théorie de la complexité.

Années 1970

Durant les années 1970, la théorie de la complexité se développe. Les classes de complexité P et NP sont définis ; la NP-complétude est définie indépendamment par Stephen Cook et Leonid Levin. Richard Karp a démontré l'importance des langages NP-complets. La question P = NP est posée et les chercheurs conjecturaient que l'on pourrait la résoudre via la correspondance entre machines de Turing et circuits.

Se développent aussi les méthodes formelles pour vérifier les programmes. On définit des sémantiques formelles aux langages de programmation.

Se développement aussi des connections entre le modèle de base de données relationnelles et le calcul des relations, afin de réaliser des requêtes dans des bases de données de manière efficace.

Ces années ont été florissantes également en algorithmique. Donald Knuth a beaucoup influencé le développement de l'algorithmique ainsi que Aho, Hopcroft et Ullman.

Années 1980 et 1990

Les années 1980 et 1990 sont propices au développement du calcul parallèle et des systèmes distribués.

Portée du domaine

Il n'est pas facile de cerner précisément ce que l'on entend par « informatique théorique »[note 1]. Le terme renvoie plutôt à une façon d'aborder les questions informatiques sous un angle plus mathématique et formel, en faisant souvent abstraction des aspects plus pratiques de l'informatique. En ce sens, l'informatique théorique est parfois considérée comme une branche des mathématiques discrètes[note 2]. Ses objectifs se caractérisent généralement par une volonté d'identifier en principe les possibilités et les limites des ordinateurs.

Le Special Interest Group on Algorithms and Computation Theory (SIGACT), regroupement affilié à l'Association for Computing Machinery (ACM) et voué au soutien à la recherche en informatique théorique en donne une définition assez large[4] qui comprend des domaines aussi divers que l'algorithmique et les structures de données, la théorie de la complexité, le parallélisme, le VLSI, l'apprentissage automatique, la bio-informatique, la géométrie algorithmique, la théorie de l'information, la cryptographie, l'informatique quantique, la théorie algorithmique des nombres et de l'algèbre, la sémantique des langages de programmation, les méthodes formelles, la théorie des automates et l'étude de l'aléatoire en informatique.

Les chercheurs en informatique théorique français sont regroupés au sein du GdR Informatique Mathématique[5] et adhèrent à l'Association française d'informatique fondamentale, membre de la Société informatique de France au niveau français et membre de l'EATCS au niveau européen.

La définition donnée par ACM SIGACT est à la fois trop restreinte en ce que la liste n'est pas exhaustive[note 3] et trop large puisque plusieurs des domaines mentionnés ne sont pas uniquement axés sur des enjeux purement théoriques.

Algorithmique

Cette discipline tente de découvrir, d'améliorer et d'étudier de nouveaux algorithmes permettant de résoudre des problèmes avec une plus grande efficacité.

Méthodes formelles

Certains programmes sensibles nécessitent une parfaite fiabilité et de ce fait des outils mathématiques à mi-chemin entre l'algorithmique, la modélisation et l'algèbre sont développés afin de permettre de vérifier formellement les programmes et algorithmes.

Théorie de l'information

La théorie de l'information résulte initialement des travaux de Ronald A. Fisher. Ce statisticien théorise l'information dans sa théorie des probabilités et des échantillons. Techniquement, « l'information » est égale à la valeur moyenne du carré de la dérivée du logarithme de la loi de probabilité étudiée. À partir de l'inégalité de Cramer, la valeur d'une telle « information » est proportionnelle à la faible variabilité des conclusions résultantes. En d'autres termes, Fisher met l'information en relation avec le degré de certitude. D'autres modèles mathématiques ont complété et étendu de façon formelle la définition de l'information.

Claude Shannon et Warren Weaver renforcent le paradigme. Ingénieurs en télécommunication, leurs préoccupations techniques les ont conduits à vouloir mesurer l'information pour en déduire les fondamentaux de la Communication (et non une théorie de l'information). Dans Théorie Mathématique de la Communication en 1948, ils modélisent l'information pour étudier les lois correspondantes : bruit, entropie et chaos, par analogie générale aux lois d'énergétique et de thermodynamique.

Leurs travaux complétant ceux d'Alan Turing, de Norbert Wiener et de Von Neuman (pour ne citer que les principaux) constituent le socle initial des « Sciences de l'information ». La théorie de l'information s'appuie principalement sur deux notions caractéristiques que sont la variation d'incertitude et l'entropie (« désordre » au sens d'absence d'ordre et donc d'information dans l'ensemble considéré, d'où l'indétermination). Déclinant ces principes et ceux d'autres sciences dures, les technologies s'occupent de la façon d'implémenter, d'agencer et de réaliser des solutions pour répondre aux besoins des sociétés humaines.

Certains chercheurs tentent de tirer des parallèles entre les concepts d'entropie en physique et d'entropie en informatique afin d'obtenir une formulation informatique de la cosmologie et de la réalité physique de notre monde qui, selon certains, pourraient trouver des clés dans des outils mathématiques que sont les automates cellulaires.

Informatique et information, un problème de terminologie

Certains ne voient dans l'informatique qu'une déclinaison technologique de l'automatisation des traitements (incluant la transmission et le transport) d'information et considèrent l'usage des termes « sciences de l'informatique » comme incorrects, ces mêmes préfèrent donc l'appellation « technologies de l'information et de la communication » parce qu'ils disent qu'elle recouvre mieux les différents composants (systèmes de traitements, réseaux, etc.) de l'informatique au sens large. Cette vision très restrictive du terme « informatique » n'est pas partagée par tout le monde et d'ailleurs beaucoup d'anglo-saxons envient la richesse du mot « informatique » et commencent à l'emprunter[6],[note 4].

Théorie des graphes

La théorie des graphes permet de modéliser de nombreux problèmes discrets : calculs de trajets, allocations de ressource, problèmes SAT... On peut citer le théorème des quatre couleurs comme résultat classique de cette branche de l'informatique.

Théorie de la complexité

La théorie de la complexité permet de classifier les algorithmes selon leur temps d'exécution asymptotique. C'est-à-dire selon leur comportement lorsqu'ils sont utilisés sur de très grandes données. C'est dans cette branche de l'informatique que se situe le célèbre problème P=NP par exemple.

Théorie de la calculabilité

La théorie de la calculabilité a pour objet la caractérisation des fonctions qu'un algorithme peut calculer. En effet, il est possible de montrer qu'il existe des fonctions qui ne sont pas calculables par un ordinateur, et il est dès lors intéressant de savoir lesquelles le sont. Le problème du castor affairé ou la fonction d'Ackermann sont des exemples classiques d'objets étudiés dans ce domaine.

Théorie des langages

La théorie des langages, souvent liée à la théorie des automates, s'intéresse à la reconnaissance d'ensemble de mots sur un vocabulaire donné. Elle est utilisée dans les algorithmes de traitement de la langue naturelle par exemple : traduction automatique, indexation automatique de documents, etc. ainsi que dans ceux des langues artificielles comme les langages de programmation : compilation, interprétation.

Logique pour l'informatique

La logique formelle est un outil fondamental de l'informatique, on y trouve notamment la théorie des types, le lambda calcul et la réécriture comme outils de base de la programmation fonctionnelle et des assistants de preuve.

Périodiques et journaux d'information (sélection)

Notes et références

Notes
  1. Par exemple, la présentation du journal « Théoretical computer science » ne décrit pas la discipline mais en donne simplement des caractéristiques et des objectifs.
  2. Comme cela se voit dans l'intitulé du groupe de recherche (GdR) du CNRS, « Informatique mathématique »
  3. La théorie des types, les assistants de preuve et la logique formelle n'y figurent pas
  4. L'association qui regroupe les départements de recherche et d'enseignement des universités en Europe s'appelle « Informatics Europe »

Références
  1. Pierre-Louis Curien, « Maurice Nivat, une grande figure », 1024 -- Bulletin de la Société Informatique de France, no 12,‎ , p. 87 -107 (lire en ligne)
  2. Claude Pair, « CRIN: The History of a Laboratory », IEEE Annals of the History of Computing, vol. 12, no 3,‎ , p. 159-166
  3. John E. Savage, Models of Computation : Exploring the Power of Computing, Addison-Wesley Longman Publishing Co., Inc., , 672 p. (ISBN 978-0-201-89539-1, lire en ligne)
  4. ACM SIGACT.
  5. GdR Informatique Mathématique
  6. « ACM Europe: Informatics education report »

Voir aussi
  • Lipton, Richard J. et Regan, Kenneth W., People, problems, and proofs. : Essays from Gödel’s lost letter: 2010, Berlin, Springer, , XVIII-333 p. (ISBN 978-3-642-41421-3, zbMATH 1305.68025).
  • Portail de l'informatique théorique
  • Portail de la logique
  • Portail des mathématiques
  • Portail de l’informatique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.