Programmation par contraintesLa programmation par contraintes (PPC, ou CP pour constraint programming en anglais) est un paradigme de programmation apparu dans les années 1970 et 1980 permettant de résoudre des problèmes combinatoires de grande taille tels que les problèmes de planification et d'ordonnancement. En programmation par contraintes, on sépare la partie modélisation à l'aide de problèmes de satisfaction de contraintes (ou CSP pour Constraint Satisfaction Problem), de la partie résolution dont la particularité réside dans l'utilisation active des contraintes du problème pour réduire la taille de l'espace des solutions à parcourir (on parle de propagation de contraintes).
Problème de satisfaction de contraintesLes problèmes de satisfaction de contraintes ou CSP (Constraint Satisfaction Problem) sont des problèmes mathématiques où l'on cherche des états ou des objets satisfaisant un certain nombre de contraintes ou de critères. Les CSP font l'objet de recherches intenses à la fois en intelligence artificielle et en recherche opérationnelle. De nombreux CSP nécessitent la combinaison d'heuristiques et de méthodes d'optimisation combinatoire pour être résolus en un temps raisonnable.
Constraint satisfactionIn artificial intelligence and operations research, constraint satisfaction is the process of finding a solution through a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a set of values for the variables that satisfies all constraints—that is, a point in the feasible region. The techniques used in constraint satisfaction depend on the kind of constraints being considered.
Graphe orienté acycliqueEn théorie des graphes, un graphe orienté acyclique (en anglais directed acyclic graph ou DAG), est un graphe orienté qui ne possède pas de circuit. Un tel graphe peut être vu comme une hiérarchie. Un graphe orienté acyclique est un graphe orienté qui ne possède pas de circuit. On peut toujours trouver un sous-graphe couvrant d’un graphe orienté acyclique qui soit un arbre (resp. une forêt). Dans un graphe orienté acyclique, la relation d'accessibilité R(u, v) définie par « il existe un chemin de u à v » est une relation d'ordre partielle.
Propagation de contraintesLa propagation de contraintes dans le domaine de la programmation par contraintes est le fait de réduire le domaine d'une variable afin de maintenir l'ensemble des valeurs possibles cohérent avec les contraintes du problème. La propagation de contraintes permet ainsi de résoudre un problème si la propagation permet d'établir la cohérence du problème. Les techniques de propagation de contraintes sont utilisées pour réduire la taille de l'espace de recherche lors de la résolution d'un problème de satisfaction de contraintes par un algorithme de recherche arborescente.
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.
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.
Graphe orientéthumb|Un graphe orienté .(Figure 1) Dans la théorie des graphes, un graphe orienté est un couple formé de un ensemble, appelé ensemble de nœuds et un ensemble appelé ensemble d'arêtes. Les arêtes sont alors nommées arcs, chaque arête étant un couple de noeuds, représenté par une flèche. Étant donné un arc , on dit que est l'origine (ou la source ou le départ ou le début) de et que est la cible (ou l'arrivée ou la fin) de . Le demi-degré extérieur (degré sortant) d'un nœud, noté , est le nombre d'arcs ayant ce nœud pour origine.
Constraint logic programmingConstraint logic programming is a form of constraint programming, in which logic programming is extended to include concepts from constraint satisfaction. A constraint logic program is a logic program that contains constraints in the body of clauses. An example of a clause including a constraint is . In this clause, is a constraint; A(X,Y), B(X), and C(Y) are literals as in regular logic programming. This clause states one condition under which the statement A(X,Y) holds: X+Y is greater than zero and both B(X) and C(Y) are true.
Recherche exhaustiveLa recherche exhaustive ou recherche par force brute est une méthode algorithmique qui consiste principalement à essayer toutes les solutions possibles. Par exemple pour trouver le maximum d'un certain ensemble de valeurs, on consulte toutes les valeurs. En cryptanalyse on parle d'attaque par force brute, ou par recherche exhaustive pour les attaques utilisant cette méthode. Le principe de cet algorithme est d'essayer toutes les possibilités dans un intervalle. Un exemple courant est l'attaque par force brute des mots de passe.
