This HTML5 document contains 42 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n17http://g.co/kg/m/
dbpedia-hehttp://he.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
category-frhttp://fr.dbpedia.org/resource/Catégorie:
dbpedia-pthttp://pt.dbpedia.org/resource/
n8http://fr.dbpedia.org/resource/Modèle:
wikipedia-frhttp://fr.wikipedia.org/wiki/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n12http://ma-graph.org/entity/
dbpedia-zhhttp://zh.dbpedia.org/resource/
dbpedia-frhttp://fr.dbpedia.org/resource/
prop-frhttp://fr.dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
dbrhttp://dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/

Statements

Subject Item
dbpedia-fr:Fonction_constructible
rdfs:label
Fonction constructible Constructible function
rdfs:comment
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.
owl:sameAs
dbpedia-pt:Função_construível wikidata:Q5164405 n12:2778748587 dbpedia-he:פונקציה_חשיבה dbpedia-zh:可構函數 n17:03nrb6 dbr:Constructible_function
dbo:wikiPageID
8556490
dbo:wikiPageRevisionID
164702532
dbo:wikiPageWikiLink
dbpedia-fr:Fonction_récursive category-fr:Propriété_de_fonction dbpedia-fr:Comparaison_asymptotique dbpedia-fr:Théorème_de_hiérarchie_en_temps_déterministe category-fr:Théorie_de_la_complexité_des_algorithmes dbpedia-fr:Démonstration_constructive dbpedia-fr:Entier_naturel dbpedia-fr:Machine_de_Turing dbpedia-fr:Complexité_en_temps dbpedia-fr:Principe_du_tiers_exclu dbpedia-fr:Complexité_en_espace dbpedia-fr:Théorie_de_la_complexité_(informatique_théorique)
dbo:wikiPageLength
5982
dct:subject
category-fr:Propriété_de_fonction category-fr:Théorie_de_la_complexité_des_algorithmes
prop-fr:wikiPageUsesTemplate
n8:Autre4 n8:Complexité_algorithmique_(Perifel) n8:Palette n8:Références n8:Portail n8:Computational_Complexity_(Arora_et_Barak) n8:Lien
prov:wasDerivedFrom
wikipedia-fr:Fonction_constructible?oldid=164702532&ns=0
prop-fr:fr
théorème de hiérarchie en espace théorème de la lacune
prop-fr:lang
en
prop-fr:trad
Space hierarchy theorem Gap theorem
foaf:isPrimaryTopicOf
wikipedia-fr:Fonction_constructible
dbo:abstract
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.