コンピュータサイエンスにおけるエントロピーの定義は何ですか?

StackOverflow https://stackoverflow.com/questions/510412

質問

最近、大学でデータ圧縮に関するコースを開始しました。しかし、コンピューターサイエンスに適用される「エントロピー」という用語の使用はかなり曖昧だと思います。私の知る限り、それはシステムや構造の「ランダム性」を大まかに意味します。

コンピューターサイエンスの「エントロピー」の正しい定義は何ですか?

役に立ちましたか？

解決

エントロピーは異なるものを意味することができます：

のコンピューティングのの

  

コンピューティングでは、エントロピーは   操作によって収集ランダム   で使用するためのシステムやアプリケーション   暗号または他の用途   ランダムなデータを必要とします。このランダム性   多くの場合、ハードウェアから収集されます   情報源は、そのような既存のもののいずれか   マウスの動きとして、または特別   ランダムジェネレータを提供します。

の情報理論のの

  

は、情報理論的には、エントロピーがあります   関連する不確実性の尺度   確率変数を持ちます。による用語   この文脈では、それ自体は通常指し   シャノンのエントロピーに、どの   の意味で、定量化   期待値、情報   通常では、メッセージに含まれます   このようなビットとしてユニット。等価的に、   シャノンエントロピーはの尺度であります   平均的な情報コンテンツです   1が知らない場合に不足しています   確率変数の値が

のエントロピーデータ圧縮にする

データ圧縮におけるエントロピーを使用すると、圧縮アルゴリズムに入力環境されているデータのランダム性を示すことができます。エントロピー、低い圧縮比より。それがテキストであるよりランダム意味、あまりあなたがそれを圧縮することができます。

  

シャノンのエントロピーを表し、   可能な限り最高の絶対的な制限   いずれかの可逆圧縮   通信：するメッセージを処理します   独立のシーケンスとして符号化   そして、同一に分布するランダム   変数、コーディングシャノンのソース   定理は示して、その限度で、   最短の平均長   符号化することが可能な表現   与えられたアルファベットのメッセージは彼らのです   の対数で割ったエントロピ   ターゲットのシンボル数   アルファベットます。

他のヒント

より実践的な焦点を当てた私のお気に入りの定義は、この優れた本の第 1 章にあります。 実用的なプログラマー:ジャーニーマンからマスターへ アンドリュー・ハントとデイビッド・トーマス著：

ソフトウェアエントロピー

ソフトウェア開発はほとんどすべての物理的法則から免疫がありますが、エントロピーは私たちを激しく襲います。エントロピーは、システム内の「障害」の量を指す物理学からの用語です。残念ながら、熱力学の法則は、宇宙のエントロピーが最大になる傾向があることを保証します。ソフトウェアの障害が増加すると、プログラマーはそれを「ソフトウェア腐敗」と呼びます。

ソフトウェアの腐敗に寄与できる多くの要因があります。最も重要なのは、プロジェクトの仕事での心理学、または文化のようです。あなたが1つのチームであっても、あなたのプロジェクトの心理学は非常に繊細なものになる可能性があります。最高の計画と最高の人々にもかかわらず、プロジェクトは依然としてその生涯の間に破滅と崩壊を経験することができます。しかし、非常に困難と絶え間ないset折にもかかわらず、自然の障害への傾向と戦うことに成功し、なんとかうまく出てくることに成功した他のプロジェクトがあります。

...

...

壊れた窓。

1つの壊れた窓は、かなりの長さの間、壊れていないままになり、建物の住民に放棄の感覚を植え付けます。これは、建物を気にしない力です。そのため、別のウィンドウが壊れます。人々は散ら始めます。落書きが現れます。深刻な構造的損傷が始まります。比較的短い時期に、建物はそれを修正したいという所有者の欲求を超えて破損し、放棄の感覚が現実になります。

「壊れた窓理論」は、ニューヨークや他の主要都市の警察署に、大きなものを排除するために小さなものを取り締まるように促しました。それは動作します：壊れた窓、落書き、その他の小さな違反の上に留まることで、深刻な犯罪レベルが低下しました。

ヒント 4

壊れた窓と一緒に暮らすのはやめましょう

「壊れた窓」（悪いデザイン、間違った決定、または貧弱なコード）を残してはいけません。発見されたらすぐにそれぞれを修正します。それを適切に修正するのに不十分な時間がある場合は、搭乗してください。おそらく、問題のコードをコメントしたり、「実装されていない」メッセージを表示したり、代わりにダミーデータを置き換えることができます。さらなる損害を防ぎ、あなたが状況に加えていることを示すために、ある程度の行動を起こしてください。

テキストの抜粋: http://pragprog.com/the-pragmatic-programmer/extracts/software-entropy

alt text
（ソース： 教育)

から メキシコ大学

エントロピーの情報理論的概念は、物理的概念の一般化です。エントロピーを説明する方法はたくさんあります。これは、ランダム変数のランダム性の尺度です。また、ランダム変数または確率的プロセスに含まれる情報の量の尺度でもあります。また、メッセージを圧縮できる量の下限です。そして最後に、その価値を決定するためにランダムなエンティティについて尋ねる必要があるのは、はい/いいえの質問の平均数です。

