ЕГЭ по информатике [попытка обзора] ЕГЭ по информатике 4 часа без компьютера [попытка обзора] М.А. Ройтберг mroytberg@lpm.org.ru, ege-go.ru 8 ноября 2014. - презентация

1 ЕГЭ по информатике [попытка обзора] ЕГЭ по информатике 4 часа без компьютера [попытка обзора] М.А. Ройтберг ege-go.ru 8 ноября 2014 МИОО

2 ПРИНЦИПЫ Минимизировать риск случайных ошибок Дать преимущество тем, кто «в теме»: задача имеет «лобовое» решение, но имеет и красивое, менее трудоемкое Анти-натаскивание: - вариативность заданий относительно демо-версии; - лучшая подготовка – знать курс информатики Наличие заданий разной сложности (в том числе – простых)

3 «Зачет»: 8 баллов Формат и количество заданий «Зачет»: 8 баллов Выбор ответа (А) 3 13 Краткий ответ (B) Развернутый ответ (С) 4 4 Всего 27 32

4 «Зачет»: 8 баллов Уровень сложности «Зачет»: 8 баллов Базовый Повышенный 11 (6) 15 Высокий 4 4 Всего 27 32

5 Темы заданий Математические основы информатики Алгоритмы Технологии Всего 27 32

6 Уменьшение количества заданий B2 (2014)B5 (2014) a := 30; b := 14; a := a – 2 * b; if a > b then c := b + 2 * a else c := b - 2 * a; var n, s: integer; begin n := 0; s := 0; while s

7 Двойные позиции в КИМ 2014 XY 3А4А6 6А5В1 7А7В3 9А8В10

8 Задание 6-X (A5) Автомат получает на вход четырехзначное число. По этому числу строится новое число по следующим правилам. 1. Складываются первая и вторая, а также третья и четвертая цифры исходного числа. 2. Полученные два числа записываются друг за другом в порядке убывания (без разделителей). Пример. Исходное число: Суммы: 3+1 = 4; 6+5 = 11. Результат: 114. Укажите наименьшее число, в результате обработки которого, автомат выдаст число

9 Задание 6-Y (B1) У исполнителя Удвоитель две команды, которым присвоены номера: 1. прибавь 1, 2. умножь на 2. Первая из них увеличивает число на экране на 1, вторая удваивает его. Запишите порядок команд в программе преобразования числа 3 в число 63, содержащей не более 8 команд, указывая лишь номера команд. Если таких программ более одной, то запишите любую из них 9

10 Задание 9-X (A8) Производилась двухканальная (стерео) звукозапись с частотой дискретизации 64 к Гц и 24-битным разрешением. В результате был получен файл размером 120 Мбайт, сжатие данных не производилось. Определите приблизительно, сколько времени (в минутах) проводилась запись? В качестве ответа укажите ближайшее к времени записи целое число кратное 5 10

11 Задание 9-Y (B10) Документ объёмом 40 Мбайт можно передать с одного компьютера на другой двумя способами: А. Сжать архиватором, передать архив по каналу связи, распаковать. Б. Передать по каналу связи без использования архиватора. Какой способ быстрее и насколько, если: средняя скорость передачи данных по каналу связи составляет 2 23 бит в секунду; объём сжатого архиватором документа равен 90% исходного; время, требуемое на сжатие документа, – 16 секунд, на распаковку – 2 секунды? В ответе напишите букву А или Б (способ передачи), после буквы напишите число обозначающее, на сколько секунд один способ быстрее другого. 11

12 Темы и уровни сложности Высо- кий Повы- шенный Базо- вый Всего Математичес- кие основы информатики Алгоритмы Технологии 0145 Всего 41112

13 Математические основы информатики Комбинаторика Кодирование (в том числе - биты, байты) Системы счисления Графы, деревья, списки Логика

14 Математические основы в КИМ Уровень сложности Тип Тема 10БАКомбинаторика 11БВКодирование - неравномерные коды 13ПВ Кодирование - равномерные коды, биты, байты 4БВСистемы счисления – двоичная 16ПВСистемы счислкения - общего вида 5БВГрафы - матрица смежности. 15ПВГрафы - подсчет числа путей 2БАЛогика - таблицы истинности 18ПВЛогика – преобр. лог. выражений 23ВВЛогика - системы уравнений 25ВССтратегии

15 Комбинаторика 15 Формулы перемножения и сложения количества вариантов. Количество текстов данной длины в данном алфавите. Перестановки, размещения и сочетания. Количество пар: P = N 1 *N 2 Количество троек: T = N 1 *N 2 *N 3 Количество слов длины k в алфавите из N букв: W(N, k) = N*…*N = N k k раз

16 Комбинаторика 16 Все 4-буквенные слова, составленные из букв К, Л, Р, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка: 1. КККК 2. КККЛ 3. КККР 4. КККТ …… Запишите слово, которое стоит под номером 67

