Я прошел несколько упражнений по теории информации и столкнулся с некоторой проблемой, которая, как мне кажется, не может привести к выводам, стоящим за ней. Самым интересным был тот факт, что энтропия была равна наименьшему числу битов. Я приведу два примера таких проблем:
Пример 1: Бинарное сравнение двух элементов a и b дает максимум один бит информации (если a меньше, чем b). Ложный результат означает, что либо a равно b, либо a больше b. Мы определяем массив с k = 5 различными символами, которые должны быть отсортированы по алфавиту. Сколько бинарных сравнений нужно хотя бы для сортировки массива?
Пример 2: Последовательность некоторых наблюдений должна быть эффективно сохранена. Каждое наблюдение состоит из одного из символов следующего набора: A, B, C, D. Все наблюдения имеют одинаковую вероятность появления в последовательности, и это не зависит от других наблюдений. Мы хотим определить двоичный код фиксированной длины для кодирования каждого наблюдения (таким образом, что оно может быть уникально декодировано). Найти, сколько битов на кодовое слово наиболее эффективно?
Я знаю ответы на эти проблемы, но меня это не интересует. Я хочу знать, как эти ответы достигаются. Я не могу установить связь между средним количеством информации и наименьшим количеством (эффективным числом) битов.