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.
Szymański's algorithmSzymański's Mutual Exclusion Algorithm is a mutual exclusion algorithm devised by computer scientist Dr. Bolesław Szymański, which has many favorable properties including linear wait, and which extension solved the open problem posted by Leslie Lamport whether there is an algorithm with a constant number of communication bits per process that satisfies every reasonable fairness and failure-tolerance requirement that Lamport conceived of (Lamport's solution used n factorial communication variables vs.
Algorithme de PetersonEn informatique, l'algorithme de Peterson est un algorithme d'exclusion mutuelle pour la programmation concurrente. Cet algorithme est basé sur une approche par attente active et est garanti d'être sans famine et sans interblocage. Il est constitué de deux parties : le protocole d'entrée dans la section critique et le protocole de sortie. L'algorithme présenté est une version pouvant fonctionner avec deux threads. Il a été publié par Gary Peterson en 1981.
Auto-organisationL'auto-organisation ou autoorganisation est un phénomène par lequel un système s'organise lui-même. Les systèmes physiques, biologiques ou écologiques, sociaux, ont tendance à s'organiser d'eux-mêmes. Il s'agit soit de l'organisation initiale du système lors de son émergence spontanée, soit lorsque le système existe déjà de l'apparition d'une organisation plus ou complexe. L'auto-organisation agit ainsi à l'encontre de l'entropie (on parle alors de néguentropie), qui est une mesure de désordre.
Classe de complexitéEn informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace.
Computational complexityIn computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.
ComplexitéLa complexité caractérise le comportement d'un système dont les composants interagissent localement et de façon non linéaire, ce qui se traduit par un comportement difficilement prédictible. La complexité peut donc caractériser un système "composé d'un grand nombre d'éléments interagissant sans coordination centrale, sans plan établi par un architecte, et menant spontanément à l'émergence de structures complexes" (Alain Barrat, directeur de recherche au Centre de physique théorique de Marseille); mais aussi caractériser des systèmes composés de peu d'éléments (voir le chaos déterministe).
Dîner des philosophesLe problème du « dîner des philosophes » est un cas d'école classique sur le partage de ressources en informatique système. Il concerne l'ordonnancement des processus et l'allocation des ressources à ces derniers et a été énoncé par Edsger Dijkstra. vignette|Illustration du problème La situation est la suivante: Cinq philosophes (initialement, mais il peut y en avoir beaucoup plus) se trouvent autour d'une table; Chacun des philosophes a devant lui un plat de spaghettis; À gauche de chaque plat de spaghettis se trouve une fourchette.
Théorie de la complexité (informatique théorique)vignette|Quelques classes de complexité étudiées dans le domaine de la théorie de la complexité. Par exemple, P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La 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 plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée ...) requis par un algorithme pour résoudre un problème algorithmique.
Problème des lecteurs et des rédacteursLe problème des lecteurs et des rédacteurs est un problème classique en théorie informatique, qui permet de modéliser les accès à des bases de données. Il fut énoncé sous cette forme par Edsger Dijkstra, qui est également à l'origine du problème du dîner des philosophes (problème relatif en particulier à l'ordonnancement des processus). Supposons qu'une base de données ait des lecteurs et des rédacteurs, et qu'il faille programmer les lecteurs et les rédacteurs de cette base de données.
Complexité descriptiveEn informatique théorique, la complexité descriptive est une branche de la théorie de la complexité et de la théorie des modèles, qui caractérise les classes de complexité en termes de logique qui permet de décrire les problèmes. La complexité descriptive donne un nouveau point de vue car on définit des classes de complexité sans faire appel à une notion de machines comme les machines de Turing. Par exemple la classe NP correspond à l'ensemble des problèmes exprimables en logique du second ordre existentielle : c'est le théorème de Fagin.
Complexité en espaceEn algorithmique, la complexité en espace est une mesure de l'espace utilisé par un algorithme, en fonction de propriétés de ses entrées. L'espace compte le nombre maximum de cases mémoire utilisées simultanément pendant un calcul. Par exemple le nombre de symboles qu'il faut conserver pour pouvoir continuer le calcul. Usuellement l'espace que l'on prend en compte lorsque l'on parle de l'espace nécessaire pour des entrées ayant des propriétés données est l'espace nécessaire le plus grand parmi ces entrées ; on parle de complexité en espace dans le pire cas.
Complexité de KolmogorovEn informatique théorique et en mathématiques, plus précisément en théorie de l'information, la complexité de Kolmogorov, ou complexité aléatoire, ou complexité algorithmique d'un objet — nombre, , chaîne de caractères — est la taille du plus petit algorithme (dans un certain langage de programmation fixé) qui engendre cet objet. Elle est nommée d'après le mathématicien Andreï Kolmogorov, qui publia sur le sujet dès 1963. Elle est aussi parfois nommée complexité de Kolmogorov-Solomonoff.
Spéculation (économie)Sur un marché quelconque, on nomme spéculation « l'activité consistant à tirer profit par anticipation de l'évolution à court, moyen ou long terme du niveau général des prix ou d'un prix particulier en vue d'en retirer une plus-value ou un bénéfice ». La finance traditionnelle préfère employer le terme d'opérations d'arbitrage. Elle considère de ce point de vue : que les mouvements spéculatifs sont utiles sinon inévitables en ce qu'ils détectent les déséquilibres existants ou potentiels d'un marché ; qu'en vertu de l'efficience du marché financier ces mouvements contribuent à la stabilisation des prix ou à l'atténuation de ses fluctuations.
Verrou (informatique)Un verrou informatique permet de s'assurer qu'une seule personne, ou un seul processus accède à une ressource à un instant donné. Ceci est souvent utilisé dans le domaine des accès à des fichiers sur des systèmes d'exploitation multi-utilisateur, car si deux programmes modifient un même fichier au même moment, le risque est de : provoquer des erreurs dans un des deux programmes, voire dans les deux ; laisser le fichier en fin de traitement dans une complète incohérence ; endommager le fichier manipulé.
Protocole de communicationDans les réseaux informatiques et les télécommunications, un protocole de communication est une spécification de plusieurs règles pour un type de communication particulier. Initialement, on nommait protocole ce qui est utilisé pour communiquer sur une même couche d'abstraction entre deux machines différentes. Par extension de langage, on utilise parfois ce mot aussi aujourd'hui pour désigner les règles de communication entre deux couches sur une même machine.
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).
Asynchrony (computer programming)Asynchrony, in computer programming, refers to the occurrence of events independent of the main program flow and ways to deal with such events. These may be "outside" events such as the arrival of signals, or actions instigated by a program that take place concurrently with program execution, without the program blocking to wait for results. Asynchronous input/output is an example of the latter case of asynchrony, and lets programs issue commands to storage or network devices that service these requests while the processor continues executing the program.
Pile de protocolesUne pile de protocoles est une mise en œuvre particulière d'un ensemble de protocoles de communication réseau. L'intitulé « pile » implique que chaque couche de protocole s'appuie sur celles qui sont en dessous afin d'y apporter un supplément de fonctionnalité. Il en existe de plusieurs : thumb|Position de la couche réseau dans le modèle OSI et dans TCP-IP • Le « modèle de référence OSI » — OSI signifiant « Open Systems Interconnection » soit en français « Interconnexion de systèmes ouverts » — défini par l'ISO décrit ainsi sept couches empilées les unes sur les autres.
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.
