Metraipolis › archive › dc_bed10167af96
Complexité générique des algorithmes — Wikipedia (fr)
- Source
- Wikipedia (fr)
- Original
- https://fr.wikipedia.org/wiki/Complexit%C3%A9_g%C3%A9n%C3%A9rique_des_algorithmes
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-05T09:44:27.640Z
- SHA-256 of the archived text
de964fe6785fee350d3e56fa254cd3a2a1d2602fe4a1d59d218453845436e5ea- Stable URL of this page
https://metraipolis.com/documento/dc_bed10167af96
How to cite
Complexité générique des algorithmes — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Complexit%C3%A9_g%C3%A9n%C3%A9rique_des_algorithmes (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_bed10167af96 (Metraipolis archive dc_bed10167af96, sha256 de964fe6785fee350d3e56fa254cd3a2a1d2602fe4a1d59d218453845436e5ea)
BibTeX
@misc{dcbed10167af96,
title = {Complexité générique des algorithmes — Wikipedia (fr)},
howpublished = {Wikipedia (fr)},
url = {https://fr.wikipedia.org/wiki/Complexit%C3%A9_g%C3%A9n%C3%A9rique_des_algorithmes},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_bed10167af96; sha256 de964fe6785fee350d3e56fa254cd3a2a1d2602fe4a1d59d218453845436e5ea},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Complexit%C3%A9_g%C3%A9n%C3%A9rique_des_algorithmes. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
La complexité générique est un domaine particulier de la complexité algorithmique qui concerne l’étude de la complexité de problèmes algorithmiques pour « la plupart des données ». La complexité générique est une façon de mesurer la complexité d'un problème algorithmique en négligeant un petit ensemble d'entrées non représentatives et en considérant la complexité dans le pire des cas sur les entrées restantes. La concept de « petit ensemble » est définie en termes de densité asymptotique. L'efficacité apparente des algorithmes mesurée par leur complexité générique provient du fait que, pour une grande variété de problèmes informatiques concrets, les cas les plus difficiles semblent être rares, alors que les cas typiques sont, eux, relativement faciles. Cette approche de la complexité prend son origine dans la théorie combinatoire des groupes qui a une tradition dans l'étude de problèmes algorithmiques qui remonte au début du XXe siècle. La notion de complexité générique a été introduit en 2003 dans des articles de Kapovich, Miasnikov, Schupp et Shpilrain. Les auteurs montrent que, pour une large classe de groupes finiment engendrés, la complexité générique de quelques problèmes de décision classiques de la théorie combinatoire des groupes, à savoir le problème du mot, le problème de conjugaison (en), ou le problème d'appartenance, est en fait linéaire. Une introduction et un survol de la complexité générique sont donnés dans un texte de R. Gilman, A. G. Miasnikov, A. D. Myasnikov, et A. Ushakov. Les livres de Miasnikov, Shpilrain et Ushakov traitent principalement des résultats des auteurs relativement à la cryptographie. 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 «Complexité générique des algorithmes» — https://fr.wikipedia.org/wiki/Complexit%C3%A9_g%C3%A9n%C3%A9rique_des_algorithmes Wikidata Q5532647 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5532647 Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Complexit%C3%A9_g%C3%A9n%C3%A9rique_des_algorithmes?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 230420211, consultata il 2026-11-05T09:40:14.753Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 8d12409b9dada2402aeec73d86fe28d329688c1546640931ebc0c1eadbbe0c17