Какое компьютерное определение энтропии? - PullRequest
62 голосов
/ 04 февраля 2009

Я недавно начал курс по сжатию данных в моем университете. Тем не менее, я нахожу использование термина «энтропия», поскольку оно относится к информатике, довольно неоднозначным. Насколько я могу судить, это примерно соответствует «случайности» системы или структуры.

Какое правильное определение компьютерных наук "энтропия"?

Ответы [ 15 ]

0 голосов
/ 05 июня 2010

Энтропия в информатике обычно относится к тому, насколько случайна цепочка битов. Следующий вопрос касается уточнения:

Как вычислить приблизительную энтропию битовой строки?

0 голосов
/ 21 марта 2009

С энтропией легко справиться. На мой взгляд, это довольно простая и полезная концепция .

По сути, это количественная оценка того, что в среднем вы узнаете из события, такого как подбрасывание монеты, выполнение инструкции ветвления или индексация массива.

Как операция сравнения в середине алгоритма поиска имеет определенную вероятность P взятия одной ветви и 1-P взятия другой.

Предположим, что P равно 1/2, как в бинарном поиске. Затем, если вы берете эту ветвь, вы знаете на 1 бит больше, чем раньше, потому что log (2/1), основание 2, равно 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 раз, примерно ноль = примерно ноль.

Сложите их вместе, и в среднем вы узнаете примерно 1/100 из этого решения.

Вот почему линейный поиск идет медленно. Энтропия (сколько вы можете ожидать усвоить) при каждом решении слишком мала, поскольку вам нужно будет выучить 10 битов, чтобы найти запись в таблице.

0 голосов
/ 07 февраля 2009

Энтропия имеет много значений, как правило, в области компьютерных наук. Это зависит от контекста. Термин «энтропия безопасности» означает, какую степень случайности вы помещаете, например, когда вы генерируете закрытый ключ, многие приложения просят вас переместить мышь для создания энтропии. Это генерирует энтропию, беря «человеческий» элемент случайности и добавляет его в процесс хеширования генерации ключа.

Теперь существует также определение для разработки программного обеспечения энтропии. Это определение представляет устаревший код или код, который написали многие разработчики. Обычно используется в отношении того, когда наступит время для реорганизации вашего программного проекта. «Код для этого проекта обладает огромным количеством энтропии, потому что многие из тех, кто поддерживал его, в настоящее время не участвуют в проекте».

Вот третий пример использования, который я тоже запомнил. В теме смоделированного отжига (в том, что касается информатики) энтропия описывается как количество распада, произошедшего во время оценки алгоритма.

Полагаю, что для ответа на ваш вопрос нет конкретного определения слова «энтропия», кроме тех, которые вы можете найти в словаре. То, как компьютерные науки склонны применять этот термин, зависит от контекста используемого термина и того, к чему он применяется.

0 голосов
/ 04 февраля 2009

Энтропия похожа на хэш-код и для исследователей вирусов. Меньше энтропии вы получите, это будет означать, что это скорее всего зашифрованный или сжатый код, который потенциально может быть вирусом.

Стандартный двоичный файл будет иметь более высокую энтропию, чем сжатый или зашифрованный.

0 голосов
/ 04 февраля 2009

Я слышал, что люди неправильно используют термодинамические определения энтропии w.r.t CS.

например. Энтропия определенно увеличивается в этой системе.

Когда они имеют в виду, что этот код становится все хуже и хуже!

...