Catégorie : Concepts

Un automate cellulaire est un modèle de calcul reposant sur une grille de cases, appelées cellules, dont chacune se trouve dans un état parmi un petit nombre de possibilités, par exemple vivante ou morte, allumée ou éteinte. Le temps y avance par étapes successives, et à chaque étape toutes les cellules changent d’état en même…

Un automate probabiliste est un modèle de calcul qui introduit le hasard dans le fonctionnement d’un automate fini. Dans un automate ordinaire, chaque symbole lu détermine sans ambiguïté l’état suivant, selon des règles fixes. Dans un automate probabiliste, en revanche, le passage d’un état à un autre n’est plus certain: à chaque symbole lu, l’automate…

Un automate temporisé est un modèle de calcul qui enrichit l’automate fini d’une notion de temps, afin de décrire des systèmes dont le comportement dépend non seulement de l’ordre des événements mais aussi des durées qui les séparent. À l’automate fini ordinaire, avec ses états et ses transitions, on ajoute une ou plusieurs horloges, c’est-à-dire…

Un automate à pile est un modèle de calcul qui enrichit l’automate fini d’une mémoire supplémentaire d’un genre particulier, appelée pile. Comme l’automate fini, il lit une suite de symboles de gauche à droite en passant d’un état à un autre, mais il dispose en plus d’une réserve où il peut empiler des symboles et…

Un automate fini est l’un des modèles de calcul les plus simples que l’on puisse imaginer, conçu pour reconnaître des motifs dans une suite de symboles lue de gauche à droite. On peut se le représenter comme un petit dispositif doté d’un nombre limité d’états, dont un état de départ et un ou plusieurs états…

Un modèle de calcul quantique est une manière abstraite de définir ce qu’est un calcul lorsqu’on autorise la machine à exploiter les lois de la physique quantique, celles qui régissent le comportement de la matière à très petite échelle. Là où les modèles classiques manipulent des informations qui valent toujours zéro ou un, ce modèle…

Le calcul probabiliste désigne une manière de calculer dans laquelle la machine a le droit de faire des choix au hasard au cours de son exécution. Une machine ordinaire est entièrement déterministe: à partir des mêmes données, elle suit toujours exactement le même chemin et aboutit toujours au même résultat. Une machine probabiliste, au contraire,…

Le calcul distribué abstrait désigne l’étude théorique du calcul lorsqu’il n’est plus accompli par une seule machine isolée, mais par plusieurs entités qui travaillent en parallèle et doivent se coordonner. Plutôt que de suivre un unique fil d’instructions, on imagine ici de nombreux acteurs, souvent appelés processus, qui effectuent chacun leurs propres opérations, échangent des…

La réécriture est un modèle de calcul qui repose sur une idée d’une grande simplicité: transformer des suites de symboles en appliquant des règles de remplacement. On part d’une expression, une chaîne de signes quelconque, et l’on dispose d’un ensemble de règles indiquant que tel motif peut être remplacé par tel autre. Calculer consiste alors…

Une machine à registres est un modèle théorique de calcul conçu pour ressembler d’assez près à la manière dont fonctionne un ordinateur réel. On l’imagine comme un dispositif disposant d’un certain nombre de cases numérotées, appelées registres, dont chacune peut contenir un nombre entier aussi grand qu’on veut. La machine exécute un programme composé d’instructions…