Metraipolis › archive › dc_c70fa4639f0e
Algorithme galactique — Wikipedia (fr)
- Source
- Wikipedia (fr)
- Original
- https://fr.wikipedia.org/wiki/Algorithme_galactique
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-17T11:52:13.111Z
- SHA-256 of the archived text
72ad70d7b75c8d021e5a407b37faccb601f871222f5d1680e8baeb64d7e640bd- Stable URL of this page
https://metraipolis.com/documento/dc_c70fa4639f0e
How to cite
Algorithme galactique — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_galactique (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_c70fa4639f0e (Metraipolis archive dc_c70fa4639f0e, sha256 72ad70d7b75c8d021e5a407b37faccb601f871222f5d1680e8baeb64d7e640bd)
BibTeX
@misc{dcc70fa4639f0e,
title = {Algorithme galactique — Wikipedia (fr)},
howpublished = {Wikipedia (fr)},
url = {https://fr.wikipedia.org/wiki/Algorithme_galactique},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_c70fa4639f0e; sha256 72ad70d7b75c8d021e5a407b37faccb601f871222f5d1680e8baeb64d7e640bd},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_galactique. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Un algorithme galactique est un algorithme de résolution d'un problème qui est plus rapide que tous les autres algorithmes quand le problème est suffisamment grand, mais dans le cas où « suffisamment grand » est tellement grand que l’algorithme n’est en pratique jamais utilisé. Les algorithmes galactiques ont été nommés ainsi par Richard Lipton et Ken Regan parce qu'ils ne seront jamais utilisés pour aucun ensemble de données trouvé sur Terre. Un exemple d'algorithme galactique est l'algorithme pour multiplier deux nombres qui est basé sur une transformée de Fourier à 1 729 dimensions. Cela signifie qu’elle ne sera pas la plus rapide tant que les nombres n’auront pas au moins 101038 chiffres, (considérablement) plus de chiffres qu’il n’y a d’atomes dans l’univers. Donc, cet algorithme n'est jamais utilisé dans la pratique. Malgré le fait qu’ils ne seront jamais utilisés, les algorithmes galactiques peuvent néanmoins contribuer à l'informatique : un algorithme, même s’il n’est pas utilisable, peut montrer de nouvelles techniques pouvant éventuellement être utilisées pour créer des algorithmes plus efficaces ; la puissance des ordinateurs peut rattraper la défaillance, de sorte qu'un algorithme auparavant peu pratique le devient ; un algorithme inutilisable peut toujours démontrer que des bornes conjecturées peuvent être obtenues, ou alternativement, montrer que les limites conjecturées sont fausses. Comme le dit Lipton, « En soi cet argument est suffisant pour donner d'excellentes raisons de trouver de tels algorithmes. Par exemple, s'il existait demain une découverte montrant qu'il existait un algorithme de factorisation avec une limite de temps énorme mais polynomiale, cela changerait nos connaissances sur la factorisation. L’algorithme pourrait ne jamais être utilisé, mais déterminerait certainement les recherches futures en factorisation. » De même, un algorithme O( N2100 ) pour le problème SAT, bien qu'inutilisable en pratique, réglerait le problème P = NP, qui est le problème ouvert le plus important en informatique. Un effet pratique immédiat serait l'obtention par le découvreur d'un prix d'un million de dollars par le Clay Mathematics Institute. Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in francese, in ordine alfabetico). Fonte: Wikipedia in francese, voce «Algorithme galactique» — https://fr.wikipedia.org/wiki/Algorithme_galactique Wikidata Q65072234 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q65072234 Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Algorithme_galactique?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 229292432, consultata il 2026-10-17T11:22:47.569Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 9a9afda518fdae4112284c1fe64235be19bc2cc6ce6696217a461e2f6d17ae96