Algorithme probabilisteEn algorithmique, un algorithme probabiliste, ou algorithme randomisé, est un algorithme qui utilise une source de hasard. Plus précisément le déroulement de l’algorithme fait appel à des données tirées au hasard. Par exemple à un certain point de l’exécution, on tire un bit 0 ou 1, selon la loi uniforme et si le résultat est 0, on fait une certaine action A et si c'est 1, on fait une autre action. On peut aussi tirer un nombre réel dans l'intervalle [0,1] ou un entier dans un intervalle [i..j].
Distance (théorie des graphes)En théorie des graphes, la distance entre deux nœuds d'un graphe est la longueur d'un plus court chemin entre ces deux nœuds. La longueur d'un chemin est sa longueur en nombre d'arêtes. Pour un graphe pondéré c'est la somme des poids des arêtes empruntées. Pour les graphes non orientés, c'est une distance au sens mathématique, tandis que pour les graphes orientés elle ne vérifie pas la propriété de symétrie. Cette notion permet entre autres de définir le diamètre et le rayon d'un graphe. Catégorie:Concept
Coût d'opportunitéLe coût d'opportunité (de l'anglais opportunity cost), également appelé coût d'option, coût alternatif, coût de substitution, coût de renonciation ou encore coût de renoncement désigne la perte des biens auxquels on renonce lorsqu'on procède à un choix, autrement dit lorsqu'on affecte les ressources disponibles à un usage donné au détriment d'autres choix. C'est le coût d'une chose estimé en termes d'opportunités non réalisées, ou encore la valeur de la meilleure autre option non réalisée.
Component (graph theory)In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components. The number of components in a given graph is an important graph invariant, and is closely related to invariants of matroids, topological spaces, and matrices.
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.
Optimisation de codeEn programmation informatique, l'optimisation de code est la pratique consistant à améliorer l'efficacité du code informatique d'un programme ou d'une bibliothèque logicielle. Ces améliorations permettent généralement au programme résultant de s'exécuter plus rapidement, de prendre moins de place en mémoire, de limiter sa consommation de ressources (par exemple les fichiers), ou de consommer moins d'énergie électrique. La règle numéro un de l'optimisation est qu'elle ne doit intervenir qu'une fois que le programme fonctionne et répond aux spécifications fonctionnelles.
Optimizing compilerIn computing, an optimizing compiler is a compiler that tries to minimize or maximize some attributes of an executable computer program. Common requirements are to minimize a program's execution time, memory footprint, storage size, and power consumption (the last three being popular for portable computers). Compiler optimization is generally implemented using a sequence of optimizing transformations, algorithms which take a program and transform it to produce a semantically equivalent output program that uses fewer resources or executes faster.
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.
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.
Recherche de cheminLa recherche de chemin, couramment appelée pathfinding par anglicisme, est un problème de l'intelligence artificielle qui se rattache plus généralement au domaine de la planification et de la recherche de solution. Il consiste à trouver comment se déplacer dans un environnement entre un point de départ et un point d'arrivée en prenant en compte différentes contraintes. Initialement, un problème de pathfinding peut se ramener à un problème de recherche du meilleur chemin entre deux nœuds dans un graphe.
Complexité en espaceEn algorithmique, la complexité en espace est une mesure de l'espace utilisé par un algorithme, en fonction de propriétés de ses entrées. L'espace compte le nombre maximum de cases mémoire utilisées simultanément pendant un calcul. Par exemple le nombre de symboles qu'il faut conserver pour pouvoir continuer le calcul. Usuellement l'espace que l'on prend en compte lorsque l'on parle de l'espace nécessaire pour des entrées ayant des propriétés données est l'espace nécessaire le plus grand parmi ces entrées ; on parle de complexité en espace dans le pire cas.
Optimisation convexevignette|320x320px|Optimisation convexe dans un espace en deux dimensions dans un espace contraint L'optimisation convexe est une sous-discipline de l'optimisation mathématique, dans laquelle le critère à minimiser est convexe et l'ensemble admissible est convexe. Ces problèmes sont plus simples à analyser et à résoudre que les problèmes d'optimisation non convexes, bien qu'ils puissent être NP-difficile (c'est le cas de l'optimisation copositive). La théorie permettant d'analyser ces problèmes ne requiert pas la différentiabilité des fonctions.
