Quelle est la définition informatique de l'entropie?

j'ai récemment commencé un cours sur la compression de données à mon université. Cependant, je trouve l'utilisation du terme "entropie" tel qu'il s'applique à l'informatique plutôt ambiguë. Pour autant que je sache, cela se traduit en gros par le "caractère aléatoire" d'un système ou d'une structure.

Quelle est la bonne définition de l ' "entropie"en informatique?

59
demandé sur Zach Scrivena 2009-02-04 10:36:26

16 réponses

l'Entropie peut signifier différentes choses:

Informatique

en informatique, l'entropie est le l'aléatoire collecté par un opérateur système ou application à utiliser dans la cryptographie ou d'autres utilisations qui exiger des données aléatoires. Ce caractère aléatoire est souvent collecté à partir de matériel sources, soit préexistantes telles que comme mouvements de souris ou spécialement à condition aléatoire générateur.

théorie de L'Information

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 dans ce contexte se réfère généralement à l'entropie de Shannon, qui quantifie, dans le sens d'une la valeur attendue, les informations contenu d'un message, habituellement dans des unités comme des bits. De manière équivalente, le Entropie de Shannon est une mesure de la contenu moyen de l'information disparu quand on ne sait pas valeur de la variable aléatoire

entropie en compression de données

entropie en compression de données peut dénoter le caractère aléatoire des données que vous saisissez à l'algorithme de compression. Plus l'entropie, moins le taux de compression. Cela signifie que plus le texte est aléatoire, moins vous peut compresser.

l'entropie de Shannon représente limite absolue sur le meilleur possible compression sans perte de tout communication: traiter les messages comme étant codé comme une séquence de et aléatoire distribué de façon identique variables, code source de Shannon théorème montre que, dans la limite, le longueur moyenne du plus court représentation possible pour encoder le les messages dans un alphabet donné entropie divisée par la logarithme de le nombre de symboles dans la cible alphabet.

54
répondu Niyaz 2009-02-04 07:41:53

Ma définition préférée, avec un plus pratique de se concentrer, se trouve dans le Chapitre 1 de l'excellent livre The pragmatic programmer: De Compagnon, de Maître par Andrew Hunt et David Thomas:

"151960920 Logiciel" Entropie

alors que le développement de logiciels est immunisé de presque toutes les lois physiques, entropie nous frappe fort. Entropie est un terme de physique qui se réfère à la quantité de "trouble" dans un système. Malheureusement, les lois de la thermodynamique garantie que l'entropie de l'univers tend vers un maximum. Lorsque le désordre augmentation des logiciels, programmeurs appelez ça "pourriture de logiciel"."

Il ya de nombreux facteurs qui peuvent contribuer à la pourriture du logiciel. La plupart des important semble être le la psychologie, ou la culture, au travail sur projet. Même si vous êtes une équipe de un, la psychologie de votre projet peut être une chose très délicate. Malgré le les meilleurs plans et les meilleures personnes, un projet peut encore éprouver la ruine et la décomposition pendant sa durée de vie. Pourtant il y en a d'autres projets sont que, malgré d'énormes difficultés et constante des revers, la lutte avec succès de la nature tendance au désordre et gérer sortir assez bien.

...

...

une fenêtre cassée.

une fenêtre cassée, "Théorie de la fenêtre cassée" a services de police inspirés dans les nouveaux York et d'autres grandes villes à craquer vers le bas sur les petites choses afin de garder les gros trucs. Il fonctionne: garder sur le dessus des fenêtres cassées, graffitis et autres infractions mineures a réduit la criminalité grave.

Astuce 4

Ne Vivez pas avec des Fenêtres Cassées

Ne quittez pas "broken windows" (mauvais dessins, mauvaises décisions ou mauvais code) non réparée. Résoudre chacun d'eux dès comme il est découvert. Si il y a pas assez de temps pour le fixer correctement, alors conseil d'administration. Peut-être vous pouvez Commenter le code incriminé, ou afficher un message "non implémenté" , ou remplacez les données factices. Prendre des mesures pour prévenir d'autres dommages et pour montrer que vous êtes sur le situation.

