Système dynamique mesuréUn système dynamique mesuré est un objet mathématique, représentant un espace de phases muni d'une loi d'évolution, particulièrement étudié en théorie ergodique. Un système dynamique mesuré est la donnée d'un espace probabilisé et d'une application mesurable f : X → X. On exige que f préserve la mesure, ce qui veut dire que : Cette propriété très riche permet d'obtenir de puissants théorèmes. Par ailleurs, un théorème affirme qu'il existe, pour toute transformation continue X → X d'un espace topologique compact X, une mesure de probabilité, borélienne, préservant cette transformation.
Interval exchange transformationIn mathematics, an interval exchange transformation is a kind of dynamical system that generalises circle rotation. The phase space consists of the unit interval, and the transformation acts by cutting the interval into several subintervals, and then permuting these subintervals. They arise naturally in the study of polygonal billiards and in area-preserving flows. Let and let be a permutation on . Consider a vector of positive real numbers (the widths of the subintervals), satisfying Define a map called the interval exchange transformation associated with the pair as follows.
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.
Suite définie par récurrenceEn mathématiques, une suite définie par récurrence est une suite définie par son (ou ses) premier(s) terme(s) et par une relation de récurrence, qui définit chaque terme à partir du précédent ou des précédents lorsqu'ils existent. Une relation de récurrence est une équation dans laquelle l'expression de plusieurs termes de la suite apparait, par exemple : ou ou ou si l'on se place dans les suites de mots sur l'alphabet : Si la relation de récurrence a une « bonne » présentation, cela permet de calculer l'expression du terme d'indice le plus élevé en fonction de l'expression des autres.
Chat d'ArnoldEn mathématiques, l'application chat d'Arnold est une certaine bijection du tore vers lui-même. Cette fonction sert à illustrer des comportements chaotiques en théorie des systèmes dynamiques. Elle porte ce nom inhabituel parce que Vladimir Arnold l'a décrite en 1967 en s'aidant du dessin d'un chat. thumb|L'effet de l'opération modulo sur le parallélogramme. On peut repérer les points sur le tore à l'aide de deux coordonnées x et y chacune dans l'intervalle [0, 1], cela revient à « déplier » ce tore pour obtenir un carré.
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).
AttracteurDans l'étude des systèmes dynamiques, un attracteur (ou ensemble-limite) est un ensemble d'états vers lequel un système évolue de façon irréversible en l'absence de perturbations. Constituants de base de la théorie du chaos, au moins cinq types sont définis : ponctuel, quasi périodique, périodique, étrange et spatial. Stephen Smale serait à l'origine du terme attracteur.
Optimizing compilerIn computing, an optimizing compiler is a compiler that tries to minimize or maximize some attributes of an executable computer program. Common requirements are to minimize a program's execution time, memory footprint, storage size, and power consumption (the last three being popular for portable computers). Compiler optimization is generally implemented using a sequence of optimizing transformations, algorithms which take a program and transform it to produce a semantically equivalent output program that uses fewer resources or executes faster.
Tent mapIn mathematics, the tent map with parameter μ is the real-valued function fμ defined by the name being due to the tent-like shape of the graph of fμ. For the values of the parameter μ within 0 and 2, fμ the unit interval [0, 1] into itself, thus defining a discrete-time dynamical system on it (equivalently, a recurrence relation). In particular, iterating a point x0 in [0, 1] gives rise to a sequence : where μ is a positive real constant.
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.
