Информация и её кодирование, моделирование

1.

ИНФОРМАЦИЯ И ЕЕ КОДИРОВАНИЕ,
МОДЕЛИРОВАНИЕ

2.

СООТВЕТСТВИЕ ЗАДАНИЙ ЕГЭ-2021 И ЕГЭ-2020
ЕГЭ-2021
ЕГЭ-2020
Сложность
Время
Материал
1
2
3
4
5
6
7
8
9
10
3
2
4-1
5
6-1
8
9-1
10
– (К10)
–
Б
Б
Б
Б
Б
Б
Б
Б
Б
Б
3
3
3
2
4
4
5
4
6
6
Анализ информационных моделей (графов)
Таблицы истинности логических функций
Поиск и сортировка в базах данных
Кодирование и декодирование
Выполнение и анализ простых алгоритмов
Анализ программы с циклом
Кодирование растровых изображений
Кодирование данных, комбинаторика
Встроенные функции в электронных таблицах
Поиск слов в текстовом документе

3.

СООТВЕТСТВИЕ ЗАДАНИЙ ЕГЭ-2021 И ЕГЭ-2020
ЕГЭ-2021
ЕГЭ-2020
Сложность
Время
11
12
13
14
15
16
17
18
19
20
21
22
23
13
14
15
16
18
11 (К11)
К4
–
26
26
26
20
22
П
П
П
П
П
П
П
П
П
П
П
П
П
3
4
3
5
5
9
15
6
6
6
10
7
8
Материал
Вычисления информационного объёма
Выполнение алгоритмов для исполнителя
Поиск количества путей в графе
Позиционные системы счисления
Основные понятия математической логики.
Вычисление значений рекурсивной функции.
Проверка делимости
Динамическое программирование
Теория игр
Теория игр
Теория игр
Анализ программы с циклами и ветвлениями
Динамическое программирование

4.

РАССМАТРИВАЕМЫЕ ЗАДАНИЯ ОГЭ
ОГЭ-2021
Сложность
Время
1
2
3
4
5
Б
Б
Б
Б
Б
3
4
3
3
6
6
Б
4
Материал
Единицы измерения количества информации
Кодирование и декодирование информации
Логические значения, операции, выражения
Моделирование объектов и процессов
Алгоритм, свойства алгоритмов, способы записи
алгоритмов
7
Б
3
Сохранение информационных объектов из компьютерных
сетей и ссылок на них для индивидуального использования (в
том числе
из Интернета)
8
П
5
Поиск информации
9
10
П
Б
4
3
Проектирование и моделирование
Единицы измерения количества информации

5.

6.

ЗАДАНИЕ 1 (ЕГЭ) – 4 (ОГЭ)
Уровень: базовый
Время: 3 мин
Тема: Использование и анализ информационных
моделей (таблицы, диаграммы, графики)
Что проверяется:
Умение представлять и считывать данные в разных
типах информационных моделей (схемы, карты,
таблицы, графики и формулы)
Виды заданий:
- поиск оптимального пути по таблице
- поиск протяженности одного ребра по таблице
- анализ расписания
Основные способы решения:
- полный перебор
- переход к другой форме представления (от
таблицы к графу и наоборот)
- анализ графа и таблицы

7.

АНАЛИЗ ГРАФА И ТАБЛИЦЫ
1)
определим для каждой вершины её степень, то есть, количество
ребёр, в которыми она связана; в таблице степень вершины – это
количество заполненных клеток в строке (или в столбце)
2)
сопоставление степеней вершин в таблице и на рисунке позволяет
сразу обнаружить в таблице вершины А (она имеет № 3), Ж (№ 4) и
Б (№ 6)
3)
нас интересуют вершины Г и Ж; вершину Ж мы нашли, вершина Г
имеет степень 2 и связана, кроме вершины Ж, с вершиной Д
степени 3;
4)
степень 2 имеют вершины № 1 и 2, но только вершина № 1
связана, кроме Ж, с вершиной степени 3 (№ 7), поэтому вершина
№ 1 – это Г
5)
по таблице определяем протяжённость дороги из пункта Г в пункт
Ж, она равна 9
6)
Ответ: 9

8.

ПОЛНЫЙ ПЕРЕБОР

9.

ЗАДАНИЕ 4 (ЕГЭ) – 2 (ОГЭ)
Уровень: базовый
Время: 2 мин / 4 мин
Тема: Кодирование и декодирование информации
Что проверяется:
Умение кодировать и декодировать информацию
Виды заданий:
- определение неравномерного кода,
удовлетворяющего условию Фано (с наименьшим
числовым значением, наименьшая сумма длин всех
кодов, наименьшая сумма закодированного
сообщения)
- определение равномерного кода с
использованием расстояния Хемминга
- однозначное декодирование
- сокращение длины кодового слова
- проверка обратного условия Фано
- кодирование черно-белого растрового
изображения

10.

ПРИМЕРЫ
001001110110100
ОБЛАКО
2

