Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 1,006

PROGRAMMING AS A TOOL OF SOLVING OLIMPIAD TASKS ON THEORETICAL INFORMATICS

Lapsheva E.E. 1 Ogneva M.V. 1
1 National research Saratov state University named after N.G. Chernyshevsky
Through the program "Digital Economy in the Russian Federation" adopted by the Government of the Russian Federation, end-to-end technologies are defined that should permeate all the directions of life of modern Russian society. To implement these directions, highly skilled personnel with flexible thinking are needed, who can use various tools to solve emerging problems. the basis for the development of schoolchildren for successful inclusion in the digital future is the secondary general school and the teacher of informatics. And the first step in in-depth study of computer science is participation in the Olympiads in this subject. The classical olympiad in informatics is the programming contest, but the olympiads, which cover the entire school computer science course, are becoming more widespread. Ability to solve tasks that are offered at such olympiads is important for schoolchildren who study in specialized classes and are set to enter the profile universities of the country. The article considers one of the approaches that allows to significantly increase the effectiveness of solving olympiad tasks on topics that are related to the so-called mathematical foundations of computer science (number systems, combinatorics, information measurement, logic). Some kinds of such tasks can be solved with the help of simple programs, which gives a gain in time and reduces the probability of making an arithmetic error in the calculations. Of course, in order to compile the correct algorithm for the operation of such a program, one must be able to build the correct mathematical model of the solution. But all the routine operations in the calculation can be shifted to the shoulders of the program. Thus, using the basic skills on the basics of programming competently, you can significantly improve the efficiency of solving complex and olympiad problems from other areas of computer science. But for this it is necessary to understand the content and essence of the problem, and be able to choose the way to solve it - analytical or software. In general, the use of programming in such problems can greatly facilitate the decision process and / or reduce the number of errors of an arithmetic nature.
training of it-specialists
olimpiad of informatics

В принятой Правительством РФ программе «Цифровая экономика в Российской Федерации» определяются сквозные технологии, которые должны пронизывать все направления жизни современного российского общества: большие данные, нейротехнологии и искусственный интеллект; системы распределенного реестра; квантовые технологии; новые производственные технологии; промышленный Интернет; компоненты робототехники и сенсорика; технологии беспроводной связи; технологии виртуальной и дополненной реальности [1].

Для реализации данных направлений необходимы высококвалифицированные кадры, обладающие гибким мышлением, умеющие применять различные инструменты для решения возникающих проблем. Для подготовки новых поколений к жизни в условиях цифровой экономики создаются региональные сети «Сириус» – центры для работы с одаренными детьми [2], детские технопарки Кванториум [3] и другие центры. Но основой развития школьников для успешного включения в цифровое будущее является средняя общеобразовательная школа, а первым шагом в углубленное изучение информатики – участие в олимпиадах по данному предмету [4]. Поэтому весьма актуальными являются проблемы, связанные с олимпиадной подготовкой в области информатики и информационных технологий.

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

Материалы и методы исследования

Материалы исследования — материалы олимпиад по информатике и методическая литература по данной теме. Методами исследования являются анализ источников, обобщение, систематизация и синтез представленных в них данных.

Классическая олимпиада по информатике – это олимпиада по программированию. Прежде всего это всероссийская олимпиада по информатике на всех ее этапах, а также олимпиады ведущих вузов страны (Московская, Санкт-Петербургская, Всесибирская и т.д.). Почти все эти олимпиады входят в список «Перечень олимпиад школьников и их уровни», то есть дают какие-то преимущества при поступлении в профильные вузы [5].

Однако существуют и другие олимпиады, список которых постепенно расширяется, – это олимпиады, охватывающие весь курс информатики (таблица). И среди них становится все больше и больше олимпиад, которые также входят в вышеупомянутый перечень.

Олимпиады по информатике и программированию

Название

Классы

Уровень

Тематика

Открытая олимпиада школьников «Информационные технологии»

7–11

1

Базовый курс информатики, программирование

«Гранит науки»

11

1

Базовый курс информатики

Олимпиада школьников «Высшая Проба»

9–11

2

Программирование, базовый курс информатики

Межрегиональная олимпиада школьников по информатике и компьютерной безопасности

8–11

2

Программирование, базовый курс информатики

Олимпиада по дискретной математике и теоретической информатике

9–11

3

Базовый курс информатики

Всероссийская олимпиада «ИНФОЗНАЙКА-ПРОФИ» по информатике

8–11

3

Программирование, базовый курс информатики

Университетская олимпиада школьников «Бельчонок»

2–11

3

Базовый курс информатики, программирование

ИНФОЗНАЙКА – конкурс по информатике и информационным технологиям

1–11

Всероссийская, уровня в перечне не имеет

Базовый курс информатики

Олимпиада центра «Фоксфорд»

6–11

Всероссийская, уровня в перечне не имеет

Базовый курс информатики

 

На наш взгляд, олимпиады данного вида имеют следующие преимущества.

Во-первых, темы, по которым строятся задания данных олимпиад, охватывают не только программирование, но и теоретическую информатику и информационные технологии, что позволяет улучшить свой результат школьникам, не имеющим навыка олимпиадного программирования, но имеющим хороший уровень знаний по курсу информатики в целом и, возможно, интересующимся другими областями информатики (не олимпиадным программированием). Во-вторых, подобные олимпиады, как правило, имеют деление заданий по уровням сложности в зависимости от класса участника, что дает возможность привлечь к олимпиаде школьников среднего школьного звена и получить хорошие результаты, осуществляя подготовку постепенно, в зависимости от возрастной группы. В-третьих, задания таких олимпиад очень близки (хотя и являются более сложными) к заданиям Государственной итоговой аттестации (в 9-х и 11-х классах) по информатике. Поэтому, готовясь к олимпиаде, школьники тем самым готовятся и к сдаче ОГЭ и ЕГЭ по информатике [6–8].

