Vérification de modèlesthumb|308x308px|Principe du model checking. En informatique, la vérification de modèles, ou model checking en anglais, est le problème suivant : vérifier si le modèle d'un système (souvent informatique ou électronique) satisfait une propriété. Par exemple, on souhaite vérifier qu'un programme ne se bloque pas, qu'une variable n'est jamais nulle, etc. Généralement, la propriété est écrite dans un langage, souvent en logique temporelle. La vérification est généralement faite de manière automatique.
BPP (complexité)En informatique théorique, plus précisément en théorie de la complexité, la classe BPP (bounded-error probabilistic polynomial time) est la classe de problèmes de décision décidés par une machine de Turing probabiliste en temps polynomial, avec une probabilité d'erreur dans la réponse inférieure à 1/3. La classe BPP est l'ensemble des problèmes, ou de façon équivalente des langages, pour lesquels il existe une machine de Turing probabiliste en temps polynomial qui satisfait les conditions d'acceptation suivantes : Si le mot n'est pas dans le langage, la machine le rejette avec une probabilité supérieure à 2/3.
Complexité paramétréeEn algorithmique, la complexité paramétrée (ou complexité paramétrique) est une branche de la théorie de la complexité qui classifie les problèmes algorithmiques selon leur difficulté intrinsèque en fonction de plusieurs paramètres sur les données en entrée ou sur la sortie. Ce domaine est étudié depuis les années 90 comme approche pour la résolution exacte de problèmes NP-complets. Cette approche est utilisée en optimisation combinatoire, notamment en algorithmique des graphes, en intelligence artificielle, en théorie des bases de données et en bio-informatique.
Structure de KripkeUne structure de Kripke est un modèle de calcul, proche d'un automate fini non déterministe, inventé par Saul Kripke. Elle est utilisée par exemple dans le model checking pour représenter le comportement d'un système. C'est un graphe orienté dont les nœuds représentent les états accessibles du système et dont les arcs représentent les transitions entre les états. Une fonction d'étiquetage fait correspondre à chaque état un ensemble de propositions logiques vraies dans cet état.
Fenêtre de registresEn architecture des ordinateurs, les fenêtres de registres constituent une technique pour améliorer la performance des appels de fonctions. Elles ont été utilisées pour la première fois dans les processeurs RISC de Berkeley, qui sont à l'origine des architectures SPARC, AMD 29000 et Intel i960. La plupart des processeurs ont un petit nombre de mémoires très rapides appelées registres. Les processeurs utilisent les registres afin de stocker temporairement des valeurs lors de l'exécution des suites d'instructions.
Registre à décalageDans le domaine de l'électronique numérique, un registre à décalage est un registre, c'est-à-dire un ensemble de bascules synchrones, dont les bascules sont reliées une à une, à l'exception de deux bascules qui ne sont pas forcément reliées. À chaque cycle d'horloge, le nombre représenté par ces bascules est mis à jour. Le concept de décalage permet d'insérer une donnée dans le registre, ou la lire, bit par bit en série. Un registre permet de stocker une donnée élémentaire, ou une adresse mémoire, sur laquelle l'unité centrale peut effectuer des calculs ou des traitements.
Exclusion mutuelleUn Mutex (anglais : Mutual exclusion, Exclusion mutuelle) est une primitive de synchronisation utilisée en programmation informatique pour éviter que des ressources partagées d'un système ne soient utilisées en même temps. Son implémentation varie selon les systèmes (masquage des interruptions, lecture/écriture en un cycle, etc.) Ces algorithmes permettent de réguler l'accès aux données, en permettant par exemple qu'une seule routine y accède à la fois. Un Mutex M.M.
Read–modify–writeIn computer science, read–modify–write is a class of atomic operations (such as test-and-set, fetch-and-add, and compare-and-swap) that both read a memory location and write a new value into it simultaneously, either with a completely new value or some function of the previous value. These operations prevent race conditions in multi-threaded applications. Typically they are used to implement mutexes or semaphores. These atomic operations are also heavily used in non-blocking synchronization.
Circuit complexityIn theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits (see below). Proving lower bounds on size of Boolean circuits computing explicit Boolean functions is a popular approach to separating complexity classes.
Registre d'étatLe registre d'état, ou registre de drapeaux, est un ensemble de bits représentant des drapeaux au sein d'un processeur. Le registre RFLAGS est un exemple de registre d'état propre à l'architecture de processeurs x64. Les bits composant le registre d'état sont indépendants les uns des autres, et la valeur de chacun apporte une information supplémentaire quant au résultat d'une opération antérieure. En effet, au cours d'un calcul, le processeur va automatiquement mettre à jour le registre d'état, en plus de fournir le résultat de l'opération.
