Algorithme A*En informatique, plus précisément en intelligence artificielle, l'algorithme de recherche A* (qui se prononce A étoile, ou A star en anglais) est un algorithme de recherche de chemin dans un graphe entre un nœud initial et un nœud final tous deux donnés. En raison de sa simplicité il est souvent présenté comme exemple typique d'algorithme de planification, domaine de l'intelligence artificielle.
A-levelthumb|Logo de l'examen. Le A level, abréviation de Advanced Level (Niveau avancé) (titre officiel de la qualification : en), est un examen passé par les jeunes Britanniques (Angleterre, Écosse, Pays de Galles et Irlande du Nord) au cours des deux dernières années de leur éducation secondaire. En Écosse, les écoles peuvent choisir entre le A-Level et l'équivalent écossais, le . Il est l'équivalent du baccalauréat en France.
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.
Logarithme itérévignette|Graphique montrant le logarithme itéré En informatique, le logarithme itéré d'un nombre n, noté (lu "log star" ou "log étoile"), est le nombre de fois que le logarithme doit lui être appliqué avant que le résultat soit inférieur ou égal à 1. Cette fonction est utilisée pour décrire la complexité de certains algorithmes, notamment en algorithmique distribuée. Le logarithme itéré de base b peut être défini par : Sur les nombres réels positifs, le continu (l'inverse de la tétration) est essentiellement équivalente : Le tableau suivant donne les valeurs du logarithme itéré (en base 2) : Cette fonction croît extrêmement lentement.
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.
Buffer circulaireUn buffer circulaire est une structure de données utilisant un buffer de taille fixe et dont le début et la fin sont considérés comme connectés. Les buffers circulaires sont souvent utilisés pour gérer des flux de données ou pour implémenter un comportement de type FIFO. Un buffer circulaire est vide au départ et a une longueur prédéterminée. Par exemple, un buffer de sept éléments : Supposons que le nombre 1 est écrit à une position, arbitrairement définie comme position initiale : Deux éléments supplémentaires — 2 & 3 — sont alors ajoutés après le 1 : Si deux éléments sont alors retirés du buffer il s’agira des deux premiers éléments ajoutés.
Tableau de bitsUn tableau de bits (en anglais bitmap) est une structure de données, en particulier un tableau de données binaires. Il s'agit d'une collection ordonnée de bits assimilables à des booléens. Certes, l'appellation tableau évoque une grille semblable à celle des mots croisés, mais un tableau de bits peut très bien être en trois dimensions ou plus. Pour autant, le nombre d'éléments étant fini, connu, voire défini, la collection peut être inventoriée selon un chemin parcourant chaque « colonne » et chaque « ligne ».
Minimum bounding boxIn geometry, the minimum or smallest bounding or enclosing box for a point set S in N dimensions is the box with the smallest measure (area, volume, or hypervolume in higher dimensions) within which all the points lie. When other kinds of measure are used, the minimum box is usually called accordingly, e.g., "minimum-perimeter bounding box". The minimum bounding box of a point set is the same as the minimum bounding box of its convex hull, a fact which may be used heuristically to speed up computation.
Collection (type de données)En programmation informatique, une collection est un regroupement d'un nombre variable d'éléments de données (éventuellement zéro) qui ont une signification commune pour le problème à résoudre et qui doivent être traités ensemble d'une manière contrôlée. En général, les éléments de données sont du même type ou, dans les langages supportant l'héritage, dérivés d'un type ancêtre commun.
Relaxation (iterative method)In numerical mathematics, relaxation methods are iterative methods for solving systems of equations, including nonlinear systems. Relaxation methods were developed for solving large sparse linear systems, which arose as finite-difference discretizations of differential equations. They are also used for the solution of linear equations for linear least-squares problems and also for systems of linear inequalities, such as those arising in linear programming. They have also been developed for solving nonlinear systems of equations.
B+ treeA B+ tree is an m-ary tree with a variable but often large number of children per node. A B+ tree consists of a root, internal nodes and leaves. The root may be either a leaf or a node with two or more children. A B+ tree can be viewed as a B-tree in which each node contains only keys (not key–value pairs), and to which an additional level is added at the bottom with linked leaves. The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage context — in particular, .
Tri par tasthumb|300px|Animation montrant le fonctionnement du tri par tas (Heapsort). En informatique, le tri par tas est un algorithme de tri par comparaisons. Cet algorithme est de complexité asymptotiquement optimale, c'est-à-dire que l'on démontre qu'aucun algorithme de tri par comparaison ne peut avoir de complexité asymptotiquement meilleure. Sa complexité est proportionnelle à où est la longueur du tableau à trier.
Tas (informatique)vignette|Un exemple de tas. Il contient 9 éléments. L'élément le plus prioritaire (100) est à la racine. En informatique, un tas (ou monceau au Canada, heap en anglais) est une structure de données de type arbre qui permet de retrouver directement l'élément que l'on veut traiter en priorité. C'est un arbre binaire presque complet ordonné. Un arbre binaire est dit presque complet si tous ses niveaux sont remplis, sauf éventuellement le dernier, qui doit être rempli sur la gauche (cf. Contre-exemples).
Problème d'affectationEn informatique, plus précisément en recherche opérationnelle et d'optimisation combinatoire, le problème d'affectation consiste à attribuer au mieux des tâches à des agents. Chaque agent peut réaliser une unique tâche pour un coût donné et chaque tâche doit être réalisée par un unique agent. Les affectations (c'est-à-dire les couples agent-tâche) ont toutes un coût défini. Le but est de minimiser le coût total des affectations afin de réaliser toutes les tâches.
Heuristique (mathématiques)Au sens le plus large, l'heuristique est la psychologie de la découverte, abordée par différents mathématiciens. En algorithmique, une heuristique est une méthode de calcul qui fournit rapidement une solution réalisable, pas nécessairement optimale ou exacte, pour un problème d'optimisation difficile. On distingue en général plusieurs temps la prise en compte du problème (question, contexte : données, contraintes, acteurs, tenants et aboutissants) l'incubation, recherche de solution, rumination parfois très longue ; la méthode du problème résolu peut ici dégager les conditions nécessaires à respecter.
SortingSorting refers to ordering data in an increasing or decreasing manner according to some linear relationship among the data items. ordering: arranging items in a sequence ordered by some criterion; categorizing: grouping items with similar properties. Ordering items is the combination of categorizing them based on equivalent order, and ordering the categories themselves. In , arranging in an ordered sequence is called "sorting". Sorting is a common operation in many applications, and efficient algorithms have been developed to perform it.
Moteur physiqueUn moteur physique est, en informatique, une bibliothèque logicielle indépendante appliquée à la résolution de problèmes de la mécanique classique. Les résolutions typiques sont les collisions, la chute des corps, les forces, la cinétique, etc. Les moteurs physiques sont principalement utilisés dans des simulations scientifiques et dans les jeux vidéo. Certains sont également libres pour l'utilisation commerciale, à vérifier bibliothèque par bibliothèque. Box2D (Licence Zlib) Chipmunk (C, C++, Ruby, Python, OCaml.
Vecteur (structure de données)En informatique, un vecteur désigne un conteneur d'éléments ordonnés et accessibles par des indices, dont la taille est dynamique : elle est mise à jour automatiquement lors d'ajouts ou de suppressions d'éléments. On retrouve les vecteurs dans de nombreux langages de programmation, notamment le C++ et le Java. Ils sont alors inclus dans des bibliothèques et l'utilisateur n'a pas besoin d'en programmer un. En langage objet, la classe vecteur est généralement polymorphe, c'est-à-dire qu'il est possible de l'utiliser avec n'importe quel type d'objet.
Complémentarité linéaireEn mathématiques, et plus spécialement en recherche opérationnelle et en optimisation, un problème de complémentarité linéaire est défini par la donnée d'une matrice et d'un vecteur et consiste à trouver un vecteur tel que ses composantes et celles de soient positives et tel que x et y soient orthogonaux pour le produit scalaire euclidien de : où désigne le vecteur x transposé. Ce problème peut être vu comme un cas particulier d'inéquation variationnelle.
Algorithme de tri externeUn algorithme de tri est dit externe lorsqu'il permet de trier des entrées trop grandes pour être contenues en intégralité dans la mémoire principale d'un ordinateur. En règle générale, la mémoire principale est la mémoire vive, et l'algorithme recourt donc à l'usage d'une mémoire située plus bas dans la hiérarchie mémoire, comme un disque dur. Recourir à la mémoire externe permet d'arriver à trier des volumes de données plus importants mais induit de nouvelles difficultés, le temps d'accès aux données étant beaucoup plus long.
