„Algorithmische Tiefe“ – Versionsunterschied
| [gesichtete Version] | [gesichtete Version] |
Inhalt gelöscht Inhalt hinzugefügt
schwache Formulierung verbessert |
Belege |
||
| Zeile 1: | Zeile 1: | ||
{{Belege}} |
|||
Die '''Algorithmische''' oder '''Logische Tiefe''' ist ein Maß für die [[Komplexität (Informatik)|Komplexität]] einer [[Daten]]menge oder [[Nachricht]], also für den [[Informationsgehalt]]. Sie wurde von [[Charles H. Bennett|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 [[Effizienz (Informatik)|effizientesten]] [[Algorithmus]], der diese Daten produzieren kann. Anders als bei der ansonsten ähnlichen [[Kolmogorow-Komplexität]] ist also die [[Laufzeit (Informatik)|Laufzeit]] bei der Ausführung des Algorithmus entscheidend und nicht dessen Länge. |
Die '''Algorithmische''' oder '''Logische Tiefe''' ist ein Maß für die [[Komplexität (Informatik)|Komplexität]] einer [[Daten]]menge oder [[Nachricht]], also für den [[Informationsgehalt]]. Sie wurde von [[Charles H. Bennett|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 [[Effizienz (Informatik)|effizientesten]] [[Algorithmus]], der diese Daten produzieren kann. Anders als bei der ansonsten ähnlichen [[Kolmogorow-Komplexität]] ist also die [[Laufzeit (Informatik)|Laufzeit]] bei der Ausführung des Algorithmus entscheidend und nicht dessen Länge. |
||
Version vom 26. Mai 2019, 11:51 Uhr
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