엔트로피에 대한 컴퓨터 과학의 정의는 무엇입니까?

Question

저는 최근 대학에서 데이터 압축 과정을 시작했습니다.그러나 나는 컴퓨터 과학에 적용되는 "엔트로피"라는 용어의 사용이 다소 모호하다고 생각합니다.내가 알 수 있는 한, 이는 대략 시스템이나 구조의 "무작위성"으로 해석됩니다.

컴퓨터 과학 "엔트로피"의 올바른 정의는 무엇입니까?

Answer 1

엔트로피는 다른 것을 의미 할 수 있습니다.

컴퓨팅

컴퓨팅에서 엔트로피는 운영 체제 또는 암호화 또는 임의의 데이터가 필요한 기타 용도에 사용하기 위해 수집 한 무작위성입니다. 이 무작위성은 종종 마우스 움직임과 같은 기존의 하드웨어 소스 또는 특별히 제공된 임의성 생성기에서 수집됩니다.

정보 이론

정보 이론에서 엔트로피는 랜덤 변수와 관련된 불확실성의 척도입니다. 이 맥락에서 용어 자체는 일반적으로 예상 값의 의미에서 메시지에 포함 된 정보, 일반적으로 비트와 같은 단위로 정량화되는 Shannon Entropy를 나타냅니다. 동일하게 Shannon Entropy는 임의 변수의 값을 모를 때 누락 된 평균 정보 컨텐츠의 척도입니다.

데이터 압축의 엔트로피

데이터 압축의 엔트로피는 압축 알고리즘에 입력하는 데이터의 무작위성을 나타낼 수 있습니다. 엔트로피가 많을수록 압축 비율이 줄어 듭니다. 즉, 텍스트가 무작위로 많을수록 압축 할 수 있습니다.

Shannon의 엔트로피는 모든 의사 소통의 최상의 무손실 압축에 대한 절대 제한을 나타냅니다. 독립적이고 동일하게 분포 된 임의 변수 시퀀스로 인코딩 할 메시지를 처리하는 Shannon의 소스 코딩 정리는 한계에서 가장 짧은 평균 길이가 가장 짧음을 보여줍니다. 주어진 알파벳에서 메시지를 인코딩 할 수있는 가능한 표현은 엔트로피를 대상 알파벳의 기호 수의 로그로 나눈 것입니다.

Answer 2

보다 실용적인 초점을 맞춘 내가 가장 좋아하는 정의는 훌륭한 책의 1장에서 찾을 수 있습니다. 실용적인 프로그래머:숙련공에서 마스터로 앤드류 헌트(Andrew Hunt)와 데이비드 토마스(David Thomas) 저:

소프트웨어 엔트로피

소프트웨어 개발은 ​​거의 모든 물리 법칙에서 면역력이 있지만 엔트로피는 우리를 강타합니다.엔트로피는 시스템의 "장애"의 양을 나타내는 물리학의 용어입니다.불행히도, 열역학 법칙은 우주의 엔트로피가 최대를 향한 경향이 있음을 보장합니다.소프트웨어의 장애가 증가하면 프로그래머는이를 "소프트웨어 썩음"이라고 부릅니다.

소프트웨어 썩음에 기여할 수있는 많은 요소가 있습니다.가장 중요한 것은 프로젝트 작업에서 심리학 또는 문화 인 것 같습니다.당신이 하나의 팀이더라도 프로젝트의 심리학은 매우 섬세한 일이 될 수 있습니다.최고의 계획과 최고의 사람들에도 불구하고 프로젝트는 평생 동안 폐허와 부패를 경험할 수 있습니다.그러나 엄청난 어려움과 끊임없는 좌절에도 불구하고 자연의 장애에 대한 경향에 맞서 싸우고 꽤 잘 나오는 다른 프로젝트가 있습니다.

...

...

깨진 창문.

상당한 시간 동안 회복되지 않은 상태로 남겨두고 건물의 주민들에게 포기감을 심어주는 것, 즉 건물에 관심이없는 힘이라는 느낌입니다.그래서 또 다른 창이 고장납니다.사람들은 쓰레기를 시작합니다.낙서가 나타납니다.심각한 구조적 손상이 시작됩니다.비교적 짧은 시간에 건물은 소유자의 욕구를 넘어서 손상되며 포기감은 현실이됩니다.

