Теоретические основы решения задачи №13
Тема: "Методика обучения учащихся решению
задачи №13 ЕГЭ по информатике"
Выполнила: Дорина Татьяна Геннадьевна
учитель информатики и ИКТ
МБОУ СОШ №7 г.о. Лобня Московской обл.
Цель:Обучение учащихся решению задачи №13 ЕГЭ по информатике.
Задачи разработки:
1. Обобщение теоретического материала по теме "Кодирование информации".
2. Разбор методики решения типовых заданий.
3. Подбор заданий для самостоятельного решения.
Теоретические основы решения задачи №13
Уровень задания: повышенный.
Время выполнения: 3 мин.
Максимальное количество баллов: 1.
Проверяемые элементы содержания:
Алфавит - конечное множество символов. Текст — произвольная последовательность символов данного алфавита. Двоичные тексты. Единицы измерения длины двоичных текстов (бит, байт, производные единицы). Шестнадцатеричное представление двоичных текстов.
Проверяемые умения:
умение осуществлять кодирование и декодирование информации.
Для успешного выполнения данного задания в рамках непрерывного курса информатики у учащихся должны быть сформированы следующие теоретические знания:
1. Мощность алфавита N– это количество символов в этом алфавите.
2. С помощью i бит можно закодировать 
различных вариантов.
3. Знание таблицы степеней двойки, которая показывает сколько вариантов N можно закодировать с помощью i бит:
| i | ||||||||||
| N |
4. Знание единиц измерения количества информации:
Минимальной единицей измерения количества информации является бит, а следующей по величине единицей является байт, причем 1 байт = 23 бит = 8 бит.
Компьютер оперирует числами не в десятичной, а в двоичной системе счисления, поэтому в кратных единицах измерения количества информации используется коэффициент 2n. Так, кратные байту единицы измерения количества информации вводятся следующим образом:
1 Кбайт = 210 байт = 1024 байт;
1 Мбайт = 210 Кбайт = 1024 Кбайт;
1 Гбайт = 210 Мбайт = 1024 Мбайт.
5. Алфавитный подход к измерению количества информации.
При алфавитном подходе к определению количества информации отвлекаются от содержания информации и рассматривают информационное сообщение как последовательность знаков определенной знаковой системы.
Чтобы найти информационный объем сообщения (текста) I, нужно умножить количество символов L на число бит на символ i: 
.
Рассмотрим решение трех типовых задач.
Пример 1
Для регистрации на сайте некоторой страны пользователю требуется придумать пароль. Длина пароля - ровно 10 символов. В качестве символов используются десятичные цифры и 10 различных букв местного алфавита, причем все буквы используются в двух начертаниях: как строчные, так и прописные (регистр буквы имеет значение!).
Под хранением каждого такого пароля на компьютере отводится минимально возможное и одинаковое целое количество байтов, при этом используется посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов.
Определите объем памяти (в байтах), который занимает хранение 25 паролей. В ответе укажите только число.
Решение:
 |