確率計算のサンプル アプリケーションのエントロピーの方程式:

それは、その値のログのログ（つまり、その値の確率のRVのすべての値の合計）ですp(x)logp(x))。この方程式は、情報の特性の第一原理から導き出すことができます。

私はいつもシャノンエントロピーの意味でのエントロピーに遭遇しました。

http://en.wikipedia.org/wiki/Information_entropyするから：

は、情報理論において、エントロピーは確率変数に伴う不確実性の尺度です。この文脈において、それ自体用語は、通常、ビットとして通常単位の期待値は、メッセージに含まれる情報の意味で、定量化シャノンエントロピーを指します。等価的に、シャノンのエントロピーは1つがランダム変数の値を知らない場合に平均情報量1の尺度が欠落しているです。

圧縮および情報理論の観点から、ソースのエントロピーは、ソースからのシンボルを搬送することができる（ビット）の情報の平均量です。非公式に、シンボルであるよりは低いが、より多くのその外観がもたらす驚き話してます。

あなたのソースは、AとBを言う、二つのシンボルを持っており、彼らは同じように可能性がある場合は、

、その後、各シンボルは、同量の情報（1ビット）を伝えます。 4つの等しい可能性が高いシンボルとソースシンボル当たり2ビットを搬送する。

あなたのソースが最初の二つは、第三の倍の可能性のある3つのシンボル、A、B、およびCを、持っている場合は、

は、より多くの興味深い例については、第3は、より驚くべきことであるが、またにくいです。下記計算したこのソースの1.52の純エントロピーが、あります。

は、シンボル毎に「驚き」確率のその確率回負バイナリログが「平均驚き」、などのエントロピーを計算する：

                            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
0と1の間の値のログ（排他的）が負であるため、

バイナリログの負は（もちろん）が使用されます。

ここでは、情報理論におけるのエントロピーのための素晴らしい代替の説明である。

  

エントロピーは作りに関与の不確実性の尺度であります   予測の。

私たちはまた、エントロピーを記述することができますどのようにの驚いの我々は結果を取得する場合、我々は我々の最初の予測をした後、私たちは次のようになります。

私たちは私たちの時間と時間の尾1％の頭部99％を与える曲がったコインを持っているとしましょう。尾を得るための唯一の百分の一のチャンスがありますので、我々は実際に尾を取得する場合、我々は非常に驚くだろう。私たちは頭を得た場合、我々はすでに頭を得るための99パーセントのチャンスがある一方、それはあまりにも意外ではありません。

私たちはそれぞれの結果のために私たちに驚きの量を与えるだろうSurprise(x)と呼ばれる機能を持っていることを前提としています。その後、我々は、確率分布に驚きの量を平均化することができます。驚きのこの平均量はまた、我々はどのように不確実のための尺度として使用することができます。この不確実性が呼ばれたの のエントロピーのの。

スーパーSIMPLE定義

ワードエントロピーは一文で定義することができます。

「システムを記述するために必要な情報の量。」

例えば宇宙の展開を想像してみて：最初から、すべての問題は、ビッグバンの前に小さな点に集められたので、私たちはしてシステムを説明している可能性が「すべての事項は一点以内です。」今日はるかに多くの情報がシステム（つまり宇宙を、）を記述する必要がありますが、一つは、すべての惑星の位置を記述する必要があるだろう、彼らの動きは、など彼らに何が... 情報理論の観点では、定義も動作します：例えばを：パスワード（システム）に追加以上の文字、より多くの情報は、パスワードを記述するために必要とされます。その後、別のユニット、例えばビットや文字などでそれを測定することができます "ハロー" = 5文字（charsizeが8ビットの場合）のエントロピー= 40ビットをエントロピ。
ログイン このことからも、より多くの情報は、あなたがあなたがその情報を手配することができますより多くの方法を持っていることだ。あなたは40ビットを持っている場合は、それらを配置することができます2 ^ 40の異なった方法があります。私たちはここにパスワードを話している場合は、情報のより多くの可能な配置（ビット）は、もはや（ブルートフォースや辞書攻撃で）割れ取るつもりされます。

簡単な言葉では、エントロピーは、ランダム性を定義します。これは、より多くの何かがあるか予測できないようなものです。より技術的な言葉で、「コンピューティングでは、エントロピーは、暗号化またはランダムなデータを必要とする他の用途に使用するためのオペレーティングシステムまたはアプリケーションによって収集ランダムです。この乱数は、乱数発生器を、しばしば、ハードウェア・ソースからそのようなマウスの動きのようないずれかの既存のものを収集するか、特別に設けられている。」ウィキペディアによって定義される。

一つは、簡単にバイトがファイル内にある乱れどのくらいの測定としてファイルに関してエントロピーの意味を締結することができます。 NAT、シャノンまたはハートリーのようなエントロピーを定義するために使用される様々なユニットがあります。まあ、使用される最も一般的な単位はシャノンです。ファイルのエントロピーは、シャノンのアルゴリズムに従ってで来なければならない値の範囲は、エントロピー値がゼロの場合、一つは結果が一定であると言うことができます、だから、0〜8です。エントロピー値が8であるとき、逆に、結果はそれができる最も予測不可能です。イベントの結果にランダム性を測定するためにシャノンによって与えられた式は：

          Entropy = ∑ pi log(1/pi)

