webentwicklung-frage-antwort-db.com.de

Was ist die Informatikdefinition von Entropie?

Ich habe vor kurzem einen Kurs zur Datenkompression an meiner Universität begonnen. Ich finde jedoch die Verwendung des Begriffs "Entropie", wie er in der Informatik gilt, eher unklar. Soweit ich das beurteilen kann, bedeutet dies grob die "Zufälligkeit" eines Systems oder einer Struktur.

Was ist die richtige Definition von Informatik "Entropie"?

59
fluffels

Entropie kann verschiedene Dinge bedeuten:

Computing

Im Rechnen ist Entropie die Zufälligkeit, die von einem operativ erfassten System oder Anwendung zur Verwendung in Kryptographie oder andere Verwendungen, die Zufallsdaten benötigen. Diese Zufälligkeit wird oft von Hardware gesammelt Quellen, entweder bereits vorhandene wie als Mausbewegungen oder speziell Zufallsgeneratoren zur Verfügung gestellt.

Informationstheorie

In der Informationstheorie ist Entropie eine Maß für die damit verbundene Unsicherheit mit einer Zufallsvariablen. Der Begriff von sich in diesem Zusammenhang normalerweise auf auf die Shannon-Entropie, die quantifiziert im Sinne eines erwarteter Wert, die Information in einer Nachricht enthalten, normalerweise in Einheiten wie Bits. Äquivalent ist das Die Shannon-Entropie ist ein Maß für die durchschnittlicher Informationsgehalt ist eins fehlt, wenn man die .__ nicht kennt. Wert der Zufallsvariablen

Entropie bei der Datenkomprimierung

Entropie bei der Datenkomprimierung kann die Zufälligkeit der Daten angeben, die Sie in den Kompressionsalgorithmus eingeben. Je größer die Entropie ist, desto geringer ist das Kompressionsverhältnis. Je zufälliger der Text ist, desto weniger können Sie ihn komprimieren.

Die Entropie von Shannon steht für eine absolute grenze für das bestmögliche verlustfreie Komprimierung eines beliebigen Kommunikation: Behandeln von Nachrichten als kodiert als Sequenz unabhängiger und gleichverteilt zufällig Variablen, Shannon Quellcodierung Theorem zeigt, dass im Grenzbereich die durchschnittliche Länge des kürzesten mögliche Darstellung zur Kodierung der Nachrichten in einem bestimmten Alphabet sind ihre Entropie geteilt durch den Logarithmus von die Anzahl der Symbole im Ziel Alphabet.

55
Niyaz

Meine Lieblingsdefinition mit einem praktischeren Fokus findet sich in Kapitel 1 des ausgezeichneten Buches Der pragmatische Programmierer: Vom Gesellen zum Meister von Andrew Hunt und David Thomas:

Software Entropie

Während die Softwareentwicklung immun ist von fast allen physikalischen Gesetzen, Entropie trifft uns hart Entropie ist ein Begriff aus Physik, die sich auf die Menge von .__ bezieht. "Störung" in einem System. Unglücklicherweise, die Gesetze der Thermodynamik garantieren dass die Entropie im Universum tendiert zu einem Maximum. Wenn Unordnung an Software, Programmierern nenne es "Software rot".

Es gibt viele Faktoren, die das können dazu beitragen, Software rot. Am meisten wichtig scheint die Psychologie oder Kultur bei der Arbeit an einem Projekt. Auch wenn Sie ein Team von .__ sind. Erstens kann die Psychologie Ihres Projekts .__ sein. eine sehr heikle Sache. Trotz der beste Pläne und die besten Leute, a Projekt kann immer noch Ruine erleben und Zerfall während seiner Lebensdauer. Noch da sind andere Projekte, die trotz enorme Schwierigkeiten und ständige Rückschläge, bekämpft erfolgreich die Natur Tendenz zur Unordnung und schaffen es, Komme ziemlich gut raus.

...

...

Ein zerbrochenes Fenster.

