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.
Fonction de répartitionEn théorie des probabilités, la fonction de répartition, ou fonction de distribution cumulative, d'une variable aléatoire réelle X est la fonction F_X qui, à tout réel x, associe la probabilité d’obtenir une valeur inférieure ou égale : Cette fonction est caractéristique de la loi de probabilité de la variable aléatoire.
Hiérarchie polynomialeEn théorie de la complexité, la hiérarchie polynomiale est une hiérarchie de classes de complexité qui étend la notion de classes P, NP, co-NP. La classe PH est l'union de toutes les classes de la hiérarchie polynomiale. Il existe plusieurs définitions équivalentes des classes de la hiérarchie polynomiale. On peut définir la hiérarchie à l'aide des quantificateurs universel () et existentiel ().
Problème P ≟ NPvignette|400px|Représentation visuelle des deux configurations possibles. Le problème P ≟ NP est une conjecture en mathématiques, et plus précisément en informatique théorique, considérée par de nombreux chercheurs comme une des plus importantes conjectures du domaine, et même des mathématiques en général. L'Institut de mathématiques Clay a inclus ce problème dans sa liste des sept problèmes du prix du millénaire, et offre à ce titre un million de dollars à quiconque sera en mesure de démontrer P = NP ou P ≠ NP ou de démontrer que ce n'est pas démontrable.
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.
Biais algorithmiquevignette|Organigramme représentant l'algorithme derrière un moteur de recommandation. Un biais algorithmique est le fait que le résultat d'un algorithme d'apprentissage ne soit pas neutre, loyal ou équitable. Le biais algorithmique peut se produire lorsque les données utilisées pour entraîner un algorithme d'apprentissage automatique reflètent les valeurs implicites des humains impliqués dans la collecte, la sélection, ou l'utilisation de ces données.
Algorithme gloutonUn algorithme glouton (greedy algorithm en anglais, parfois appelé aussi algorithme gourmand, ou goulu) est un algorithme qui suit le principe de réaliser, étape par étape, un choix optimum local, afin d'obtenir un résultat optimum global. Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins possible de pièces), l'algorithme consistant à répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la somme restante est un algorithme glouton.
Apprentissage de représentationsEn apprentissage automatique, l'apprentissage des caractéristiques ou apprentissage des représentations est un ensemble de techniques qui permet à un système de découvrir automatiquement les représentations nécessaires à la détection ou à la classification des caractéristiques à partir de données brutes. Cela remplace l'ingénierie manuelle des fonctionnalités et permet à une machine d'apprendre les fonctionnalités et de les utiliser pour effectuer une tâche spécifique.
Fonction quantileEn probabilités, la fonction quantile est une fonction qui définit les quantiles. Soit X une variable aléatoire et F sa fonction de répartition, la fonction quantile est définie par pour toute valeur de , la notation désignant l’inverse généralisé à gauche de . Si F est une fonction strictement croissante et continue, alors est l'unique valeur de telle que . correspond alors à la fonction réciproque de , notée . En revanche, pour les lois discrètes, les fonctions de répartition sont toutes en escalier, d'où l'intérêt de la définition précédente.
NP (complexité)La classe NP est une classe très importante de la théorie de la complexité. L'abréviation NP signifie « non déterministe polynomial » (« en »). Un problème de décision est dans NP s'il est décidé par une machine de Turing non déterministe en temps polynomial par rapport à la taille de l'entrée. Intuitivement, cela revient à dire qu'on peut vérifier « rapidement » (complexité polynomiale) si une solution candidate est bien solution.
Perceptrons (book)Perceptrons: an introduction to computational geometry is a book written by Marvin Minsky and Seymour Papert and published in 1969. An edition with handwritten corrections and additions was released in the early 1970s. An expanded edition was further published in 1987, containing a chapter dedicated to counter the criticisms made of it in the 1980s. The main subject of the book is the perceptron, a type of artificial neural network developed in the late 1950s and early 1960s.
Coordinate descentCoordinate descent is an optimization algorithm that successively minimizes along coordinate directions to find the minimum of a function. At each iteration, the algorithm determines a coordinate or coordinate block via a coordinate selection rule, then exactly or inexactly minimizes over the corresponding coordinate hyperplane while fixing all other coordinates or coordinate blocks. A line search along the coordinate direction can be performed at the current iterate to determine the appropriate step size.