texte tiré de: http://pragprog.com/the-pragmatic-programmer/extracts/software-entropy

16
répondu Ash 2012-03-17 08:20:35

j'ai toujours rencontré entropie dans le 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 en lui-même dans ce contexte se réfère habituellement à L'entropie de Shannon, qui quantifie, dans le sens d'une valeur attendue, l'information contenue dans un message, généralement en unités telles que sous forme de bits. De la même façon, L'entropie de Shannon est une mesure du contenu d'information moyen dont on manque lorsqu'on ne connaît pas la valeur de la variable aléatoire.

9
répondu Adrian Grigore 2009-02-04 07:41:16

alt text http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-050JSpring-2008/9CD33A23-A58F-4CCD-8C34-DF5A83D56435/0/chp_telegraph_1.jpg

à partir de de l'Université de Mexico

La théorie de l'information notion de L'entropie est une généralisation de la physique de la notion. Il existe de nombreuses façons pour décrire l'Entropie. C'est une mesure du caractère aléatoire aléatoire variable. C'est aussi une mesure de la quantité d'informations aléatoires processus variable ou stochastique contenir. C'est aussi une borne inférieure sur la quantité qu'un message peut être compressé. Et c'est finalement l' nombre moyen de questions oui/non qui doivent être posées sur un aléatoire entité de déterminer sa valeur.

Équation pour l'Entropie dans un exemple d'application pour le calcul de possibilité:

il est la somme sur toutes les valeurs d'un rv de la probabilité de la valeur temps le journal de ce problème(c'est à dire p (x)logp (x)). Cette équation peut être dérivé des premiers principes de la les propriétés de l'information.

9
répondu Ric Tokyo 2009-02-04 13:14:41

en termes de compression et de théorie de l'information, l'entropie d'une source est la quantité moyenne d'information (en bits) que les symboles de la source peuvent transmettre. De façon informelle, plus un symbole est improbable, plus son apparence surprend.

si votre source a deux symboles, dites A et B , et ils sont également probables, alors chaque symbole transmet la même quantité d'information (un peu). Une source avec quatre chances égales symboles transmet deux bits par symbole.

pour un exemple plus intéressant, si votre source a trois symboles, A , B , et C , où les deux premiers sont deux fois plus probables que le troisième, alors le troisième est plus surprenant, mais est aussi moins probable. Il y a une entropie nette de 1,52 pour cette source, comme calculé ci-dessous.

vous calculez entropie comme la "surprise moyenne", où la" surprise " pour chaque symbole est ses temps de probabilité le log 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 log binaire est utilisé (bien sûr) parce que les logs de valeurs entre 0 et 1 (exclusif) sont négatifs.

4
répondu joel.neely 2009-02-07 17:42:11

Super SIMPLE definition

le mot entropie peut être défini dans une phrase:

"La quantité d'information nécessaire pour décrire un système."

imaginez par exemple l'expansion de l'univers: dès le début, toute matière a été recueillie en un petit point avant le Big bang, de sorte que nous aurions pu décrire le système avec "toute matière est à l'intérieur d'un point."Alors qu'aujourd'hui beaucoup plus l'information est nécessaire pour décrire le système (L'univers, c'est-à-dire), il faudrait décrire toutes les positions planétaires, leur mouvement, ce qu'il y a dessus, etc.. En termes de théorie de l'information, la définition fonctionne également: par exemple: plus vous ajoutez de lettres à un mot de passe (le système), plus d'informations sont nécessaires pour décrire le mot de passe. Ensuite, vous pouvez le mesurer en différentes unités, par exemple des bits ou des caractères, comme "hello" = entropie de 5 caractères = 40 bits d'entropie (si charsize est de 8 bits).



