Sparse approximationSparse approximation (also known as sparse representation) theory deals with sparse solutions for systems of linear equations. Techniques for finding these solutions and exploiting them in applications have found wide use in , signal processing, machine learning, medical imaging, and more. Consider a linear system of equations , where is an underdetermined matrix and . The matrix (typically assumed to be full-rank) is referred to as the dictionary, and is a signal of interest.
Sparse dictionary learningSparse dictionary learning (also known as sparse coding or SDL) is a representation learning method which aims at finding a sparse representation of the input data in the form of a linear combination of basic elements as well as those basic elements themselves. These elements are called atoms and they compose a dictionary. Atoms in the dictionary are not required to be orthogonal, and they may be an over-complete spanning set. This problem setup also allows the dimensionality of the signals being represented to be higher than the one of the signals being observed.
Matching pursuitMatching pursuit (MP) is a sparse approximation algorithm which finds the "best matching" projections of multidimensional data onto the span of an over-complete (i.e., redundant) dictionary . The basic idea is to approximately represent a signal from Hilbert space as a weighted sum of finitely many functions (called atoms) taken from . An approximation with atoms has the form where is the th column of the matrix and is the scalar weighting factor (amplitude) for the atom . Normally, not every atom in will be used in this sum.
Classe de complexitéEn informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace.
Algorithme de rechercheEn informatique, un algorithme de recherche est un type d'algorithme qui, pour un domaine, un problème de ce domaine et des critères donnés, retourne en résultat un ensemble de solutions répondant au problème. Supposons que l'ensemble de ses entrées soit divisible en sous-ensemble, par rapport à un critère donné, qui peut être, par exemple, une relation d'ordre. De façon générale, un tel algorithme vérifie un certain nombre de ces entrées et retourne en sortie une ou plusieurs des entrées visées.
Poursuite de baseLa poursuite de base (de l'anglais basis pursuit), aussi appelée recouvrement par norme ou plus simplement recouvrement , est une technique d'optimisation mathématique utilisée initialement en traitement du signal qui revient à résoudre un problème d'optimisation de la forme où l'inconnue est un vecteur formé de nombres réels, est la norme , est une matrice réelle et . Il s'agit donc de trouver le plus petit vecteur , au sens de la norme , qui vérifie l'équation affine Ce problème est convexe (l'objectif est convexe et l'ensemble admissible est affine, donc convexe), mais non lisse (la norme n'est pas partout différentiable).
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.
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.
Complexité paramétréeEn algorithmique, la complexité paramétrée (ou complexité paramétrique) est une branche de la théorie de la complexité qui classifie les problèmes algorithmiques selon leur difficulté intrinsèque en fonction de plusieurs paramètres sur les données en entrée ou sur la sortie. Ce domaine est étudié depuis les années 90 comme approche pour la résolution exacte de problèmes NP-complets. Cette approche est utilisée en optimisation combinatoire, notamment en algorithmique des graphes, en intelligence artificielle, en théorie des bases de données et en bio-informatique.
Algorithme d'approximationEn informatique théorique, un algorithme d'approximation est une méthode permettant de calculer une solution approchée à un problème algorithmique d'optimisation. Plus précisément, c'est une heuristique garantissant à la qualité de la solution qui fournit un rapport inférieur (si l'on minimise) à une constante, par rapport à la qualité optimale d'une solution, pour toutes les instances possibles du problème.
Intérêt (finance)En finance, l'intérêt est la rémunération d'un prêt, sous forme généralement d'un versement périodique de l'emprunteur au prêteur. Pour le prêteur, c'est le prix de sa renonciation temporaire à la liquidité. Pour l'emprunteur, c'est un coût correspondant à une utilisation anticipée. Une épargne rémunérée par un intérêt est assimilable à un prêt fait à un emprunteur, comme une banque ou l'organisme bénéficiaire de cette épargne. Taux d'intérêt L'intérêt est proportionnel au capital et croît avec le temps couru.
P (complexité)La classe P, aussi noté parfois PTIME ou DTIME(nO(1)), est une classe très importante de la théorie de la complexité, un domaine de l'informatique théorique et des mathématiques. Par définition, un problème de décision est dans P s'il est décidé par une machine de Turing déterministe en temps polynomial par rapport à la taille de l'entrée. On dit que le problème est décidé en temps polynomial. Les problèmes dans P sont considérés comme « faisables » (feasible en anglais), faciles à résoudre (dans le sens où on peut le faire relativement rapidement).
Dictionnairethumb|upright=1.2|Dictionnaire en latin constitué de plusieurs volumes, œuvre d'Egidio Forcellini (1771). Un dictionnaire est un ouvrage de référence contenant un ensemble de mots d’une langue ou d’un domaine d’activité généralement présentés par ordre alphabétique et fournissant pour chacun une définition, une explication ou une correspondance (synonyme, antonyme, cooccurrence, traduction, étymologie). Le présent article concerne les dictionnaires unilingues qui décrivent ou normalisent une langue.
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).
Algorithme de Primthumb|right|Arbre couvrant de poids minimum L'algorithme de Prim est un algorithme glouton qui calcule un arbre couvrant minimal dans un graphe connexe pondéré et non orienté. En d'autres termes, cet algorithme trouve un sous-ensemble d'arêtes formant un arbre sur l'ensemble des sommets du graphe initial et tel que la somme des poids de ces arêtes soit minimale. Si le graphe n'est pas connexe, alors l'algorithme détermine un arbre couvrant minimal d'une composante connexe du graphe.
Algorithme de DijkstraEn théorie des graphes, l'algorithme de Dijkstra (prononcé ) sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer un plus court chemin pour se rendre d'une ville à une autre connaissant le réseau routier d'une région. Plus précisément, il calcule des plus courts chemins à partir d'une source vers tous les autres sommets dans un graphe orienté pondéré par des réels positifs. On peut aussi l'utiliser pour calculer un plus court chemin entre un sommet de départ et un sommet d'arrivée.
Produit scalaireEn mathématiques, et plus précisément en algèbre et en géométrie vectorielle, le produit scalaire est une opération algébrique s'ajoutant aux lois s'appliquant aux vecteurs. C'est une forme bilinéaire, symétrique, définie positive. À deux vecteurs, elle associe un scalaire, c'est-à-dire un nombre tel que ceux qui définissent cet espace vectoriel — réel pour un espace vectoriel réel. Si et sont deux vecteurs d'un espace vectoriel E sur le corps R des nombres réels, alors le produit scalaire de u par v est un scalaire (c'est-à-dire un élément de R), noté ∙ , , , ou .
Complexité de KolmogorovEn informatique théorique et en mathématiques, plus précisément en théorie de l'information, la complexité de Kolmogorov, ou complexité aléatoire, ou complexité algorithmique d'un objet — nombre, , chaîne de caractères — est la taille du plus petit algorithme (dans un certain langage de programmation fixé) qui engendre cet objet. Elle est nommée d'après le mathématicien Andreï Kolmogorov, qui publia sur le sujet dès 1963. Elle est aussi parfois nommée complexité de Kolmogorov-Solomonoff.
Segmentation d'imageLa segmentation d'image est une opération de s consistant à détecter et rassembler les pixels suivant des critères, notamment d'intensité ou spatiaux, l'image apparaissant ainsi formée de régions uniformes. La segmentation peut par exemple montrer les objets en les distinguant du fond avec netteté. Dans les cas où les critères divisent les pixels en deux ensembles, le traitement est une binarisation. Des algorithmes sont écrits comme substitut aux connaissances de haut niveau que l'homme mobilise dans son identification des objets et structures.
Multiplication par un scalairevignette|320x320px|Exemple de multiplication d'un vecteur par un scalaire En mathématiques, la multiplication par un scalaire est l'une des lois externes de base définissant un espace vectoriel en algèbre linéaire (ou plus généralement, un module en algèbre générale). Si K est un corps commutatif, la définition d'un espace vectoriel E sur K prescrit l'existence d'une loi de composition externe, une application de K × E dans E. L'image d'un couple (λ, v), pouvant être notée λv ou λ∙v, est la multiplication du vecteur v par le scalaire λ.
