Читать онлайн Книга-тренажер: «Базовая подготовка к ЕГЭ по информатике в компьютерной форме». Авторский курс бесплатно
Учитель информатики Егор Валерьевич Наумов
© Евгений Леонидович Сидоркин, 2023
ISBN 978-5-0055-1904-7
Создано в интеллектуальной издательской системе Ridero
Введение
В данной книге приведена в минимальном количестве теоретическая часть и рассмотрены основные подходы к решению задач компьютерного ЕГЭ по информатике. Наилучшим психологическим подходом на экзамене считается такой: вы решаете все задания, которые легко вам даются, а более сложные пропускаете. После чего, воодушевленные своими успехами в решении задач, приступаете к решению задач, более сложных на ваш взгляд. Далее, если осталось время, то начинаете проверку заданий, которые решили. И напоследок при наличии времени начинаете прорешивать все задания вторым способом и сверяетесь с тем, что у вас получилось при решении первым способом. Если выявились расхождения в ответах, то ищите ошибку. Такая тактика позволит вам набрать максимальное число баллов на экзамене. В книге рассмотрено решение задачи на языке Python, т.к. на нем код получается более коротким в сравнении с другими языками, что поможет сэкономить время на экзамене и набрать более высокий балл. В качестве рекомендации максимального усвоения материала рекомендую читать книгу последовательно по разделам и в конце каждого пробовать самостоятельно решать задания на компьютере, аналитически и сверяться с ответом. После понимания материала, связанного с программированием, пробовать самостоятельно написать код, стараясь не подглядывать, и также решать аналитическим способом, в тех заданиях, где это возможно.
Каждый вариант экзаменационной работы включает в себя 27 заданий, различающихся уровнем сложности и необходимым для их выполнения программным обеспечением.
В работу входят 9 заданий, для выполнения которых, помимо тестирующей системы, необходимо специализированное программное обеспечение (ПО), а именно редакторы электронных таблиц и текстов, среды программирования.
Ответы на все задания представляют собой одно или несколько чисел, или последовательности символов (букв или цифр).
В 2021 г. ЕГЭ по информатике и ИКТ проводится в компьютерной форме, что позволило включить в КИМ задания на практическое программирование (составление и отладка программы в выбранной участником среде программирования), работу с электронными таблицами и информационный поиск. Таких заданий в работе 9, т.е. треть от общего количества заданий.
Максимальный первичный балл за работу – 30.
Общее время выполнения работы – 235 мин.
Экзаменационная работа ЕГЭ охватывает основные темы курса информатики и ИКТ: «Информация и ее кодирование», «Моделирование и компьютерный эксперимент», «Системы счисления», «Логика и алгоритмы», «Элементы теории алгоритмов», «Языки программирования», «Обработка числовой информации», «Технологии поиска и хранения информации».
В книге задания разбиты по темам на основании кодификатора и спецификации контрольных измерительных материалов для проведения в 2021 г. единого государственного экзамена по информатике и ИКТ, подготовленных Федеральным государственным бюджетным научным учреждением «Федеральный институт педагогических измерений». В книге рассмотрены все основные типы задач, которые встречались в тренировочных, репетиционных и диагностических работах, ЕГЭ по информатике основной и досрочной волны 2018—2021 годах.
Прилагаю памятку, которую желательно прочитать перед экзаменом: https://yadi.sk/i/wcTFdrdtA71c8g.
Глава 1. Моделирование и компьютерный эксперимент
Задача №1. Анализ информационных моделей
Граф – это способ графического представления информации. Объекты в нем – это вершины (узлы), а связи между объектами – ребра (дуги). То есть граф – это набор вершин и связывающих их ребер. Путь в графе – это конечная последовательность вершин, каждая из которых (кроме последней) соединена со следующим ребром. Граф может содержать циклы (первая вершина пути может совпадать с последней). Обычно в задачах используют взвешенный граф, т.е. граф, в котором с каждым ребром связано число (вес). Например, расстояние, стоимость и т. д. Граф обычно задается таблицей, в которой на пересечении строки и столбца с наименованиями вершин записано числовое значение (вес) ребра, соединяющего эти вершины.
Задачи на графы лучше всего решать аналитически, например, в программе «Ножницы», которая стандартно будет у вас открываться на экзамене. Вы можете скопировать картинку, нажать пуск/ найти/ввести слово «ножницы» и в открывшейся программе попытаться рисовать, решая данные задачи тем методом, что будет предложено ниже. Рассмотрим их.
Пример 1.1
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населенных пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта В в пункт Е. В ответе запишите целое число – так, как оно указано в таблице.
Решение:
Из вершины B выходит 5 ребер, значит, в таблице соответствующий пункт должен иметь дороги в 5 других (строка должна содержать 5 заполненных клеток). Такой пункт в таблице один: П6. На графе из вершины Е выходит 4 ребра, значит, в таблице соответствующий пункт должен иметь дороги в 4 других (строка должна содержать 4 заполненные клетки). Такой пункт в таблице один: П4. Таким образом, нам нужно найти расстояние между П6 и П4. На пересечении П6 и П4 находится цифра 20.
Ответ: 20.
Пример 1.2
На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах. Известно, что длина дороги ВД меньше дороги ВЕ. Определите длину дороги ГЖ.
Решение: Для начала расставим количество путей, которые выходят из каждой вершины.
Минимальное число путей из вершин – это 2.
Им соответствует вершина А и Ж. Мы видим в таблице, что в П5 есть два пути. Поэтому предположим, что П5=А, тогда П4=Ж. Т. к. П5 пересекается в значении 10 с П6 и П6=3, то П6=Б. Аналогично получаем, что П7=Д. Далее П7 пересекается с П3, то П3=В. Т. к. П6 пересекается с П2, то П2=В, остается, что П3=Е. Осталась одна вершина – это П1=Г. Условие, что ВЕ> ВД, 23> 16. Это условие истинно, значит, наше предположение изначальное, что П5=А, а П4=Ж, а не наоборот – истинное. А если бы было ложное, тогда что? Тогда бы пришлось рисовать заново, предполагая, что П5=Ж, а П4=А. Смотрим по таблице пересечение П1 и П4 – это число 2.
Ответ: 2.
Пример 1.3
На рисунке слева схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.
Определите номера пунктов, соответствующих пунктам З и Ж на графе. В качестве ответа запишите два числа в порядке возрастания без разделителей – найденные номера.
Решение:
Пункт К соединяется с вершинами Г (4 вершины) и В (4 вершины). П8 соединяется как раз с двумя вершинами П1 и П2, каждая из которых имеет по 4 дороги, значит, П8=К. Т. к. П8 соединяется с П1 и П2 имеет четыре вершины, то можно предположить, что П1=В, а П2=Г. П1 соединяется с П5, и т. к. П5 имеет 2 вершины, то П5=З. Ранее выяснили, что П2=Г и П2 пересекается с П3, которая имеет 2 вершины, значит, П3=Ж.
Ответ: 35.
Задачи для самостоятельного решения
Задача 1.4
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину кратчайшего пути из пункта А в пункт В, если передвигаться можно только по указанным дорогам. В ответе запишите целое число – длину пути в километрах.
Задача 1.5
На рисунке схема дорог изображена в виде графа, в таблице звёздочками обозначено наличие дороги между населёнными пунктами.
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Выпишите последовательно без пробелов и знаков препинания, указанные на графе буквенные обозначения пунктов от П1 до П8: сначала букву, соответствующую П1, затем букву, соответствующую П2, и т. д.
Глава 2. Алгебра логики и базы данных
Задание №2. Алгебра логики
Алгебра логики или булева алгебра – так их называют. Как вы думаете, для чего вообще нужна алгебра логики, кроме как мучить детей? Представьте, что по проводу течет ток. Если ток есть в проводе, то обозначим это действие за 1, т.е. истина. Если же тока нет, то ноль, т.е. ложь. Сборка различных схем на компьютере осуществляется как раз схемами, которые представлены на рис.1.
Рисунок №1
Причем можно усложнить схемы, сделать их большими и громоздкими. В компьютере, понятное дело, используются большие логические схемы взаимодействий. Учить это не хочется, но важно понять, как это работает. Для этого и придумали алгебру логики. Какая бы сложная схема ни получилась, ее всегда можно упростить до двух проводов, далее буду говорить до 2 переменных, на языке алгебры логики. Высказывание – повествовательное предложение, о котором можно сказать, истинно оно или ложно. В алгебре простым высказываниям ставятся в соответствии логические переменные (А, В, С и т.д.). Пример высказываний:
Рисунок №2
Логическая переменная – это простое высказывание.
Логические переменные обозначаются прописными и строчными латинскими буквами (a-z, A-Z) и могут принимать всего два значения – 1, если высказывание истинно, или 0, если высказывание ложно.
Логическая формула (логическое выражение) – формула, содержащая лишь логические переменные и знаки логических операций. Результатом вычисления логической формулы является ИСТИНА (1) или ЛОЖЬ (0).
Логическое умножение – конъюнкция. Принятые обозначения: /\, •, и, and. Этой операции соответствует знак умножения. Например, переменные А=0, B=0, то F=A*B=0*1=0. То же самое можно представить в виде примера А=«Немцы победили русских в Великой Отечественной войне»=0, ложь, т.к. русские выиграли, B=«Лимон кислый на вкус»=1, истина, т.к. это соответствует действительности. Тогда A*B=0*1=0, т.к. я настаиваю, чтобы и А, и B выполнялось (через действие умножение), поэтому значением выражения будет ложь. Остальные значения таблицы истинности вы можете посмотреть на Рисунке №3. Логическая формула истинна только в одном случае и ложна в трех других.
Рисунок №3
Логическое сложение (дизъюнкция). Объединение двух (или нескольких) высказываний в одно с помощью союза ИЛИ. Обозначение: \/, +, или, or.
Рисунок №4
На рисунке №4 функция истинна в трех случаях и ложна только в одном, когда ложь. Дизъюнкции соответствует знак сложения.
Отрицание (инверсия), от лат. InVersion – переворачиваю – Рисунок №5:
Соответствует частице НЕ, словосочетаниям НЕВЕРНО, ЧТО или НЕ. Обозначение: не А, ¬А, not. В данной функции значения функции меняются наоборот. Если А=0, то F= Не А=1.
Рисунок №5
Логическая функция импликация. Обозначается cтрелкой ->. В языке программирования соответствует операции меньше либо равно <=. Как из лжи А=0 получить ложь B=0? Рассмотрим на примере A=2> 3 – ложь, то прибавим к обоим частям неравенства +2 и получим тоже ложь B = 4> 5. Если из лжи А=0 и B=0 можно получить ложь, значит, истина A -> B=1. A= -5> 3 – ложь, то обе части неравенства возведу в квадрат и получим уже истину B= 25> 9, тогда при A=0 и B=0 получаю, что А -> B=1. Из истины А=1 я не могу получить B=0, поэтому A -> B=0. Если вы поняли смысл, как мы получили логические высказывания, то вам не потребуется зубрить таблицы истинности.
Рисунок №6
Вы еще не устали от логики)?
Последняя функция эквиваленция. Обозначается как на рисунке №6.
Рисунок №6
Функция истинна A <-> B=1 только в двух случаях: либо когда обе логических переменных А и B истинны, или когда А и B – ложны.
В каком же приоритете выполняются данные операции, спросите Вы? Да все очень просто: сначала отрицание, затем конъюнкция (умножение), потом дизъюнкция (сложение), далее импликация и эквиваленция.
Рисунок №7
В ЕГЭ представлено две задачи на знания алгебры логики. Это задачи №2 и №15. Рассмотрим основные типы этих задач ниже.
Пример 2.1
Логическая функция F задается выражением (x ⟶ y) ∧ (x ∨ ¬z) ∧ (x ≣ ¬w). Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных w, x, y, z.
Решение:
Первый способ – это написание программы на языке программирования Python. Код представлен ниже.
- print (’x’,’y’,’z’,’w’)
- def f (x,y,z,w):
- return (not x or y) and (x or not z) and (x == (not w)) # условие из задачи, преобразовали x ⟶ y= not x or y
- for x in range (0,2): # изменение переменных от истины до лжи.
- for y in range(0, 2):
- for w in range(0, 2):
- for z in range(0, 2):
- if f (x,y,z,w) == 1: # условие истинности из задачи
- print (x,y,z,w)
После запуска программы мы можем заметить строку, содержащую 0 0 0 1. Если сравнить эту строку со строками из таблицы (что в условии), то в данной таблице мы не найдем строку с тремя нулями, поэтому строку 0 0 0 1 можем смело исключить из решения. Рассмотрим оставшиеся три строки, которые необходимо сопоставить с таблицей, что в условии. Второй столбец с тремя единицами соответствует второму столбцу из таблицы, значит, второй столбец – Y. В первую ячейку третьего столбца однозначно можно поставить только ноль, и тогда образуется первая строка 1 1 1 0. Т.к. в последней строчке из рисунка №7 стоит такая же строка 1 1 1 0, что в условиях таблицы, то третий столбец – однозначно W. На рисунке №7 в первой и третьей ячейке третьей строки стоят нули, которые мы можем перенести в таблицу из условия на соответствующие места и однозначно определить, что Z – это первый столбец, а Z – третий.
- Рисунок №7
- x y z w
- 0 1 0 1
- 1 1 0 0
- 1 1 1 0
- Решение:
Второй способ решения этой же задачи состоит в том, что мы составляем таблицу истинности без помощи компьютера. Заполняем первую строку, если w=0, то x=1, а y=1, а z – или ноль, или один. Итого получим почти две одинаковые строчки, за исключением значения z. 1 1 0 0 и 1 1 1 0. Теперь предположим, что W=1, тогда x=0. Т.к. в условии есть столбец с тремя единицами, то необходимо в ручном решении тоже получить такой столбец, поэтому y=1, а z=0. Ответ: ZYWX.
Пример 2.2
Логическая функция F задается выражением (¬z) ∧ x ∨ x ∧ y. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.
Решение:
Расставим скобки, выражение (¬z) ∧ x ∨ x ∧ y является дизъюнкцией двух конъюнкций: ((¬z) ∧ x) ∨ (x ∧ y). В обеих конъюнкциях присутствует x. То есть при x = 0 все выражение равно нулю. Только в третьем столбце напротив нулей стоят значения функции F=0, поэтому третий столбец – это x. Также можно заметить, что выражение ((¬z) ∧ x) ∨ (x ∧ y) =1, если x =1 и выполняется хотя бы одно из условий: y = 1 или z = 0. Из четвертой строки следует, что Перем.1 = z, а Перем.2 = y.
Ответ: zyx.
Пример 2.3
Дан фрагмент таблицы истинности для выражения F. Укажите максимально возможное число различных строк полной таблицы истинности этого выражения, в которых значения x4 не совпадает с F.
Решение:
Таблица истинности выражения с семью переменными (x1…x7) содержит 27=128 строк. В приведенном фрагменте таблицы x4 не совпадает с F в 4-х строках, а совпадает только в последней нижней строке. Во всех остальных может не совпадать. Тогда максимально возможное количество строк, где значения x4 и F не совпадают, будет 128—1=127.
Ответ: 127.
Задачи для самостоятельного решения
Задача 2.4
Логическая функция F задаётся выражением: (x ∧ ¬ y) ∨ (y ≣ z) ∨ w. На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w. В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Задача 2.5
Для функции F известен фрагмент таблицы истинности, представленный ниже. Определите, какое максимальное количество единиц может быть в столбце F полной таблицы истинности, если известно, что при значении x4 = 1 значение функции равно 1.
Задача №3. Файловая система. Базы данных
Возможно, помните из школьного курса информатики, что файл представляет собой имя файла и расширение. Например, mama.doc. Где расширение? Слева от точки – это имя файла, а справа – расширение. Примеры некоторых типов файлов:
Текстовые файлы – расширения. txt,.doc;
Исполняемые файлы – расширения. exe,.com;
Звуковые файлы – расширения. mp3,.waf.
Звездочка «*» – заменяет любое количество (в том числе и нулевое) любых символов.
«?» – заменяет один и только один обязательно стоящий в указанном месте символ. Например, по маске «*.*» будут отобраны вообще все файлы с любыми именами и расширениями, по маске «*.txt» – файлы с расширением. txt, по маске «aл?.doc» – файлы, с расширением. doc, имена которых начинаются на «aл» и имеют обязательный непустой третий символ.
Для хранения и обработки большого объема информации организовывают Базы Данных. Под Базой Данных понимают организованную в соответствии с некоторыми правилами структурированную совокупность логически связанных данных. Эти данные предназначены для удобного совместного хранения и анализа.
Реляционная База Данных состоит из связанных между собой таблиц.
Если установлена сортировка по имени или типу, сравнение идет по кодам символов из кодировочной таблицы. При этом если задана сортировка, к примеру, по имени, то при наличии одинаковых имен сортировка будет применена к расширению файла. Цифра всегда «меньше» буквы.
Пример 3.1
Для групповых операций с файлами используются маски имен файлов. Маска представляет собой последовательность букв, цифр и прочих допустимых в именах файлов символов, в которых также могут встречаться следующие символы: символ»?» (вопросительный знак) означает ровно один произвольный символ. Символ «*» (звездочка) означает любую последовательность символов произвольной длины, в том числе «*» может задавать и пустую последовательность. Определите, какое из указанных имен файлов удовлетворяет маске:?fi*r.?xt
1) dir. txt 2) ofir. txt 3) ofir. xt 4) firr. txt
Решение:
Рассмотрим все варианты ответов: 1) не подходит, т.к. в имени отсутствует буква f; 2) полностью удовлетворяет условию маски; 3) не подходит, т.к. на месте»?» после точки отсутствует лишний символ перед буквой x; 4) не подходит, т.к. перед буквой f нет никакого символа, а он должен быть по условию задачи.
Ответ: 2.
Пример 3.2
Каталог содержит файлы с именами
а) p5.pas г) pq. u
б) p4.ppt д) pq.pas
в) p12.pas е) p12.ppt
Определите, в каком порядке будут показаны файлы, если выбрана сортировка по типу (по возрастанию).
1) вадгеб 2) гавдбе
3) вадгбе 4) гвадеб
Решение:
Отсортируем файлы по типу (по возрастанию), а это значит, что сначала отсортируем по расширению, а потом по имени файла. Все расширения начинаются на одну букву p, тогда смотрим расширения. На первом месте будет стоять файл, в расширении которого вообще нет второй буквы – пустой символ всегда меньше непустого: pq. u (г).
Далее идут файлы с расширением. pas (а и д), но поскольку таких файлов несколько, то анализируем имена файлов. Известно, что цифра «меньше» буквы в кодировочной таблице.
p12.pas (в) – т.к. 1 <5
p5.pas (а) – т.к. 5 <q
pq.pas (д) —
Дальше идут файлы с расширением. ppt, т.к. в расширении ppt вторая буква p больше второй буквы а в расширении pas.
p12.ppt (е) – т.к. 1 <4
p4.ppt (б)
Ответ: 4. pq. u, p12.pas, p5.pas, pq.pas, p12.ppt, p4.ppt
Пример 3.3
Ниже представлены два фрагмента таблиц из базы данных о жителях микрорайона. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных ID женщины, ставшей матерью в наиболее молодом возрасте. При вычислении ответа учитывайте только информацию из приведённых фрагментов таблиц.
Решение:
Нарисуем 3 дерева ниже, где матерями будут выступать женщины со следующими ID: 44, 34, 64. По рисунку ниже мы видим, что мать с ID= 44 родила в 26 и 36 лет, мать с ID=34 родила в 26 и 29 лет, а мать с ID=64 родила в 22 и 28 лет. Из чего можем сделать вывод, что 22 года – это самый младший возраст женщины, которая родила ребенка. Поэтому это мать с ID=64.
Ответ: 64.
Задачи для самостоятельного решения
Задача 3.4
Ниже представлены два фрагмента таблиц из базы данных о жителях микрорайона. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных, у скольких детей на момент их рождения отцам было больше 25 полных лет. При вычислении ответа учитывайте только информацию из приведённых фрагментов таблиц.