De cela vient aussi que plus d'informations vous avez les moyens plus vous pouvez organiser cette information. Si vous avez 40 bits, il y a 2^40 façons différentes de les organiser. Si nous parlons de mots de passe ici, alors les arrangements plus possibles de l'information (bits) plus il va prendre cracking (avec la force brute ou des attaques de dictionnaires).

3
répondu Axel K 2014-05-19 20:13:42

Voici une excellente explication alternative pour entropie dans la théorie de l'information.

entropie est une mesure de incertitude liée à la réalisation d'un prédiction .

nous pouvons aussi décrire entropie comme comment surpris nous serions si nous obtenons un résultat après que nous avons fait notre prédiction initiale.

disons que nous avons une pièce pliée qui donne-nous une tête 99% du temps, et une queue de 1% du temps. Puisqu'il y a seulement un pour cent de chances d'obtenir une queue, nous serions très surpris si l'on fait la queue. D'autre part, il ne sera pas trop surprenant si nous avons eu un chef que nous avons déjà 99% de chances d'obtenir une tête.

laisse supposer que nous avons une fonction appelée Surprise(x) qui nous donnerait la quantité de surprise pour chaque résultat; alors nous pouvons moyenne la quantité de surprise sur une probabilité distribution. Cette surprise moyenne pourrait également servir à mesurer notre degré d'incertitude. Cette incertitude est appelée entropie .

3
répondu r2d2oid 2017-06-11 03:59:18

en termes plus simples, entropie définit le hasard. C'est plus comme si quelque chose était imprévisible. En termes plus techniques, " dans le calcul, entropie est le caractère aléatoire recueilli par un système d'exploitation ou une application pour une utilisation en cryptographie ou d'autres utilisations qui exigent des données aléatoires. Ce caractère aléatoire est souvent collecté à partir de sources matérielles, soit préexistantes comme les mouvements de la souris, soit spécialement fournies comme générateurs d'aléatoire."comme défini par wikipedia.

on peut maintenant conclure facilement la signification de l'entropie par rapport à un fichier comme la mesure de combien désordonné les octets sont dans un fichier. Il existe différentes unités utilisées pour définir l'entropie comme nat, shannon ou hartley. L'unité la plus utilisée est Shannon. La plage de valeurs de l'entropie d'un fichier doit venir dans l'algorithme de Shannon est 0 à 8. Ainsi, lorsque la valeur d'entropie est nulle, on peut dire que le résultat est certain. Au contraire, lorsque la valeur d'entropie est de 8, le résultat est plus imprévisible qu'il pourrait être. La formule donnée par Shannon pour mesurer le caractère aléatoire dans le résultat des événements est:

          Entropy = ∑ pi log(1/pi)

i est l'événement avec Probabilité pi .

cette équation donnera toujours entre 0 et 8.

pour plus d'informations, allez sur le lien: https://www.talentcookie.com/2016/02/file-entropy-in-malware-analysis /

1
répondu Tarang Arora 2016-02-05 15:29:02

entropie se réfère à la mesure où un logiciel est remodelé occasionnellement en se basant sur les exigences du client, donc le coût de remodelage pour répondre aux exigences du client devient maximum.

1
répondu machajackson 2017-06-27 15:10:33

entropie est comme un code de hachage pour les chercheurs de virus aussi bien. Moins vous obtenez entropie, cela signifierait qu'il est probablement crypté ou code compressé qui pourrait être un virus.

un binaire standard aurait une entropie plus élevée qu'un binaire comprimé ou chiffré.

0
répondu Codingday 2009-02-04 11:18:22

L'entropie a plusieurs significations typiquement en informatique. Ça dépend du contexte. En entropie de sécurité signifie Combien de randomalité vous placez, par exemple quand vous générez une clé privée de nombreuses applications vous demandent de déplacer la souris pour générer entropie. Cela génère l'entropie en prenant l'élément" humain " de l'aléatoire et l'ajoute au processus de hachage de générer la clé.

