Automate fini non déterministeUn 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 machine finie à états), finite-state automaton ou finite-state machine (FSA, FSM), est une machine abstraite qui est un outil fondamental en mathématiques discrètes et en informatique. On les retrouve dans la modélisation de processus, le contrôle, les protocoles de communication, la vérification de programmes, la théorie de la calculabilité, dans l'étude des langages formels et en compilation.
Automate finithumb|upright=2|Fig. 1 : Une hiérarchie d'automates. Un 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 nombreuses circonstances, allant de la conception de programmes informatiques et de circuits en logique séquentielle aux applications dans des protocoles de communication, en passant par le contrôle des processus, la linguistique et même la biologie.
Automate fini déterministeUn 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 sont déterminées de façon unique par le symbole d'entrée. Un tel automate se distingue ainsi d'un automate fini non déterministe, où au contraire plusieurs possibilités de transitions peuvent exister simultanément pour un état et un symbole d'entrée donné.
Concurrency controlIn information technology and computer science, especially in the fields of computer programming, operating systems, multiprocessors, and databases, concurrency control ensures that correct results for concurrent operations are generated, while getting those results as quickly as possible. Computer systems, both software and hardware, consist of modules, or components. Each component is designed to operate correctly, i.e., to obey or to meet certain consistency rules.
Système de transition d'étatsEn informatique théorique, un système de transition d'états est une forme de machine abstraite utilisée pour modéliser un ou des calcul(s). Un système de transition d'états est constitué d'un ensemble d'états et d'un ensemble de transitions d'un état à un autre, qui peuvent être étiquetées ; une même étiquette peut apparaître sur plusieurs transitions. Si l'ensemble des étiquettes est un singleton, on peut omettre l'étiquetage. Les systèmes d'états-transitions sont des graphes orientés.
Diagramme états-transitionsUn diagramme états-transitions est un schéma utilisé en génie logiciel pour représenter des automates déterministes. Il fait partie du modèle UML et s'inspire principalement du formalisme des statecharts et rappelle les grafcets des automates. S'ils ne permettent pas de comprendre globalement le fonctionnement du système, ils sont directement transposables en algorithme. En effet, contrairement au diagramme d'activité qui aborde le système d'un point de vue global, le diagramme états-transitions cible un objet unique du système.
Unbounded nondeterminismIn computer science, unbounded nondeterminism or unbounded indeterminacy is a property of concurrency by which the amount of delay in servicing a request can become unbounded as a result of arbitration of contention for shared resources while still guaranteeing that the request will eventually be serviced. Unbounded nondeterminism became an important issue in the development of the denotational semantics of concurrency, and later became part of research into the theoretical concept of hypercomputation.
Programmation concurrenteLa programmation concurrente est un paradigme de programmation tenant compte, dans un programme, de l'existence de plusieurs piles sémantiques qui peuvent être appelées threads, processus ou tâches. Elles sont matérialisées en machine par une pile d'exécution et un ensemble de données privées. La concurrence est indispensable lorsque l'on souhaite écrire des programmes interagissant avec le monde réel (qui est concurrent) ou tirant parti de multiples unités centrales (couplées, comme dans un système multiprocesseurs, ou distribuées, éventuellement en grille ou en grappe).
Automate quantiqueEn informatique quantique et en informatique théorique, un automate fini quantique est une généralisation des automates finis où un mot est accepté selon le résultat d'une certaine mesure. Il existe plusieurs modèles des automates finis quantiques ; le plus restrictif est celui des automates dits « measure-once » de ; un autre est celui des automates « measure-many » de . Ces deux modèles sont très différents l'un de l’autre ; le modèle « measure-once » se rapproche plus de la théorie classique des automates finis.
Optimistic concurrency controlOptimistic concurrency control (OCC), also known as optimistic locking, is a concurrency control method applied to transactional systems such as relational database management systems and software transactional memory. OCC assumes that multiple transactions can frequently complete without interfering with each other. While running, transactions use data resources without acquiring locks on those resources. Before committing, each transaction verifies that no other transaction has modified the data it has read.
Multiversion Concurrency ControlMultiversion concurrency control (abrégé en MCC ou MVCC) est une méthode informatique de contrôle des accès concurrents fréquemment utilisée dans les systèmes de gestion de base de données et les langages de programmation concernant la gestion des caches en mémoire. Le principe de MVCC repose sur un verrouillage dit optimiste contrairement au verrouillage pessimiste qui consiste à bloquer préalablement les objets à des garanties de bonne fin. L'inconvénient logique est qu'une mise à jour peut être annulée du fait d'un "blocage" en fin de traitement.
Sérialisationvignette|Schéma d'une sérialisation puis d'une désérialisation de données En informatique, la sérialisation (de l'anglais américain serialization) est le codage d'une information sous la forme d'une suite d'informations plus petites (dites atomiques, voir l'étymologie de atome) pour, par exemple, sa sauvegarde (persistance) ou son transport sur le réseau (proxy, RPC...). L'activité réciproque, visant à décoder cette suite pour créer une copie conforme de l'information d'origine, s'appelle la désérialisation (ou unmarshalling).
Théorie de l'ordonnancementLa théorie de l'ordonnancement est une branche de la recherche opérationnelle qui s'intéresse au calcul de dates d'exécution optimales de tâches. Pour cela, il est très souvent nécessaire d'affecter en même temps les ressources nécessaires à l'exécution de ces tâches. Un problème d'ordonnancement peut être considéré comme un sous-problème de planification dans lequel il s'agit de décider de l'exécution opérationnelle des tâches planifiées.
Automate fini déterministe bidirectionnelEn informatique théorique, et notamment en théorie des automates, un automate fini déterministe bidirectionnel (en anglais ) souvent abrégé en 2AFD (en anglais 2DFA), est un automate fini déterministe qui peut relire des symboles d'entrée déjà vus. Comme pour les automates finis déterministes usuels, un 2AFD possède un nombre fini d'états, et le passage d'un état à un autre est régi par des transitions en fonction du symbole lu. De plus, une transition porte une information sur la direction de déplacement de la lecture, soit vers la droite soit vers la gauche.
Database transactionA database transaction symbolizes a unit of work, performed within a database management system (or similar system) against a database, that is treated in a coherent and reliable way independent of other transactions. A transaction generally represents any change in a database. Transactions in a database environment have two main purposes: To provide reliable units of work that allow correct recovery from failures and keep a database consistent even in cases of system failure.
Commitment orderingCommitment ordering (CO) is a class of interoperable serializability techniques in concurrency control of databases, transaction processing, and related applications. It allows optimistic (non-blocking) implementations. With the proliferation of multi-core processors, CO has also been increasingly utilized in concurrent programming, transactional memory, and software transactional memory (STM) to achieve serializability optimistically. CO is also the name of the resulting transaction schedule (history) property, defined in 1988 with the name dynamic atomicity.
Communicating sequential processesEn programmation concurrente, Communicating sequential processes (CSP) est une algèbre de processus permettant de modéliser l'interaction de systèmes. CSP intègre un mécanisme de synchronisation basé sur le principe du rendez-vous (détaillé plus loin au travers de la commande d'entrée/sortie). Combinant ce mécanisme à une syntaxe simple et concise, CSP permet l'implémentation rapide des paradigmes classiques de la concurrence, tels que producteurs/consommateurs ou lecteurs/écrivains.
Automate fini inambiguupright=1.5|thumb|Un automate fini inambigu à n+1 états reconnaissant les mots qui ont un a en position n depuis la fin. Un automate déterministe équivalent a au moins états En théorie des automates, un automate fini inambigu (on dit aussi non ambigu, en anglais , abrégé en UFA) est un automate fini non déterministe d'un type particulier. C'est un automate qui, pour chaque mot accepté, ne possède qu'un seul calcul réussi. Tout automate fini déterministe est inambigu, mais la réciproque est fausse.
Automate fini alternantEn informatique théorique, et notamment en théorie des automates, un automate fini alternant est une extension des automates finis. Dans un automate fini non déterministe usuel, un mot est accepté si, parmi les états atteints, il y a au moins un état final. Dans automate fini alternant, c'est la valeur d'une fonction booléenne sur les états atteints qui définit la condition d'acceptation.
Non-blocking algorithmIn computer science, an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; for some operations, these algorithms provide a useful alternative to traditional blocking implementations. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress, and wait-free if there is also guaranteed per-thread progress. "Non-blocking" was used as a synonym for "lock-free" in the literature until the introduction of obstruction-freedom in 2003.
