Algorithmische Tiefe

Die Algorithmische oder Logische Tiefe ist ein Maß für die Komplexität einer Datenmenge oder Nachricht, also für den Informationsgehalt. Sie wurde von Charles Bennett definiert als der Aufwand, der betrieben werden muss, um die Daten zu erzeugen oder zu entschlüsseln. Formal ist sie die Zeitkomplexität des effizientesten Algorithmus, der diese Daten produzieren kann. Anders als bei der ansonsten ähnlichen Kolmogorow-Komplexität ist also die Laufzeit bei der Ausführung des Algorithmus entscheidend und nicht dessen Länge.

Siehe auch: Komplexitätstheorie, Information, Informationstheorie, Informationsmenge, Algorithmische Informationstheorie


Wikimedia Foundation.

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

  • Algorithmische Komplexität — Die Kolmogorow Komplexität (nach Andrei Nikolajewitsch Kolmogorow) ist ein Maß für die Strukturiertheit einer Zeichenkette und ist durch die Länge des kürzesten Programms gegeben, das diese Zeichenkette erzeugt. Dieses kürzeste Programm gibt… …   Deutsch Wikipedia

  • Logische Tiefe — Die Algorithmische oder Logische Tiefe ist ein Maß für die Komplexität einer Datenmenge oder Nachricht, also für den Informationsgehalt. Sie wurde von Charles Bennett definiert als der Aufwand, der betrieben werden muss, um die Daten zu erzeugen… …   Deutsch Wikipedia

  • Rechenaufwand — Komplexität bezeichnet in der Informatik die „Kompliziertheit“ von Problemen, Algorithmen oder Daten. Die Komplexitätstheorie befasst sich dabei mit dem Ressourcenverbrauch von Algorithmen, die Informationstheorie dagegen verwendet den Begriff… …   Deutsch Wikipedia

  • Überraschungswert — Der Begriff der Information, wie er in der Informationstheorie nach Shannon[1] verwendet wird, ist streng von dem gewöhnlichen Gebrauch dieses Begriffes zu unterscheiden. Insbesondere darf darin die Information nicht mit dem Begriff der Bedeutung …   Deutsch Wikipedia

  • Algorithmischer Informationsgehalt — Die Kolmogorow Komplexität (nach Andrei Nikolajewitsch Kolmogorow) ist ein Maß für die Strukturiertheit einer Zeichenkette und ist durch die Länge des kürzesten Programms gegeben, das diese Zeichenkette erzeugt. Dieses kürzeste Programm gibt… …   Deutsch Wikipedia

  • Beschreibungskomplexität — Die Kolmogorow Komplexität (nach Andrei Nikolajewitsch Kolmogorow) ist ein Maß für die Strukturiertheit einer Zeichenkette und ist durch die Länge des kürzesten Programms gegeben, das diese Zeichenkette erzeugt. Dieses kürzeste Programm gibt… …   Deutsch Wikipedia

  • Kolmogoroff-Komplexität — Die Kolmogorow Komplexität (nach Andrei Nikolajewitsch Kolmogorow) ist ein Maß für die Strukturiertheit einer Zeichenkette und ist durch die Länge des kürzesten Programms gegeben, das diese Zeichenkette erzeugt. Dieses kürzeste Programm gibt… …   Deutsch Wikipedia

  • Kolmogorov-Entropie — Die Kolmogorow Komplexität (nach Andrei Nikolajewitsch Kolmogorow) ist ein Maß für die Strukturiertheit einer Zeichenkette und ist durch die Länge des kürzesten Programms gegeben, das diese Zeichenkette erzeugt. Dieses kürzeste Programm gibt… …   Deutsch Wikipedia

  • Kolmogorov-Komplexität — Die Kolmogorow Komplexität (nach Andrei Nikolajewitsch Kolmogorow) ist ein Maß für die Strukturiertheit einer Zeichenkette und ist durch die Länge des kürzesten Programms gegeben, das diese Zeichenkette erzeugt. Dieses kürzeste Programm gibt… …   Deutsch Wikipedia

  • Kolmogorowkomplexität — Die Kolmogorow Komplexität (nach Andrei Nikolajewitsch Kolmogorow) ist ein Maß für die Strukturiertheit einer Zeichenkette und ist durch die Länge des kürzesten Programms gegeben, das diese Zeichenkette erzeugt. Dieses kürzeste Programm gibt… …   Deutsch Wikipedia

Share the article and excerpts

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