11.

ЗАДАНИЕ 5 (ЕГЭ)
Уровень: базовый
Время: 4 мин
Тема: Выполнение и анализ простых алгоритмов.
Что проверяется:
Формальное исполнение алгоритма, записанного на
естественном языке, или умение создавать
линейный алгоритм для формального исполнителя
с ограниченным набором команд
Виды заданий:
- поиск числа, получаемого в результате работы
алгоритма
- поиск числа, подаваемого на вход алгоритма
- определение количества чисел, полученных в
результате работы алгоритма
- анализ правил алгоритма
Основные способы решения:
- аналитический (традиционный)
- с помощью калькулятора
- с помощью Excel
- программный

12.

СПОСОБЫ РЕШЕНИЯ ЗАДАНИЯ 5
Аналитический (традиционный)
С помощью калькулятора
1) фактически на шаге 2а добавляется бит
чётности так, чтобы количество единиц в
двоичной записи нового числа стало чётным
2) на шаге 2б всегда дописывается 0, поскольку
после шага 2а число единиц уже чётно
3) если двоичная запись числа оканчивается на
0, то число чётно, поэтому имеет смысл искать
число-результат R среди чётных чисел
4) возьмём первое чётное число, большее, чем
77, и переведём его в двоичную систему:
78 = 10011102 ;
5) видим, что все условия выполняются: в
двоичной записи числа 78 чётное число
единиц (четыре), поэтому оно могло быть
получено в результате работы приведённого
алгоритма
6) во время работы алгоритма к двоичной
записи приписали сзади две цифры, их нужно
отбросить, получается 100112 = 19
7) Ответ: 19.
1) переключаем Калькулятор в режим
Программист (Вид – Программист или Alt+3);
2) в десятичной системе (по умолчанию включен
режим Dec) набираем 78;
3) под окошком вывода отображается двоичный
код 78 (0…01001110);
4) т.к. двоичный код содержит четное количество
единиц (четыре), то R может равняться 78.
5) чтобы получить ответ (N) надо от двоичного кода
R=78 отбросить два правых разряда. Для этого
можно использовать команду Калькулятора
сдвиг вправо (Right SHift): нажать кнопку Rsh,
затем кнопку «2» (сдвиг на два разряда) и
кнопку «=»;
6) в окошке вывода видим ответ в десятичном
коде: 19
7) Ответ: 19.

13.

СПОСОБЫ РЕШЕНИЯ ЗАДАНИЯ 5
С помощью Excel
Программный
1) для перебора чётных чисел, больших 77, и
останова, когда найдено число-результат,
которое мог получить автомат, в основной
программе использован цикл с условием
2) функция OK(R) должна вернуть True, если в
двоичной записи числа чётное количество
единиц
Формулы
3) с помощью встроенной функции bin строится
двоичная запись числа, срезом [2:] убираются
символы "0b" в начале. Затем подсчитывается
число символов '1' с помощью метода count и
проверяется полученное значение на чётность

14.

ПРИМЕРЫ ЗАДАНИЙ 5
Вид задания: поиск числа,
подаваемого на вход
алгоритма
Рекомендуемый способ
решения: с помощью
Excel
Вид задания: анализ
правил алгоритма
Рекомендуемый способ
решения: аналитический

15.

ЗАДАНИЕ 8 (ЕГЭ)
Уровень: базовый
Время: 4 мин
Тема: Кодирование данных, комбинаторика,
системы счисления.
Что проверяется:
Знание о методах измерения количества
информации
Виды заданий:
- подсчет количества кодовых слов
- определение слова, записанного по номеру в
списке
Основные способы решения:
- аналитический (традиционный)
- программный

16.

СПОСОБЫ РЕШЕНИЯ ЗАДАНИЯ 8
Аналитический (традиционный)
1) буква К может стоять на одном из трёх
мест, остальные две буквы
выбираются из оставшихся четырёх:
Ш, О, Л или А
2) пусть К – первая буква, тогда
оставшиеся две буквы можно выбрать
42 = 16 способами
Программный
1) для построения множества всевозможных
слов можно использовать функцию
product из модуля itertools; затем
необходимо выбрать и пересчитать
подходящие слова
3) так как К может стоять на одной из
трёх позиций, общее количество
подходящих слов –
3 16 = 48
4) Ответ: 48
2) Ответ: 48

17.

СПОСОБЫ РЕШЕНИЯ ЗАДАНИЯ 8
1) расстановка слов в алфавитном порядке
равносильна расстановке по возрастанию
чисел, записанных в четверичной системе
счисления (основание системы счисления
равно количеству используемых букв)
2) выполним замену К 0, Л 1, Р 2, Т 3;
поскольку нумерация слов начинается с
единицы, а первое число КККК 0000
равно 0, под номером 67 будет стоять
число 66, которое нужно перевести в
четверичную систему: 66 = 10024
3) Выполнив обратную замену (цифр на
буквы), получаем слово ЛККР
4) Ответ: ЛККР

