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.
Circuit électriquevignette|Circuit électrique à Calcutta, Inde. Un circuit électrique au sens matériel est un ensemble simple ou complexe de composants électriques ou électroniques, y compris des simples conducteurs, parcourus par un courant électrique. Au sens de la théorie des circuits, un circuit électrique est une abstraction des configurations matérielles, un agencement d'éléments définis par des relations mathématiques, reliés par des conducteurs idéaux. L'étude électrocinétique d'un circuit électrique consiste à déterminer, à chaque endroit, l'intensité du courant et la tension.
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.
Couplage croiséEn chimie organique, un couplage croisé est une réaction de couplage entre deux fragments moléculaires par formation d'une liaison carbone-carbone sous l'effet d'un catalyseur organométallique. Par exemple, un composé , où R est un fragment organique et M un métal du groupe principal, réagit avec un halogénure organique , où X est un halogène, pour former un produit . Les chimistes Richard Heck, Ei-ichi Negishi et Akira Suzuki ont reçu le prix Nobel de chimie 2010 pour avoir développé des réactions de couplage catalysées au palladium.
Réaction de couplageEn chimie organique, une réaction de couplage est une transformation qui permet l'association de deux radicaux hydrocarbures, en général à l'aide d'un catalyseur métallique. Deux classifications sont possibles en fonction de la nature du produit formé ou de celle des réactifs mis en jeu : dans le premier cas, si le produit est symétrique (formé par l'association de deux molécules identiques), on parle d'homocouplage. Il s'agit en général de la réaction d'un halogénure aromatique avec une deuxième molécule identique ou de celle d'un organométallique de la même manière.
Couplage de HiyamaLe couplage de Hiyama est une réaction de couplage entre un organosilane et un halogénure organique ou un triflate, catalysée par du palladium parfois assisté par du nickel. Ce couplage a été décrit pour la première fois par Yasuo Hatanaka et Tamejiro Hiyama en 1988. Dans la publication initiale de 1988, le 1-iodonaphtalène réagit avec le triméthylvinylsilane pour produire le 1-vinylnaphtalène avec une catalyse au chlorure d'allylpalladium. Cette réaction dispose de plusieurs avantages.
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.
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é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).