maintenant il y a aussi une définition pour l'ingénierie logicielle de l'entropie. Ce la définition représente le code périmé, ou le code qui a été écrit par de nombreux développeurs. Généralement utilisé en référence à quand il est proche de temps pour remanier votre projet de logiciel. "Le code pour ce projet a une énorme quantité d'entropie, parce que beaucoup de particuliers qui ne sont pas sur le projet actuellement".

voici un troisième exemple d'usage dont je me souviens aussi. Dans le domaine du recuit simulé (en ce qui concerne l'informatique), l'entropie est décrit comme combien de désintégration qui s'est passé 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 l'informatique a tendance à appliquer ce terme dépend du contexte du terme et ce qu'il est appliqué.

0
répondu jwendl 2009-02-07 17:41:10

c'est facile de faire une grosse affaire avec entropie. À mon avis, c'est un joli concept simple et utile .

fondamentalement, il quantifie ce que, en moyenne, vous apprendrez d'un événement, comme retourner une pièce de monnaie, prendre une instruction de branche, ou indexer un tableau.

Comme une opération de comparaison au moyen d'un algorithme de recherche a une certaine probabilité P de se prendre une branche, et 1-P de l'autre.

Suppose P est 1/2, comme il est dans une recherche binaire. Puis si vous prenez cette branche, vous en savez un peu plus qu'avant, car log(2/1), base 2, est 1. D'autre part, si vous prenez l'autre branche, vous apprenez également 1 bit.

pour obtenir la quantité moyenne d'information que vous apprendrez, multipliez ce que vous apprenez sur la première branche fois la probabilité que vous prenez cette branche, plus ce que vous apprenez sur la deuxième branche fois la probabilité de cette branche.

1/2 fois 1 bit, plus 1/2 fois 1 bit, est de 1/2 peu plus de 1/2 bits, ou total 1 bits d'entropie. C'est ce que vous pouvez vous attendre à apprendre en moyenne de cette décision.

, d'autre part, supposons que vous faites une recherche linéaire dans un tableau de 1024 entrées.

Sur le premier == test, la probabilité de OUI est 1/1024, donc l'entropie de OUI à cette décision est

1/1024 times log(1024/1)

ou 1/1024 * 10 = environ 1/100 bit.

donc si la réponse est oui, vous apprenez 10 bits, mais la chance de cela est d'environ 1 sur mille.

d'un autre côté, non est beaucoup plus probable. C'est entropie est

1023/1024 * log(1024/1023)

ou environ 1 fois environ zéro = environ zéro.

additionnez les deux, et en moyenne vous apprendrez environ 1/100 d'un peu 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 petit, car vous allez avoir à apprendre 10 bits pour trouver l'entrée dans la table.

0
répondu Mike Dunlavey 2017-05-23 11:54:40

entropie en informatique se réfère généralement à la façon dont aléatoire une chaîne de bits est. La question suivante est de préciser:

comment calculer l'entropie approximative d'une chaîne de bits?

0
répondu dreeves 2017-05-23 12:09:59

en mots simples si vous connaissez les probabilités des symboles dans le langauge ,on peut calculer le contenu d'information moyen du symbole dans la langue .

ou

L'entropie d'une langue est une mesure du contenu de l'information moyenne d'un symbole dans la langue

Envisager une foire pièce de monnaie ;

il y a deux symboles, chacun avec Probabilité 1/2 ainsi l'entropie est calculée comme

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

0
répondu fahad pirzada 2017-03-21 16:03:54

j'ai entendu dire que les gens abusent des définitions thermodynamiques de l'entropie.R. T CS.

E. G. L'entropie augmente nettement dans ce système.

quand ce qu'ils veulent dire c'est que ce code est de pire en pire!

-1
répondu Fortyrunner 2009-02-04 07:50:08