Metraipolis › archive › dc_1e3daae55fda
Fonction constructible — Wikipedia (fr)
- Source
- Wikipedia (fr)
- Original
- https://fr.wikipedia.org/wiki/Fonction_constructible
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-07T08:47:32.382Z
- SHA-256 of the archived text
53646f702b8518f217c655a6fa11c44eb5915efaf9e5e006073ec45db12d675f- Stable URL of this page
https://metraipolis.com/documento/dc_1e3daae55fda
How to cite
Fonction constructible — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Fonction_constructible (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_1e3daae55fda (Metraipolis archive dc_1e3daae55fda, sha256 53646f702b8518f217c655a6fa11c44eb5915efaf9e5e006073ec45db12d675f)
BibTeX
@misc{dc1e3daae55fda,
title = {Fonction constructible — Wikipedia (fr)},
howpublished = {Wikipedia (fr)},
url = {https://fr.wikipedia.org/wiki/Fonction_constructible},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_1e3daae55fda; sha256 53646f702b8518f217c655a6fa11c44eb5915efaf9e5e006073ec45db12d675f},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Fonction_constructible. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
En théorie de la complexité, une fonction constructible en temps est une fonction f des entiers naturels vers les entiers naturels, avec la propriété que f(n) peut être calculée à partir de n par une machine de Turing qui se termine en un temps du même ordre de grandeur que f(n). Le but de cette définition est d'exclure les fonctions qui n'apportent pas de borne supérieure sur le temps d'exécution. Une définition similaire pour la complexité en espace existe et introduit la notion de fonction constructible en espace. 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 «Fonction constructible» — https://fr.wikipedia.org/wiki/Fonction_constructible Wikidata Q5164405: «function whose values can be computed in a number of steps or a number of Turing-machine cells of order given by the function itself» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5164405 Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Fonction_constructible?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 212895863, consultata il 2026-11-07T08:43:02.264Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 75f4be1b161657321f74e2c77c04fa314352c51e7be3c2b1c95c2624876713c5