18.

ЗАДАНИЕ 11 (ЕГЭ) – 1 (ОГЭ)
Уровень: повышенный / базовый
Время: 3 мин
Тема: Вычисление информационного объема
сообщения
Что проверяется:
Умение подсчитывать информационный объём
сообщения
Виды заданий:
- определение объема памяти для хранения
сведений о N объектах
- определение объема памяти для хранения
части сведений об объекте
- определение мощности алфавита
- энтропия информации

19.

ЗАДАНИЕ 12 (ЕГЭ)
Уровень: повышенный
Время: 6 мин
Тема: Выполнение алгоритмов для исполнителя
Что проверяется:
Умение анализировать результат исполнения алгоритма
Виды заданий:
- поиск и замена символов в цикле, определение результата
- определение исходной строки символов
- определение местоположения на координатной плоскости
- определение местоположения робота в прямоугольном
лабиринте
Основные способы решения:
- аналитический
- программный
- с помощью Excel

20.

СПОСОБЫ РЕШЕНИЯ ЗАДАНИЯ 12
Аналитический
1)
2)
3)
4)
5)
6)
7)
8)
чтобы понять принцип работы алгоритма, сначала
рассмотрим строку из 10 цифр 8: 8888888888
поскольку цепочки 2222 пока нет, сначала заменяем
8888 на 22: 22888888
цепочки 2222 снова нет, поэтому опять заменяем
8888 на 22: 222288
теперь появилась цепочка 2222, которая согласно
алгоритму заменяется на 88: 8888
таким образом, в результате трёх замен цепочка
восьмёрок укоротилась на 6 цифр
посчитаем, сколько раз так можно сделать: 70 : 6 =
11,(6) – округляем вниз до 11
после 11 таких укорачиваний удалено 66 цифр 8,
осталось всего 4, которые заменяются на 22
Ответ: 22
Программный

21.

СПОСОБЫ РЕШЕНИЯ ЗАДАНИЯ 12
С помощью Excel
Использованы функции:
- ПОВТОР
- НАЙТИ
- ЕСЛИОШИБКА
- ЗАМЕНИТЬ

22.

ЗАДАНИЕ 13 (ЕГЭ) – 9 (ОГЭ)
Уровень: повышенный
Время: 3 мин / 4 мин
Тема: Графы. Поиск количества путей
Что проверяется:
Умение представлять и считывать данные в разных
типах информационных моделей (схемы,
карты, таблицы, графики и формулы)
Виды заданий:
- определение количества путей
- определение количества путей, проходящих через
пункт N
- определение количества путей, НЕ проходящих
через пункт N

23.

ЗАДАНИЕ 14 (ЕГЭ) – 10 (ОГЭ)
Уровень: повышенный / базовый
Время: 5 мин / 3 мин
Тема: Позиционные системы
счисления
Что проверяется:
Знание позиционных систем
счисления
Виды заданий:
- определение количества старших
цифр выражения с одним вычитанием
- определение количества старших
цифр выражения с несколькими
вычитаниями
- определение количества значащих
нулей
- решение уравнений с числами,
записанными в разных системах
счисления
- определение основания системы
счисления
число 10N-10M записывается как N-M девяток, за которыми стоят M нулей:
10 N 10 M 9
90
0
N M
M
число aN – aM записывается в системе счисления с основанием a как N-M
старших цифр этой системы счисления, за которыми стоят M нулей:
a N a M (a 1) (a 1)0 0 a
N M
M

24.

СПОСОБЫ РЕШЕНИЯ ЗАДАНИЯ 14
1)
2)
3)
4)
5)
Аналитический
приведём все числа к степеням
семерки, учитывая, что 49 = 72
714 + 721 – 71
расставим степени в порядке
убывания: 721 + 714 – 71
очевидно, что «шестёрки» в
семеричной записи значения
выражения возникнут только за
счёт вычисления разности 714 – 71,
их количество равно 14-1=13
Ответ: 13
Программный
1) программа, которая вычисляет
нужное значение и методом
деления в столбик определяет все
цифры его записи в семеричной
системе счисления

25.

СПОСОБЫ РЕШЕНИЯ ЗАДАНИЯ 14
С помощью Excel
Укажите наименьшее основание
системы счисления, в которой запись
числа 50 двузначна.
Формулы

26.

Формулы

27.

ИСПОЛЬЗОВАННЫЕ МАТЕРИАЛЫ
1. http://www.fipi.ru - Федеральный институт педагогических измерений
2. https://inf-oge.sdamgia.ru/ - тренировочные тесты
3. https://neznaika.pro/oge/inf_oge/ - тренировочные тесты
4. http://distan-school.ru/oge/?tap=3 - тренировочные тесты
5. http://kpolyakov.spb.ru/school/oge.htm - тренировочные тесты, в том числе
тренировочные тесты для компьютерного ЕГЭ
6. http://kpolyakov.spb.ru – сайт учителя информатики К.Ю. Полякова