Asymptotic computational complexityIn computational complexity theory, asymptotic computational complexity is the usage of asymptotic analysis for the estimation of computational complexity of algorithms and computational problems, commonly associated with the usage of the big O notation. With respect to computational resources, asymptotic time complexity and asymptotic space complexity are commonly estimated. Other asymptotically estimated behavior include circuit complexity and various measures of parallel computation, such as the number of (parallel) processors.
Complexité en tempsEn algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat. Habituellement, le temps correspondant à des entrées de taille n est le temps le plus long parmi les temps d’exécution des entrées de cette taille ; on parle de complexité dans le pire cas. Les études de complexité portent dans la majorité des cas sur le comportement asymptotique, lorsque la taille des entrées tend vers l'infini, et l'on utilise couramment les notations grand O de Landau.
Schéma d'approximation en temps polynomialEn informatique, un schéma d'approximation en temps polynomial (en anglais polynomial-time approximation scheme, abrégé en PTAS) est une famille d'algorithmes d'approximation pour des problèmes d'optimisation combinatoire. On dit aussi plus simplement schéma d'approximation polynomial. Le plus souvent, les problèmes d'optimisation combinatoire considérés sont NP-difficiles. Plusieurs variantes des PTAS existent : des définitions plus restrictives comme les EPTAS et FPTAS, ou d'autres qui reposent sur les algorithmes probabilistes comme les PRAS et FPRAS.
Facet (geometry)In geometry, a facet is a feature of a polyhedron, polytope, or related geometric structure, generally of dimension one less than the structure itself. More specifically: In three-dimensional geometry, a facet of a polyhedron is any polygon whose corners are vertices of the polyhedron, and is not a face. To facet a polyhedron is to find and join such facets to form the faces of a new polyhedron; this is the reciprocal process to stellation and may also be applied to higher-dimensional polytopes.
Conseil (informatique théorique)En théorie de la complexité, un conseil est une entrée supplémentaire passée à une machine de Turing qui dépend de la taille de l'entrée, afin d'aider la machine à reconnaître un langage. Cette notion est introduite par Richard Karp et Richard J. Lipton en 1982. Étant donnés une fonction et une classe de complexité , la classe est l'ensemble des langages tels qu'il existe un langage et une suite de conseils de taille tels que pour toute entrée de taille , si et seulement si .
Parameterized approximation algorithmA parameterized approximation algorithm is a type of algorithm that aims to find approximate solutions to NP-hard optimization problems in polynomial time in the input size and a function of a specific parameter. These algorithms are designed to combine the best aspects of both traditional approximation algorithms and fixed-parameter tractability. In traditional approximation algorithms, the goal is to find solutions that are at most a certain factor away from the optimal solution, known as an -approximation, in polynomial time.
5-polytopeIn geometry, a five-dimensional polytope (or 5-polytope) is a polytope in five-dimensional space, bounded by (4-polytope) facets, pairs of which share a polyhedral cell. A 5-polytope is a closed five-dimensional figure with vertices, edges, faces, and cells, and 4-faces. A vertex is a point where five or more edges meet. An edge is a line segment where four or more faces meet, and a face is a polygon where three or more cells meet. A cell is a polyhedron, and a 4-face is a 4-polytope.
ConnexionnismeLe connexionnisme est une approche utilisée en sciences cognitives, neurosciences, psychologie et philosophie de l'esprit. Le connexionnisme modélise les phénomènes mentaux ou comportementaux comme des processus émergents de réseaux d'unités simples interconnectées. Le plus souvent les connexionnistes modélisent ces phénomènes à l'aide de réseaux de neurones. Il s'agit d'une théorie qui a émergé à la fin des années 1980 en tant qu'alternative au computationnalisme (Putnam, Fodor) alors dominant.
HypercubeUn hypercube est, en géométrie, un analogue n-dimensionnel d'un carré (n = 2) et d'un cube (n = 3). C'est une figure fermée, compacte, convexe constituée de groupes de segments parallèles opposés alignés dans chacune des dimensions de l'espace, à angle droit les uns par rapport aux autres. Un hypercube n-dimensionnel est aussi appelé un n-cube. Le terme « polytope de mesure » a aussi été utilisé (notamment par Coxeter), mais il est tombé en désuétude. Enfin, le cas particulier du 4-cube est souvent désigné par le terme de tesseract.
6-polytopeIn six-dimensional geometry, a six-dimensional polytope or 6-polytope is a polytope, bounded by 5-polytope facets. A 6-polytope is a closed six-dimensional figure with vertices, edges, faces, cells (3-faces), 4-faces, and 5-faces. A vertex is a point where six or more edges meet. An edge is a line segment where four or more faces meet, and a face is a polygon where three or more cells meet. A cell is a polyhedron. A 4-face is a polychoron, and a 5-face is a 5-polytope.
