Информация и ее кодирование
материал для подготовки к егэ (гиа) по информатике и икт (11 класс)

Слайд 1

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

Слайд 2

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

Слайд 3

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

Слайд 4

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

Слайд 6

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

Слайд 7

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

Слайд 8

Полный перебор

Слайд 9

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

Слайд 10

Примеры 00 100 111 01 101 00 ОБЛАКО 2

Слайд 11

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

Слайд 12

Способы решения задания 5 Аналитический (традиционный) фактически на шаге 2а добавляется бит чётности так, чтобы количество единиц в двоичной записи нового числа стало чётным на шаге 2б всегда дописывается 0, поскольку после шага 2а число единиц уже чётно если двоичная запись числа оканчивается на 0, то число чётно, поэтому имеет смысл искать число-результат R среди чётных чисел возьмём первое чётное число, большее, чем 77, и переведём его в двоичную систему: 78 = 1001110 2 ; видим , что все условия выполняются: в двоичной записи числа 78 чётное число единиц (четыре), поэтому оно могло быть получено в результате работы приведённого алгоритма во время работы алгоритма к двоичной записи приписали сзади две цифры, их нужно отбросить, получается 10011 2 = 19 Ответ: 19 . С помощью калькулятора переключаем Калькулятор в режим Программист (Вид – Программист или Alt+3); в десятичной системе (по умолчанию включен режим Dec ) набираем 78; под окошком вывода отображается двоичный код 78 (0…01001110); т.к. двоичный код содержит четное количество единиц (четыре), то R может равняться 78. чтобы получить ответ ( N ) надо от двоичного кода R=78 отбросить два правых разряда. Для этого можно использовать команду Калькулятора сдвиг вправо ( Right SHift ): нажать кнопку Rsh , затем кнопку «2» (сдвиг на два разряда) и кнопку «=»; в окошке вывода видим ответ в десятичном коде: 19 Ответ: 19.

Слайд 13

Способы решения задания 5 С помощью Excel Программный для перебора чётных чисел, больших 77, и останова, когда найдено число-результат, которое мог получить автомат, в основной программе использован цикл с условием функция OK( R ) должна вернуть Tru e , если в двоичной записи числа чётное количество единиц с помощью встроенной функции bin строится двоичная запись числа, срезом [2:] убираются символы "0 b " в начале. Затем подсчитывается число символов '1' с помощью метода count и проверяется полученное значение на чётность Формулы

Слайд 14

Примеры заданий 5 Вид задания: анализ правил алгоритма Рекомендуемый способ решения: аналитический Вид задания: поиск числа, подаваемого на вход алгоритма Рекомендуемый способ решения: с помощью Excel

Слайд 15

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

Слайд 16

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

Слайд 17

Способы решения задания 8 расстановка слов в алфавитном порядке равносильна расстановке по возрастанию чисел, записанных в четверичной системе счисления (основание системы счисления равно количеству используемых букв) выполним замену К  0, Л  1, Р  2, Т  3; поскольку нумерация слов начинается с единицы, а первое число КККК  0000 равно 0, под номером 67 будет стоять число 66, которое нужно перевести в четверичную систему: 66 = 1002 4 Выполнив обратную замену (цифр на буквы), получаем слово ЛККР Ответ: ЛККР

Слайд 18

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

Слайд 19

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

Слайд 20

Способы решения задания 12 Аналитический чтобы понять принцип работы алгоритма, сначала рассмотрим строку из 10 цифр 8 : 8888 888888 поскольку цепочки 2222 пока нет, сначала заменяем 8888 на 22 : 22 8888 88 цепочки 2222 снова нет, поэтому опять заменяем 8888 на 22 : 22 22 88 теперь появилась цепочка 2222 , которая согласно алгоритму заменяется на 88 : 8888 таким образом, в результате трёх замен цепочка восьмёрок укоротилась на 6 цифр посчитаем, сколько раз так можно сделать: 70 : 6 = 11,(6) – округляем вниз до 11 после 11 таких укорачиваний удалено 66 цифр 8, осталось всего 4, которые заменяются на 22 Ответ: 22 Программный

Слайд 21

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

Слайд 22

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

Слайд 23

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

Слайд 24

Способы решения задания 14 Аналитический приведём все числа к степеням семерки, учитывая, что 49 = 7 2 7 14 + 7 21 – 7 1 расставим степени в порядке убывания : 7 21 + 7 14 – 7 1 очевидно , что «шестёрки» в семеричной записи значения выражения возникнут только за счёт вычисления разности 7 14 – 7 1 , их количество равно 14-1=13 Ответ: 13 Программный программа, которая вычисляет нужное значение и методом деления в столбик определяет все цифры его записи в семеричной системе счисления

Слайд 25

Способы решения задания 14 С помощью Excel Укажите наименьшее основание системы счисления, в которой запись числа 50 двузначна. Формулы

Слайд 26

Формулы

Слайд 27

Использованные материалы http://www.fipi.ru - Федеральный институт педагогических измерений https://inf-oge.sdamgia.ru/ - тренировочные тесты https://neznaika.pro/oge/inf_oge/ - тренировочные тесты http://distan-school.ru/oge/?tap=3 - тренировочные тесты http://kpolyakov.spb.ru/school/oge.htm - тренировочные тесты, в том числе тренировочные тесты для компьютерного ЕГЭ http://kpolyakov.spb.ru – сайт учителя информатики К.Ю. Полякова