Измерение количества информации. Формула Хартли

Допустим, нам требуется что-либо найти или определить в той или иной системе. Есть такой способ поиска как «деление пополам». Например, кто-то загадывает число от 1 до 100, а другой должен отгадать его, получая лишь ответы «да» или «нет». Задается вопрос: число меньше? Ответ и «да» и «нет» сократит область поиска вдвое. Далее по той же схеме диапазон снова делится пополам. В конечном итоге, загаданное число будет найдено.

Посчитаем сколько вопросов надо задать, чтобы найти задуманное число. Допустим загаданное число 27. Начали:

Больше 50? Нет
Больше 25? Да
Больше 38? Нет
Меньше 32? Да
Меньше 29? Да
Больше 27? Нет
Это число 26? Нет

Ура! если число не 26 и не больше 27, то это явно 27.
Чтобы угадать методом «деления пополам» число от 1 до 100 нам потребовалось 7 вопросов.

Кто-то может задаться вопросом: а почему именно так надо задавать вопросы? Ведь, например, можно просто спрашивать: это число 1? Это число 2? И т.д. Но тогда вам потребуется намного больше вопросов (возможность того, что вы телепат, и угадаете с первого раза не рассматривается). «Деление пополам» самый короткий рациональный способ найти число.

Объем информации заложенный в ответ «да» или «нет» равен одному биту. Действительно, ведь бит может быть в состоянии 1 или 0. Итак, для угадывания числа от 1 до 100 нам потребовалось семь бит (семь ответов «да» - «нет»).

N = 2^k

Такой формулой можно представить, сколько вопросов (бит информации) потребуется, чтобы определить одно из возможных значений. N – это количество значений, а k – количество бит. Например, в нашем примере 100 меньше чем 27, однако больше, чем 26. Да, нам могло потребоваться и всего 6 вопросов, если бы загаданное число было бы 28.

Формула Хартли: k = log₂N. Количество информации (k), необходимой для определения конкретного элемента, есть логарифм по основанию 2 общего количества элементов (N).