Презентация - Измерение информации, алфавитный подход. Учебная презентация по информатике

Измерение информации, алфавитный подход
Учебная презентация по информатике Автор: Звездина Вера Алексеевна, учитель информатики МБОУ «Образовательный центр №1», г.Ивантеевка Московской обл.

Введение. Общие понятия

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

Бит - наименьшая единица измерения количества информации, которое можно передать с помощью одного знака в двоичном коде – «0» или «1» (bit = binary digit, двоичная цифра)

Идея выражения количества информации через длину двоичного кода этого сообщения принадлежит выдающемуся российскому математику Андрею Николаевичу Колмогорову (1903-1987)

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

Таблица степеней двойки, где 2k - результат возведения числа 2 в степень k, при алфавитном подходе к измерению информации показывает, сколько вариантов всевозможных «слов» Q = 2k можно закодировать с помощью k бит на символ.

Соответствие единиц измерения количества информации: 1 байт (bytе) = 8 бит (23 бит) 1 Кбит (Килобит) = 1024 бита (210 бит) 1 Кбайт (Килобайт) = 1024 байта (210 байт = 213 бит) 1 Мбайт (мегабайт) = 1024 Кбайт (210 Кбайт = 220 байт =223 бит)

При решении задач следует обязательно привести единицы измерения количества информации к одному виду. При этом помним, что значение k – это бит на символ, другого измерения здесь быть не может!

Информационный объем сообщения I выражается формулой I = N * k, где N - длина сообщения, k - информационный вес символа (количество бит, необходимое для его кодирования, бит на символ)

Количество вариантов Q всех возможных «слов» (символьных цепочек без учета смысла) длиной k равно Q = М k (формула Хартли), где М – виды, типы, состояния символов. Для двоичного кодирования (два вида символов – 0 и 1) получаем формулу: М = 2k

Таким образом, формулы подсчета объема сообщения и количества вариантов слов взаимодействуют друг с другом через величину k (бит на символ)

Алфавитный подход

Алфавит – это набор символов, используемых в языке, на котором передается сообщение
Мощность алфавита – это количество символов в алфавите
Мощность русского алфавита равна 32 при Е = Ё и 33 в обратном случае
Мощность английского алфавита = 26

Для упрощения понимания и легкости запоминания различий в рассматриваемых далее задачах, разобьем их на 5 типов и будем рассматривать решения соответственно этим типам.

Задача 1 типа
В велокроссе участвуют 119 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объем в битах сообщения, записанного устройством, после того как промежуточный финиш прошли 70 велосипедистов?

Рекомендации к решению
Перед решением этой задачи следует проговорить ее условие, заменяя слова в них синонимами, которые можно найти по смыслу слова в формулах. Читаем условие очень внимательно, находим хотя бы один синоним – и задача практически решена, остается только подставить формулы и получить ответ!

Решение
Есть 119 спортсменов с различными номерами, то есть 119 вариантов различных номеров, то Q = 119. Так как Q = М k, то для одного номера получаем Q = 119 ≤ 128 = 27, откуда k = 7. Тогда для N = 70 номеров получаем информационный объем сообщения I = N * k = 70 * 7 = 490 бит.

Задача 2 типа
Объем сообщения, содержащего 4096 символов, равен 1/512 части Мбайта. Какова мощность алфавита, с помощью которого записано это сообщение?

Рекомендации к решению
Задачи данного типа – чисто математические, и здесь очень полезно использовать таблицу степеней двойки. Подставляем числовые значения в формулы, заменяем числа степенями числа 2 и упрощаем. При этом не забываем привести единицы измерения к одному виду и помнить, что k – это бит на символ!

Решение
Воспользовавшись таблицей степеней двойки, имеем: N = 4096 = 212 символов, I =1/512 Мбайта = 223/ 29 = 214 бит, то k = I/N = 214/212=22=4 бита на символ. Тогда мощность алфавита (количество различных вариантов символов в нем) М=24 = 16 символов.