Ein zerbrochenes Fenster, das für .__ nicht repariert wurde. eine wesentliche Zeitdauer... instills in die Bewohner der ein Gefühl der Verlassenheit aufbauen - a spüre, dass die Kräfte, die sein werden, nicht kümmere dich um das Gebäude. Also noch eine Fenster wird kaputt. Die Leute beginnen Abfall Graffiti erscheint. Ernst Strukturschaden beginnt. In einem relativ kurzer Zeit die Gebäude wird jenseits des .__ beschädigt. der Wunsch des Besitzers, das Problem zu beheben, und die Verlassenheit wird zur Realität.

Die "Broken Window Theory" hat inspirierte Polizeibehörden in New York und andere Großstädte zu knacken runter auf die kleinen Sachen um Halten Sie das große Zeug fern. Es klappt: auf kaputten Fenstern zu bleiben, Graffiti und andere kleine Verstöße hat die schwere Kriminalitätsrate reduziert.

Tipp 4

Lebe nicht mit kaputten Fenstern

Lassen Sie "zerbrochene Fenster" (schlechte Designs, falsche Entscheidungen oder schlechter Code) nicht repariert. Repariere jeden so schnell wie es entdeckt wird. Wenn da ist nicht genügend Zeit, um es richtig zu beheben, dann einsteigen. Vielleicht kannst du Kommentieren Sie den fehlerhaften Code aus oder eine Meldung "Nicht implementiert" anzeigen, oder ersetzen Sie stattdessen Dummy-Daten. Nehmen einige Maßnahmen, um weitere Schäden zu vermeiden und um zu zeigen, dass Sie oben auf der .__ sind. Situation.

Text entnommen aus: http://pragprog.com/the-pragmatic-programmer/extracts/software-entropy

16
Ash

Ich habe immer Entropie im Sinne von Shannon Entropie getroffen. 

Von http://en.wikipedia.org/wiki/Information_entropy :

In der Informationstheorie ist Entropie ein Maß für die mit einer Zufallsvariablen verbundene Unsicherheit. Der Begriff an sich bezieht sich in diesem Zusammenhang üblicherweise auf die Shannon-Entropie, die im Sinne eines erwarteten Werts die in einer Nachricht enthaltenen Informationen quantifiziert, üblicherweise in Einheiten wie Bits. Äquivalent dazu ist die Shannon-Entropie ein Maß für den durchschnittlichen Informationsinhalt, dem man fehlt, wenn man den Wert der Zufallsvariablen nicht kennt.

9
Adrian Grigore

 alt text
(Quelle: mit.edu )

von Universität von Mexiko

Der informationstheoretische Begriff von Entropie ist eine Verallgemeinerung des physikalische Vorstellung Es gibt viele Wege Entropie zu beschreiben. Es ist eine Maßnahme der Zufälligkeit eines Zufälligen Variable. Es ist auch ein Maß für die Informationsmenge zufällig variabler oder stochastischer Prozess enthält. Es ist auch eine untere Schranke an Der Betrag einer Nachricht kann .__ sein. komprimiert. Und schließlich ist es das durchschnittliche Anzahl von Ja/Nein-Fragen das muss nach einem zufälligen gefragt werden Unternehmen, um seinen Wert zu bestimmen.

Gleichung für Entropie in einer Beispielanwendung zur Wahrscheinlichkeitsberechnung: 

es ist die Summe aller Werte eines Rv der Wahrscheinlichkeit dieses Wertes mal das Protokoll dieses Probens (d. h p (x) logp (x)). Diese Gleichung kann .__ sein. abgeleitet von den ersten Prinzipien des Eigenschaften von Informationen.

9
Ric Tokyo

Komprimierungs- und Informationstheorie ist die Entropie einer Quelle die durchschnittliche Informationsmenge (in Bits), die Symbole von der Quelle übertragen können. Informell gesprochen, je unwahrscheinlicher ein Symbol ist, desto mehr Überraschung bringt es.

