DSPACE

http://dbpedia.org/resource/DSPACE an entity of type: Work

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 = rdf:langString
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. rdf:langString
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 rdf:langString
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 . rdf:langString
DSPACE または SPACE は、計算複雑性理論における計算資源のうち空間的リソースを指し、決定性チューリング機械のメモリ空間を表す。実在の一般的コンピュータが、ある問題を特定のアルゴリズムで解くのに要するメモリ空間の量を表す。実際のリソース(プログラムの実行に必要な物理的メモリ量)と直接対応することから、最もよく研究されている複雑性の尺度の1つである。 rdf:langString
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. rdf:langString
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: . rdf:langString
rdf:langString DSPACE (Complexitat)
rdf:langString DSPACE
rdf:langString DSPACE
rdf:langString DSPACE
rdf:langString DSPACE
rdf:langString DSPACE
rdf:langString DSPACE
xsd:integer 658520
xsd:integer 981852024
rdf:langString 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 =
rdf:langString 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.
rdf:langString 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: .
rdf:langString 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
rdf:langString 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 .
rdf:langString DSPACE または SPACE は、計算複雑性理論における計算資源のうち空間的リソースを指し、決定性チューリング機械のメモリ空間を表す。実在の一般的コンピュータが、ある問題を特定のアルゴリズムで解くのに要するメモリ空間の量を表す。実際のリソース(プログラムの実行に必要な物理的メモリ量)と直接対応することから、最もよく研究されている複雑性の尺度の1つである。
rdf:langString 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.
xsd:nonNegativeInteger 6687

data from the linked data cloud