Измерение информации, алфавитный подход
Учебная презентация по информатике
Автор: Звездина Вера Алексеевна, учитель информатики МБОУ «Образовательный центр №1», г.Ивантеевка Московской обл.
Введение.
Общие понятия
Основоположник теории информатики как науки
Клод Элвуд Шеннон
впервые использовал слово «bit» для обозначения наименьшей единицы количества информации в 1948 году , приписывая происхождение этого слова
Джону Тьюки .
Бит - наименьшая единица
измерения количества информации,
которое можно передать с помощью одного знака в двоичном коде – « 0 » или « 1 » ( bit = b inary digi t , двоичная цифра)
Идея выражения количества информации через длину двоичного кода этого сообщения принадлежит выдающемуся российскому математику
Андрею Николаевичу Колмогорову
(1903-1987)
При изучении данной темы активно пользуемся таблицами степеней двойки и соответствия единиц измерения количества информации .
При этом знание таблиц является необходимым условием для максимально быстрого и точного решения задач , без потери времени и математических ошибок.
Таблица степеней двойки ,
где 2 k - результат возведения числа 2 в степень k, при алфавитном подходе к измерению информации
показывает, сколько вариантов всевозможных «слов» Q = 2 k можно закодировать с помощью k бит на символ.
Соответствие единиц измерения
количества информации:
1 байт (bytе) = 8 бит ( 2 3 бит)
1 Кбит (Килобит) = 1024 бита ( 2 10 бит)
1 Кбайт (Килобайт) = 1024 байта
( 2 1 0 байт = 2 13 бит)
1 Мбайт (мегабайт) = 1024 Кбайт
( 2 1 0 Кбайт = 2 2 0 байт = 2 23 бит)
При решении задач следует обязательно привести единицы измерения количества информации
к одному виду .
При этом помним, что значение
k – это бит на символ, другого измерения здесь быть не может!
Информационный объем сообщения
I выражается формулой
I = N * k ,
где N - длина сообщения,
k - информационный вес
символа (количество бит,
необходимое для его
кодирования, бит на символ )
Вспомним, что:
Количество вариантов Q
всех возможных «слов»
(символьных цепочек без учета смысла) длиной k равно
Q = М k ( формула Хартли ),
где М – виды, типы, состояния символов.
Для двоичного кодирования (два вида символов – 0 и 1 ) получаем формулу:
М = 2 k
Здесь для обозначения М используются термины (виды, типы, состоянмя), наиболее часто встречаемые в задачах.
Таким образом, формулы подсчета объема сообщения и количества вариантов слов взаимодействуют
друг с другом через величину
k
(бит на символ)
Здесь для обозначения М используются термины, наиболее часто встречаемые в задачах.
Алфавитный подход
Алфавит – это набор символов, используемых в языке, на котором передается сообщение
Мощность алфавита – это количество символов в алфавите
Мощность русского алфавита равна 32
при Е = Ё и 33
Мощность
в обратном случае
английского
алфавита = 26
Для упрощения понимания и
легкости запоминания
различий в рассматриваемых
далее задачах, разобьем их
на 5 типов
и будем рассматривать решения соответственно этим типам .
Задача 1 типа
В велокроссе участвуют 119 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена.
Каков информационный объем в битах сообщения, записанного устройством, после того как промежуточный финиш прошли 70 велосипедистов?
Рекомендации к решению
Перед решением этой задачи следует проговорить ее условие, заменяя слова
в них синонимами, которые можно
найти по смыслу слова в формулах.
Читаем условие очень внимательно, находим хотя бы один синоним – и задача практически решена, остается только подставить формулы и получить ответ!
Решение
Есть 119 спортсменов с различными
номерами, то есть 119 вариантов
различных номеров, то Q = 119 .
Так как Q = М k , то для одного номера
получаем Q = 119 ≤ 128 = 2 7 ,
откуда k = 7 .
Тогда для N = 70 номеров получаем
информационный объем сообщения
I = N * k = 70 * 7 = 490 бит .
Будем в дальней шем называьть этот тип «велосипедистами»
Задача 2 типа
Объем сообщения,
содержащего 4096 символов,
равен 1/512 части Мбайта.
Какова мощность алфавита,
с помощью которого записано
это сообщение?
Этот тип задач будем называть «математическим»
Рекомендации к решению
Задачи данного типа – чисто математические, и здесь очень полезно использовать таблицу степеней двойки.
Подставляем числовые значения в формулы, заменяем числа степенями числа 2 и упрощаем. При этом не забываем привести единицы измерения к одному виду и помнить, что k – это бит на символ!
Решение
Воспользовавшись таблицей степеней двойки, имеем:
N = 4096 = 2 12 символов,
I =1/512 Мбайта = 2 23 / 2 9 = 2 14 бит,
то k = I/N = 2 14 /2 12 =2 2 =4 бита на символ .
Тогда мощность алфавита (количество различных вариантов символов в нем)
М=2 4 = 16 символов.
Задача 3 типа
В некоторой стране автомобильный номер длиной 7 символов составляется из заглавных букв (всего используется 26 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным целым количеством байт .
Определите объем памяти, необходимый для хранения 20 автомобильных номеров.
Будем так и называть этот тип задач – «автомобильные номера», хотя здесь встречаются и задачи на нахождение паролей (решение задач от этого не зависит).
Рекомендации к решению
Решая задачи данного типа, необходимо обратить внимание на слова «каждый символ» и «каждый номер» ,
которые подразумевают разделение информации при решении. Здесь следует сначала найти объем одного номера в битах, перевести его в байты (с округлением до целого числа в большую сторону!) и только потом искать общий объем на несколько номеров .
6 байт 2. Следовательн о , на 20 номеров требуется I 2 = 20 * 6 = 120 байт. " width="640"
Решение
1. Мощность используемого алфавита
Q = 26 + 10 = 36 ≤ 2 6 ,
откуда k=6 бит на символ.
Тогда объем одного номера равен
I 1 = 7*6=42 бита = 6 байт
2. Следовательн о , на 20 номеров
требуется
I 2 = 20 * 6 = 120 байт.
Рекомендации к решению
Для проверки правильности рассуждений пересчитаем объем без учета рекомендаций, данных ранее и сравним итоги. Мощность используемого алфавита и значение k=6 бит на символ остаются. Тогда объем одного номера
I 1 = 7*6=42 бита ,
а 20 номеров
I 2 = 42 * 20 = 840 бит или 105 байт.
В итоге потеряны 15 байт
информации, а это значит, что не все номера были бы закодированы.
Задача 4 типа
В школьной базе данны х хранятся записи , содержащие
информацию об учениках:
- – 16 символов: русские буквы (первая прописная, остальные строчные),
- – 12 символов: русские буквы (первая прописная, остальные строчные),
- – 16 символов: русские буквы (первая прописная, остальные строчные),
- – числа от 1992 до 2003.
Каждое поле записывается с использованием
минимально возможного количества бит.
Определите минимальное количество байт,
необходимое для кодирования одной записи, если
буквы е и ё считаются совпадающими.
Здесь поясняем, что в таблице ASCII ( так как таблица кодировки не указана, то берем ее по умолчанию) каждый символ занимает один байт памяти, и число (до определенного значения) – тоже один байт памяти. Этот тип задач будем называть «базами данных»
Рекомендации к решению
Базы данных (БД) состоят из записей, которые делятся на поля. И преимущество БД перед другим способом хранения информации в том , что поля в одной записи могут иметь разные форматы данных (числовые, символьные, даты и другие).
Здесь поясняем, что в таблице ASCII ( так как таблица кодировки не указана, то берем ее по умолчанию) каждый символ занимает один байт памяти, и число (до определенного значения) – тоже один байт памяти. Этот тип задач будем называть «базами данных»
Рекомендации к решению
При решении задач данного типа следует сначала
закодировать каждое из четырех поле отдельно минимально возможным количеством бит соответственно его формату,
а затем сложить результаты .
Здесь поясняем, что в таблице ASCII ( так как таблица кодировки не указана, то берем ее по умолчанию) каждый символ занимает один байт памяти, и число (до определенного значения) – тоже один байт памяти. Этот тип задач будем называть «базами данных»
Решение
По условию задачи, первые буквы имени, отчества и фамилии – всегда заглавные , то можно хранить их в виде строчных и делать заглавными только при выводе на экран.
Таким образом, для символьных полей достаточно использовать алфавит из 32 символов (русские строчные буквы, «е» и «ё» совпадают, пробелы не нужны).
Решение (продолжение)
Для кодирования каждого символа
32-символьного алфавита нужно 5 бит (32 = 2 5 ), то для хранения имени, отчества
и фамилии нужно
(16 + 12 + 16) * 5 = 220 бит.
Для года рождения есть 12 вариантов чисел , поэтому для него
нужно отвести 4 бита
( 12 ≤ 16 = 2 4 ).
Тогда для одной записи требуется
220 + 4 = 224 бита, или 28 байт.
Задача 5 типа (1)
В корзине лежат 32 клубка шерсти,
из них 4 красных.
Сколько бит информации несет сообщение о том, что достали
клубок красной шерсти?
Этот тип задач будем называть соответственно «задачи с разноцветными клубками»
Рекомендации к решению
Заметим, что условие этой задачи отличается от задачи 1 типа только тем, здесь требуется выбор мотка определенного цвета , т.е. вся
информация разделена на части .
Поэтому в решении задач 5 типа делается один дополнительный шаг –
определяется, какую часть от общего количества составляет
выделенная информация .
Решение
По условию , красные клубки составляют 1/8 часть от целого (от всех клубков) .
Поэтому сообщение о том, что первый вынутый клубок шерсти – красный, соответствует выбору одного из 8 вариантов , и это будет: Q = 8 = 2 3 , что дает нам k = 3 бит .
Решение (продолжение)
Можно решить данную задачу без
дробей и дополнительных объяснений:
в дополнительном по отношению к задачам 1 типа шаге находим
Q = 32/4 = 8 вариантов ,
а затем решаем,
как и задачи 1 типа:
Q = 8 = 2 3 , что дает нам k = 3 бит .
Задача 5 типа (2)
В зоопарке 32 обезьяны живут в двух вольерах, А и Б. Одна из обезьян заболела. Сообщение «Заболевшая обезьяна живет в вольере А» содержит
4 бита информации.
Сколько обезьян живут в вольере Б?
Так к описанию типа задач можно добавить «задачи про обезьян»
Решение
Почему эта задача относится к 5 типу?
Подумайте и ответьте сами.
Решается она в порядке, обратном решению предыдущей задачи.
Информация в 4 бита соответствует выбору одного из 16 вариантов , поэтому
в вольере А живет 1/16 часть всех обезьян: 32/16 = 2 обезьяны
Тогда в вольере Б живут все оставшиеся
32 – 2 = 30 обезьян.
Ждем ответа от учеников на вопрос: почему у задачи 5 тип? Потому что информация разделена на части – обезьяны здоровые и больные.
Задачи смешанных типов
Усвоив решение каждого типа задач отдельно, можно рассмотреть задачи смешанных типов.
Для их успешного решения необходимо прежде всего внимательно рассмотреть условие задачи, чтобы не пропустить это смешивание, а потом уже решать с учетом всех тонкостей, описанных ранее.
Разберем две из таких задач.
Задача 1
При регистрации в компьютерной системе каждому пользователю выдаётся идентификатор, состоящий из
8 символов, первый и последний из которых – одна из 18 букв, а остальные – цифры (допускается использование 10 десятичных цифр.
Каждый такой идентификатор в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование; все цифры кодируются одинаковым и минимально возможным количеством бит, все буквы также кодируются одинаковым и минимально возможным количеством бит).
Определите объём памяти в байтах, отводимый этой программой для записи 500 паролей.
Решение
Рассмотрим условие и разделим его на части, относящиеся к разным типам задач.
В первом абзаце говорится, что идентификатор состоит из букв и цифр в определенном порядке, а они кодируются по-разному .
Это подтверждается и во втором абзаце, где способ кодировки для цифр и букв описывается отдельно. Следовательно, каждый идентификатор рассматривается как запись из БД , то есть эта часть задачи относится к типу 4.
Ждем ответа от учеников: почему у задачи 5 тип?
Решение (продолжение)
Во втором абзаце условия так же сказано, что каждый идентификатор записывается минимально возможным и одинаковым
целым количеством байт ,
а посимвольное (т.е. для каждого символа отдельно) кодирование выполняется минимальным количеством бит, возможным для каждого вида символов. Следовательно, эта часть задачи относится к типу 3.
Ждем ответа от учеников: почему у задачи 5 тип?
Решение (продолжение)
Тогда решение будет следующим.
В идентификаторе есть шесть цифр из алфавита мощностью 10 символов,
тогда k 1 = 4 и I 1 = 6 * k 1 = 24 бита .
Вторая часть идентификатора длиной
2 символа состоит из алфавита мощностью 18 символов,
тогда k 2 = 5 и I 2 = 2 * k 2 = 10 бит .
Ждем ответа от учеников: почему у задачи 5 тип?
Решение (окончание)
Значит, объем одного идентификатора равен I 1 + I 2 = 24 + 10 = 34 бита .
Далее решаем задачу соответственно решению, описанному в 3 типе задач :
34 бита = 5 байт ,
Общий объем 500 идентификаторов равен I = 5 * 500 = 2500 байт .
Ждем ответа от учеников: почему у задачи 5 тип?
Задача 2
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 12-символьного набора. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит.
Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего отведено 12 байт на одного пользователя.
Определите объём памяти (в байтах), необходимый для хранения сведений о 50 пользователях. В ответе запишите только целое число – количество байт.
Будем так и называть этот тип задач – «автообильные номера»
Решение
В условии сказано, что сведения о пользователях хранятся в БД , где запись состоит из двух полей – собственно идентификатора и дополнительных сведений ( тип 4 ).
При этом идентификатор рассчитывается как в задачах 1 типа , а дополнительные сведения заданы конкретным значением и расчет их не нужен.
= 8 байт 2. Объем одной записи равен I 1+2 = 8 + 12 = 20 байт. 3. Следовательно, для 50 записей требуется I 50 = 20 * 50 = 1000 байт. " width="640"
Решение (продолжение)
1. Мощность используемого алфавита
Q = 12 ≤ 2 4 ,
откуда k = 4 бита на символ.
Тогда объем одного идентификатора
I 1 = 15 * 4 = 60 бит = 8 байт
2. Объем одной записи равен
I 1+2 = 8 + 12 = 20 байт.
3. Следовательно, для 50 записей требуется
I 50 = 20 * 50 = 1000 байт.
Контакты
Вопросы, замечания или рекомендации по презентации или по теме в целом принимаются на сайте звездина . рус через форму обратной связи, в группе сайта ВКонтакте или по электронной почте v_zvezdina@mail.ru