Les hypercubes, ou n-cubes, forment une famille de graphes. Dans un hypercube ${\displaystyle Q_{n}}$, chaque sommet porte une étiquette de longueur ${\displaystyle n}$ sur un alphabet ${\displaystyle 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

Autres articles sélectionnés au sein du portail informatique théorique

L'algorithme de Knuth-Morris-Pratt (qui devrait peut-être s'appeler l'algorithme de Knuth-Matiyasevich-Morris-Pratt) et le théorème de Cook-Levin partagent la particularité d'avoir été découverts vers 1970 indépendamment aux États-Unis et en Union soviétique.