ComputationA computation is any type of arithmetic or non-arithmetic calculation that is well-defined. Common examples of computations are mathematical equations and computer algorithms. Mechanical or electronic devices (or, historically, people) that perform computations are known as computers. The study of computation is the field of computability, itself a sub-field of computer science. The notion that mathematical statements should be ‘well-defined’ had been argued by mathematicians since at least the 1600s, but agreement on a suitable definition proved elusive.
Theory of computationIn theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., approximate solutions versus precise ones). The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?".
Model of computationIn computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes how units of computations, memories, and communications are organized. The computational complexity of an algorithm can be measured given a model of computation. Using a model allows studying the performance of algorithms independently of the variations that are specific to particular implementations and specific technology.
Entropie (thermodynamique)L'entropie est une grandeur physique qui caractérise le degré de désorganisation d'un système. Introduite en 1865 par Rudolf Clausius, elle est nommée à partir du grec , littéralement « action de se retourner » pris au sens de « action de se transformer ». En thermodynamique, l'entropie est une fonction d'état extensive (c'est-à-dire, proportionnelle à la quantité de matière dans le système considéré). Elle est généralement notée , et dans le Système international d'unités elle s'exprime en joules par kelvin ().
Entropie de ShannonEn théorie de l'information, l'entropie de Shannon, ou plus simplement entropie, est une fonction mathématique qui, intuitivement, correspond à la quantité d'information contenue ou délivrée par une source d'information. Cette source peut être un texte écrit dans une langue donnée, un signal électrique ou encore un fichier informatique quelconque (suite d'octets). Elle a été introduite par Claude Shannon. Du point de vue d'un récepteur, plus la source émet d'informations différentes, plus l'entropie (ou incertitude sur ce que la source émet) est grande.
Mécanique newtonienneLa mécanique newtonienne est une branche de la physique. Depuis les travaux d'Albert Einstein, elle est souvent qualifiée de mécanique classique. La mécanique classique ou mécanique newtonienne est une théorie physique qui décrit le mouvement des objets macroscopiques lorsque leur vitesse est faible par rapport à celle de la lumière. Avant de devenir une science à part entière, la mécanique a longtemps été une section des mathématiques. De nombreux mathématiciens y ont apporté une contribution souvent décisive, parmi eux des grands noms tels qu'Euler, Cauchy, Lagrange.
Statistical mechanicsIn physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. It does not assume or postulate any natural laws, but explains the macroscopic behavior of nature from the behavior of such ensembles. Sometimes called statistical physics or statistical thermodynamics, its applications include many problems in the fields of physics, biology, chemistry, and neuroscience.
Couplage (théorie des graphes)En théorie des graphes, un couplage ou appariement (en anglais matching) d'un graphe est un ensemble d'arêtes de ce graphe qui n'ont pas de sommets en commun. Soit un graphe simple non orienté G = (S, A) (où S est l'ensemble des sommets et A l'ensemble des arêtes, qui sont certaines paires de sommets), un couplage M est un ensemble d'arêtes deux à deux non adjacentes. C'est-à-dire que M est une partie de l'ensemble A des arêtes telle que Un couplage maximum est un couplage contenant le plus grand nombre possible d'arêtes.
Propagation des convictionsLa propagation des convictions (Belief Propagation ou BP en anglais), aussi connu comme la transmission de message somme-produit, est un algorithme à passage de message pour effectuer des inférences sur des modèles graphiques, tels que les réseaux Bayésiens et les champs de Markov. Il calcule la distribution marginale de chaque nœud « non-observé » conditionnée sur les nœuds observés.
Perfect matchingIn graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph G = (V, E), a perfect matching in G is a subset M of edge set E, such that every vertex in the vertex set V is adjacent to exactly one edge in M. A perfect matching is also called a 1-factor; see Graph factorization for an explanation of this term. In some literature, the term complete matching is used. Every perfect matching is a maximum-cardinality matching, but the opposite is not true.
Entropie de RényiL'entropie de Rényi, due à Alfréd Rényi, est une fonction mathématique qui correspond à la quantité d'information contenue dans la probabilité de collision d'une variable aléatoire. Étant donnés une variable aléatoire discrète à valeurs possibles , ainsi qu'un paramètre réel strictement positif et différent de 1, l' entropie de Rényi d'ordre de est définie par la formule : L'entropie de Rényi généralise d'autres acceptions de la notion d'entropie, qui correspondent chacune à des valeurs particulières de .
Limite thermodynamiqueEn physique statistique, la limite thermodynamique est la limite mathématique conjointe où : le nombre de particules du système considéré tend vers l'infini ; le volume du système considéré tend vers l'infini ; la densité de particules du système considéré reste constante. Dans le problème thermodynamique de la réunion de systèmes disjoints, on peut aussi voir la limite thermodynamique comme étant le passage d'effets de surface prépondérants à des effets de volume prépondérants.
Graphe aléatoirevignette|Graphe orienté aléatoire avec 20 nœuds et une probabilité de présence d'arête égale à 0,1. En mathématiques, un graphe aléatoire est un graphe généré par un processus aléatoire. Le premier modèle de graphes aléatoires a été popularisé par Paul Erdős et Alfréd Rényi dans une série d'articles publiés entre 1959 et 1968. Il y a deux modèles d'Erdős et Rényi, formellement différents, mais étroitement liés : le graphe aléatoire binomial et le graphe aléatoire uniforme.
Transformation de LegendreLa transformation de Legendre est une opération mathématique qui, schématiquement, transforme une fonction définie par sa valeur en un point en une fonction définie par sa tangente. Elle tire son nom du mathématicien Adrien-Marie Legendre. Les cas classiques d'utilisation de la transformation de Legendre se rencontrent en thermodynamique et en mécanique lagrangienne. En thermodynamique, elle permet de calculer le potentiel thermodynamique adapté à des conditions particulières.
Entropie croiséeEn théorie de l'information, l'entropie croisée entre deux lois de probabilité mesure le nombre de bits moyen nécessaires pour identifier un événement issu de l'« ensemble des événements » - encore appelé tribu en mathématiques - sur l'univers , si la distribution des événements est basée sur une loi de probabilité , relativement à une distribution de référence . L'entropie croisée pour deux distributions et sur le même espace probabilisé est définie de la façon suivante : où est l'entropie de , et est la divergence de Kullback-Leibler entre et .
Niveau d'énergieUn niveau d'énergie est une quantité utilisée pour décrire les systèmes en mécanique quantique et par extension dans la physique en général, sachant que, s'il y a bien quantification de l'énergie, à un niveau d'énergie donné correspond un « état du système » donné ; à moins que le niveau d'énergie soit dit « dégénéré ». La notion de niveau d'énergie a été proposée en 1913 par le physicien danois Niels Bohr.
Entropy (statistical thermodynamics)The concept entropy was first developed by German physicist Rudolf Clausius in the mid-nineteenth century as a thermodynamic property that predicts that certain spontaneous processes are irreversible or impossible. In statistical mechanics, entropy is formulated as a statistical property using probability theory. The statistical entropy perspective was introduced in 1870 by Austrian physicist Ludwig Boltzmann, who established a new field of physics that provided the descriptive linkage between the macroscopic observation of nature and the microscopic view based on the rigorous treatment of large ensembles of microstates that constitute thermodynamic systems.
Algorithmethumb|Algorithme de découpe d'un polygone quelconque en triangles (triangulation). Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de problèmes. Le domaine qui étudie les algorithmes est appelé l'algorithmique. On retrouve aujourd'hui des algorithmes dans de nombreuses applications telles que le fonctionnement des ordinateurs, la cryptographie, le routage d'informations, la planification et l'utilisation optimale des ressources, le , le traitement de textes, la bio-informatique L' algorithme peut être mis en forme de façon graphique dans un algorigramme ou organigramme de programmation.
Problème des mariages stablesvignette|Algorithme de Gale Shapley. En mathématiques, informatique et économie, le problème des mariages stables consiste à trouver, étant donné n hommes et n femmes, et leurs listes de préférences, une façon stable de les mettre en couple. Une situation est dite instable s'il y a au moins un homme et une femme qui préféreraient se mettre en couple plutôt que de rester avec leurs partenaires actuels (Dupont préfère à , et préfère Dupont à Durand). Ce problème a des applications en économie, en théorie des jeux et en physique statistique.
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.