"깨진 창문 이론"은 뉴욕과 다른 주요 도시의 경찰서가 큰 물건을 막기 위해 작은 물건을 단속하도록 영감을주었습니다.효과가있다:깨진 창문, 낙서 및 기타 작은 위반으로 인해 심각한 범죄 수준이 줄어 듭니다.

팁 4

깨진 유리창을 갖고 살지 마세요

"Broken Wind발견 되 자마자 각각을 고정하십시오.제대로 고칠 시간이 충분하지 않은 경우 탑승하십시오.아마도 불쾌한 코드를 주석하거나 "구현되지 않은"메시지를 표시하거나 대신 더미 데이터를 대체 할 수 있습니다.추가 피해를 방지하고 상황이 위에 있음을 보여주기 위해 조치를 취하십시오.

다음에서 가져온 텍스트: http://pragprog.com/the-pragmatic-programmer/extracts/software-entropy

Answer 3

_{(원천: mit.edu)}

~에서 멕시코 대학교

엔트로피의 정보 이론적 개념은 물리적 개념의 일반화입니다. 엔트로피를 설명하는 방법에는 여러 가지가 있습니다. 임의 변수의 무작위성 측정입니다. 또한 무작위 변수 또는 확률 적 프로세스에 포함 된 정보의 양의 척도입니다. 또한 메시지를 압축 할 수있는 양의 하한입니다. 마지막으로 값을 결정하기 위해 임의의 엔티티에 대해 요청 해야하는 평균 예/아니오 질문 수입니다.

확률 계산을위한 샘플 응용 프로그램에서 엔트로피에 대한 방정식 :

그것은 해당 값의 확률의 RV의 모든 값에 대한 합계입니다. 이 방정식은 정보 속성의 첫 번째 원칙에서 파생 될 수 있습니다.

Answer 4

나는 항상 섀넌 엔트로피의 의미에서 엔트로피를 만났다.

에서 http://en.wikipedia.org/wiki/information_entropy:

정보 이론에서 엔트로피는 랜덤 변수와 관련된 불확실성의 척도입니다. 이 맥락에서 용어 자체는 일반적으로 예상 값의 의미에서 메시지에 포함 된 정보, 일반적으로 비트와 같은 단위로 정량화되는 Shannon Entropy를 나타냅니다. 동일하게, Shannon Entropy는 임의 변수의 값을 모를 때 누락 된 평균 정보 컨텐츠의 척도입니다.

Answer 5

압축 및 정보 이론 측면에서, 소스의 엔트로피는 소스의 상징이 전달할 수있는 평균 정보 (비트)입니다. 비공식적으로 말하자면, 상징이 더 가능성이 높을수록 외모가 더 놀랍습니다.

소스에 두 개의 기호가있는 경우 A 그리고 B, 그리고 그럴 가능성이 높습니다. 각 기호는 동일한 양의 정보 (한 번)를 전달합니다. 4 개의 기호가있는 소스는 기호 당 두 비트를 전달합니다.

더 흥미로운 예를 위해, 소스에 세 가지 기호가있는 경우 A, B, 그리고 C, 첫 번째 두 사람이 세 번째보다 두 배나 높고 세 번째는 더 놀랍지 만 가능성이 적습니다. 아래 계산 된 바와 같이이 소스에 대해 순 엔트로피가 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 (독점) 사이의 값의 로그가 음수이기 때문에 사용됩니다 (물론).

Answer 6

다음은 훌륭한 대체 설명입니다 엔트로피 정보 이론에서.

엔트로피는의 척도입니다 예측과 관련된 불확실성.

엔트로피를 방법으로 설명 할 수도 있습니다 놀란 우리가 초기 예측을 한 후에 결과를 얻는다면 우리는 될 것입니다.

시간의 99%와 꼬리의 시간을 1%로주는 구부러진 동전이 있다고 가정 해 봅시다. 꼬리를 얻을 확률은 1 %에 불과하기 때문에 실제로 꼬리를 얻는다면 매우 놀랄 것입니다. 반면에, 우리가 이미 머리를 얻을 확률이 99 %가 있기 때문에 우리가 머리를 얻었다면 너무 놀라운 것은 아닙니다.

우리가 호출되는 함수가 있다고 가정하자 Surprise(x) 그것은 우리에게 각 결과에 대한 놀라움의 양을 줄 것입니다. 그런 다음 확률 분포에 대한 놀라움의 양을 평균화 할 수 있습니다. 이 평균 놀라움은 우리가 얼마나 불확실한지를위한 척도로 사용될 수 있습니다. 이 불확실성을 불러옵니다 엔트로피.

