На уроках информатики мы никогда ничего не зубрим! Ученики должны понимать все, о чем говорится на уроках, и запоминать новое путем повторений пройденного материала, сравнений и ассоциаций с уже знакомыми темами и понятной информацией.
Для максимально быстрого и однозначно верного решения задач мы придерживаемся принципа: чем меньше вычислений и другой работы мы делаем, тем меньше времени тратиться на решение задачи и тем меньшую вероятность появления ошибок получаем в результате. При этом, соглашаясь с Аристотелем, что «Ум заключается не только в знании, но и в умении прилагать знания на деле», я настаиваю на способах решений, соответствующих этому принципу, хотя существуют и другие варианты. На своих уроках я придерживаюсь изложения темы именно в этом ключе. Сначала это бывает сложно, особенно тем, кто приходит ко мне на уроки уже знакомым с иначе излагаемым материалом и не желает переучиваться. Но цель урока - научить решать быстро и без ошибок, экономя время и силы для новых задач. Поверьте, это несложно, нужно только поверить в свои силы - и все получится! При этом проверочные работы и тесты проводятся мной на время с расчетом решения задач именно по такому принципу.
В данной методике рассматривается алфавитный подходк измерению информации.
При изучении данной темы обращаем особое внимание на таблицы степеней двойки и соответствия единиц измерения количества информации, а так же их взаимосвязь, что послужит изложенному выше принципу решения задач.
При этом знание таблиц является необходимым условием для максимально быстрого и точного решения, без потери времени и математических ошибок.
Ниже приведена таблица степеней двойки, где k – это степень, а 2k - результат возведения числа 2 в степень k. При алфавитном подходе эта таблица показывает, сколько вариантов всевозможных «слов» Q= 2k можно закодировать с помощью k бит на символ.
| n | 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
2n |
1 |
2 |
4 |
8 |
16 |
32 |
64 |
128 |
256 |
512 |
1024 |
2048 |
4096 |
Бит - наименьшая единица измерения количества информации, может принимать только два значения – 0 или 1.
Байт содержит 8 бит (23 бит). При этом байт является неделимой единицей и всегда отображается целым числом.
Во второй таблице даны укрупненные единицы информации и их соответствие.
В России правила образования укрупненных единиц в информатике подтверждены постановлением № 879 Правительства РФ от 31 октября 2009г. Это постановление гласит:
«Наименование и обозначение единицы количества информации «байт» применяются с двоичными приставками «Кило», «Мега», «Гига», которые соответствуют множителям 210, 220 и 230 (1 Килобайт = 1024 байт, 1 Мегабайт = 1024 Килобайт,
1 Гигабайт = 1024 Мегабайт). Эти приставки пишутся с большой буквы».
Таким образом, каждая следующая единица измерения количества информации в 1024 = 210 раза больше предыдущей, на основании чего и строится таблица их соответствия:
| Наименование ед.изм. | В бит= |
В бит / байт |
Примечание |
1 Кбит (один Килобит) |
210 бит |
1 024 бит |
более 1 тыс.бит |
бит (один Мегабит) |
220 бит |
1 048 576 бит |
более 1 млн.бит |
1 Гбит (один Гигабит) |
230 бит |
более 109 бит |
более 1 млрд.бит |
1 Кбайт (один Килобайт) |
213 бит |
210 байт = 1024 байт |
более 1 тыс.байт |
1 Мбайт (один Мегабайт) |
223 бит |
220 байт = 1 048 576 байт |
более 1 млн.байт |
1 Гбайт (один Гигабайт) |
233 бит |
230 байт = 109 байт |
более 1 млрд.байт |
Таблицы не нужно учить наизусть! Рекомендуется пользоваться ими при решении задач, но при этом заглядывать в них все реже и реже, пытаясь сначала вспомнить значения, приведенные в них. Тогда эти таблицы сами «улягутся» в Вашей голове, и очень поможет Вам на экзамене в этой и в других темах!
Отцом-основателем теории информации, нашедшей применение в современных высокотехнологических системах связи, является американский инженер, криптоаналитик и математик Клод Шеннон. Именно он в 1948 году предложил использовать слово «бит» для обозначения наименьшей единицы измерения информации (в статье «Математическая теория связи»). Кроме того, понятие энтропии было важной особенностью теории Шеннона. Он продемонстрировал, что введённая им энтропия эквивалентна мере неопределённости информации в передаваемом сообщении, что и лежит в основе содержательного подхода к измерению информации, который в данной разработке нами не рассматривается. Статьи Шеннона «Математическая теория связи» и «Теория связи в секретных системах» считаются основополагающими для теории информации и криптографии.
В начале 60-х гг. русский советский математик, один из крупнейших математиков XX века Андрей Николаевич Колмогоров начал искать пути построения теории информации и теории вероятностей на принципиально новой, алгоритмической основе. В свое первой статье по алгоритмической теории информации «Три подхода к определению понятия «количество информации», вышедшей в первом выпуске первого тома журнала «Проблемы передачи информации», в 1965г, А.Н.Колмогоров указал способ измерения сложности конечного объекта (слова), для чего он ввел понятие, называемое сейчас «колмогоровской сложностью». Свое новое понятие он применил для построения алгоритмического варианта теории информации, позволяющего измерять информацию в конечной строке знаков.
Согласно Колмогорову, количество информации, содержащейся в тексте, определяется минимально возможной длиной двоичного кода, необходимого для представления этого текста.
Общей формулой, применяемой в двух различных подходах к измерению информации является формула Хартли - логарифмическая мера информации, которая определяет количество информации, содержащееся в сообщении (объем сообщения):
I = N *log2М
Здесь М - количество символов в используемом алфавите (мощность алфавита), N - длина сообщения (количество символов в сообщении), I - количество информации в сообщении в битах.
Формула была предложена Ральфом Хартли в 1928 году как один из научных подходов к оценке сообщений.
Для случая определения количества информации k в одном символе (бит на символ) алфавита мощности М, формула Хартли принимает вид:
k = log2М
Соответственно, мощность алфавита равна:
M= 2k
Из формулы Хартли следует, что алфавит, содержащий только 1 символ, не может быть использован для передачи информации, так как
log21 = 0.
Пусть, имеется алфавит, из Mбукв которого составляется сообщение.
Количество возможных вариантов Q всех возможных «слов» (символьных цепочек без учета смысла) длиной N равно
Q = Мk
где М — количество букв в алфавите, k - информационный вес символа (количество бит, необходимое для его кодирования, бит на символ).
Для простоты понимания и решения задач, за М мы будем принимать значения терминов, наиболее часто применяемых в условиях задач – виды, типы, состояния символов. Это упростит понимание и решение задач в алфавитном подходе.
Отметим, что формулы вычисления объема информации I = N * k и подсчета количества вариантов Q=Mk взаимодействуют друг с другом через величину k (бит на символ).
Алфавитный подход к измерению информации
Основные понятия и термины:
Алфавит – это набор символов, используемых в языке, на котором передается сообщение. При этом символом алфавита могут быть буквы, цифры и прочие символы, входящие в сообщение.
Мощность алфавита - это количество символов в алфавите.
Например, мощность русского алфавита равна 32 при Е =Ё и 33 – в противном случае. Мощность английского алфавита равно 26.0
Для упрощения понимания и легкости запоминания различий в рассматриваемых далее задачах, разобьем их на 5 типов и будем рассматривать решения соответственно этим типам.
Для быстрого и точного вычисления количества информации следует применять таблицу степеней двойки, которая показывает, сколько вариантов всевозможных «слов» Q можно закодировать с помощью k бит на символ.
Так же при решении задач следует обязательно привести единицы измерения количества информации к одному виду. При этом помним, что значение k – это бит на символ, другого измерения здесь быть не может!
Задача 1 типа.
В велокроссе участвуют 119 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена.
Каков информационный объем в битах сообщения, записанного устройством, после того как промежуточный финиш прошли 70 велосипедистов?
Рекомендации к решению.
Перед решением этой задачи следует проговорить ее условие, заменяя слова из него синонимами, которые можно найти в формулах.
Читаем условие очень внимательно, находим хотя бы один синоним – и задача практически решена, остается только подставить формулы и получить ответ!
Чтобы легче запомнить задачи 1 типа, будем называть их общим термином «велосипедисты».
Решение.
Есть 119 спортсменов с различными номерами, т.е. 119 вариантов различных номеров, тогда Q=119.
Так как Q = Мk, то для одного номера получаем Q = 119 ≤ 128=27, откуда k=7.
Тогда для N = 70 номеров получаем информационный объем сообщения
I = N * k = 70 * 7 = 490 бит.
Также для вычисления значения бита на символ можно использовать математическое решение формулы Хартли:
k= log2N
В данном случае k= log28 = 3.
Ответ: 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 символов.
Ответ: 16
Задача 3 типа.
В некоторой стране автомобильный номер длиной 7 символов составляется из заглавных букв (всего используется 26 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным целым количеством байт.
Определите объем памяти, необходимый для хранения 20 автомобильных номеров.
Рекомендации к решению.
Решая задачи данного типа, необходимо обратить внимание на слова «каждый символ» и «каждый номер», которыеподразумевают разделение информации при решении. Поэтому при решении задач 3 типа следует сначала считать объем одного номера в битах, перевести его в байты (с округлением до целого числа в большую сторону!) и только потом искать общий объем на несколько номеров.
Округление в большую сторону при вычислении объема одного номера необходимо, чтобы не потерять ни одного символа кодируемой информации.
Запомним, что округление при вычислении объемов информации всегда будем выполнять в большую сторону!
Будем так и называть этот тип задач – «автомобильные номера», хотя здесь встречаются и задачи на нахождение паролей (решение задач от этого не зависит).
Решение.
Особенность решения данной задачи – решение в два шага, т.е. поиск двух видов объема:
I1 - отдельно для каждого номера, I2 – для всех номеров.
Шаг 1. Мощность используемого алфавита Q = 26 + 10 = 36 ≤26, откуда k=6 бит на символ. Тогда I1 = 7*6=42 бита = > 6 байт на один номер.
Шаг 2.Следовательно, на 20 номеров требуется I2 = 20 * 6 = 120 байт.
Ответ: 120
Для проверки правильности рассуждений пересчитаем объем без учета рекомендаций, данных ранее, и сравним итоги.
Мощность используемого алфавита и значение k=6 бит на символ остаются. Тогда объем одного номера I1 = 7*6=42 бита, а 20 номеров I2 = 42 * 20 = 840 бит > = 105 байт.
В итоге потеряны 15 байт информации, а это значит, что не все номера были бы закодированы.
Задача 4 типа.
В школьной базе данных хранятся записи, содержащие информацию об учениках:
- <Фамилия> -16 символов: русские буквы (первая прописная, остальные строчные),
- <Имя> -12 символов: русские буквы (первая прописная, остальные строчные),
- <Отчество> - 16 символов: русские буквы (первая прописная, остальные строчные),
- <Год рождения> - числа от 1992 до 2003.
Каждое поле записывается с использованием минимально возможного количества бит. Определите минимальное количество байт, необходимое для кодирования одной записи, если буквы е и ё считаются совпадающими.
Рекомендации к решению.
Перед решением задач данного типа вспомним, что базы данных (далее – БД) состоят из записей, которые делятся на поля.
И преимущество БД перед другим способом хранения информации в том, что поля в одной записи могут иметь разные форматы данных(числовые, символьные, даты и др.), которые кодируются соответственно их форматам.
Поэтому для подсчета общего объема одной записи следует считать объем каждого поля отдельно, а затем сложить их.
При этом помним, что в таблице ASCII (так как таблица кодировки в условии задачи не указана, берем ее по умолчанию) каждый символ занимает один байт памяти. Число (до определенного значения) – тоже кодируется одним байтом памяти.
Запомним определение задач 4 типа как «базы данных».
Решение.
Определяем минимально возможные размеры в битах для каждого из полей (в данном случае – четырех) с учетом их типов отдельно.
Так как по условию задачи первые буквы имени, отчества и фамилии – всегда заглавные, то будем хранить их в виде строчных и делать заглавными только при выводе на экран.
Таким образом, для символьных полей достаточно использовать алфавит из 32 символов (русские строчные буквы, «е» и «ё» совпадают, пробелы не нужны).
Для кодирования каждого символа 32-символьного алфавита нужно 5 бит (32 = 25), то для хранения имени, отчества и фамилии нужно (16 + 12 + 16)•5=220 бит.
Для года рождения есть 12 вариантов чисел, поэтому для него нужно отвести 4 бита
(12 ≤ 16 = 24).
Таким образом, всего требуется 220+4 = 224 бита или 28 байт.
Ответ: 28
Задача 5 типа (1).
В зоопарке 32 обезьяны живут в двух вольерах, А и Б. Одна из обезьян заболела. Сообщение «Заболевшая обезьяна живет в вольере А» содержит 4 бита информации.
Сколько обезьян живут в вольере Б?
Рекомендации к решению.
Заметим, что условие этой задачи отличается от задачи 1 типа только тем, что там все номера считались как единая информация, а здесь требуется выбор мотка определенного цвета, т.е. вся информация разделена на части.
Поэтому в решении задач 5 типа делается один дополнительный шаг - определяется, какую часть от общего количества составляет выделенная информация.
Решение.
По условию, красные клубки составляют 1/8 часть от целого (от всех клубков).
Поэтому сообщение о том, что первый вынутый клубок шерсти – красный, соответствует выбору одного из 8 вариантов, и это будет: Q = 8 = 23, что дает нам k = 3 бит.
(Можно запомнить решение задач 5 типа без дробей и дополнительных объяснений: в дополнительном по отношению к задачам 1 типа шаге находим Q = 32/4 = 8 вариантов, а затем решаем, как и задачи 1 типа: Q = 8 = 23, что дает нам k = 3 бит).
Ответ: 3
Задача 5 типа (2).
В зоопарке 32 обезьяны живут в двух вольерах, А и Б. Одна из обезьян заболела. Сообщение «Заболевшая обезьяна живет в вольере А» содержит 4 бита информации.
Сколько обезьян живут в вольере Б?
Решение.
Почему эта задача относится к 5 типу? Потому что информация разделена на части – обезьяны здоровые и больные.
Решается она в порядке, обратном решению предыдущей задачи.
Итак, информация в 4 бита соответствует выбору одного из 16 вариантов, поэтому в вольере А живет 1/16 часть всех обезьян: 32/16 = 2 обезьяны
Тогда в вольере Б живут все оставшиеся 32 – 2 = 30 обезьян.
Описание задач 5 типа можно определить и запомнить как задачи «про шары и обезьян».
Ответ: 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 байт.
Ответ: 2500
Задача 2.
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 12-символьного набора. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит.
Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего отведено 12 байт на одного пользователя.
Определите объём памяти (в байтах), необходимый для хранения сведений о 50 пользователях. В ответе запишите только целое число – количество байт.
Решение.
В условии сказано, что сведения о пользователях хранятся в БД, где запись состоит из двух полей – собственно идентификатора и дополнительных сведений (тип 4).
При этом идентификатор рассчитывается как в задачах 1 типа, а дополнительные сведения заданы конкретным значением и расчет их не нужен.
Тогда решение будет следующим:
Мощность используемого алфавита Q = 12 ≤24, откуда k=4 бита на символ. Тогда I1 = 15*4 = 60 бит >= 8 байт на один идентификатор.
Объем одной записи равен I1+2 = 8 + 12 = 20 байт.
Следовательно, для 50 записей требуется I50 = 20 * 50 = 1000 байт.
Ответ: 1000