Aide
Ajouter cette page à votre livre
Afficher le livre (0 article)
Suggérer des pagesThéorie du calcul
La théorie du calcul est une branche de l'informatique théorique qui traite des problèmes pouvant être résolus en utilisant des algorithmes, sur un modèle de calcul spécifique. Elle s'intéresse particulièrement à l’efficacité avec laquelle ils peuvent être résolus et dans quelle mesure (par exemple à l’efficacité de solutions approchées par rapport aux solutions exactes). Ce domaine se divise en trois branches principales : la théorie des automates et des langages formels, la théorie de la calculabilité et la théorie de la complexité algorithmique. Tous ces domaines cherchent à déterminer les capacités et limites des ordinateurs[1].
À la base de l’étude rigoureuse du calcul se trouvent des modèles de calcul. Le plus couramment utilisé est le modèle des machines de Turing[2]. Les informaticiens étudient les machines de Turing parce qu'elles sont faciles à représenter, parce qu'elles peuvent être analysées et utilisées pour prouver des résultats, et parce qu'elles représentent un modèle de calcul « raisonnable » le plus puissant possible (voir la thèse de Church-Turing)[3]. Le fait qu’une machine de Turing dispose d’une capacité de mémoire infinie pourrait sembler problématique a priori, car irréalisable dans les faits. Cependant, tout problème résolu par une machine de Turing ne nécessitera toujours qu'une quantité finie de mémoire. Ainsi, en principe, tout problème pouvant être décidé par une machine de Turing peut être résolu par un ordinateur disposant d'une quantité finie de mémoire[4].
Histoire
[modifier | modifier le code]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.
Branches
[modifier | modifier le code]
Théorie des automates
[modifier | modifier le code]| Grammaire | Langage | Automate | Règles d'inférence (contraintes) |
|---|---|---|---|
| Type 0 | récursivement énumérable | machine de Turing | |
| Type 1 | contextuel | automate linéairement borné | |
| Type 2 | non contextuel / | automate à pile | |
| Type 3 | régulier | automate fini |
et |
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é.
Théorie des langages formels
[modifier | modifier le code]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é.
Théorie de la calculabilité
[modifier | modifier le code]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].
Théorie de la complexité
[modifier | modifier le code]
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.
Modèles de calcul
[modifier | modifier le code]En dehors des machines de Turing, d’autres modèles de calcul équivalents (voir la thèse de Church-Turing) sont utilisés en théorie du calcul.
Les calculs consistent en une λ-expression originale (ou deux si on sépare la fonction de son argument) plus une séquence finie de λ-termes, tous déduits du précédent par béta-réduction.
La logique combinatoire présente de nombreuses similarités avec le λ-calcul. Cependant, il existe certaines différences majeures: par exemple, le point fixe Ω a une forme normale en logique combinatoire, mais pas en λ-calcul.
La logique combinatoire a été développée avec de grandes ambitions : comprendre la nature des paradoxes, rendre les fondements des mathématiques plus économiques (conceptuellement), éliminer la notion de variables (clarifiant ainsi leur rôle en mathématiques).
Un calcul correspond à une fonction μ-récursive. Une fonction μ-récursive est définie par une séquence de fonctions récursives, qui doivent elles-mêmes découler des fonctions de base par composition, récursivité primitive ou μ-récursivité.
Utilise des règles similaires à des règles grammaticales pour réécrire des chaînes de symboles.
C’est une modélisation intéressante d’un ordinateur. Plusieurs variantes existent. Dans la plupart d'entre elles, chaque registre peut contenir un nombre naturel (de taille illimitée) et les instructions sont simples et peu nombreuses. Par exemple seules existent la décrémentation (combinée à un saut conditionnel) et l'incrémentation (et l'arrêt). L'absence de mémoire externe infinie (ou à croissance dynamique) (que l'on observe dans les machines de Turing) peut être comprise en remplaçant son rôle par les techniques de numérotation de Gödel : le fait que chaque registre contienne un nombre naturel permet de représenter une chose complexe (par exemple une séquence, une matrice, etc.) par un nombre naturel suffisamment grand — l'absence d'ambiguïté de la représentation et de l'interprétation peut être établie par les fondements théoriques numériques de ces techniques.
Outre les modèles computationnels généraux, certains modèles computationnels plus simples sont utiles pour des applications spéciales et restreintes. Les expressions régulières, par exemple, spécifient des modèles de chaînes de caractères dans de nombreux contextes, des logiciels de bureautique aux langages de programmation. Autre formalisme mathématiquement équivalent aux expressions régulières, les automates finis sont utilisés dans la conception de circuits et dans certains types de résolution de problèmes. Les grammaires non-contextuelles spécifient la syntaxe des langages de programmation. Les automates à pile non déterministes sont un autre formalisme équivalent aux grammaires non-contextuelles. Les fonctions récursives primitives sont une sous-classe des fonctions récursives.
Différents modèles de calcul permettent d'effectuer différentes tâches. Une façon de mesurer la puissance d'un modèle de calcul consiste à étudier la classe des langages formels que le modèle peut générer ; c'est ainsi que l'on obtient la hiérarchie des langages de Chomsky.
Références
[modifier | modifier le code]- ↑ (en) Michael Sipser, Introduction to the theory of computation, Cengage Learning, (ISBN 978-1-133-18779-0, 978-1-133-18781-3 et 978-0-357-67058-3).
- ↑ (en) Andrew Hodges, Alan Turing: the enigma, Princeton University Press, (ISBN 978-0-691-15564-7).
- ↑ (en) Michael O. Rabin, « Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View » [vidéo] d'une conférence, sur videolectures.net, .
- ↑ (en) J. Donald Monk, Mathematical logic, Springer-Verlag, coll. « Graduate texts in mathematics », (ISBN 978-0-387-90170-1).
- ↑ (en) John E. Hopcroft, Rajeev Motwani et Jeffrey D. Ullman, Introduction to automata theory, languages, and computation, Pearson/Addison Wesley, (ISBN 978-0-321-45536-9, 978-0-321-46225-1 et 978-0-321-45537-6).
- ↑ (en) N. Chomsky, « Three models for the description of language », IEEE Transactions on Information Theory, vol. 2, no 3, , p. 113–124 (ISSN 0018-9448, DOI 10.1109/TIT.1956.1056813, lire en ligne, consulté le ).
- ↑ (en) A. M. Turing, « On Computable Numbers, with an Application to the Entscheidungsproblem », Proceedings of the London Mathematical Society, vol. s2-42, no 1, , p. 230–265 (DOI 10.1112/plms/s2-42.1.230, lire en ligne, consulté le ).
- ↑ (en) H. G. Rice, « Classes of Recursively Enumerable Sets and Their Decision Problems », Transactions of the American Mathematical Society, vol. 74, no 2, , p. 358 (DOI 10.2307/1990888, lire en ligne, consulté le ).
- ↑ (en) The undecidable: basic papers on undecidable propositions, unsolvable problems, and computable functions, Dover Publication, coll. « Dover books on mathematics », (ISBN 978-0-486-43228-1).
Liens externes
[modifier | modifier le code]- Notices dans des dictionnaires ou encyclopédies généralistes :