17 Кодирование – 1 (двоичные тексты, биты, байты равномерные коды Алфавит - конечное множество символов. Текст произвольная последовательность символов данного алфавита. Двоичные тексты. Единицы измерения длины двоичных текстов (бит, байт, производные единицы). Шестнадцатеричное представление двоичных текстов. Битовые операции с двоичными текстами Посимвольное кодирование текста. Кодовое слово. Кодовая таблица. Декодирование. Посимвольное равномерное двоичное кодирование текста. 7-битная кодовая таблица ASCII; 8- битные кодовые таблицы для кодирования текстов, включающих символы латиницы и кириллицы. Стандарт Unicode. 17

18 Кодирование - 1 ПРИМЕР При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы Ш, К, О, Л, А (таким образом, используется 5 различных символов). Каждый такой пароль в компьютерной системе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит). Укажите объём памяти в байтах, отводимый этой системой для записи 30 паролей. 18

19 Кодирование - 2 Неравномерное кодирование. Возможность однозначного декодирования. Префиксные коды. Условие Фано. Код, обеспечивающий по возможности меньшую среднюю длину сообщения при известной частоте символов. Коды, исправляющие ошибки. 19

20 Кодирование - 2 Неравномерное кодирование. Возможность однозначного декодирования. Префиксные коды. Условие Фано. ПРИМЕР Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 0; Б – 100; В – 1010; Г – 111; Д – 110. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать? 1) для буквы В – 101 3) для буквы В – 010 2) это невозможно 4) для буквы Б – 10 20

21 А – 0; Б – 100; В – 1010; Г – 111; Д –

22 Системы счисления -1 (основание 2, 8, 16) Запись натуральных чисел в 2-чной системе. Запись натуральных чисел в 8-чной и 16-чной системе. Сложение и вычитание натуральных чисел, записанных в двоичной системе счисления. Перевод чисел из двоичной системы в системы счисления с основанием 8 и 16 и обратно. Задание целых чисел с помощью дополнительного двоичного кода. ПРИМЕР. Сколько единиц в двоичной записи десятичного числа 519? 22

23 Системы счисления -2 (позиционные системы счисления общего вида) Запись натуральных чисел в позиционной системе с заданным основанием. Сложение и вычитание натуральных чисел, записанных в позиционной системе счисления. Свойства позиционной записи (примеры: количество цифр в записи числа, ноль в конце записи). ПРИМЕР 1 (демо). Сколько единиц содержится в двоичной записи значения выражения: – 8 ПРИМЕР 2 Десятичное число 57 в некоторой системе счисления записывается как 212. Определите основание системы счисления 23

24 Дискретные объекты (списки, деревья, графы) Список. Первый элемент, последний элемент. Предыдущий элемент, следующий элемент. Замена, вставка и удаление элемента. Дерево. Вершина, корень, лист, Поддерево. Предыдущая вершина. Следующие вершины. Бинарное дерево. Высота дерева. Частичный порядок на множестве вершин. Генеалогическое дерево. Префиксное дерево. Граф. Вершина, ребро, путь. Ориентированные и неориентированные графы. Начальная вершина (источник) и конечная вершина (сток) в ориентированном графе. Веса ребер. Вес пути. Понятие минимального пути. Матрица смежности (с весами ребер). Расстояние между вершинами. Диаметр графа 24

25 Дискретные объекты (списки, деревья, графы) Граф. … Веса ребер. Вес пути. Понятие минимального пути. Матрица смежности (с весами ребер). ПРИМЕР 1 25

26 Дискретные объекты (списки, деревья, графы) Граф. … Веса ребер. Вес пути. Понятие минимального пути. Матрица смежности (с весами ребер). ПРИМЕР 2 На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л? 26

27 Логика Логические значения. Логические связки (операции): отрицание, дизъюнкция, конъюнкция, импликация. Логические (булевы) выражения, их истинность и ложность. Эквивалентные преобразования булевых выражений. Таблицы истинности. Высказывания, логические операции, кванторы, истинность высказывания 27

28 Логика. Пример

29 Логика На числовой прямой даны два отрезка: P = [37; 60] и Q = [40; 77]. Укажите наименьшую возможную длину такого отрезка A, что формула истинна при любом значении переменной х, то есть принимает значение 1 при любом значении переменной х.

30 Логика - 3 Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям? (x1->x2) & (x2->x3) & (x3->x4) & (x4->x5 ) = 1 (y1->y2) & (y2->y3) & (y3->y4) & (y4->x5 ) = 1 x1\/y1 =1 В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

31 B13 У исполнителя Кузнечик две команды: 1. прибавь 3, 2. вычти 2. Первая из них увеличивает число на экране на 3, вторая – уменьшает его на 2 (отрицательные числа допускаются). Программа для Кузнечика – это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью различных программ, содержащих ровно 5 команд?

32 B3 Определите, что будет напечатано в результате работы следующего фрагмента программы: Алгоритмический язык нач цел k, s s:=0 k:=0 нц пока s < 1024 s:=s+10 k:=k+1 кц вывод k кон

33 АЛГОРИТМЫ и ПРОГРАММИРОВАНИЕ 33

34 Получив на вход число x, алгоритм печатает два числа L и M. Укажите наибольшее из таких чисел x, при вводе которых алгоритм печатает сначала 3, а потом 7. алг нач цел x, L, M ввод x L:=0; M:=0 нц пока x>0 L:=L+1 если M < mod(x,10) то M:= mod(x,10) все x:=div(x,10) кц вывод L, нс, M кон

35 C3 У исполнителя Утроитель две команды, которым присвоены номера: 1. прибавь 1, 2. умножь на 3. Первая из них увеличивает число на экране на 1, вторая – утраивает его. Программа для Утроителя – это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 29? Ответ обоснуйте.