imported>SchlurcherBot: Bot: http → https

2025-07-31T11:18:00Z

Bot: http → https

Neue Seite

In der [[Informatik]] ist ein '''Time-Memory Tradeoff''' (TMTO, deutsch ''Zeit-Speicher-Kompromiss'' oder ''Zeit-Speicher-Ausgleich'') ein [[Kompromiss]], bei dem der [[Speicherbedarf]] eines [[Computerprogramm|Programmes]] auf Kosten einer längeren [[Laufzeit (Informatik)|Laufzeit]] gesenkt wird oder umgekehrt die Laufzeit auf Kosten eines höheren Speicherbedarfs verkürzt wird. Ziel dabei ist es, das Programm unter aktuellen technischen Voraussetzungen möglichst [[Effizienz_(Informatik)|effizient]] umzusetzen.

Der Begriff wird nicht nur für den entstehenden Kompromiss und für den Vorgang des Abwägens, sondern auch zur Benennung von Problemenklassen, die eine solche Abwägung nahelegen, verwendet. Darüber hinaus werden manche Programme und [[Algorithmus|Algorithmen]], die von diesem Vorgehen entscheidend geprägt wurden, mit diesem Wort bezeichnet.

== Beispiele für Kompromissformen ==
* [[Lookup-Tabelle]] gegenüber Neuberechnung <br/> Bei der Verwendung von Lookup-Tabellen kann in der Implementierung die gesamte Tabelle vorberechnet werden, wodurch die Laufzeit verringert, aber der Speicherbedarf erhöht wird.
* Komprimierte Daten gegenüber unkomprimierten Daten <br/> Ein Ausgleich zwischen Speicher und Laufzeit erfolgt bei der [[Datenkompression]], wobei der Speicherbedarf von Daten verringert wird, aber mehr Zeit zum Dekomprimieren benötigt wird.
* [[Bildsynthese|Re-rendering]] gegenüber gespeicherten Bildern <br/> Werden auf einem [[Server]] [[LaTeX]]-Formeln als [[Quelltext]] und nicht als [[Bilddatei]] gespeichert, so wird der Speicherbedarf gesenkt, aber durch das wiederholte Rendern die Laufzeit erhöht.
* Kleiner Programmcode gegenüber [[loop unrolling]] <br /> Durch Auflösen von [[Schleife (Programmierung)|Schleifen]] konnte früher die Laufzeit verkürzt werden, während sich der Programmcode vergrößert. [[Intel Pentium Pro|Heutige CPUs]] benötigen dies nicht mehr und laufen teilweise mit loop unrolling langsamer als ohne.

== Beispiele für Algorithmen ==
* [[Babystep-Giantstep-Algorithmus]], der für die Berechnung des [[Diskreter Logarithmus|diskreten Logarithmus]] verwendet wird.
* [[Dynamische Programmierung]] zur algorithmischen Lösung von [[Optimierungsproblem]]en
* [[Rainbow table|Rainbow-Tabellen]] in der [[Kryptographie]]

Bei den Rainbow-Tabellen hat die konsequente Anwendung dieses Prinzips zu einer kompletten Zweiteilung der Lösung geführt. In einem völlig eigenständigen Vorbereitungsprogramm werden mit ganz erheblichem Rechenaufwand große Tabellen vorbereitet. Andere Programme nutzen die vorbereiteten Tabellen, um damit in relativ geringer Zeit Verschlüsselungen oder Passwörter zu brechen.

== Weblinks ==
* [http://lasecwww.epfl.ch/pub/lasec/doc/Oech03.pdf Philippe Oechslin: Making a Faster Cryptanalytic Time-Memory Trade-Off.] (PDF; 243 kB)
* [https://www.cs.sjsu.edu/faculty/stamp/RUA/TMTO.pdf Once Upon a Time-Memory Tradeoff.] (PDF; 135 kB)

[[Kategorie:Praktische Informatik]]
[[Kategorie:Theoretische Informatik]]

Time-Memory Tradeoff - Versionsgeschichte

imported>SchlurcherBot: Bot: http → https