Алгоритмы КЕГЭ-20

Здравствуйте уважаемая аттестационная комиссия. Хочу представить вам свою работу на тему «Алгоритмы КЕГЭ-2021 по информатике и их реализация»

Актуальность выбранной темы объясняется тем, что в 2021 году произошли изменения в формате проведения ЕГЭ по информатике, а именно он стал проводится с использованием специализированного ПО

Целью нашей работы стало систематизация, формализация и реализация базовых алгоритмов КЕГЭ-2021.

Для достижения поставленной цели было необходимо выполнить следующий ряд задач:

1. Анализ особенностей КЕГЭ и обзор контрольно-измерительных материалов (КИМ) по алгоритмизации и программированию

2. Систематизация и описание основных алгоритмов решения задач на программирование.

3. Варианты эффективной реализации некоторых алгоритмов на примере задач из КИМ

Какие же изменения произошли.

1. В ЕГЭ прошлых лет достаточно было закодить фрагмент программы или полную программу, Теперь для выполнения данного типа заданий необходимо не только написать программу, но также в ответ вывести числа, которые выдаст программа при указанных входных данных.

2. Увеличилось число заданий, в которых необходимо самостоятельно писать программный код: раньше их было всего два задания, теперь шесть.

3. Убрали один из языков программирования — Бейсик. Теперь чтобы решить задания, с готовым программным кодом, используются следующие языки программирования: Pascal, Алгоритмический язык, Python и C++. Для самостоятельного написания программы можно использовать языки Pascal, C#, Java, Python и C++.

4. Появились абсолютно новые задания на работу с электронными таблицами и поиск указанных данных в текстовом документе

5. Большое задание, которое было под номером 26 в прежних КИМах, по теме Теория игр разбили на несколько отдельных задания, теперь оно будет идти под номерами 19, 20 и 21, в соответствии с пунктами старого задания.

6. В современном ЕГЭ убрали решение логических уравнений, которые всегда были одним из самых проблемных заданий на экзамене

Стоит сказать, что Каждый вариант экзаменационной работы включает в себя 27 заданий, различающихся уровнем сложности и необходимым для их выполнения программным обеспечением.

По данным ФИПИ В работу входят 9 заданий, для выполнения которых, помимо тестирующей системы, необходимо специализированное программное обеспечение (ПО), а именно редакторы электронных таблиц и текстов, среды программирования, а именно…

Но проведя анализ ДЕМО-версии можно выделить таких заданий намного больше, так например, для решения Задание №2 можно использовать ПО для работы с электронными таблицами, так как в них имеются все логические операции или с помощью среды программирования или Задание №16, связанное с рекурсивными процедурами и функциями. Хоть это задание и не отмечено, как задание с использованием ПО, но для решения удобнее написать программу.

Обзор существующих ресурсов для подготовки к ЕГЭ по информатике

Для успешной сдачи экзамена по информатике и поступления в ВУЗ необходимо минимально набрать 40 баллов.

Проанализируем результаты пробного экзамена по информатике. В нем приняли участие 103 человека. Посчитав количество человек, справившихся с каждым из заданий, мы получили следующую таблицу.

Как мы видим из данной таблицу, наибольшее затруднение вызвали задания под номерами 2, 18, 24, 25 и 27.

Остановимся более подробно на 27 задании. Проанализировав основные виды задач, предлагаемые в 27 задании, можно составить следующую схему

Задачи на множества и подмножества

Сортировка подсчетом. Вся идея решения будет заключаться в том, что мы создадим массив с количеством элементов, равным количество возможных остатков (оно всегда равно числу, на которое делим)

Задачи на последовательность чисел

Суть этого метода будет заключаться в том, что произведение двух чисел будет не кратно 49 и кратно 7 только в том случае, когда один из множителей делится на 7 и при этом не делится на 49, а второй — не делится на 7. Максимальное значение произведения будет только в том случае, когда оба множителя будут максимальными. Если в какой-то из групп не будет ни одного числа, то тогда нужное нам произведение не существует.

Решение с помощью динамического программирования

Рассмотрим ситуацию на конкретном примере. На рисунке описана ситуация, когда первые 5 значений были считаны, и контрольные значения для них подсчитаны. Разберемся с ситуацией, когда на вход приходит 6 число. Для начала необходимо найти максимальную нечетную сумму, которую можно составить из пришедшего числа и одного из предыдущих. Так как пришло четное число, то из ранее считанных нам нужно МАКСИМАЛЬНОЕ НЕЧЕТНОЕ, а оно равно 3. Соответственно, максимальная сумма будет равна 12+3. И так как она больше, чем максимальная сумма, которая была получена на отрезке от 1 до 5 мы обновляем значение. В конце необходимо обновить поле «максимальное четное», так как оно понадобится в дальнейшем.

Соответственно, всю задачу можно разбить на три этапа:

1) Считывание очередного числа

2) Обновить поле максимального значение (если необходимо)

3) Обновить поле максимального четного или нечетного числа (если необходимо)

Задачи на последовательность пар чисел

Сложность данной задачи заключается в том, чтобы полученная сумма делилась на заданное число. В идеальной ситуации сумма больших чисел в паре делится на указанное число, тогда достаточно просто ее вывести на экран.

Больший интерес представляет ситуация, когда набранная сумма не делится на указанное число. В этом случае придётся заменить числа в одной или нескольких парах так, чтобы «убрать» остаток от деления на 6, то есть вычесть из суммы всех наибольших чисел значение, которое имеет тот же остаток от деления на 6, что и сумма. Если нам повезёт, такая коррекция выполняется заменой всего в одной паре, но чаще всего одной заменой не обойтись.