Answer 7

매우 간단한 정의

엔트로피라는 단어는 한 문장으로 정의 할 수 있습니다.

"시스템을 설명하는 데 필요한 정보의 양."

예를 들어 우주의 확장을 상상해보십시오. 처음부터 모든 물질은 빅뱅 이전의 작은 지점에서 수집되었으므로 우리는 "모든 문제가 한 지점 내에있는 시스템"을 설명 할 수있었습니다. 오늘날 시스템 (우주, 즉)을 설명하기 위해서는 더 많은 정보가 필요하지만, 모든 행성 위치, 그들의 움직임, 그들에 관한 것 등을 설명해야 할 것입니다. 정보 이론의 관점에서, 정의는 다음과 같습니다. 비밀번호 (시스템)에 더 많은 문자를 추가할수록 비밀번호를 설명하기 위해 더 많은 정보가 필요합니다. 그런 다음 "hello"= 5 문자 엔트로피 = 40 비트의 엔트로피 (Charsize가 8 비트 인 경우)와 같은 비트 또는 문자와 같은 다른 단위로 측정 할 수 있습니다.

이것으로부터 더 많은 정보를 얻을수록 해당 정보를 더 많이 준비 할 수 있습니다. 40 비트가있는 경우 2^40 가지 방법이 있으면 배열 할 수 있습니다. 우리가 여기서 비밀번호를 말하는 경우 정보 (비트)의 가능한 배열이 더 길어지면 크래킹 (무차별 인력 또는 사전 공격)이 더 길어질 것입니다.

Answer 8

간단한 단어에서 엔트로피는 무작위성을 정의합니다. 그것은 예측할 수없는 것과 비슷합니다. 보다 기술적 인 말로,“컴퓨팅에서 엔트로피는 운영 체제 또는 암호화 또는 임의의 데이터가 필요한 다른 용도에 사용하기 위해 수집 한 무작위성입니다. 이 무작위성은 종종 마우스 움직임과 같은 기존의 하드웨어 소스에서 수집되거나 특별히 제공된 임의성 생성기를 제공합니다.” Wikipedia에 의해 정의 된대로.

파일에 바이트가 얼마나 무질서한 양의 측정으로서 파일과 관련하여 엔트로피의 의미를 쉽게 결론을 내릴 수 있습니다. NAT, Shannon 또는 Hartley와 같은 엔트로피를 정의하는 데 사용되는 다양한 장치가 있습니다. 글쎄, 가장 일반적인 단위는 Shannon입니다. Shannon의 알고리즘에 따라 파일의 엔트로피가 들어와야하는 값의 범위는 0 ~ 8입니다. 따라서 엔트로피 값이 0 일 때 결과가 확실하다고 말할 수 있습니다. 반대로 엔트로피 값이 8 인 경우 결과는 가장 예측할 수 없습니다. 사건의 결과에서 무작위성을 측정하기 위해 Shannon이 제공 한 공식은 다음과 같습니다.

          Entropy = ∑ pi log(1/pi)

어디 나 확률이있는 이벤트입니다 pi.

이 방정식은 항상 0에서 8 사이입니다.

자세한 내용은 링크를 확인하십시오. https://www.talentcookie.com/2016/02/file-entropy-in-malware-analysis/

Answer 9

엔트로피는 소프트웨어가 때때로 고객 요구 사항을 바탕으로 재 형성되는 정도를 말합니다. 따라서 고객 요청을 충족시키기 위해이를 재 형성하는 데 드는 비용이 최대가됩니다.

Answer 10

엔트로피는 바이러스 연구자들을위한 해시 코드와 같습니다. 엔트로피가 적습니다. 그것은 잠재적으로 바이러스 일 수있는 암호화되거나 압축 된 코드 일 가능성이 있음을 의미합니다.

표준 바이너리는 압축 또는 암호화 된 엔트로피보다 높은 엔트로피를 갖습니다.

Answer 11

엔트로피는 일반적으로 컴퓨터 과학에서 많은 의미가 있습니다. 상황에 따라 다릅니다. 보안 엔트로피에서 예를 들어 개인 키를 생성 할 때 많은 응용 프로그램이 엔트로피를 생성하기 위해 마우스를 이동하도록 요구하는 것과 같은 무작위성의 양을 의미합니다. 이것은 무작위성의 "인간"요소를 취하여 엔트로피를 생성하고 키를 생성하는 해싱 프로세스에 추가합니다.

