Problème de décisionEn informatique théorique, un problème de décision est une question mathématique dont la réponse est soit « oui », soit « non ». Les logiciens s'y sont intéressés à cause de l'existence ou de la non-existence d'un algorithme répondant à la question posée. Les problèmes de décision interviennent dans deux domaines de la logique : la théorie de la calculabilité et la théorie de la complexité. Parmi les problèmes de décision citons par exemple le problème de l'arrêt, le problème de correspondance de Post ou le dernier théorème de Fermat.
Optimization problemIn mathematics, computer science and economics, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables are continuous or discrete: An optimization problem with discrete variables is known as a discrete optimization, in which an object such as an integer, permutation or graph must be found from a countable set.
Polynôme de LaguerreEn mathématiques, les polynômes de Laguerre, nommés d'après Edmond Laguerre, sont les solutions normalisées de l'équation de Laguerre : qui est une équation différentielle linéaire homogène d'ordre 2 et se réécrit sous la forme de Sturm-Liouville : Cette équation a des solutions non singulières seulement si n est un entier positif. Les solutions L forment une suite de polynômes orthogonaux dans L (R, edx), et la normalisation se fait en leur imposant d'être de norme 1, donc de former une famille orthonormale.
Polynômethumb|Courbe représentative d'une fonction cubique. En mathématiques, un polynôme est une expression formée uniquement de produits et de sommes de constantes et d'indéterminées, habituellement notées X, Y, Z... Ces objets sont largement utilisés en pratique, ne serait-ce que parce qu'ils donnent localement une valeur approchée de toute fonction dérivable (voir l'article Développement limité) et permettent de représenter des formes lisses (voir l'article Courbe de Bézier, décrivant un cas particulier de fonction polynomiale).
Polynôme de Legendrethumb|upright=1.5|Polynômes de Legendre En mathématiques et en physique théorique, les polynômes de Legendre constituent l'exemple le plus simple d'une suite de polynômes orthogonaux. Ce sont des solutions polynomiales P(x), sur l'intervalle x ∈ [–1, 1], de l'équation différentielle de Legendre : dans le cas particulier où le paramètre n est un entier naturel. De façon équivalente, les polynômes de Legendre sont les fonctions propres de l'endomorphisme de R[X] défini par : pour les valeurs propres .
Optimisation linéairethumb|upright=0.5|Optimisation linéaire dans un espace à deux dimensions (x1, x2). La fonction-coût fc est représentée par les lignes de niveau bleues à gauche et par le plan bleu à droite. L'ensemble admissible E est le pentagone vert. En optimisation mathématique, un problème d'optimisation linéaire demande de minimiser une fonction linéaire sur un polyèdre convexe. La fonction que l'on minimise ainsi que les contraintes sont décrites par des fonctions linéaires, d'où le nom donné à ces problèmes.
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.
Polynôme d'HermiteEn mathématiques, les polynômes d'Hermite sont une suite de polynômes qui a été nommée ainsi en l'honneur de Charles Hermite (bien qu'ils aient été définis, sous une autre forme, en premier par Pierre-Simon Laplace en 1810, surtout été étudiés par Joseph-Louis Lagrange lors de ses travaux sur les probabilités puis en détail par Pafnouti Tchebychev six ans avant Hermite). Ils sont parfois décrits comme des polynômes osculateurs.
Problème algorithmiqueUn problème algorithmique est, en informatique théorique, un objet mathématique qui représente une question ou un ensemble de questions auxquelles un ordinateur devrait être en mesure de répondre. Le plus souvent, ces problèmes sont de la forme : étant donné un objet (l'instance), effectuer une certaine action ou répondre à telle question. Par exemple, le problème de la factorisation est le problème suivant : étant donné un nombre entier, trouver un facteur premier de cet entier.
Optimisation (mathématiques)L'optimisation est une branche des mathématiques cherchant à modéliser, à analyser et à résoudre analytiquement ou numériquement les problèmes qui consistent à minimiser ou maximiser une fonction sur un ensemble. L’optimisation joue un rôle important en recherche opérationnelle (domaine à la frontière entre l'informatique, les mathématiques et l'économie), dans les mathématiques appliquées (fondamentales pour l'industrie et l'ingénierie), en analyse et en analyse numérique, en statistique pour l’estimation du maximum de vraisemblance d’une distribution, pour la recherche de stratégies dans le cadre de la théorie des jeux, ou encore en théorie du contrôle et de la commande.
NP-difficilevignette|300px|Mise en évidence d'un problème NP-difficile si Problème P ≟ NP. Un problème NP-difficile est, en théorie de la complexité, un problème appartenant à la classe NP-difficile, ce qui revient à dire qu'il est au moins aussi difficile que les problèmes les plus difficiles de la classe NP. Ainsi, un problème H est NP-difficile, si tout problème L de la classe NP peut être réduit en temps polynomial à H. Si un problème NP-difficile est dans NP, alors c'est un problème NP-complet.
Optimisation combinatoireL’optimisation combinatoire, (sous-ensemble à nombre de solutions finies de l'optimisation discrète), est une branche de l'optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l'algorithmique et la théorie de la complexité. Dans sa forme la plus générale, un problème d'optimisation combinatoire (sous-ensemble à nombre de solutions finies de l'optimisation discrète) consiste à trouver dans un ensemble discret un parmi les meilleurs sous-ensembles (ou solutions) réalisables, la notion de meilleure solution étant définie par une fonction objectif.
Problème NP-completEn théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) est un problème de décision vérifiant les propriétés suivantes : il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes vérifiant cette propriété est notée NP ; tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale ; cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de l
Méthodes de points intérieursvignette|Visualisation de la méthode des points intérieur : le chemin reste à l’intérieur du polyèdre. vignette|Visualisation de la méthode du simplexe : le chemin suit les arêtes du polyèdre vignette|Visualisation de la méthode par ellipsoïde : l’ellipse se rétrécit Les méthodes de points intérieurs forment une classe d’algorithmes qui permettent de résoudre des problèmes d’optimisation mathématique.
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.
Problème du sac à dosEn algorithmique, le problème du sac à dos, parfois noté (KP) (de l'anglais Knapsack Problem) est un problème d'optimisation combinatoire. Ce problème classique en informatique et en mathématiques modélise une situation analogue au remplissage d'un sac à dos. Il consiste à trouver la combinaison d'éléments la plus précieuse à inclure dans un sac à dos, étant donné un ensemble d'éléments décrits par leurs poids et valeurs.
Informatiquealt=Salle informatique de la bibliothèque d'Art et d'Archéologie de Genève|vignette|Salle informatique de la bibliothèque d'Art et d'Archéologie de Genève (2017). L'informatique est un domaine d'activité scientifique, technique, et industriel concernant le traitement automatique de l'information numérique par l'exécution de programmes informatiques hébergés par des dispositifs électriques-électroniques : des systèmes embarqués, des ordinateurs, des robots, des automates Ces champs d'application peuvent être séparés en deux branches : théorique : concerne la définition de concepts et modèles ; pratique : s'intéresse aux techniques concrètes de mise en œuvre.
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.
Polynôme de TchebychevEn mathématiques, un polynôme de Tchebychev est un terme de l'une des deux suites de polynômes orthogonaux particulières reliées à la formule de Moivre. Les polynômes de Tchebychev sont nommés ainsi en l'honneur du mathématicien russe Pafnouti Lvovitch Tchebychev. Il existe deux suites de polynômes de Tchebychev, l'une nommée polynômes de Tchebychev de première espèce et notée T et l'autre nommée polynômes de Tchebychev de seconde espèce et notée U (dans les deux cas, l'entier naturel n correspond au degré).
Problème de flot maximumthumb|right|Un exemple de graphe de flot avec un flot maximum. la source est , et le puits . Les nombres indiquent le flot et la capacité. Le problème de flot maximum consiste à trouver, dans un réseau de flot, un flot réalisable depuis une source unique et vers un puits unique qui soit maximum. Quelquefois, on ne s'intéresse qu'à la valeur de ce flot. Le s-t flot maximum (depuis la source s vers le puits t) est égal à la s-t coupe minimum du graphe, comme l'indique le théorème flot-max/coupe-min.
