Complexe simplicialthumb|Exemple d'un complexe simplicial.En mathématiques, un complexe simplicial est un objet géométrique déterminé par une donnée combinatoire et permettant de décrire certains espaces topologiques en généralisant la notion de triangulation d'une surface. Un tel objet se présente comme un graphe avec des sommets reliés par des arêtes, sur lesquelles peuvent se rattacher des faces triangulaires, elles-mêmes bordant éventuellement des faces de dimension supérieure, etc.
Abstract simplicial complexIn combinatorics, an abstract simplicial complex (ASC), often called an abstract complex or just a complex, is a family of sets that is closed under taking subsets, i.e., every subset of a set in the family is also in the family. It is a purely combinatorial description of the geometric notion of a simplicial complex. For example, in a 2-dimensional simplicial complex, the sets in the family are the triangles (sets of size 3), their edges (sets of size 2), and their vertices (sets of size 1).
Théorie de l'homotopieLa théorie de l'homotopie est une branche des mathématiques issue de la topologie algébrique dans laquelle les espaces et applications sont considérés à homotopie près. La notion topologique de déformation est étendue à des contextes algébriques notamment via les structures de complexe différentiel puis d’algèbre A. Étant donné deux équivalences d’homotopie f : X′ → X et g : Y → Y′, l’ensemble des classes d'homotopie des applications continues entre X et Y s’identifie à celui des applications entre X′ et Y′ par composition avec f et g.
Groupe d'homotopieEn mathématiques, et plus particulièrement en topologie algébrique, les groupes d'homotopie sont des invariants qui généralisent la notion de groupe fondamental aux dimensions supérieures. Il y a plusieurs définitions équivalentes possibles. Première définition Soit X un espace topologique et un point de X. Soit la boule unité de dimension i de l'espace euclidien . Son bord est la sphère unité de dimension . Le i-ième groupe d'homotopie supérieur est l'ensemble des classes d'homotopie relative à d'applications continues telle que : .
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.
Ensemble simplicialEn mathématiques, un ensemble simplicial X est un objet de nature combinatoire intervenant en topologie. Il est la donnée : d'une famille (X) d'ensembles, indexée par les entiers naturels, les éléments de X étant pensés comme des simplexes de dimension n et pour toute application croissanted'une application le tout tel que Autrement dit : X est un foncteur contravariant, de la catégorie simpliciale Δ dans la catégorie Set des ensembles, ou encore un foncteur covariant de la catégorie opposée Δ dans Set.
Simplicial homologyIn algebraic topology, simplicial homology is the sequence of homology groups of a simplicial complex. It formalizes the idea of the number of holes of a given dimension in the complex. This generalizes the number of connected components (the case of dimension 0). Simplicial homology arose as a way to study topological spaces whose building blocks are n-simplices, the n-dimensional analogs of triangles. This includes a point (0-simplex), a line segment (1-simplex), a triangle (2-simplex) and a tetrahedron (3-simplex).
Réduction polynomialeUne réduction polynomiale est un outil d'informatique théorique, plus particulièrement de théorie de la complexité. C'est une classe particulière de réductions particulièrement importante, notamment pour le problème P = NP. Dans le cadre des langages formels pour les problèmes de décision, on dit qu'un langage est réductible en temps polynomial à un langage (noté ) s'il existe une fonction calculable en temps polynomial telle que pour tout , si et seulement si .
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.
HomotopieEn mathématiques, une homotopie est une déformation continue entre deux applications, notamment entre les chemins à extrémités fixées et en particulier les lacets. Cette notion topologique permet de définir des invariants algébriques utilisés pour classifier les applications continues entre espaces topologiques dans le cadre de la topologie algébrique. L’homotopie induit une relation d'équivalence sur les applications continues, compatible avec la composition, qui mène à la définition de l’équivalence d'homotopie entre espaces topologiques.
