Collection · Informatique théorique
Calculabilité
Dans Technologie
117 cartes30 joueurs l'ont commencée
Collection « Calculabilité » sur Wikicard : 117 cartes tirées de Wikipédia, dont Théorie de la calculabilité, Automate fini, Machine de Turing. Terminée, elle donne un badge brodé « Or », généré pour elle par IA.
Ses cartes les plus connues
Machine de TuringLégendaireUne machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur.
Théorie de la complexité (informatique théorique)LégendaireLa théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et…
Automate finiÉpiqueUn automate fini ou automate avec un nombre fini d'états (en anglais finite-state automaton ou finite state machine ou FSM) est un modèle mathématique de calcul, utilisé dans de…
- Théorie de la calculabilitéÉpiqueLa théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est un domaine de la logique mathématique et de l'informatique théorique qui vise à identifier les…
Automate cellulaireÉpiqueUn automate cellulaire consiste en un ensemble d'automates, appelés « cellules », disposées sur une grille régulière et contenant chacune un « état » choisi parmi un ensemble fini.
Lambda-calculÉpiqueLe lambda-calcul (ou λ-calcul) est un système formel inventé par Alonzo Church dans les années 1930.Analyse de la complexité des algorithmesÉpiqueL'analyse de la complexité d'un algorithme consiste en l'étude formelle de la quantité de ressources (par exemple de temps ou d'espace) nécessaire à l'exécution de cet algorithme.
- DécidabilitéÉpiqueDécidabilité est la négation de la décidabilité.
Problème de l'arrêtÉpiqueLe problème de l'arrêt est le problème de décision qui détermine, à partir d'une description d'un programme informatique, et d'une entrée, si le programme s'arrête avec cette…- Thèse de ChurchÉpiqueLa thèse de Church — du nom du mathématicien Alonzo Church — est une thèse concernant la définition de la notion de calculabilité.
- Fonction récursiveÉpiqueFonction récursive ou fonction calculable désigne la classe de fonctions dont les valeurs peuvent être calculées à partir de leurs paramètres par un processus mécanique fini.
Hiérarchie de ChomskyÉpiqueLa hiérarchie de Chomsky (parfois appelée hiérarchie de Chomsky-Schützenberger) est une classification des grammaires formelles (et par extension, des langages formels respectifs…
- Langage rationnelÉpiqueEn théorie des langages, les langages rationnels ou langages réguliers ou encore langages reconnaissables peuvent être décrits de plusieurs façons équivalentes : ce sont les…
- Automate fini déterministeÉpiqueUn automate fini déterministe, parfois abrégé en AFD (en anglais deterministic finite automaton, abrégé en DFA) est un automate fini dont les transitions à partir de chaque état…
- Constructivisme (mathématiques)ÉpiqueLe constructivisme est une position vis-à-vis des mathématiques qui considère que l'on ne peut effectivement démontrer l'existence d'objets mathématiques qu'en donnant une…
- Correspondance de Curry-HowardÉpiqueLa correspondance de Curry-Howard, appelée également isomorphisme de Curry-de Bruijn-Howard, correspondance preuve/programme ou correspondance formule/type, est une série de…
Automate à pileÉpiqueUn automate à pile est une machine abstraite utilisée en informatique théorique et, plus précisément, en théorie des automates.
- Réécriture (informatique)RareLa réécriture est un modèle de calcul dans lequel il s’agit de transformer des objets syntaxiques (mots, termes, lambda-termes, programmes, preuves, graphes, etc.) en appliquant…
Récursivement énumérableRareRécursivement énumérable ou semi-décidable si : il existe un algorithme qui prend un entier naturel en entrée, et qui s'arrête exactement sur les entiers de E ; ou, de manière…
Ensemble récursifRareUn ensemble récursif ou ensemble décidable ou ensemble calculable est un ensemble d'entiers (ou d'éléments facilement codables dans les entiers) dont la fonction caractéristique…
Nombre réel calculableRareUn nombre réel calculable est un réel pour lequel il existe un algorithme ou une machine de Turing permettant d'énumérer la suite de ses chiffres (éventuellement infinie), ou plus…
- Fonction d'AckermannRareLa fonction d'Ackermann (aussi appelée fonction d'Ackermann-Péter) est un exemple simple de fonction récursive non récursive primitive, trouvée en 1926 par Wilhelm Ackermann.
- Machine abstraiteRareUne machine abstraite est un modèle théorique d'un ordinateur logique et discret.
- Complexité de KolmogorovRareLa complexité de Kolmogorov, ou complexité aléatoire, ou complexité algorithmique d'un objet — nombre, image numérique, chaîne de caractères — est la taille du plus petit…
- Automate fini non déterministeRareUn automate fini (on dit parfois, par une traduction littérale de l'anglais, machine à états finis, au lieu de machine avec un nombre fini d'états ou machine à états finie ou…
- Langage algébriqueRareUn langage algébrique ou langage non contextuel est un langage qui est engendré par une grammaire algébrique.
- Logique combinatoireRareLa logique combinatoire est une théorie logique introduite par Moses Schönfinkel en 1920 lors d'une conférence et développée dès 1929 par Haskell Brooks Curry pour supprimer le…
- Modèle de calculRareUn modèle de calcul est un formalisme abstrait qui modélise l'exécution d'un algorithme.
Circuit booléenRareUn circuit booléen est un modèle de calcul constitué de portes logiques (fonctions logiques) reliées entre elles.
- Dixième problème de HilbertRareLe dixième problème de Hilbert à un autre problème de décision, qui est de savoir si une équation diophantienne admet des solutions entières positives (on parle de réduction).
Machine de MealyRareUne machine de Mealy ou automate de Mealy est un transducteur fini (i.e.Machine de MooreRareUne machine de Moore est un 6-uplet ( Q , i , A , B , δ , λ ) {\displaystyle (Q,i,A,B,\delta ,\lambda )} constitué de : un ensemble fini d'états Q {\displaystyle Q} ; un état…
- Fonction récursive primitiveRareUne fonction récursive primitive est une fonction construite à partir de la fonction nulle, de la fonction successeur, des fonctions projections et des schémas de récursion…
- HypercalculRareHypercalcul désigne les différentes méthodes proposées pour le calcul de fonctions non-Turing-calculables.
- Random access machineRareRandom Access Machine, est un modèle abstrait d'ordinateur destiné à étudier des algorithmes.
- Réduction (complexité)RareUne réduction est un algorithme transformant une instance d'un problème algorithmique en une ou plusieurs instances d'un autre problème.
Oméga de ChaitinRareEn théorie algorithmique de l'information, une constante Oméga de Chaitin (nombres définis et étudiés par Gregory Chaitin) caractérise de manière univoque et mathématiquement…- Évaluation paresseuseRareL’évaluation paresseuse (en anglais : lazy evaluation), appelée aussi appel par nécessité ou évaluation retardée est une technique d'implémentation des programmes récursifs pour…
- Machine de Turing probabilisteRareUne machine de Turing probabiliste (ou randomisée) est une machine de Turing qui peut utiliser du hasard.
- Automate sur les mots infinisRareUn automate sur les mots infinis ou ω-automate est un automate fini qui accepte des mots infinis.
Automate de BüchiRareUn automate de Büchi est un ω-automate ou automate fini opérant sur des mots infinis, avec une condition d'acceptation particulière : une trace (ou calcul ou chemin infini) est…- Machine à compteursRareUne machine à compteurs est un modèle de calcul.
- Castor affairéRareLe castor affairé parmi un ensemble de machines de Turing à n états donnés est un problème insoluble algorithmiquement ; en pratique, on ne peut même pas espérer exhiber un castor…
- Corps réel closRareUn corps réel clos est un corps totalement ordonnable dont aucune extension algébrique propre n'est totalement ordonnable.
- Transducteur finiRareUn transducteur fini (appelé aussi transducteur à états finis par une traduction littérale de l'anglais finite state transducer) est un automate fini avec sorties.
- Théorème de RiceRareLe théorème de Rice énonce que toute propriété sémantique non triviale d'un programme est indécidable.
Oracle (machine de Turing)RareOracle sont une variante des machines de Turing disposant d'une boîte noire, un oracle, capable de résoudre un problème de décision en une seule opération élémentaire.
- Machine à registres illimitésRareUne machine à registres illimités ou URM (de l'anglais : Unlimited Register Machine) est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tout comme les…
- Automate d'arbresRareUn automate d'arbres fini ascendant (bottom-up finite tree automaton en anglais) sur F {\displaystyle F} est défini par les objets : ( Q , F , Q f , Δ ) {\displaystyle…
Hiérarchie arithmétiquePeu communeLa hiérarchie arithmétique, définie par Stephen Cole Kleene, est une hiérarchie des sous-ensembles de l'ensemble N des entiers naturels définissables dans le langage du premier…
- Structure de KripkePeu communeUne structure de Kripke est un modèle de calcul, proche d'un automate fini non déterministe, inventé par Saul Kripke.
Fonction partiellePeu communeUne fonction partielle (quelquefois appelée simplement fonction) sur un ensemble donné E {\displaystyle E} est une application définie sur une partie de celui-ci, appelé ensemble…
- Grammaire contextuellePeu communeUne grammaire contextuelle est une grammaire formelle dans laquelle les substitutions d'un symbole non terminal sont soumises à la présence d'un contexte gauche et d'un contexte…
- Principe de Church-Turing-DeutschPeu communeLe principe de Church-Turing-Deutsch est une forme plus forte de la thèse de Church (ou thèse de Church-Turing) qui a été formulée par David Deutsch en 1985.
- Langage contextuelPeu communeUn langage contextuel (en anglais context-sensitive language) est un langage formel engendré par une grammaire contextuelle.
- Automate probabilistePeu communeUn automate probabiliste est une généralisation des automates finis non déterministes; chaque transition de l'automate est équipée d'une probabilité (un nombre réel entre 0 et 1).
- Langage sans étoilePeu communeUn langage sans étoile car la définition par expression rationnelle demande de passer en revue toutes les expressions rationnelles sans étoile pour affirmer que le langage est…
- Automate linéairement bornéPeu communeUn automate linéairement borné (en anglais linear bounded automaton, abrégé en LBA) est une machine de Turing non déterministe qui n'utilise qu'une portion contiguë du ruban de…
- Problème de correspondance de PostPeu communeLe problème de correspondance de Post (PCP) est un problème de décision indécidable qui fut introduit par Emil Post en 1946.
- Méthode de Brzozowski et McCluskeyPeu communeLa méthode de Brzozowski et McCluskey, aussi appelée méthode d'élimination d'états (« state elimination method »), est une méthode permettant d'obtenir une expression rationnelle…
Ouvrez des paquets de cartes tirées de Wikipédia, terminez vos collections pour gagner leur badge brodé, défiez d'autres joueurs en Joute. Gratuit, sans avantage payant.