« Modèle de calcul » : différence entre les versions
Apparence
Contenu supprimé Contenu ajouté
Ébauche correcte et catégorie |
mAucun résumé des modifications |
||
Ligne 21 :
* [[Automate cellulaire]]
* [[Réseau de Petri]]
== Liens externes ==
{{Liens}}
{{Portail|informatique théorique}}
[[Catégorie:
[[Catégorie:Calculabilité]]
|
Version du 27 avril 2024 à 08:39
En informatique théorique, un modèle de calcul est un formalisme abstrait qui modélise l'exécution d'un algorithme. Les modèles de calcul sont le fondement de l'informatique théorique. Par exemple :
- En calculabilité, ils permettent de définir la notion de fonction calculable,
- En complexité, ils définissent le temps et la mémoire nécessaires à un calcul,
- La théorie des automates étudie une famille de modèles de calcul, les automates, qui sont souvent plus faibles que les modèles Turing-complets de la calculabilité et de l'algorithmique.
Quelques modèles de calcul courants
- Machine de Turing
- Automate fini
- Automate à pile
- Machine à registres illimités
- Random access machine
- Grammaire
- λ-calcul
- Fonction récursive générale, fonction récursive primitive
- Système de réécriture
- Logique combinatoire
- Automate cellulaire
- Réseau de Petri
Liens externes