이제 엔트로피의 소프트웨어 엔지니어링에 대한 방어가 있습니다. 이 정의는 날짜가 아닌 코드 또는 많은 개발자가 작성한 코드를 나타냅니다. 일반적으로 소프트웨어 프로젝트를 리팩터링하는 데 거의 시간이 지나면 사용됩니다. "이 프로젝트의 코드는 현재 프로젝트를 유지 한 많은 개인이 현재 프로젝트에 있지 않기 때문에 매우 적은 양의 엔트로피를 가지고 있습니다."

다음은 내가 기억 한 세 번째 예제입니다. 시뮬레이션 어닐링 주제 (컴퓨터 과학에 관한 한)에서 엔트로피는 알고리즘 평가 중에 얼마나 많은 부패가 발생했는지에 대해 설명합니다.

그래도 귀하의 질문에 답하기 위해 '엔트로피'라는 단어에 대한 구체적인 정의는 없습니다. 사전에서 찾을 수있는 것을 제외하고. 컴퓨터 과학이 그 용어를 적용하는 경향은 사용되는 용어의 맥락과 그것이 적용되는 것에 달려 있습니다.

Answer 12

엔트로피에서 큰 일을하기가 쉽습니다. 내 마음에 그것은 예쁘다 간단하고 유용한 개념.

기본적으로 평균적으로 동전을 뒤집거나 분기 지침을 취하거나 배열을 색인하는 등 이벤트에서 배울 수있는 것을 정량화합니다.

검색 알고리즘의 중간에 비교 작업과 마찬가지로 한 분기를 복용 할 수있는 특정 확률 P가 있고 다른 분기를 복용하면 1-p가 있습니다.

이진 검색에서 P가 1/2이라고 가정합니다. 그런 다음 해당 지점을 가져 가면 이전보다 1 비트를 알 수 있습니다. 로그 (2/1), Base 2는 1이기 때문에 1. 반면에, 다른 지점을 복용하면 1 비트를 배웁니다.

배울 수있는 평균 정보를 얻으려면 첫 번째 지점에서 배운 내용을 곱하십시오.

1/2 회 1 비트, 1/2 배 1 비트, 1/2 비트 플러스 1/2 비트 또는 총 1 비트의 엔트로피입니다. 그것이 당신이 그 결정에서 평균적으로 배울 수있는 것입니다.

반면에, 당신이 1024 항목의 표에서 선형 검색을하고 있다고 가정 해 봅시다.

첫 번째 == 테스트에서 예의 확률은 1/1024이므로 해당 결정에서 예의 엔트로피는 다음과 같습니다.

1/1024 times log(1024/1)

또는 1/1024 * 10 = 약 1/100 비트.

따라서 대답이 예라면 10 비트를 배우지 만 그 가능성은 천에서 약 1입니다.

반면에, 아무도 훨씬 더 가능성이 높습니다. 엔트로피입니다

1023/1024 * log(1024/1023)

또는 대략 1 배 대략 0 = 약 0입니다.

두 사람을 함께 추가하면 평균적으로 그 결정에 대해 약 1/100에 대해 배우게됩니다.

그렇기 때문에 선형 검색이 느려집니다. 각 결정에서 엔트로피 (배울 수있는 금액)는 테이블에서 항목을 찾기 위해 10 비트를 배워야하기 때문에 너무 작습니다.

Answer 13

컴퓨터 과학의 엔트로피는 일반적으로 비트의 무작위가 얼마나 무작위인지를 나타냅니다. 다음 질문은 정확하게 만드는 것입니다.

비트 스트링의 대략적인 엔트로피를 어떻게 계산합니까?

Answer 14

간단히 말해서 Langauge에서 상징의 확률을 알고 있다면 언어에서 상징의 평균 정보 내용을 계산할 수 있습니다.

또는

언어의 엔트로피는 언어에서 평균 기호의 정보 내용의 척도입니다.

공정한 동전을 고려하십시오.

확률이 1/2 인 두 가지 기호가 있으므로 엔트로피는 다음과 같이 계산됩니다.

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

Answer 15

나는 사람들이 엔트로피 WRT CS의 열역학적 정의를 오용한다고 들었습니다.

예를 들어 엔트로피 가이 시스템에서 확실히 증가하고 있습니다.

그들이 의미하는 바는이 코드가 악화되고 악화되고 있다는 것입니다!