DSPACE

DSPACE

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 Speicherdarf 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:

\mbox{PSPACE} = \bigcup_{k \ge 1} \mbox{DSPACE}(n^k).

Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • DSpace — Тип платформа для институционального репозитория Разработчик DuraSpace Написана на Java Операционная система кроссплатформенное …   Википедия

  • DSpace — Saltar a navegación, búsqueda DSpace es un software de código abierto que provee herramientas para la administración de colecciones digitales, y comunmente es usada como solución de repositorio institucional. Soporta una gran variedad de datos,… …   Wikipedia Español

  • DSpace — steht für: DSPACE als Komplexitätsklasse aus der Komplexitätstheorie der Informatik DSpace (Programm) ist auch ein OpenSource System für die Archivierung elektronischer Dokumente dSPACE (Unternehmen), Anbieter von Werkzeugen für die Entwicklung… …   Deutsch Wikipedia

  • Dspace — steht für: DSPACE als Komplexitätsklasse aus der Komplexitätstheorie der Informatik DSpace (Programm) ist auch ein OpenSource System für die Archivierung elektronischer Dokumente dSPACE (Unternehmen), Anbieter von Werkzeugen für die Entwicklung… …   Deutsch Wikipedia

  • Dspace — may refer to: DSpace, a software package for digital repositories DSPACE, a complexity measure in computational complexity theory dSPACE GmbH, the company dSPACE GmbH (Germany) or its US subsidiary This disambiguation page lists articles… …   Wikipedia

  • DSPACE — Saltar a navegación, búsqueda 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… …   Wikipedia Español

  • DSpace — This article is about the software package. For the complexity class, see DSPACE. DSpace Developer(s) DuraSpace Initial release November 2002 Stable release …   Wikipedia

  • DSPACE — For digital repositories, see DSpace. 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… …   Wikipedia

  • DSPACE — 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… …   Enciclopedia Universal

  • DSpace (Programm) — DSpace ist eine freie Software zum Betrieb eines Dokumentenservers. Sie stellt Werkzeuge zur Erfassung, Speicherung und Weiterverbreitung von digitalen Ressourcen zur Verfügung und wird meist in Universitäten, Bibliotheken und… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”