Quelle est la définition de la science informatique de l'entropie?
https://stackoverflow.com/questions/510412
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai récemment commencé un cours sur la compression de données à mon université. Cependant, je trouve l'utilisation du terme « entropie » telle qu'elle s'applique à la science informatique plutôt ambiguë. Pour autant que je peux dire, il se traduit à peu près au « hasard » d'un système ou une structure.
Quelle est la définition correcte de la science informatique "entropie"?
La solution
Entropy peut signifier différentes choses:
Dans le calcul, l'entropie est le aléatoire collectés par un fonctionnement système ou d'une application pour une utilisation dans cryptographie ou d'autres utilisations que exiger des données aléatoires. ce caractère aléatoire est souvent collecté du matériel sources, soit les pré-existants, tels comme les mouvements de souris ou spécialement générateurs de caractère aléatoire fourni.
Dans la théorie de l'information, l'entropie est une mesure de l'incertitude associée avec une variable aléatoire. Le terme par lui-même dans ce contexte, fait généralement référence l'entropie de Shannon, qui quantifie, dans le sens d'une valeur attendue, les informations contenu dans un message, généralement des unités telles que des bits. De manière équivalente, la Shannon entropie est une mesure de la l'information est une teneur moyenne en manquant quand on ne sait pas La valeur de la variable aléatoire
Entropy dans la compression de données
Entropie en compression de données peut indiquer le caractère aléatoire des données que vous inputing à l'algorithme de compression. Plus l'entropie, le moins élevé du taux de compression. Cela signifie que plus aléatoire le texte est, le moins vous pouvez compresser.
entropie de Shannon représente un limite absolue sur la meilleure possible la compression sans perte de toute communication: traitement de messages à codées comme une séquence d'indépendant et identiquement distribués au hasard les variables, la source de Shannon codage théorème montre que, dans la limite, la longueur moyenne de la plus courte représentation possible de coder la les messages dans un alphabet donné est leur entropie divisé par le logarithme de le nombre de symboles dans la cible alphabet.
Autres conseils
Ma définition préférée, avec un accent plus pratique, se trouve dans le chapitre 1 de l'excellent Le pragmatique programmeur: de Journeyman à Maître par Andrew Hunt et David Thomas:
Logiciels Entropy
Alors que le développement de logiciels est à l'abri de presque toutes les lois physiques, l'entropie nous frappe fort. Entropy est un terme de la physique qui se réfère à la quantité de « Désordre » dans un système. Malheureusement, les lois de la garantie de la thermodynamique que l'entropie de l'univers tend vers un maximum. lorsque le trouble augmente dans le logiciel, les programmeurs appeler "la pourriture du logiciel".
Il y a beaucoup de facteurs qui peuvent contribuer à la pourriture du logiciel. Le plus importante semble être la la psychologie ou la culture, au travail sur une projet. Même si vous êtes une équipe de un, la psychologie de votre projet peut être une chose très délicate. Malgré la meilleurs plans et les meilleurs, un projet peut encore l'expérience et la ruine décroissance pendant sa durée de vie. Pourtant, il d'autres projets qui, en dépit de d'énormes difficultés et constante revers, lutte avec succès de la nature tendance vers le désordre et à gérer sortir assez bien.
...
...
Une fenêtre brisée.
Une fenêtre brisée, pour unrepaired gauche toute longueur de temps substantielle, insuffle dans les habitants de la la construction d'un sentiment d'abandon, un sens que les pouvoirs en place ne le font pas se soucient de l'immeuble. Donc, une autre la fenêtre se brise. Les gens commencent jeter des ordures. Graffiti apparaît. Sérieux dommage structurel commence. Dans un espace de temps relativement court, la bâtiment est endommagé au-delà du le désir du propriétaire de le fixer, et sentiment d'abandon devient réalité.
La « Broken théorie de la fenêtre » a les services de police inspirés à New York et d'autres grandes villes à se fissurer vers le bas sur les petites choses pour garder le gros trucs. Ça marche: en gardant au-dessus des fenêtres brisées, graffitis, et d'autres petites infractions a réduit le taux de criminalité grave.
Astuce n ° 4
Ne pas vivre avec la vitre brisée
Ne laissez pas « fenêtres cassées » (mauvais conceptions, de mauvaises décisions ou pauvres code) unrepaired. Fixer chacun dès comme il est découvert. S'il y a suffisamment de temps pour le fixer correctement, bord puis vers le haut. Peut-être que vous pouvez commenter le code incriminé, ou afficher un message « Non implémenté », ou des données fictives au lieu de substitution. Prendre des mesures pour prévenir d'autres dommages et de montrer que vous êtes au-dessus de la situation.
Texte extrait de: http://pragprog.com/the-pragmatic- programmeur / extraits / logiciel entropie
(source: mit.edu )
Les informations notion de théorétique Entropy est une généralisation de la notion physique. Il y a plusieurs façons pour décrire Entropie. Il est une mesure du caractère aléatoire d'un aléatoire variable. Il est également une mesure de la une quantité d'information aléatoire Procédé variable ou stochastique contient. Il est également une borne inférieure le montant peut être un message comprimé. Et enfin, il est le nombre moyen de questions oui / non qui ont besoin d'être interrogé sur un aléatoire entité de déterminer sa valeur.
équation pour Entropy dans un exemple d'application pour le calcul des probabilités:
est la somme de toutes les valeurs d'une variable aléatoire de la probabilité de ce que les temps de valeur le journal de ce prob (i.e.. p (x) LogP (x)). Cette équation peut être provenant de premiers principes de la propriétés de l'information.
I entropie toujours rencontré au sens de Shannon Entropie.
De http://en.wikipedia.org/wiki/Information_entropy :
Dans la théorie de l'information, l'entropie est une mesure de l'incertitude associée à une variable aléatoire. Le terme par lui-même dans ce contexte se réfère généralement à l'entropie de Shannon, qui quantifie, dans le sens d'une valeur attendue, l'information contenue dans un message, habituellement en unités telles que des bits. De manière équivalente, l'entropie de Shannon est une mesure du contenu de l'information moyenne un manque quand on ne connaît pas la valeur de la variable aléatoire.
En ce qui concerne la compression et la théorie de l'information, l'entropie d'une source est la quantité moyenne d'informations (en bits) que les symboles de la source peut transmettre. parlant Officieusement, plus un symbole est peu probable, plus surprendre son apparence apporte.
Si votre source a deux symboles, disent et A B, et ils sont tout aussi susceptibles, chaque symbole transmet la même quantité d'informations (un bit). Une source avec quatre symboles équiprobables transmet deux bits par symbole.
Pour un exemple plus intéressant, si la source a trois symboles, C, <=> et <=>, où les deux premiers sont deux fois plus susceptibles que le troisième, le troisième est plus surprenant, mais aussi moins probable. Il y a une entropie nette de 1,52 pour cette source, tel que calculé ci-dessous.
Vous calculez l'entropie comme la « surprise moyenne », où le pour chaque symbole « surprise » est son temps de probabilité le journal binaire négatif de la probabilité:
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
Le négatif du journal binaire est utilisé (bien sûr), car les journaux des valeurs comprises entre 0 et 1 (exclusif) sont négatifs.
Voici un autre explication dans la théorie de l'information entropie .
Entropy est une mesure de incertitude liée à faire une prévision .
On peut aussi décrire l'entropie comme comment surpris nous serions si nous obtenons un résultat après que nous ayons fait notre prévision initiale.
Disons que nous avons une pièce pliée qui nous donne une tête de 99% du temps et une queue 1% du temps. Comme il n'y a un pour cent de probabilité d'obtenir une queue, nous serions très surpris si nous obtenons en fait une queue. D'autre part, il ne sera pas trop surprenant si l'on a obtenu une tête comme nous avons déjà une chance de 99 pour cent d'obtenir une tête.
laisse supposer que nous avons une fonction appelée qui nous Surprise(x) donner le montant de surprise pour chaque résultat; alors nous pouvons en moyenne la quantité de surprise sur une distribution de probabilité. Ce montant moyen de surprise pourrait aussi être utilisé comme une mesure de la façon dont nous ne savons pas. Cette incertitude est appelée entropie .
Super simple définition
L'entropie de mot peut être défini dans une phrase:
« La quantité d'informations nécessaires pour décrire un système. »
Imaginez un exemple l'expansion de l'univers: Dès le début, toute la matière a été recueillie dans un petit point avant le big bang, donc on aurait pu décrire le système avec « toute la matière est à un point. » Alors qu'aujourd'hui beaucoup plus d'informations est nécessaire pour décrire le système (l'Univers, qui est), on aurait besoin de décrire toutes les positions planétaires, leur mouvement, ce qui est sur eux, etc ..
En termes de théorie de l'information, la définition fonctionne aussi: par exemple: plus de lettres que vous ajoutez à un mot de passe (le système), plus d'informations sont nécessaires pour décrire le mot de passe. Ensuite, vous pouvez mesurer dans différentes unités, par exemple des bits ou des caractères, comme
"Bonjour" = 5 caractères entropie = 40 bits d'entropie (si charsize est de 8 bits).
De là vient que plus d'informations que vous avez les moyens plus vous pouvez organiser cette information. Si vous avez 40 bits il y a 2 ^ 40 façons différentes peuvent être organisées. Si nous parlons ici des mots de passe alors les plus arrangements possibles de l'information (bits) plus il va prendre la fissuration (avec la force brutale ou attaques par dictionnaire).
En mots plus simples, Entropy définit hasard. Il est plus comme la façon dont quelque chose est imprévisible. En termes plus techniques, « Dans l'informatique, l'entropie est le caractère aléatoire recueilli par un système d'exploitation ou une application pour une utilisation dans la cryptographie ou d'autres utilisations qui nécessitent des données aléatoires. Ce caractère aléatoire est souvent recueillies auprès de sources matérielles, que ce soit les pré-existants, tels que les mouvements de souris ou spécialement fourni des générateurs de caractère aléatoire. » Tel que défini par wikipedia.
On peut maintenant conclure facilement le sens de l'entropie en ce qui concerne un fichier en tant que mesure de la façon dont beaucoup désordonnées les octets sont dans un fichier. Il existe différentes unités utilisées pour définir l'entropie comme nat, ou shannon hartley. Eh bien, l'unité la plus couramment utilisée est Shannon. La gamme des valeurs de l'entropie d'un fichier doit venir selon l'algorithme de Shannon est de 0 à 8. Ainsi, lorsque la valeur d'entropie est nulle, on peut dire le résultat est certain. En revanche, lorsque la valeur d'entropie est 8, le résultat est plus imprévisible qu'il pourrait être. La formule donnée par Shannon pour mesurer l'aléatoire dans les résultats des événements est:
Entropy = ∑ pi log(1/pi)
où i est l'événement avec une probabilité pi .
Cette équation donne toujours entre 0 à 8.
Pour plus d'informations, rendez-vous via le lien: https: //www.talentcookie.com/2016/02/file-entropy-in-malware-analysis/
entropie fait référence dans la mesure où un logiciel est remodelée de temps en temps basant sur les exigences des clients d'où le coût de remodelant pour répondre reqrments à la clientèle devient maximale.
Entropy est comme un code de hachage pour les chercheurs de virus ainsi. Moins entropie vous obtenez, cela signifierait qu'il est probable chiffré ou un code comprimé qui pourrait être potentiellement être un virus.
Un binaire standard aurait une entropie plus élevée qu'un comprimé ou une cryptée.
Entropy a beaucoup de significations généralement en informatique. Ça dépend du contexte. Dans l'entropie de sécurité signifie combien randomality vous placez, par exemple lorsque vous générez une clé privée de nombreuses applications vous demandent de déplacer la souris pour générer l'entropie. Cela génère l'entropie en prenant l'élément « humain » de randomality et il ajoute au processus de hachage de génération de la clé.
Maintenant, il y a aussi un défnition pour l'ingénierie logicielle d'entropie. Cette définition représente de code de date ou le code qui a eu de nombreux développeurs l'écrire. Généralement utilisé en référence au moment où il est temps près de factoriser votre projet de logiciel. « Le code de ce projet a une quantité enourmous d'entropie parce que beaucoup des personnes qui maintenaient ne sont pas sur le projet en cours ».
Voici un troisième exemple d'utilisation que je me suis souvenu aussi. Dans le thème de recuit simulé (pour autant que la science informatique est concerné), l'entropie est décrit comme la quantité de décomposition est arrivé lors de l'évaluation de l'algorithme.
Je suppose que pour répondre à votre question cependant, il n'y a pas une définition concrète du mot « entropie », sauf pour ceux que vous pouvez trouver dans un dictionnaire. Comment la science informatique a tendance à appliquer ce terme dépend du contexte du terme utilisé et ce qu'il est appliqué.
Il est facile de faire une grosse affaire d'entropie. À mon avis, il est un joli concept simple et utile .
Fondamentalement, il quantifie, en moyenne, vous apprendrez d'un événement, comme une pièce de monnaie en feuilletant, en prenant une instruction de branchement, ou l'indexation d'un tableau.
Comme une opération de comparaison dans le milieu d'un algorithme de recherche a une certaine probabilité P de prendre une branche, et le 1-P de prendre l'autre.
Supposons que P est 1/2, comme dans une recherche binaire. Ensuite, si vous prenez cette branche, vous savez 1 peu plus que vous avez fait avant, parce que log (2/1), base 2, est 1. D'autre part, si vous prenez l'autre branche, vous apprendrez également 1 bit.
Pour obtenir le montant moyen d'information que vous apprendrez, il faut multiplier ce que vous apprenez sur les premiers temps de branche la probabilité que vous prenez cette branche, plus ce que vous apprenez sur le deuxième temps de branche la probabilité de cette branche.
1/2 fois 1 bit, plus 1/2 fois 1 bit, est de 1/2 bit plus 1/2 bit, 1 bit ou totale de l'entropie. C'est ce que vous pouvez vous attendre à apprendre en moyenne de cette décision.
D'autre part, supposons que vous faites la recherche linéaire dans une table de 1024 entrées.
Le premier test ==, la probabilité de YES est 1/1024, de sorte que l'entropie de OUI à cette décision est
1/1024 times log(1024/1)
ou 1/1024 * 10 = environ 1/100 bits.
Donc, si la réponse est OUI, vous apprendre 10 bits, mais la chance de qui est d'environ 1 mille.
Par contre, le NO est beaucoup plus probable. Il est de l'entropie
1023/1024 * log(1024/1023)
soit environ 1 fois à environ zéro = environ zéro.
Ajoutez les deux ensemble, et en moyenne, vous apprendrez un peu de 1/100 sur cette décision.
C'est pourquoi la recherche linéaire est lente. L'entropie (combien vous pouvez vous attendre à apprendre) à chaque décision est trop petite, puisque vous allez devoir apprendre 10 bits pour trouver l'entrée dans le tableau.
Entropy dans la science informatique se réfère généralement à la façon dont une chaîne de bits aléatoires est. La question suivante est de faire qui précise:
Comment puis-je calculer l'entropie approximative d'une chaîne de bits?
En mots simples si vous connaissez les probabilités de symboles dans le langauge, on peut calculer le contenu de l'information moyenne de symbole dans la langue.
ou
L'entropie d'une langue est une mesure du contenu de l'information d'un symbole moyenne dans la langue
Pensez à une pièce de monnaie;
Il y a deux symboles, chacun avec probabilité 1/2 si l'entropie est calculée comme
h = - (1/2 * log1 / 2 + 1/2 * log1 / 2) = 1
J'ai entendu des gens abusent des définitions de l'entropie thermodynamique w.r.t CS.
par exemple. Entropie augmente sans aucun doute dans ce système.
Quand ce qu'ils veulent dire est ce code est de pire en pire!