Далее рассмотрим один из подходов, позволяющий существенно повысить эффективность решения заданий по темам, которые связаны с так называемыми математическими основами информатики (системы счисления, комбинаторика, измерение информации, логика) на примере заданий Открытой олимпиады школьников «Информационные технологии» [9].

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

В первую очередь такими программно-решаемыми заданиями можно считать задания, требующие генерации комбинаторных объектов. Задачи подобного типа можно встретить в разделах на системы счисления, логику, комбинаторику и вероятностный подход к измерению информации. Как правило, любая задача с вопросом, начинающимся на слово «сколько…», решается с помощью программирования. Если при решении используется язык программирования Python, то удобно применить методы из модуля itertools.

Разберем несколько подобных задач.

Задача 1. 2014 год, Открытая олимпиада школьников «Информационные технологии». 11-й класс, 1-й дистанционный тур.

Сколько существует натуральных чисел, для которых одновременно выполняются следующие условия:

1.         Запись числа в семеричной системе счисления имеет ровно три значащих разряда.

2.         Если перевести это число в шестеричную систему счисления, то запись числа останется трехразрядной, но значение каждого разряда увеличится на единицу по сравнению со значениями соответствующих разрядов в записи этого числа в семеричной системе счисления. Ответ: 5

Очевидно, что в данной задаче нужно перебрать все решения уравнения:

где , . По сути дела, нам нужно организовать перебор 100 комбинаций цифр ,  и .

# Импортируем из модуля itertools метод product

from itertools import product

# Генерируем списки цифр: для a от 1 до 4 включительно,

# для b и c от 0 до 4 включительно

a = [x for x in range(1, 5)]

b = c = [x for x in range(5)]

# обнуляем результативный счетчик

res = 0

# Генерируем все возможные тройки из элементов списков a, b, c

for i, j, k in product(a, b, c):

# если полученная тройка удовлетворяет нашему условию,

# то увеличиваем счетчик

    if i * 49 + j * 7 + k == (i + 1) * 36 + (j + 1) * 6 + (k + 1):

        res += 1

print(res)

Задача 2. 2014 год, Открытая олимпиада школьников «Информационные технологии». 11-й класс, 1-й дистанционный тур.

Даны две логические функции, зависящие от четырех аргументов , ,  и .

Сколько существует различных комбинаций значений , ,  и  таких, что для них:
?

Так как в используемых нами языках программирования нет реализации операции импликации, избавимся от нее:

from itertools import product

logic = (True, False)

# Создадим две функции, вычисляющие нужные нам значения:

def f1(a, b, c, d):

    return (not a or not b) and (not b or not c) and (not c or not d)

def f2(a, b, c, d):

    return (not a or b) and (not b or c) and (not c or d)

res = 0

# Перебираем все возможные последовательности из четырех логических

# значений:

for a, b, c, d in product(logic, repeat=4):

    if f1(a, b, c, d) == f2(a, b, c, d):

        res += 1

print(res)

Задача 3. 2014 год, Открытая олимпиада школьников  «Информационные технологии». 8-й класс, очный тур.

Для наглядного планирования предстоящей операции начдив Чапаев раскладывает на столе овощи, изображающие отдельные подразделения, включенные в состав сил, участвующих в операции. Для изображения подразделений начдив использовал: 2 картофелины, 3 морковки, 5 свекол и 6 луковиц. Овощи одного вида неразличимы друг от друга и обозначают один вид подразделения. Сколько различных вариантов состава сил, участвующих в операции, мог предложить своему штабу Чапаев, если известно, что одновременно на столе располагалось ровно 7 овощей? Ответ: 61

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

from itertools import combinations

# Создаем «корзину» – список наших овощей

vegetables = ['potato'] * 2 + ['carrot'] * 3 + ['beet'] * 5 + ['onion'] * 6

# Найдем множество всех возможных сочетаний овощей из нашей корзины

# Выведем на экран мощность этого множества

print(len(set(combinations(vegetables, 7))))

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

Задача 4. 2016–2017 год, 1-й заочный тур, 9–10-й класс

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

1. По истечении каждых 10 секунд от запуска таймера добавить к текущему значению на таймере 17 секунд.

2. По истечении каждых 3 секунд отсчета от запуска таймера уменьшить текущее значение на таймере на 11 секунд.

3. При совпадении времени операций 1 и 2 выполнить операцию 1.

Определите, по истечении какого времени таймер закончит работу (будет получено значение 0). В ответе укажите целое число секунд, прошедшее с момента запуска таймера. Ответ: 58.

Выполнить решение можно с помощью следующей короткой и несложной программы:

from itertools import count

timer = 148

for i in count(start=1):

    if i % 10 == 0:

        timer += 17

    elif i % 3 == 0:

        timer -= 11

    else:

        timer -= 1

    if timer == 0:

        print(i)

        break

 

Ряд задач, которые содержат в условии блок-схему, также можно решать программным путем. Если при этом нужно узнать, что будет на входе, имея определенный результат на выходе, можно подобрать ответ, запуская программу несколько раз. Однако не всегда это возможно сделать методом простого подбора. В некоторых случаях нужно сначала понять хотя бы в общем, что делает данный алгоритм. Иногда в таких задачах понимание сущности алгоритма является определяющим, следовательно, программирование не дает ожидаемой пользы и не должно использоваться.

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

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

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