Задача 3 типа
В некоторой стране автомобильный номер длиной 7 символов составляется из заглавных букв (всего используется 26 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным целым количеством байт. Определите объем памяти, необходимый для хранения 20 автомобильных номеров.

Рекомендации к решению
Решая задачи данного типа, необходимо обратить внимание на слова «каждый символ» и «каждый номер», которые подразумевают разделение информации при решении. Здесь следует сначала найти объем одного номера в битах, перевести его в байты (с округлением до целого числа в большую сторону!) и только потом искать общий объем на несколько номеров.

Решение
1. Мощность используемого алфавита Q = 26 + 10 = 36 ≤ 26, откуда k=6 бит на символ. Тогда объем одного номера равен I1 = 7*6=42 бита = > 6 байт 2. Следовательно, на 20 номеров требуется I2 = 20 * 6 = 120 байт.

Рекомендации к решению
Для проверки правильности рассуждений пересчитаем объем без учета рекомендаций, данных ранее и сравним итоги. Мощность используемого алфавита и значение k=6 бит на символ остаются. Тогда объем одного номера I1 = 7*6=42 бита , а 20 номеров I2 = 42 * 20 = 840 бит или 105 байт. В итоге потеряны 15 байт информации, а это значит, что не все номера были бы закодированы.

Задача 4 типа
В школьной базе данных хранятся записи, содержащие информацию об учениках:  <Фамилия> – 16 символов: русские буквы (первая прописная, остальные строчные), <Имя> – 12 символов: русские буквы (первая прописная, остальные строчные), <Отчество> – 16 символов: русские буквы (первая прописная, остальные строчные), <Год рождения> – числа от 1992 до 2003. Каждое поле записывается с использованием минимально возможного количества бит. Определите минимальное количество байт, необходимое для кодирования одной записи, если буквы е и ё считаются совпадающими.

Рекомендации к решению
Базы данных (БД) состоят из записей, которые делятся на поля. И преимущество БД перед другим способом хранения информации в том, что поля в одной записи могут иметь разные форматы данных (числовые, символьные, даты и другие).

Рекомендации к решению
При решении задач данного типа следует сначала закодировать каждое из четырех поле отдельно минимально возможным количеством бит соответственно его формату, а затем сложить результаты.

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

Решение (продолжение)
Для кодирования каждого символа 32-символьного алфавита нужно 5 бит (32 = 25), то для хранения имени, отчества и фамилии нужно (16 + 12 + 16) * 5 = 220 бит. Для года рождения есть 12 вариантов чисел, поэтому для него нужно отвести 4 бита ( 12 ≤ 16 = 24 ). Тогда для одной записи требуется 220 + 4 = 224 бита, или 28 байт.

Задача 5 типа (1)
В корзине лежат 32 клубка шерсти, из них 4 красных. Сколько бит информации несет сообщение о том, что достали клубок красной шерсти?

Рекомендации к решению
Заметим, что условие этой задачи отличается от задачи 1 типа только тем, здесь требуется выбор мотка определенного цвета, т.е. вся информация разделена на части. Поэтому в решении задач 5 типа делается один дополнительный шаг – определяется, какую часть от общего количества составляет выделенная информация.

Решение
По условию, красные клубки составляют 1/8 часть от целого (от всех клубков). Поэтому сообщение о том, что первый вынутый клубок шерсти – красный, соответствует выбору одного из 8 вариантов, и это будет: Q = 8 = 23 , что дает нам k = 3 бит.

Решение (продолжение)
Можно решить данную задачу без дробей и дополнительных объяснений: в дополнительном по отношению к задачам 1 типа шаге находим Q = 32/4 = 8 вариантов, а затем решаем, как и задачи 1 типа: Q = 8 = 23 , что дает нам k = 3 бит.

Задача 5 типа (2)
В зоопарке 32 обезьяны живут в двух вольерах, А и Б. Одна из обезьян заболела. Сообщение «Заболевшая обезьяна живет в вольере А» содержит 4 бита информации. Сколько обезьян живут в вольере Б?

Решение
Почему эта задача относится к 5 типу? Подумайте и ответьте сами. Решается она в порядке, обратном решению предыдущей задачи. Информация в 4 бита соответствует выбору одного из 16 вариантов, поэтому в вольере А живет 1/16 часть всех обезьян: 32/16 = 2 обезьяны Тогда в вольере Б живут все оставшиеся 32 – 2 = 30 обезьян.

Задачи смешанных типов
Усвоив решение каждого типа задач отдельно, можно рассмотреть задачи смешанных типов. Для их успешного решения необходимо прежде всего внимательно рассмотреть условие задачи, чтобы не пропустить это смешивание, а потом уже решать с учетом всех тонкостей, описанных ранее. Разберем две из таких задач.

Задача 1
При регистрации в компьютерной системе каждому пользователю выдаётся идентификатор, состоящий из 8 символов, первый и последний из которых – одна из 18 букв, а остальные – цифры (допускается использование 10 десятичных цифр. Каждый такой идентификатор в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование; все цифры кодируются одинаковым и минимально возможным количеством бит, все буквы также кодируются одинаковым и минимально возможным количеством бит). Определите объём памяти в байтах, отводимый этой программой для записи 500 паролей.

Решение
Рассмотрим условие и разделим его на части, относящиеся к разным типам задач. В первом абзаце говорится, что идентификатор состоит из букв и цифр в определенном порядке, а они кодируются по-разному. Это подтверждается и во втором абзаце, где способ кодировки для цифр и букв описывается отдельно. Следовательно, каждый идентификатор рассматривается как запись из БД, то есть эта часть задачи относится к типу 4.

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

Решение (продолжение)
Тогда решение будет следующим. В идентификаторе есть шесть цифр из алфавита мощностью 10 символов, тогда k1 = 4 и I1= 6 * k1 = 24 бита. Вторая часть идентификатора длиной 2 символа состоит из алфавита мощностью 18 символов, тогда k2 = 5 и I2 = 2 * k2 = 10 бит.

Решение (окончание)
Значит, объем одного идентификатора равен I1 + I2 = 24 + 10 = 34 бита. Далее решаем задачу соответственно решению, описанному в 3 типе задач: 34 бита = 5 байт, Общий объем 500 идентификаторов равен I = 5 * 500 = 2500 байт.

Задача 2
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 12-символьного набора. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего отведено 12 байт на одного пользователя. Определите объём памяти (в байтах), необходимый для хранения сведений о 50 пользователях. В ответе запишите только целое число – количество байт.

Решение
В условии сказано, что сведения о пользователях хранятся в БД, где запись состоит из двух полей – собственно идентификатора и дополнительных сведений (тип 4). При этом идентификатор рассчитывается как в задачах 1 типа, а дополнительные сведения заданы конкретным значением и расчет их не нужен.

Решение (продолжение)
1. Мощность используемого алфавита Q = 12 ≤ 24, откуда k = 4 бита на символ. Тогда объем одного идентификатора I1 = 15 * 4 = 60 бит >= 8 байт 2. Объем одной записи равен I1+2 = 8 + 12 = 20 байт. 3. Следовательно, для 50 записей требуется I50 = 20 * 50 = 1000 байт.

Контакты
Вопросы, замечания или рекомендации по презентации или по теме в целом принимаются на сайте звездина. рус через форму обратной связи, в группе сайта ВКонтакте или по электронной почте v_zvezdina@mail.ru