| dbo:abstract
|
- En teoria de la complexitat, la classe de complexitat DSPACE(f(n)) o SPACE(f(n)) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing determinista en espai O(f(n)) i temps il·limitat. Es la contrapartida determinista de la classe NSPACE. Diverses classe de complexitat es defineixen en funció de DSPACE:
* REG = DSPACE(O(1)).
* L = DSPACE(O(log n))
* PSPACE =
* EXPSPACE = (ca)
- In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine. It represents the total amount of memory space that a "normal" physical computer would need to solve a given computational problem with a given algorithm. (en)
- Der Begriff DSPACE stammt aus der Komplexitätstheorie in der theoretischen Informatik. Er liefert eine grundsätzliche Aussage darüber, welchen Speicherbedarf ein Rechenverfahren auf einem idealisierten Modell eines Computers beansprucht. Es lässt sich so also der Speicherbedarf für bestimmte Anwendungen abschätzen. Wenn beispielsweise der Speicherbedarf eines Rechenverfahrens in linearer Proportion mit der Länge des Eingabewerts wächst, so sagt man, das Verfahren gehöre zu DSPACE(n). Wenn der Speicherbedarf exponentiell mit der Länge des Eingabewerts wächst, so gehört das Verfahren zu DSPACE(exp(n)). DSPACE(f) oder auch kurz SPACE(f) steht für die Menge der Raumkomplexitätsklassen in Bezug auf eine deterministische Turingmaschine. Wird eine konkrete Funktion f angegeben, so bedeutet dies: DSPACE(f) ist die Klasse derjenigen Entscheidungsprobleme, die auf einer deterministischen Turingmaschine mit O(f) Speicherplatz lösbar sind. Man beachte, dass bei Angabe einer konkreten Funktion f die Bezeichnung DSPACE(f) für eine einzelne Komplexitätsklasse steht, während bei Verwendung einer nicht näher definierten Funktion f die Bezeichnung DSPACE(f) eine ganze Menge von Komplexitätsklassen meint. Darüber hinaus sieht man in der Regel von konstanten Faktoren bei der Funktionsdefinition von f ab und setzt somit DSPACE(f) = DSPACE(O(f)). Die Schreibweise DSPACE(f) wird insbesondere häufig zur Definition konkreterer Komplexitätsklassen verwendet: So ist beispielsweise die wichtige Klasse PSPACE wie folgt definiert: . (de)
- En teoría de la complejidad computacional, la clase de complejidad DSPACE(f(n)) o SPACE(f(n)) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en espacio O(f(n)) y tiempo ilimitado. Es la contrapartida determinista de la clase NSPACE. La clase de complejidad PSPACE puede definirse en términos de DSPACE como:
* Datos: Q1155722 (es)
- En théorie de la complexité, DSPACE (ou SPACE) désigne une famille de classes de complexité caractérisées par leur complexité en espace sur une machine de Turing déterministe. Plus précisément, est la classe des problèmes de décision qui, pour une entrée de taille , peuvent être décidés par une machine de Turing déterministe fonctionnant en espace . (fr)
- DSPACE または SPACE は、計算複雑性理論における計算資源のうち空間的リソースを指し、決定性チューリング機械のメモリ空間を表す。実在の一般的コンピュータが、ある問題を特定のアルゴリズムで解くのに要するメモリ空間の量を表す。実際のリソース（プログラムの実行に必要な物理的メモリ量）と直接対応することから、最もよく研究されている複雑性の尺度の1つである。 (ja)
- Em complexidade computacional, DSPACE ou simplesmente SPACE é um descrevendo a disponibilidade de memória para uma máquina de Turing. Este representa o quantidade total de memória que um computador físico "normal" precisaria para solucionar um dado problema computacional com um algoritmo.É uma das mais estudadas medidas de complexidade, dada sua relevância para solução de um problema real: qual é a quantidade de memória necessária para resolver um dado problema com um dado algoritmo. (pt)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 6687 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- En teoria de la complexitat, la classe de complexitat DSPACE(f(n)) o SPACE(f(n)) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing determinista en espai O(f(n)) i temps il·limitat. Es la contrapartida determinista de la classe NSPACE. Diverses classe de complexitat es defineixen en funció de DSPACE:
* REG = DSPACE(O(1)).
* L = DSPACE(O(log n))
* PSPACE =
* EXPSPACE = (ca)
- In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine. It represents the total amount of memory space that a "normal" physical computer would need to solve a given computational problem with a given algorithm. (en)
- En teoría de la complejidad computacional, la clase de complejidad DSPACE(f(n)) o SPACE(f(n)) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en espacio O(f(n)) y tiempo ilimitado. Es la contrapartida determinista de la clase NSPACE. La clase de complejidad PSPACE puede definirse en términos de DSPACE como:
* Datos: Q1155722 (es)
- En théorie de la complexité, DSPACE (ou SPACE) désigne une famille de classes de complexité caractérisées par leur complexité en espace sur une machine de Turing déterministe. Plus précisément, est la classe des problèmes de décision qui, pour une entrée de taille , peuvent être décidés par une machine de Turing déterministe fonctionnant en espace . (fr)
- DSPACE または SPACE は、計算複雑性理論における計算資源のうち空間的リソースを指し、決定性チューリング機械のメモリ空間を表す。実在の一般的コンピュータが、ある問題を特定のアルゴリズムで解くのに要するメモリ空間の量を表す。実際のリソース（プログラムの実行に必要な物理的メモリ量）と直接対応することから、最もよく研究されている複雑性の尺度の1つである。 (ja)
- Em complexidade computacional, DSPACE ou simplesmente SPACE é um descrevendo a disponibilidade de memória para uma máquina de Turing. Este representa o quantidade total de memória que um computador físico "normal" precisaria para solucionar um dado problema computacional com um algoritmo.É uma das mais estudadas medidas de complexidade, dada sua relevância para solução de um problema real: qual é a quantidade de memória necessária para resolver um dado problema com um dado algoritmo. (pt)
- Der Begriff DSPACE stammt aus der Komplexitätstheorie in der theoretischen Informatik. Er liefert eine grundsätzliche Aussage darüber, welchen Speicherbedarf ein Rechenverfahren auf einem idealisierten Modell eines Computers beansprucht. Es lässt sich so also der Speicherbedarf für bestimmte Anwendungen abschätzen. Die Schreibweise DSPACE(f) wird insbesondere häufig zur Definition konkreterer Komplexitätsklassen verwendet: So ist beispielsweise die wichtige Klasse PSPACE wie folgt definiert: . (de)
|
| rdfs:label
|
- DSPACE (Complexitat) (ca)
- DSPACE (de)
- DSPACE (es)
- DSPACE (en)
- DSPACE (fr)
- DSPACE (ja)
- DSPACE (pt)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
