Théorie du calcul

La théorie du calcul peut être considérée comme la création de modèles variés en informatique. Elle utilise donc à la fois les mathématiques et la logique. Au cours du siècle dernier, elle s'est séparée des mathématiques et est devenue une discipline académique indépendante avec ses propres conférences telles que FOCS en 1960 et STOC en 1969, et ses propres prix tels que la médaille IMU Abacus (créée en 1981 sous le nom de prix Rolf Nevanlinna), le prix Gödel, créé en 1993, et le prix Knuth, créé en 1996.

Parmi les pionniers de la théorie de l'informatique, on peut citer Ramon Llull, Alonzo Church, Kurt Gödel, Alan Turing, Stephen Kleene, Rózsa Péter, John von Neumann et Claude Shannon.

Summarize Timeline Top Qs Fact Check

Grammaire	Langage	Automate	Règles d'inférence (contraintes)
Type 0	récursivement énumérable	machine de Turing	${\displaystyle \alpha \rightarrow \beta }$
Type 1	contextuel	automate linéairement borné	${\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }$
Type 2	non contextuel / algébrique	automate à pile	${\displaystyle A\rightarrow \gamma }$
Type 3	régulier	automate fini	${\displaystyle A\rightarrow a}$ et ${\displaystyle A\rightarrow aB}$

La théorie des automates est l'étude d’un type de machine abstraite permettant de formaliser des méthodes de calcul, et des problèmes résolubles par de telles machines. Ces machines abstraites sont appelées automates. Le mot « automate » vient du grec (Αυτόματα) qui signifie « quelque chose qui agit de manière autonome ». L'objet traité par un automate est un mot d'un langage. Les automates sont souvent classés selon la classe de langages formels qu'ils sont capables de reconnaître. La théorie des automates est donc étroitement liée à la théorie des langages formels^[5]. Les automates peuvent par exemple servir à prouver la calculabilité.

La théorie des langages formels est une branche des mathématiques qui s'intéresse à la description des langages comme un ensemble d'opérations sur un alphabet. Elle est étroitement liée à la théorie des automates, car ceux-ci sont utilisés pour générer et reconnaître les langages formels. Il existe plusieurs classes de langages formels, chacune permettant une spécification linguistique plus complexe que la précédente et chacune correspondant à une classe d'automates qui la reconnaît. Ces classes correspondent à la hiérarchie de Chomsky^[6]. Les automates étant utilisés comme modèles de calcul, les langages formels sont un mode de spécification privilégié pour tout problème devant être calculé.

La théorie de la calculabilité s’intéresse principalement à dans quelle mesure un problème peut être résolu par un ordinateur. Un résultat très utilisé de la théorie de la calculabilité est l’indécidabilité du problème de l’arrêt. En effet, l’affirmation que le problème de l’arrêt ne peut être résolu par une machine de Turing^[7] est un exemple de problème indécidable concret et facile à formuler, donc idéal pour d’éventuelles réductions.

Un autre résultat majeur est le théorème de Rice, qui stipule que pour toutes les propriétés non triviales, il est indécidable de savoir si une machine de Turing vérifie cette propriété (idem avec les fonctions partielles associées)^[8].

La théorie de la calculabilité est étroitement liée à la branche de la logique mathématique appelée théorie de la récursivité, qui supprime la restriction consistant à n'étudier que les modèles de calcul réductibles au modèle de Turing. De nombreux mathématiciens et théoriciens du calcul qui étudient la théorie de la récursivité confondent donc les deux^[9].

La théorie de la complexité examine non seulement si un problème peut être résolu sur un ordinateur, mais surtout avec quelle efficacité il peut l'être. Deux aspects majeurs sont pris en compte : la complexité en temps et la complexité en espace, qui correspondent respectivement au nombre d’étapes nécessaire pour effectuer un calcul et à la quantité de mémoire requise pour effectuer ce calcul.

Afin d'analyser le temps et l'espace requis par un algorithme donné, les informaticiens expriment le temps ou l'espace nécessaires pour résoudre le problème en fonction de la taille du problème d'entrée. Par exemple, trouver un nombre particulier dans une longue liste de nombres devient plus difficile à mesure que la liste s'allonge. Si nous disons qu'il y a n nombres dans la liste, et si la liste n'est pas triée ou indexée d'une manière particulière, il sera peut-être nécessaire d’examiner chaque nombre afin de trouver celui qui est recherché. Il apparaît donc que pour résoudre ce problème, l'ordinateur doit effectuer un nombre d'étapes qui augmente linéairement avec la taille du problème.

Pour simplifier ce problème, les informaticiens ont adopté une notation en grand O. Celle-ci permet de comparer les fonctions en tenant uniquement compte de leur comportement asymptotique (pour des paramètres qui deviennent grands). Ainsi, dans notre exemple précédent, nous pourrions dire que le problème nécessite O(n) étapes pour être résolu.

Le problème ouvert le plus important dans tout le domaine de l'informatique est peut-être celui de savoir si une certaine classe générale de problèmes désignée par NP peut être résolue efficacement (c’est-à-dire polynomialement). Ce sujet est abordé plus en détail dans les classes de complexité P et NP. Le problème P = NP est l'un des sept problèmes du millénaire énoncés par le Clay Mathematics Institute en 2000. La description officielle du problème a été donnée par Stephen Cook.