Wenn Ihre Quelle zwei Symbole hat, sagen Sie A und B, und sie sind gleich wahrscheinlich, dann übermittelt jedes Symbol die gleiche Informationsmenge (ein Bit). Eine Quelle mit vier gleich wahrscheinlichen Symbolen übermittelt zwei Bits pro Symbol.

Für ein interessanteres Beispiel, wenn Ihre Quelle die drei Symbole A, B und C enthält, bei denen die ersten beiden doppelt so wahrscheinlich sind wie die dritten, ist das dritte eher überraschend, aber auch weniger wahrscheinlich. Für diese Quelle gibt es eine Netto-Entropie von 1,52 (siehe unten).

Sie berechnen die Entropie als "durchschnittliche Überraschung", wobei die "Überraschung" für jedes Symbol die Wahrscheinlichkeit mal dem negativen binären Log der Wahrscheinlichkeit ist:

                            binary
symbol  weight  probability   log    surprise
  A        2        0.4      -1.32    0.53
  B        2        0.4      -1.32    0.53
  C        1        0.2      -2.32    0.46
total      5        1.0               1.52

Das Negativ des binären Protokolls wird (natürlich) verwendet, da Protokolle mit Werten zwischen 0 und 1 (exklusiv) negativ sind.

4
joel.neely

Hier ist eine großartige alternative Erklärung für Entropie in der Informationstheorie.

Entropie ist ein Maß für die Unsicherheit bei der Erstellung eines Vorhersage .

Wir können die Entropie auch so beschreiben, wie überrascht wäre, wenn wir nach unserer ursprünglichen Vorhersage ein Ergebnis erzielen würden.

Nehmen wir an, wir haben eine gebogene Münze, die uns zu 99% einen Kopf und zu 1% einen Schwanz gibt. Da es nur eine Chance von einem Prozent gibt, einen Schwanz zu bekommen, wären wir sehr überrascht, wenn wir tatsächlich einen Schwanz bekommen würden. Andererseits ist es nicht überraschend, wenn wir einen Kopf bekommen, da wir bereits eine 99-prozentige Chance haben, einen Kopf zu bekommen.

nehmen wir an, wir haben eine Funktion namens Surprise(x), die uns die Überraschung für jedes Ergebnis geben würde. dann können wir die Überraschungsmenge anhand einer Wahrscheinlichkeitsverteilung berechnen. Diese durchschnittliche Überraschung könnte auch als Maßstab dafür dienen, wie unsicher wir sind. Diese Unsicherheit heißtEntropie.

4
r2d2oid

Super SIMPLE Definition

Die Wortentropie kann in einem Satz definiert werden:

"Die Menge an Informationen, die zur Beschreibung eines Systems erforderlich ist."

Stellen Sie sich als Beispiel die Erweiterung des Universums vor: Von Anfang an wurde die gesamte Materie vor dem Urknall an einem kleinen Punkt gesammelt, so dass wir das System mit "alle Materie in einem Punkt" hätten beschreiben können. Während heutzutage wesentlich mehr Informationen benötigt werden, um das System (das Universum) zu beschreiben, müsste man alle Planetenpositionen, ihre Bewegung, das, was sich darauf befindet, beschreiben. Was die Informationstheorie angeht, funktioniert die Definition auch : Beispiel: Je mehr Buchstaben Sie zu einem Kennwort hinzufügen (System), desto mehr Informationen werden zur Beschreibung des Kennworts benötigt. Dann können Sie es in verschiedenen Einheiten messen, z. B. Bits oder Zeichen, wie "Hallo" = 5 Zeichen Entropie = 40 Bit Entropie (wenn die Zeichengröße 8 Bit beträgt).

Daraus ergibt sich auch, dass je mehr Informationen Sie haben, desto mehr Möglichkeiten zur Anordnung dieser Informationen. Wenn Sie 40 Bits haben, gibt es 2 ^ 40 verschiedene Möglichkeiten, diese anzuordnen. Wenn hier von Passwörtern die Rede ist, wird es umso länger dauern, bis die Informationen (Bits) besser angeordnet sind (mit Brute-Force- oder Wörterbuchangriffen).

