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.
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.
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.
Complexité de la communicationLa complexité de la communication ou complexité de communication est une notion étudiée en informatique théorique. Le dispositif abstrait classique est le suivant : Alice et Bob ont chacun un message, et ils veulent calculer un nouveau message à partir de leurs messages, en se transmettant un minimum d'information. Par exemple, Alice et Bob reçoivent un mot chacun, et ils doivent décider s'ils ont reçu le même mot ; ils peuvent bien sûr s'envoyer leur mot l'un à l'autre et comparer, mais la question est de minimiser le nombre de messages.
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.
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.
Situation de compétitionUne situation de compétition (ou situation de concurrence, accès concurrent, concurrence critique, course critique, séquencement critique ; race condition en anglais, littéralement « situation de course »), est une situation caractérisée par un résultat différent selon l'ordre dans lequel agissent les acteurs du système. Le terme est plutôt employé à propos de programmes informatiques et de systèmes électroniques. C'est généralement considéré comme un défaut car source de panne ou de blocage.
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.
Edsger DijkstraEdsger Wybe Dijkstra (prononciation : ), né à Rotterdam le et mort à Nuenen le , est un mathématicien et informaticien néerlandais du . Il reçoit en 1972 le prix Turing pour ses contributions sur la science et l’art des langages de programmation et au langage Algol. Juste avant sa mort, en 2002, il reçoit le prix PoDC de l'article influent, pour ses travaux sur l'autostabilisation. L'année suivant sa mort, le prix sera renommé en son honneur prix Dijkstra.
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.
