« Complexité »
-
Préciser avec l'index
-
-
Filtrer les résultats par type
-
-
COMPLEXITÉ, mathématique
- Écrit par Jean-Paul DELAHAYE
- 1 626 mots
De nouvelles classes de complexité quantique sont donc venues compléter la famille commencée avec P et NP. La deuxième conséquence du résultat de Shor est que la mise au point de calculateurs quantiques, dont on ne sait pas aujourd'hui si elle aboutira, entraînerait des bouleversements graves en cryptographie. On le voit, la théorie du calcul, qui a permis le développement à la fois de la théorie des classes de complexité et de la théorie algorithmique de la complexité, est soumise à de rapides et profondes évolutions. Lire la suite
-
KOLMOGOROV THÉORIE DE LA COMPLEXITÉ DE
- Écrit par Jean-Paul DELAHAYE
- 563 mots
La théorie de la complexité de Kolmogorov d'une suite numérique S est définie comme la taille, K(S), du plus court programme P qui, confié à une machine universelle (tout ordinateur contemporain en est une), produit la suite S. Cette notion est séduisante car elle synthétise en un seul nombre plusieurs mesures de complexité dont celle que propose la théorie de l'information de l'Américain Claude Shannon (1916-2001), dont elle est la généralisation. Lire la suite
-
KHOT SUBHASH (1978- )
- Écrit par Bernard PIRE
- 651 mots
Selon la citation de cette prestigieuse récompense, Subhash Khot est distingué pour « sa définition visionnaire du problème des jeux uniques et son rôle de leader dans les efforts pour comprendre sa complexité, et pour son rôle central dans l’étude de problèmes d’approximation efficaces, qui ont produit des avancées majeures dans la conception d’algorithmes et dans la question de la difficulté de l’approximation, et pour de nouvelles interactions entre la complexité des calculs, l’analyse et la géométrie ». Lire la suite
-
ALGORITHMIQUE
- Écrit par Philippe COLLARD, Philippe FLAJOLET
- 6 652 mots
- 3 médias
La complexité de l'algorithme TEC vérifie donc : De nombreux algorithmes de tri élémentaires possèdent une complexité en O(n2). Comme dans le cas des algorithmes arithmétiques, une conception récursive conduit à une réduction importante de complexité. L'algorithme de tri-fusion est ainsi fondé sur le principe suivant : Supposons n pair, n = 2 m ; pour trier x1, x2, . Lire la suite
-
RAZBOROV ALEXANDER ALEXANDROVITCH (1963- )
- Écrit par Bernard PIRE
- 248 mots
Les contributions majeures de Razborov à l'élucidation du problème central en théorie de la complexité, à savoir le nombre de pas et la quantité de mémoire nécessaires au calcul d'une fonction, sont nombreuses. En 1985, encore étudiant, il parvient à établir un résultat marquant sur l'existence d'algorithmes polynomiaux en temps pour une tâche qui semble non polynomiale. Lire la suite
-
WIGDERSON AVI (1956- )
- Écrit par Bernard PIRE
- 309 mots
Il a établi nombre de résultats fondamentaux permettant l'analyse rigoureuse de la complexité des circuits. Ses travaux sur les algorithmes probabilistes ont permis une compréhension fine de l'intérêt de tels outils pour la résolution de problèmes où les outils habituels sont inefficaces. En 1989, il parvient, par exemple, à rendre déterministe un algorithme contenant un générateur de nombre pseudo-aléatoire. Lire la suite
-
MOORE LOI DE
- Écrit par Christophe LÉCUYER
- 1 035 mots
- 1 média
La loi de Moore est un ensemble de conjectures et d’énoncés sur la complexité des circuits intégrés, qui a été formulé par Gordon Earle Moore (1929-2023), chimiste et entrepreneur américain. Moore était aussi connu pour avoir cofondé deux sociétés de semi-conducteurs dans la Silicon Valley : Fairchild Semiconductor et Intel (aujourd’hui le grand fabricant de microprocesseurs). Lire la suite
-
MORIN EDGAR (1921- )
- Écrit par Jean-Louis LE MOIGNE
- 1 626 mots
- 1 média
Mais peut-être faut-il privilégier l'ouvrage que l'on peut présenter comme le manifeste de l'épistémologie de la complexité (ou des nouvelles sciences de la complexité) par lequel Edgar Morin condense La Méthode, activité réorganisatrice, Science avec conscience, qui constitue un manifeste épistémologique aussi important « pour sortir du xxe siècle » que le fut, en 1934, Le Nouvel Esprit scientifique de Gaston Bachelard pour nous aider à sortir culturellement des scientismes et des positivismes. Lire la suite
-
UNE NOUVELLE CHIMIE
- Écrit par Jean-Marie LEHN
- 492 mots
Le chimiste se prend à rêver de combiner la complexité de la biologie avec la diversité de la chimie et de dépasser le monde des substances et des organismes produits par l'évolution biologique, en créant tous ces mondes nouveaux en puissance dans l'univers de tous les mondes possibles. Lire la suite
-
BIOLOGIE L'être vivant
- Écrit par Andrée TÉTRY, Universalis
- 5 069 mots
- 1 média
Tout d’abord, au cours de l’évolution, la complexité va-t-elle croissante ? Dans la seconde moitié du xixe siècle, l’idée s’est imposée que l’évolution des organismes partait du plus simple – par exemple, une hydre d’eau douce, sans parler des procaryotes – pour aller vers des organismes de complexité croissante, l’implicite étant que le maximum de complexité était atteint chez l’homme – comme par hasard, pourrait-on dire. Lire la suite