1 шаг: представление обобщенного алгоритма решения задачи (рис.1).
рис.1
2 шаг: определение входных и выходных данных, введение условных обозначений.
| Входные данные | Промежуточные данные | Выходные данные | |||
| L | K | N | i | I1 | I |
| Длина пароля | Количество паролей | Мощность алфавита | Количество битов для хранения одного символа | Количество информации для хранения одного пароля | Количество информации для хранения всех паролей (в байтах) |
| 10+10*2 | ? |
3 шаг: выполнение алгоритма, поиск ответа.
Данная задача решается с использованием алфавитного подхода к измерению количества информации.
1. Определим мощность используемого алфавита.
N=10(десятичные цифры)+10*2(буквы местного алфавита строчные и прописные)=30 символов.
2. Определим количество битов, используемое для хранения одного символа.
По формуле находим:
N=30 , а 30 не является степенью числа 2.
Т.к. речь идет о целом количестве битов, минимально достаточном для представления одного знака данного алфавита, выбираем ближайшее большее N число, являющееся степенью числа 2.
Получаем 
, следовательно i=6 бит.
3. Определим информационный вес одного пароля.
Согласно формуле 
, находим, что 
бит.
переведем биты в байты: 60/8=7,5 байтов = 8 байтов (округляем результат до целого в большую сторону).
4. Определим количество информации для хранения 25 паролей.
байтов.
Ответ: 200 байтов.
Пример 2.
При регистрации в компьютерной системе каждому пользователю выдается пароль, состоящий из 15 символов и содержащий только символы из 8 символьного набора, A,B,C,D,E,F,G,H. В базе данных для хранения сведений о любых пользователях отводится одинаковое минимально возможное целое число байт.
При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым минимально возможным количеством бит. Кроме пароля для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт, одно и то же для всех пользователей. Для хранения сведений о 20 пользователях потребовалось 320 байт.
Сколько байт выделено для хранения дополнительных сведений об одном пользователе?
Решение:
1 шаг: представление обобщенного алгоритма решения задачи (рис. 2).
рис. 2
2 шаг: определение входных и выходных данных, введение условных обозначений.
| Входные данные | Промежуточные данные | Выходные данные | |||||
| N | K | L | I | i | I1 | Iп1 | Iд1 |
| Мощность алфавита | Количество символов в пароле | Количество пользователей | Количество информации в сведениях о 20 пользователях | Количество битов для хранения одного символа | Количество информации для хранения сведений об одном пользователе | Количество информации для хранения одного пароля | Количество информации для хранения доп. сведений об одном пользователе |
| 400 байт | ? |
3 шаг: выполнение алгоритма, поиск ответа.
1. Определим количество информации, используемое для хранения данных об одном пользователе.
байт.
2. Для определения количества информации, используемого для хранения пароля одного пользователя воспользуемся формулой:
.
3. Определим количество битов, используемых для хранения одного символа алфавита.
бит.
4. Теперь определим количество байтов используемое для хранения пароля одного пользователя.
.
5. Тогда количество информации для хранения дополнительных сведений об одном пользователе находим как разность общего количества информации об одном пользователе и количества информации, используемого для хранения пароля одного пользователя.
байт.
Ответ: 10 байтов.
Пример 3
В некоторой стране автомобильный номер длиной 6 символов составляется из заглавных букв (всего используется 26 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным целым количеством байт. Определите объем памяти в байтах, необходимый для хранения 20 автомобильных номеров.
Решение:
1 шаг: представление обобщенного алгоритма решения задачи (рис. 3).
рис. 3
2 шаг: определение входных и выходных данных, введение условных обозначений.
| Входные данные | Промежуточные данные | Выходные данные | |||
| L | N | K | i | I1 | I |
| Длина автомобильного номера | Мощность алфавита | Количество автомобильных номеров | Количество битов для хранения одного символа | Объем памяти для хранения одного номера | Объем памяти для хранения всех номеров (в байтах) |
| 26+10 | ? |
3 шаг: выполнение алгоритма, поиск ответа.
1. Определим мощность используемого алфавита.
N=10(десятичные цифры)+26(заглавные буквы местного алфавита)=36 символов.
2. Определим количество битов, используемое для хранения одного символа.
По формуле находим:
N=36 , а 36 не является степенью числа 2.
Т.к. речь идет о целом количестве битов, минимально достаточном для представления одного знака данного алфавита, выбираем ближайшее большее N число, являющееся степенью числа 2.
Получаем i=6 бит.
3. Определим объем памяти, необходимый для хранения одного автомобильного номера.
Согласно формуле находим, что 
бит.
переведем биты в байты: 36/8=4,5 байта=5 байтов (округляем результат до целого в большую сторону).
4. Определим объем памяти для хранения 20 автомобильных номеров.
байтов.
Ответ: 100 байтов.
Задачи для тренировки
1. При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 12-символьного набора: А, В, C, D, Е, F, G, H, K, L, M, N. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей.
Для хранения сведений о 20 пользователях потребовалось 400 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число – количество байт.
2. При регистрации в компьютерной системе каждому пользователю выдается пароль, состоящий из 25 символов и содержащий только 9 символов - Q, W, E, R, T, Y, U, I, O, P (это заглавные символы верхнего ряда латинской раскладки клавиатуры:). Каждый такой пароль в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт. При этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит.
Определите объём памяти (в байтах), отводимый этой программой для записи 100 паролей. В ответе запишите только число.
3. При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы Ш, К, О, Л, А (таким образом, используется 5 различных символов). Каждый такой пароль в компьютерной системе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит). Укажите объём памяти в байтах, отводимый этой системой для записи 30 паролей. В ответе запишите только число, слово «байт» писать не нужно.
4. В велокроссе участвуют 359 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Какой объём памяти будет использован устройством, когда промежуточный финиш прошли 168 велосипедистов?
5. В велокроссе участвуют 678 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объем в байтах сообщения, записанного устройством, после того как промежуточный финиш прошли 200 велосипедистов?
6. В некоторой стране автомобильный номер длиной 5 символов составляют из заглавных букв (задействовано 30 различных букв) и любых десятичных цифр в любом порядке. Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит). Определите объём памяти, отводимый этой программой для записи 50 номеров.
7. В некоторой стране автомобильный номер длиной 6 символов составляется из заглавных букв (всего используется 19 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным целым количеством байт. Определите объем памяти в байтах, необходимый для хранения 40 автомобильных номеров.
8. В некоторой стране автомобильный номер длиной 7 символов составляется из заглавных букв (всего используется 18 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным целым количеством байт. Определите объем памяти в байтах, необходимый для хранения 60 автомобильных номеров.
Список источников:
1. Богомолова О.Б. Информатика: Новый полный справочник для подготовки к ЕГЭ.-Москва: АСТ: Астрель, 2016.
2. Демонстрационные варианты ЕГЭ по информатике 2012-2016 гг.
3. Крылов С.С., Чуркина Т.Е. ЕГЭ. Информатика и ИКТ: типовые экзаменационные варианты: 10 вариантов.- М.: Издательство "Национальное образование", 2016.
4. Описание проекта экзаменационной модели для проведения Единого государственного экзамена по информатике в соответствии с требованиями ФГОС среднего общего образования.