3
Axel K
2
Ray Tayek

Vereinfacht ausgedrückt, definiert Entropie Zufälligkeit. Es ist eher so, wie unvorhersehbar etwas ist. Technisch ausgedrückt: „Entropie ist in der Datenverarbeitung die Zufälligkeit, die von einem Betriebssystem oder einer Anwendung für die Verwendung in der Kryptographie oder für andere Zwecke erfasst wird, die Zufallsdaten erfordern. Diese Zufälligkeit wird häufig aus Hardwarequellen gesammelt, entweder aus bereits vorhandenen Quellen wie etwa Mausbewegungen oder speziell bereitgestellten Zufallsgeneratoren. “.

Man kann nun leicht auf die Bedeutung der Entropie in Bezug auf eine Datei schließen, als Maß dafür, wie viel Unordnung die Bytes in einer Datei haben. Es gibt verschiedene Einheiten zur Definition der Entropie wie Nat, Shannon oder Hartley. Nun, die am häufigsten verwendete Einheit ist Shannon. Der Wertebereich, den eine Entropie einer Datei gemäß dem Algorithmus von Shannon annehmen muss, ist 0 bis 8. Wenn der Entropiewert Null ist, kann man sagen, dass das Ergebnis sicher ist. Wenn dagegen der Entropiewert 8 ist, ist das Ergebnis höchst unvorhersehbar. Die von Shannon gegebene Formel zur Messung der Zufälligkeit im Ergebnis von Ereignissen lautet:

          Entropy = ∑ pi log(1/pi)

wobei i das Ereignis mit der Wahrscheinlichkeit pi ist. 

Diese Gleichung wird immer zwischen 0 und 8 ergeben.

Weitere Informationen erhalten Sie über den Link: https://www.talentcookie.com/2016/02/file-entropy-in-malware-analysis/

1
Tarang Arora

entropie bezieht sich auf den Umfang, in dem eine Software umgeformt wird, die gelegentlich auf den Kundenanforderungen basiert. Daher sind die Kosten für die Umgestaltung der Software zur Erfüllung der Kundenanforderungen maximal.

1
machajackson

Es ist leicht, aus Entropie eine große Sache zu machen. Meiner Meinung nach handelt es sich um ein hübsches einfaches und nützliches Konzept .

Im Grunde wird dadurch quantifiziert, was Sie im Durchschnitt aus einem Ereignis lernen werden, z. B. eine Münze werfen, eine Verzweigungsanweisung nehmen oder ein Array indizieren.

Wie eine Vergleichsoperation in der Mitte eines Suchalgorithmus hat eine bestimmte Wahrscheinlichkeit P einen Zweig und 1-P den anderen.

Angenommen, P ist 1/2, wie bei einer binären Suche. Wenn Sie dann diesen Zweig nehmen, wissen Sie 1 Bit mehr als zuvor, da log (2/1), Basis 2, 1 ist. Wenn Sie dagegen den anderen Zweig nehmen, lernen Sie auch 1 Bit.

Um die durchschnittliche Menge an Informationen zu erhalten, die Sie lernen werden, multiplizieren Sie das, was Sie in der ersten Verzweigung lernen, multipliziert mit der Wahrscheinlichkeit, dass Sie diesen Zweig nehmen, und mit dem, was Sie in der zweiten Verzweigung lernen, und zwar mit der Wahrscheinlichkeit dieses Zweigs.

1/2 mal 1 Bit plus 1/2 mal 1 Bit ist 1/2 Bit plus 1/2 Bit oder insgesamt 1 Bit Entropie. Das können Sie von dieser Entscheidung im Durchschnitt lernen.

Angenommen, Sie führen eine lineare Suche in einer Tabelle mit 1024 Einträgen durch.

