Was ist die Informatik Definition der Entropie?
https://stackoverflow.com/questions/510412
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe einen Kurs über Datenkompression an meiner Universität vor kurzem begonnen. Allerdings finde ich die Verwendung der Begriff „Entropie“, wie es in der Informatik gilt eher zweideutig. Soweit ich sagen kann, es übersetzt in etwa die „Zufälligkeit“ einem System oder eine Struktur.
Was ist die richtige Definition der Informatik "Entropie"?
Lösung
Entropy kann verschiedene Dinge bedeuten:
Bei der Berechnung der Entropie ist die Zufälligkeit durch einen Betrieb gesammelte System oder Anwendung für die Verwendung in Kryptographie oder andere Verwendungen, die erfordern Zufallsdaten. diese Zufälligkeit wird oft von der Hardware gesammelt Quellen, entweder vorge bestehende solche wie Mausbewegungen oder speziell vorgesehen Zufälligkeit Generatoren.
In der Informationstheorie, Entropie ist ein Maß für die Unsicherheit im Zusammenhang mit einer Zufallsgröße. Der Begriff von in der Regel selbst in diesem Zusammenhang bezieht sich an die Shannon-Entropie, die im Sinne einer quantifiziert, Erwartungswert, die Informationen in einer Nachricht enthalten sind, in der Regel in Einheiten wie Bits. Gleichwertig, die Shannon Entropie ist ein Maß für die durchschnittliche Informationsgehalt ist fehlt, wenn man nicht weiß, hat die Wert der Zufallsvariablen
Entropy in Datenkompression
Entropy in Datenkompression kann die Zufälligkeit der Daten bezeichnen, die Sie mit dem Kompressionsalgorithmus inputing. Je mehr sich die Entropie, desto geringer ist das Kompressionsverhältnis. Das heißt, die mehr zufällig der Text ist, desto weniger können Sie es komprimieren.
Shannons Entropie stellt ein absolute Grenze für die bestmögliche verlustfreie Komprimierung von irgend Kommunikation: Nachrichten Behandlung zu sein codiert als eine Folge unabhängiger und identisch verteilte Zufalls Variablen, Shannons Quellcodierverfahren Theorem zeigt, daß in der Begrenzung, die durchschnittliche Länge der kürzesten mögliche Darstellung zu kodieren, die Nachrichten in einem bestimmten Alphabet ist ihre Entropie dividiert durch den Logarithmus von die Anzahl der Symbole in dem Ziel Alphabet.
Andere Tipps
Meine Lieblings Definition, mit einem praktischeren Fokus wird in Kapitel 1 des ausgezeichneten Buch pragmatische Programmierer: von Gesellen Meister von Andrew Hunt und David Thomas:
Software Entropy
Während der Software-Entwicklung ist immun von fast allen physikalischen Gesetzen, Entropie trifft uns hart. Entropy ist ein Begriff aus Physik, die den Betrag von verweist "Unordnung" in einem System. Unglücklicherweise, die Gesetze der Thermodynamik Garantie daß die Entropie im Universum neigt zu einem Maximum. wenn Störung erhöht in der Software-Programmierer nennt es "Software rot."
Es gibt viele Faktoren, die können Software rot beitragen. Am meisten wichtig scheint der zu sein, Psychologie oder Kultur, bei der Arbeit an einem Projekt. Selbst wenn Sie sind ein Team von ein, kann Ihr Projekt Psychologie eine sehr heikle Sache. Trotz der beste Pläne und die besten Leute, ein Projekt kann noch erleben Ruine und Zerfall während seiner Lebensdauer. doch es dass es andere Projekte, trotz enorme Schwierigkeiten und konstant Rückschläge, kämpfen erfolgreich Natur Tendenz zur Unordnung und verwalten zu kommt ziemlich gut.
...
...
Ein zerbrochenes Fenster.
Ein zerbrochenes Fenster, links unrepaired für eine wesentliche Länge der Zeit, flößt den Bewohnern der Gebäude ein Gefühl des Verlassenseins-a Sinn, dass die Kräfte, die nicht tun über das Gebäude kümmern. so ein anderer Fenster wird gebrochen. Die Menschen beginnen Littering. Graffiti erscheint. ernst Bauschäden beginnt. In einem relativ kurze Zeit, das Gebäude wird über die beschädigt Besitzer den Wunsch, es zu beheben, und die Gefühl der Verlassenheit wird Realität.
Die "Broken Window Theory" hat inspiriert Polizei in New York und andere große Städte zu knacken nach unten auf den kleinen Dingen, um halten die großen Sachen aus. Es klappt: auf den zerbrochenen Fensterscheiben zu halten, Graffiti und andere kleine Übertretungen das schwere Kriminalität Niveau reduziert.
Tipp 4
Sie nicht leben mit zerbrochenen Fensterscheiben
Lassen Sie keine "broken windows" (bad Entwürfe, falsche Entscheidungen oder schlecht Code) nicht repariert. Fix jeden so schnell wie es entdeckt. Wenn da ist nicht genügend Zeit, um es richtig zu beheben, Bord es dann nach oben. Vielleicht können Sie Kommentar der säumige Code aus, oder zeigen eine „nicht implementiert“ -Meldung, oder Ersatzblinddaten statt. Nehmen eine Aktion um weitere Schäden zu verhindern und zu zeigen, dass Sie oben auf der sind Situation.
Text aus: http://pragprog.com/the-pragmatic- Programmierer / Extrakte / Software-Entropie
(Quelle: mit.edu )
Der informationstheoretische Begriff der Entropy ist eine Verallgemeinerung der physikalischer Begriff. Es gibt viele Wege zu beschreiben Entropy. Es ist ein Maß der Zufälligkeit einer zufälligen Variable. Es ist auch ein Maß für die Menge an Informationen eines zufälligen Variable oder stochastischer Prozess enthält. Es ist auch eine untere Schranke auf die Menge eine Nachricht sein kann komprimiert. Und schließlich ist es die durchschnittliche Anzahl der Ja / Nein-Fragen dass Notwendigkeit, um eine zufällig gefragt, Unternehmen seinen Wert zu bestimmen.
Die Gleichung für Entropy in einer Beispielanwendung für Wahrscheinlichkeitsrechnung:
Es ist die Summe über alle Werte einer rv der Wahrscheinlichkeit, dass Wertzeiten das Protokoll dieser prob (d. p (x) logP (x)). Diese Gleichung kann sein abgeleitet von ersten Grundsätzen der Eigenschaften von Informationen.
ich immer Entropie im Sinne von Shannon Entropy begegnet.
http://en.wikipedia.org/wiki/Information_entropy :
In der Informationstheorie ist die Entropie ein Maß für die Unsicherheit, die mit einer Zufallsvariablen zugeordnet. Der Begriff selbst in diesem Zusammenhang bezieht sich normalerweise auf die Shannon-Entropie, die im Sinne von einem erwarteten Wert quantifiziert, die Informationen in einer Nachricht enthalten ist, in der Regel in Einheiten wie Bits. Gleichwertig, die Shannon-Entropie ist ein Maß für die durchschnittliche Informationsgehalt eines fehlt, wenn man nicht den Wert der Zufallsvariablen nicht kennt.
Im Hinblick auf die Komprimierung und Informationstheorie ist die Entropie einer Quelle ist die durchschnittliche Menge an Informationen (in Bits), die Symbole von der Quelle vermitteln kann. Informell gesprochen, desto unwahrscheinlicher ist ein Symbol, bringt das mehr überraschen seine Erscheinung.
Wenn Ihre Quelle zwei Symbole hat, sagen A und B, und sie ist gleich wahrscheinlich, dann jedes Symbol vermittelt die gleiche Menge an Informationen (ein Bit). Eine Quelle mit vier gleich wahrscheinlich Symbolen vermittelt zwei Bits pro Symbol.
Für ein interessantes Beispiel, wenn Ihre Quelle drei Symbole hat, A, B und C, wo die ersten beiden doppelt so wahrscheinlich wie die dritte, dann ist das dritte überraschender ist aber auch weniger wahrscheinlich. Es gibt eine Netto-Entropie von 1,52 für diese Quelle, wie unten berechnet.
Sie berechnen Entropie als „durchschnittliche Überraschung“, wo die „Überraschung“ für jedes Symbol seiner Wahrscheinlichkeit mal die negative Binärlog 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 der binären logarithmischen wird (natürlich) verwendet, da logs von Werten zwischen 0 und 1 (exklusiv) ist negativ.
Hier ist eine große alternative Erklärung für Entropie in der Informationstheorie.
Entropie ist ein Maß für Unsicherheit bei der Herstellung eines beteiligt Vorhersage .
Wir können auch Entropie wie überrascht beschreiben wären wir, wenn wir ein Ergebnis erhalten, nachdem wir unsere erste Vorhersage gemacht.
Lassen Sie uns sagen wir einen gebogenen Münze, die uns einen Kopf 99% der Zeit und einem Schwanz 1% der Zeit gibt. Da es, sich einen Schwanz nur eine einprozentige Chance ist, würden wir sehr überrascht, wenn wir tatsächlich einen Schwanz bekommen. Auf der anderen Seite, es wird nicht allzu überraschend, wenn wir einen Kopf bekamen, wie wir bereits eine 99-prozentige Chance, einen Kopf zu bekommen.
lässt vermuten, dass wir eine Funktion namens Surprise(x) haben, die uns die Menge Überraschung für jedes Ergebnis geben würde; dann können wir die Menge der Überraschung auf einer Wahrscheinlichkeitsverteilung im Durchschnitt. Diese durchschnittliche Menge der Überraschung könnte auch als Maß für die verwendet werden, wie unsicher wir sind. Diese Unsicherheit wird als Entropie .
Super einfache Definition
Das Wort Entropie kann in einem Satz definiert werden:
"Die Menge an Informationen benötigt ein System zu beschreiben."
Stellen Sie sich zum Beispiel die Expansion des Universums: Von Anfang an alle Materie in einem kleinen Punkt vor dem Urknall gesammelt, so konnten wir das System beschrieben haben, mit „alle Materie in einem Punkt ist.“ Während heute wesentlich mehr Informationen benötigt, um das System (das Universum, das ist) zu beschreiben, müßte man alle Planeten-Positionen beschreiben, ihre Bewegung, was etc auf sie ist ..
In Bezug auf der Informationstheorie funktioniert die Definition auch: Z. B: Je mehr Buchstaben Sie ein Passwort hinzufügen (das System), desto mehr Informationen benötigt, um das Passwort zu beschreiben. Dann können Sie es in verschiedenen Einheiten, zB Bits oder Zeichen messen, wie
"Hallo" = 5 Zeichen Entropie = 40 Bits Entropie (wenn charsize ist 8 Bits).
Daraus ergibt sich auch, dass die mehr Informationen, desto mehr Möglichkeiten haben Sie diese Informationen in arrangieren können. Wenn Sie 40 Bits haben, gibt es 2 ^ 40 verschiedene Arten können sie angeordnet werden. Wenn wir Passwörter hier dann die weiteren möglichen Anordnungen der Information (Bits), desto länger sprechen, es wird (mit Brute-Force oder Wörterbuch-Attacken) nehmen knacken.
In einfacheren Worten definiert Entropy Zufälligkeit. Es ist mehr wie, wie unberechenbar etwas ist. In technischen Worten: „Bei der Berechnung ist die Entropie die Zufälligkeit durch ein Betriebssystem oder eine Anwendung für die Verwendung in der Kryptographie oder anderen Verwendungen gesammelt, die Zufallsdaten erfordern. Diese Zufälligkeit wird häufig von Hardware-Quellen gesammelt, entweder vorge bestehende wie Mausbewegungen oder speziell Zufälligkeit Generatoren zur Verfügung gestellt.“, Wie wikipedia definiert.
Man kann nun leicht die Bedeutung der Entropie in Bezug auf eine Datei schließen, wie die Messung der wie viel Unordnung die Bytes in einer Datei sind. Es gibt verschiedene Einheiten zur Definition von Entropie wie nat, shannon oder hartley verwendet. Nun, die meisten gemeinsame Einheit verwendet wird, ist Shannon. Der Wertebereich eine Entropie der Datei nach Shannon-Algorithmus kommen muss, ist 0 bis 8 Also, wenn die Entropie Wert gleich Null ist, kann man sagen, das Ergebnis ist sicher. Im Gegenteil, wenn die Entropie Wert 8 ist, ist das Ergebnis unvorhersehbarsten es sein könnte. Die Formel von Shannon gegeben Zufälligkeit der Ereignisse in den Ergebnissen zu messen ist:
Entropy = ∑ pi log(1/pi)
Dabei steht i ist das Ereignis mit einer Wahrscheinlichkeit von pi .
Diese Gleichung führt immer zwischen 0-8.
Weitere Informationen finden Sie über den Link: https: //www.talentcookie.com/2016/02/file-entropy-in-malware-analysis/
Entropie bezieht sich auf das Ausmaß, wo eine Software gelegentlich auf Kundenanforderungen basieren neu geformt wird damit die Kosten für Umformung Kunden reqrments gerecht zu werden maximal wird.
Entropy ist wie ein Hash-Code für die Virus-Forscher als auch. Weniger Entropie Sie erhalten, würde es bedeuten, dass es wahrscheinlich verschlüsselt oder Code komprimiert, die möglicherweise einen Virus enthalten sein könnte.
Ein Standardbinärdistributionen würde eine höhere Entropie als eine komprimierte oder verschlüsselte ein.
Entropy hat viele Bedeutungen typischerweise in der Informatik. Es hängt vom Kontext ab. Entropie bedeutet, in Sicherheit, wie viel randomality Sie platzieren, zum Beispiel, wenn Sie einen privaten Schlüssel viele Anwendungen generieren fragen Sie die Maus zu bewegen um Entropie zu erzeugen. Dies erzeugt Entropie durch das „menschliche“ Element randomality nehmen und fügt sie den Hashing-Prozess die Schlüssel zu erzeugen.
Jetzt gibt es auch eine defnition für Software Engineering der Entropie. Diese Definition stellt veraltet Code oder Code, der viele Entwickler schreiben sie gehabt hat. Typischerweise in Referenz verwendet, wenn es in der Nähe von Zeit, um Ihr Software-Projekt Refactoring. „Der Code für dieses Projekt hat eine enorme Menge an Entropie, weil viele der Personen, die gepflegt es ist nicht für das Projekt zur Zeit“.
Hier ist ein drittes Beispiel für die Verwendung, die ich auch in Erinnerung hatte. Im Thema der simulierten Glühen (soweit Informatik betroffen ist), wird die Entropie beschrieben, wie vielen Zerfall bei der Auswertung des Algorithmus geschehen ist.
Ich glaube, Ihre Frage zu beantworten gibt es aber keine konkrete Definition des Wortes ‚Entropie‘, außer für diejenigen, die Sie in einem Wörterbuch finden. Wie Informatik neigt dieser Begriff hängt vom Kontext des Begriffs anzuwenden ist, verwendet und was sie angewandt wird.
Es ist einfach eine große Sache aus der Entropie zu machen. Meiner Meinung nach ist es ein ziemlich einfaches und nützliches Konzept .
Im Grunde quantifiziert es, was im Durchschnitt Sie von einem Ereignis erfahren, wie eine Münze werfen, einen Verzweigungsbefehl nehmen, oder die Indizierung eines Arrays.
Wie eine Vergleichsoperation in der Mitte eines Suchalgorithmus hat eine gewisse Wahrscheinlichkeit P einen Zweig des Nehmens und 1-P von den andere nehmen.
Sei P 1/2, wie es in einer binären Suche ist. Dann, wenn Sie diesen Zweig nehmen, wissen Sie, ein bisschen mehr als vorher, denn log (2/1), Basis 2, 1. Auf der anderen Seite ist, wenn Sie die andere Zweig nehmen auch Sie ein bisschen lernen.
Um die durchschnittliche Menge an Informationen erhalten Sie lernen, sich vermehren, was Sie auf dem ersten Zweig mal lernen die Wahrscheinlichkeit Sie diesen Zweig nehmen, und was Sie lernen, auf dem zweiten Zweig mal die Wahrscheinlichkeit dieses Zweiges.
1/2 mal 1 Bit plus 1/2 mal 1 Bit, ist 1/2 Bit Plus 1/2 Bit oder 1 Bit insgesamt der Entropie. Das ist, was können Sie von dieser Entscheidung im Durchschnitt lernen erwartet.
Auf der anderen Seite an, dass Sie in einer Tabelle von 1024 Einträgen lineare Suche tun.
Im ersten == Test die Wahrscheinlichkeit von YES ist 1/1024, so dass die Entropie von JA zu dieser Entscheidung ist
1/1024 times log(1024/1)
oder 1/1024 * 10 = etwa 1/100 Bit.
Also, wenn die Antwort ja ist, lernen Sie 10 Bits, aber die Wahrscheinlichkeit, dass etwa 1 in tausend.
Auf der anderen Seite ist keine viel wahrscheinlicher. Es ist Entropie
1023/1024 * log(1024/1023)
oder etwa 1 mal grob Null = etwa Null.
Fügen Sie die beiden zusammen, und im Durchschnitt werden Sie etwa 1/100 eines Bits auf diese Entscheidung erfahren.
Deshalb lineare Suche langsam ist. Die Entropie bei jeder Entscheidung zu klein (wie viel Sie können zu lernen, erwarten) ist, da man 10 Bits zu lernen haben werden Sie den Eintrag in der Tabelle zu finden.
Entropy in der Informatik bezieht sich allgemein auf, wie zufällig eine Folge von Bits ist. Die folgende Frage geht es darum, dass eine präzise:
In einfachen Worten, wenn Sie die Wahrscheinlichkeiten der Symbole in dem Langauge kennen, kann man den durchschnittlichen Informationsgehalt des Symbols in der Sprache berechnen.
oder
Die Entropie einer Sprache ist ein Maß für den Informationsgehalt eines durchschnittlichen Symbols in der Sprache
Betrachten wir eine faire Münze;
Es gibt zwei Symbole, die jeweils mit einer Wahrscheinlichkeit von 1/2 so Entropie wird wie folgt berechnet
h = - (1/2 * log1 / 2 + 1/2 * log1 / 2) = 1
Ich habe gehört, wie Leute, die thermodynamische Definition der Entropie w.r.t CS missbräuchlich verwenden.
z. Entropy ist auf jeden Fall in diesem System zu erhöhen.
Wenn das, was sie bedeuten, ist dieser Code wird immer schlimmer!