私はをどこ確率のパイの持つイベントです。

この式は常に8から0の間になります。

ます。https：

詳細については、リンクを介してアクセスしてください。 //www.talentcookie.com/2016/02/file-entropy-in-malware-analysis/する

エントロピーソフトウェアは、顧客の要件に基づか時折再形成される程度を指す従って顧客reqrmentsを満たすためにそれを再成形するためのコストが最大となる。

エントロピーは、同様のウイルス研究者のためのハッシュコードのようなものです。あなたが得るより少ないエントロピーが、それはおそらく、暗号化やウイルスの可能することができ、コードを圧縮されていることを意味します。

標準バイナリは、圧縮または暗号化されたものより高いエントロピーを有するであろう。

エントロピーは通常、コンピュータサイエンスの多くの意味を持っています。これは、文脈に依存します。あなたは秘密鍵を生成する際に、セキュリティのエントロピーでは、たとえば、あなたが置くどのくらいrandomality意味し、多くのアプリケーションでは、エントロピーを生成するために周りにマウスを移動するように依頼します。これはrandomalityの「ヒト」の要素を取ることによって、エントロピーを生成し、鍵を生成するハッシュプロセスに追加します。

今エントロピーのソフトウェアエンジニアリングのためのdefnitionもあります。この定義は、多くの開発者がそれを書いてきた日付コード、またはコードの外に表しています。一般的に、それはあなたのソフトウェアプロジェクトをリファクタリングする時間に近いときに言及して使用されます。 「それを維持し、個人の多くは、現在のプロジェクトではないため、このプロジェクトのコードは、エントロピーのenourmous量を持っている」。

ここで私はあまりにも思い出し第三使用例です。 （コンピュータサイエンスが懸念している限り）シミュレーテッドアニーリングのトピックでは、エントロピーはアルゴリズムの評価の中に起こっているどのくらいの崩壊と記載されています。

私もあなたの質問に答えるために思い、言葉、あなたが辞書で見つけることができるものを除いて、「エントロピー」の具体的な定義はありません。どのようにコンピュータサイエンスは、その用語が使用されている用語とそれが適用されているの文脈に依存して適用する傾向がある。

これは、エントロピーのうち、大きな取引をするのは簡単です。私の心には、<かなりシンプルかつ有用な概念であります/>。

基本的には、平均して、あなたは、コイン投げ分岐命令を取る、または配列のインデックスを作成するように、イベントから学ぶどうなるか、定量化します。

探索アルゴリズムの途中で比較動作等が一方の分岐を取る特定の確率Pを有し、そして他の撮影の1-P。

それはバイナリサーチにあるように、

、Pが1/2であると仮定する。あなたはその枝を取る場合は、ログ（2/1）は、あなたが他のブランチを取る場合は、また、1ビットを学ぶ一方、1台2であるので。

最初の分岐時間にあなたは何を学ぶあなたがその枝を取る確率を掛け、あなたが学びます情報量の平均値を取得するには、プラスあなたは第二分岐時間にその枝の確率を学ぶものに。

1/2倍、1ビット、プラス1/2倍、1ビット1/2ビットプラス1/2ビット、またはエントロピーの合計1ビットです。それはあなたがその決定から平均的に学ぶことを期待することができるものです。

一方、あなたは1024個のエントリのテーブルで線形探索を行っていると仮定します。

第==試験で、YESの確率は1/1024であるので、その判定でYESのエントロピーである

1/1024 times log(1024/1)

または1/1024 * 10 =約1/100ビット

答えはYESですので、もし

、あなたは10ビットを学び、それのチャンスはおよそ千である。

一方、NOは、はるかに可能性があります。それのエントロピーがある

1023/1024 * log(1024/1023)

またはおおよそ1回おおよそゼロ=約ゼロ

2つを追加し、平均的に、あなたはその決定して約1/100ビットのを学ぶことができます。

線形検索が遅い理由です。あなたがテーブルのエントリを見つけるために、10ビットを習得する必要があるとしているので、各決定のエントロピーは（あなたが学ぶことを期待することができますどのくらい）、小さすぎます。

あなたがのlangauge内のシンボルの確率を知っていれば、

簡単な言葉では、一つは言語のシンボルの平均情報量を計算することができます。

または

言語のエントロピーは、言語の平均シンボル

の情報内容の尺度であります

公正コインを考えてみましょう。

二つのシンボル、確率1/2で、それぞれがあります。 そうエントロピーは次のように計算された

H = - （1/2 * LOG1 / 2 + 1/2 * LOG1 / 2）= 1

私は人々がCS w.r.tエントロピーの熱力学的定義を誤用聞いた。

例えば。エントロピーは間違いなく、このシステムでは増加しています。

その意味することは、このコードが悪化し、悪化しているときに！

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top