Beim ersten Test ist die Wahrscheinlichkeit von JA 1/1024, also die Entropie von JA bei dieser Entscheidung

1/1024 times log(1024/1)

oder 1/1024 * 10 = etwa 1/100 Bit.

Wenn die Antwort JA lautet, lernen Sie 10 Bits, aber die Wahrscheinlichkeit dafür liegt bei etwa einem Tausendstel.

Andererseits ist NO viel wahrscheinlicher. Es ist Entropie

1023/1024 * log(1024/1023)

oder ungefähr 1 mal ungefähr null = ungefähr null.

Addieren Sie die beiden zusammen, und im Durchschnitt erfahren Sie ungefähr 1/100 von dieser Entscheidung.

Deshalb ist die lineare Suche langsam. Die Entropie (wie viel erwartet werden kann) ist bei jeder Entscheidung zu gering, da Sie 10 Bits lernen müssen, um den Eintrag in der Tabelle zu finden.

0
Mike Dunlavey

Entropie in der Informatik bezieht sich im Allgemeinen darauf, wie zufällig eine Bitfolge ist .. Die folgende Frage bezieht sich auf die Präzisierung:

Wie berechne ich die ungefähre Entropie einer Bitfolge?

0
dreeves

Wenn Sie mit einfachen Worten die Wahrscheinlichkeiten von Symbolen in der Sprache kennen, können Sie den durchschnittlichen Informationsgehalt des Symbols in der Sprache berechnen.

Oder 

Die Entropie einer Sprache ist ein Maß für den Informationsgehalt eines Durchschnittssymbols in der Sprache

Betrachten Sie eine faire Münze.

Es gibt zwei Symbole mit der Wahrscheinlichkeit 1/2 Die Entropie wird also als berechnet

h = - (1/2 * log1/2 + 1/2 * log1/2) = 1 

0
fahad pirzada

Entropie hat in der Informatik viele Bedeutungen. Das hängt vom Kontext ab. In Sicherheit bedeutet Entropie, wie viel Randomität Sie platzieren. Wenn Sie zum Beispiel einen privaten Schlüssel erstellen, werden Sie in vielen Anwendungen aufgefordert, die Maus zu bewegen, um Entropie zu erzeugen. Dies erzeugt Entropie, indem das "menschliche" Element der Zufälligkeit genommen und dem Hash-Prozess der Schlüsselerzeugung hinzugefügt wird.

Nun gibt es auch eine Definition für das Software-Engineering der Entropie. Diese Definition stellt veralteten Code dar, oder Code, bei dem viele Entwickler ihn geschrieben haben. Wird normalerweise in Bezug auf den Zeitpunkt verwendet, zu dem es an der Zeit ist, das Softwareprojekt umzugestalten. "Der Code für dieses Projekt hat eine enorme Menge an Entropie, da viele der Personen, die es gepflegt haben, derzeit nicht an dem Projekt teilnehmen.".

Hier ist ein drittes Beispiel, an das ich mich auch erinnerte. Beim Thema des simulierten Temperns (in der Informatik) wird als Entropie beschrieben, wie viel Zerfall während der Bewertung des Algorithmus aufgetreten ist.

Ich denke, um Ihre Frage zu beantworten, gibt es keine konkrete Definition des Wortes "Entropie" mit Ausnahme derjenigen, die Sie in einem Wörterbuch finden können. Wie der Begriff Informatik dazu neigt, diesen Begriff anzuwenden, hängt vom Kontext des verwendeten Begriffs ab und davon, worauf er angewendet wird.

0
jwendl

Entropie ist wie ein Hashcode auch für Virenforscher. Wenn Sie weniger Entropie erhalten, bedeutet dies, dass es sich wahrscheinlich um verschlüsselten oder komprimierten Code handelt, der möglicherweise ein Virus ist. 

Eine Standard-Binärdatei hätte eine höhere Entropie als eine komprimierte oder verschlüsselte.

0
Codingday