Print
Category: Теоретическая информатика
Hits: 8060

Коль из города выйдут британцы сегодня
По суше иль морем, он другу сказал,
Повесишь фонарь на верху колокольни
Северной церкви, как особый сигнал,.

Один, если сушей, и два, если морем.

С этого стихотворения Генри Уодсворт Лонгфелло, я начинаю со своими учениками тему «Кодирование информации». Оно взято из замечательной книги Ч. Петцольд «Код. Тайный язык информатики»/ В стихотворении говорится о передаче информации в закодированном виде.

Если у системы есть только два состояния, например, готов к уроку/не готов, пришел вовремя/опоздал, болен/здоров и т.п. достаточно одного «фонаря». Нам достаточно договориться о том что означает сигнал «свет есть» и «света нет».  

В случае если количество вариантов больше двух, как, например, в стихотворении:

одного фонаря не хватит, нужно как минимум два. Для того, чтобы не рисовать фонари (на уроке я их рисую) дальше горящий фонарь будем обозначать 1, а не горящий – 0.

Проанализируем закономерность сколько состояний системы можно закодировать, используя N фонарей:

кол-во фонарей кол-во комбинаций
1 2 (0,1)
2 4 (00, 01, 10, 11)
3 8 (000, 001, 010, 011, 100, 101, 110, 111)

Как правило, при перечислении всех возможных вариантов для трех фонарей ученики не строят последовательно все возможные комбинации, так как связи между «кодированием» и двоичной системой счисления они пока не видят. Мы подробно рисуем все возможные варианты, пытаемся понять, можно ли нарисовать еще какую-нибудь последовательность и находим простое доказательство утверждения:

«При увеличении количества фонарей на один, количество вариантов возрастает в два раза».

Из этого утверждения следует основной закон:

А = 2n

Где А – количество вариантов, n – количество фонарей. Отсюда до битов – рукой подать.

Этот принцип кодирования:

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

Примеры:

Задача: В классе 25 человек, сколько фонарей (бит) необходимо для кодирования каждого ученика?
Решение: 4 бит не хватит, 24=16, а вот пяти бит – вполне. Пять бит могут вместить 32 различные комбинации.

Задача: сколько бит необходимо для кодирования одного символа текста?
Решение: Подсчитаем сколько символов мы используем при письме:

33 русских строчных,
33 русских прописных
26 латинских строчных
26 латинских прописных
10 цифр
~ 20 знаков препинания

Итого: 148 символа. 7 бит не хватит, 27=128, а вот восемь бит – хватит. восемь бит могут вместить 256 различных комбинаций.

Задача: Сколько цветов может содержать картинка 10х10 пикселей, размером 50 байт.
Решение: 50 байт = 400 бит. На один пиксель приходится 4 бита, следовательно палитра такого изображения может состоять не более чем из 24=16 цветов.

Задача: Сколько минут длится мелодия, чей файл размером в 10 560 000 байт имеет следующие параметры: частота дискретизации 44 КГц, глубина звука 16 бит (используется на CD), стерео.

Решение: размер файла = время * частота дескретизации * глубина звука * количество каналов
10 560 000(байт) = t(секунды) * 44000(Гц) * 2(байт) * 2(стерео)
t = 60 секунд

и т.д, и т.п.