Speedup-Theorem

Speedup-Theorem

In der Komplexitätstheorie dienen verschiedene Speedup-Theoreme (Beschleunigungssätze) für den Nachweis, dass eine Maschine oder ein Algorithmus um einen gewissen Faktor beschleunigt werden kann, wenn bereits eine andere Maschine oder ein anderer Algorithmus bekannt ist.

Die ursprüngliche Version des Speedup-Theorems stammt von Manuel Blum (1967), ist jedoch heute aufgrund der Verwendung beliebiger Komplexitätsfunktionen nicht mehr von großer Bedeutung. Man setzt heute in der Komplexitätstheorie im allgemeinen echte Komplexitätsfunktionen voraus, die gewisse Eigenschaften erfüllen müssen (siehe auch Anforderungen an Schrankenfunktionen).

Der bekannteste Vertreter ist das lineare Speedup-Theorem, das auch als lineares Beschleunigen bezeichnet wird. Das lineare Speedup-Theorem besagt, dass sich zu jeder Turingmaschine, die ein Problem in O(f(n)) Zeit berechnet, eine neue Turingmaschine konstruieren lässt, die das Problem in O(f'(n)) Zeit mit f' = ε·f + n + 2 (0 < ε) berechnet. Dies bedeutet vereinfachend, dass sich jede Turingmaschine, die ein bestimmtes Problem in einer bestimmten Zeit löst, um einen beliebigen linearen Faktor beschleunigen lässt. Die zusätzliche Addition von (n + 2) ergibt sich aus der Notwendigkeit, das Eingabewort der Ausgangsmaschine vollständig einzulesen.

Die Möglichkeit, Turingmaschinen zu beschleunigen verdankt man der freien Wahl des Arbeitsalphabets der Maschine. Dadurch können mehrere Speicherzellen zusammengefasst werden, indem man sie durch eine Zelle repräsentiert.

Andere Speedup-Theoreme sind das Speedup-Theorem von Blum und das quadratische Speedup-Theorem.

Beispiel aus der Mathematik

Die Addition der Binärzahlen 1001101 und 1010011 benötigt je einen Additionsschritt je Ziffernpaar. Insgesamt also sieben. Schreibt man die Zahlen im Dezimalsystem (77 und 83) so benötigt man nur zwei Additionen - allerdings mit größeren Zahlen.

Das Beispiel erklärt auch, warum Programme auf realen Rechnern nicht auf diese Art und Weise beschleunigt werden können. Anders als eine Turingmaschine können binäre Rechner kein anderes Alphabet außer {0,1} verarbeiten.


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

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

  • Speedup Theorem — In der Komplexitätstheorie dienen verschiedene Speedup Theoreme (Beschleunigungssätze) für den Nachweis, dass eine Maschine oder ein Algorithmus um einen gewissen Faktor beschleunigt werden kann, wenn bereits eine andere Maschine oder ein anderer …   Deutsch Wikipedia

  • Speedup theorem — In computational complexity theory, a speedup theorem is a theorem that considers some algorithm solving a problem and demonstrates the existence of a faster algorithm solving the same problem (or more generally, an algorithm using less of any… …   Wikipedia

  • Blum's speedup theorem — In computational complexity theory Blum s speedup theorem, first stated by Manuel Blum in 1967, is an important theorem about the complexity of computable functions. Each computable function has an infinite number of different program… …   Wikipedia

  • Linear speedup theorem — In computational complexity theory, the linear speedup theorem for Turing machines proves that given any c > 0 and any Turing machine solving a problem in time f( n ), there is another machine that solves the same problem in time c f( n… …   Wikipedia

  • Gap theorem — See also Gap theorem (disambiguation) for other gap theorems in mathematics. In computational complexity theory the Gap theorem is a major theorem about the complexity of computable functions. [Lance Fortnow, Steve Homer,… …   Wikipedia

  • Beschleunigungssatz — In der Komplexitätstheorie dienen verschiedene Speedup Theoreme (Beschleunigungssätze) für den Nachweis, dass eine Maschine oder ein Algorithmus um einen gewissen Faktor beschleunigt werden kann, wenn bereits eine andere Maschine oder ein anderer …   Deutsch Wikipedia

  • List of theorems — This is a list of theorems, by Wikipedia page. See also *list of fundamental theorems *list of lemmas *list of conjectures *list of inequalities *list of mathematical proofs *list of misnamed theorems *Existence theorem *Classification of finite… …   Wikipedia

  • Asymptotically optimal — In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor (independent of the input size) worse than the best possible algorithm. It is a term commonly… …   Wikipedia

  • Komplexitätstheorie — Die Komplexitätstheorie als Teilgebiet der Theoretischen Informatik befasst sich mit der Komplexität von algorithmisch behandelbaren Problemen auf verschiedenen mathematisch definierten formalen Rechnermodellen. Die Komplexität von Algorithmen… …   Deutsch Wikipedia

  • List of computability and complexity topics — This is a list of computability and complexity topics, by Wikipedia page. Computability theory is the part of the theory of computation that deals with what can be computed, in principle. Computational complexity theory deals with how hard… …   Wikipedia

Share the article and excerpts

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