Problème 2-SATEn informatique théorique, le problème 2-SAT est un problème de décision. C'est une restriction du problème SAT qui peut être résolu en temps polynomial, alors que le problème général est NP complet. Le problème 2-SAT consiste à décider si une formule booléenne en forme normale conjonctive, dont toutes les clauses sont de taille 2, est satisfaisable. De telles formules sont appelées 2-CNF ou formules de Krom. On considère des formules en forme normale conjonctive, c'est-à-dire que ce sont des ET de OU de littéraux (un littéral est une variable ou la négation d'une variable).
Horn-satisfiabilitéUne formule de Horn est une conjonction de clauses contenant chacune au plus un littéral positif, c'est-à-dire une conjonction de clauses de Horn. Puisque le problème SAT est NP-complet, donc vérifiable en temps polynomial et plus difficile que tout problème dans NP, il est naturel de rechercher des problèmes proches mais plus "faciles" à résoudre. C'est notamment le cas de la satisfaisabilité d'une formule de Horn, puisqu'il s'agit d'un problème P-complet, plus difficile que tout problème dans P.
Generalized algebraic data typeIn functional programming, a generalized algebraic data type (GADT, also first-class phantom type, guarded recursive datatype, or equality-qualified type) is a generalization of parametric algebraic data types. In a GADT, the product constructors (called data constructors in Haskell) can provide an explicit instantiation of the ADT as the type instantiation of their return value. This allows defining functions with a more advanced type behaviour.
Programmation fonctionnelleLa programmation fonctionnelle est un paradigme de programmation de type déclaratif qui considère le calcul en tant qu'évaluation de fonctions mathématiques. Comme le changement d'état et la mutation des données ne peuvent pas être représentés par des évaluations de fonctions la programmation fonctionnelle ne les admet pas, au contraire elle met en avant l'application des fonctions, contrairement au modèle de programmation impérative qui met en avant les changements d'état.
Formule de CayleyEn mathématiques, et plus particulièrement en théorie des graphes, la formule de Cayley est un résultat sur les arbres du théoricien Arthur Cayley. Elle affirme le résultat suivant : Note : on parle aussi d'arbres décorés ou étiquetés pour dire que l'on identifie les sommets avec des couleurs, des nombres, etc. On parle aussi d'arbres de Cayley. Pour l'exemple illustré ci-contre, on obtient les résultats suivants, en appliquant le théorème : 1 arbre avec 2 sommets, 3 arbres avec 3 sommets, 16 arbres avec 4 sommets.
Futures (informatique)En programmation, les notions de futurs (« futures »), promesses (« promises ») ou délais (« delay ») font référence à des techniques de synchronisation pour certains langages concurrents. Il s'agit d'abstractions qui servent de proxy pour un résultat non-connu au moment où il est référencé pour la première fois, car son calcul ou son obtention se feront « plus tard » à l'exécution. Le terme générique de promise (« promesse ») a été proposé par Daniel P. Friedman et David Wise en 1976 ; Peter Hibbard le dénommait eventual à la même époque.
Arbre couvrantDans le domaine mathématique de la théorie des graphes, un arbre couvrant d'un graphe non orienté et connexe est un arbre inclus dans ce graphe et qui connecte tous les sommets du graphe. De façon équivalente, c'est un sous-graphe acyclique maximal, ou encore, un sous-graphe couvrant connexe minimal. Dans certains cas, le nombre d'arbres couvrants d'un graphe connexe est facilement calculable. Par exemple, si lui-même est un arbre, alors , tandis que si est un n-cycle, alors .
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.
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.
Arbre (théorie des graphes)En théorie des graphes, un arbre est un graphe acyclique et connexe. Sa forme évoque en effet la ramification des branches d'un arbre. Par opposition aux arbres simples, arbres binaires, ou arbres généraux de l'analyse d'algorithme ou de la combinatoire analytique, qui sont des plongements particuliers d'arbres (graphes) dans le plan, on appelle parfois les arbres (graphes) arbres de Cayley, car ils sont comptés par la formule de Cayley. Un ensemble d'arbres est appelé une forêt.
