Wikipédia:Sélection/Informatique théorique

Arborescence de l'informatique théorique Catégorie mère Projet Portail Café

Modifier Problème du sac à dos Le problème du sac à dos, aussi noté KP (en anglais, Knapsack Problem) est un problème d’optimisation combinatoire. Il modélise une situation analogue au remplissage d’un sac à dos, ne pouvant supporter plus d’un certain poids, avec tout ou partie d’un ensemble d’objets ayant chacun un poids et une valeur. Les objets mis dans le sac à dos doivent maximiser la valeur totale, sans dépasser le poids maximum. Le problème du sac à dos est l’un des 21 problèmes NP-complets de Richard Karp, de son article de 1972. Il est intensivement étudié depuis le milieu du siècle dernier. La formulation du problème est fort simple, mais sa résolution est plus complexe. Les algorithmes existants peuvent résoudre des instances pratiques de taille conséquente. Cependant, la structure singulière du problème, et le fait qu’il soit présent en tant que sous-problème d’autres problèmes plus généraux, en font un sujet de choix pour la recherche. Lire la suite

Modifier Hypercube (graphe) Les hypercubes, ou n-cubes, forment une famille de graphes. Dans un hypercube $Q_{n}$, chaque sommet porte une étiquette de longueur $n$ sur un alphabet $A=\{0,1\}$, et deux sommets sont adjacents si leurs étiquettes ne diffèrent que d'un symbole. C'est le graphe squelette de l'hypercube, un polytope n-dimensionnel, généralisant la notion de carré (n = 2) et de cube (n = 3). Dans les années 1980, des ordinateurs furent réalisés avec plusieurs processeurs connectés selon un hypercube : chaque processeur traite une partie des données et ainsi les données sont traitées par plusieurs processeurs à la fois, ce qui constitue un calcul parallèle. L'hypercube est couramment introduit pour illustrer des algorithmes parallèles, et de nombreuses variantes ont été proposées, soit pour des cas pratiques liés à la construction de machines parallèles, soit comme objets théoriques. Lire la suite

Modifier Énigme des trois maisons Résoudre l’énigme consiste à relier chacune des trois maisons du bas à chaque usine du haut par des chemins. Cette illustration est l’œuvre de Henry Dudeney qui présente cette énigme en 1917 dans son livre Amusements in mathematics. L’énigme des trois maisons, aussi appelée l’énigme de l’eau, du gaz et de l’électricité, est un jeu mathématique dont l’analyse utilise un théorème de topologie ou de théorie des graphes. Ce problème n’a pas de solution. Georges Perec le cite en 1978 dans son livre Je me souviens : « Je me souviens des heures que j’ai passées, en classe de troisième je crois, à essayer d’alimenter en eau, gaz et électricité, trois maisons, sans que les tuyaux se croisent (il n’y a pas de solution tant que l’on reste dans un espace à deux dimensions ; c’est un des exemples élémentaires de la topologie, comme les ponts de Königsberg, ou le coloriage des cartes) ». Cette énigme est déjà posée par H. E. Dudeney en 1917 dans son livre Amusements in mathematics. Il précise qu’« il existe une demi-douzaine d’énigmes aussi vieilles que les collines, qui réapparaissent perpétuellement ». Celle de l’article en est une, qu’il appelle eau, gaz, et électricité. Elle est popularisée par M. Gardner, qui la présente dans ses Six livres de jeux mathématiques… Lire la suite

Modifier Algorithme de colonies de fourmis Certains comportements des fourmis sont à l'origine d'algorithmes d’optimisation (ici, des fourmis légionnaires du genre Dorylus). Les algorithmes de colonies de fourmis sont des algorithmes inspirés du comportement des fourmis et qui constituent une famille de métaheuristiques d’optimisation. Initialement proposé par Marco Dorigo et al. dans les années 1990, pour la recherche de chemins optimaux dans un graphe, le premier algorithme s’inspire du comportement des fourmis recherchant un chemin entre leur colonie et une source de nourriture. L’idée originale s'est depuis diversifiée pour résoudre une classe plus large de problèmes et plusieurs algorithmes ont vu le jour, s’inspirant de divers aspects du comportement des fourmis. En anglais, le terme consacré à la principale classe d’algorithme est « Ant Colony Optimization » (abrégé ACO). Les spécialistes réservent ce terme à un type particulier d'algorithme. Il existe cependant plusieurs familles de méthodes s'inspirant du comportement des fourmis. En français, ces différentes approches sont regroupées sous les termes : algorithmes de colonies de fourmis, optimisation par colonies de fourmis, fourmis artificielles, ou diverses combinaisons de ces variantes. Lire la suite