Сетевое издание

Современные проблемы науки и образования

ISSN 2070-7428

"Перечень" ВАК

ИФ РИНЦ = 1,006

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

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

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

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

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

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

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

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

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

Во-первых, темы, по которым строятся задания данных олимпиад, охватывают не только программирование, но и теоретическую информатику и информационные технологии, что позволяет улучшить свой результат школьникам, не имеющим навыка олимпиадного программирования, но имеющим хороший уровень знаний по курсу информатики в целом и, возможно, интересующимся другими областями информатики (не олимпиадным программированием). Во-вторых, подобные олимпиады, как правило, имеют деление заданий по уровням сложности в зависимости от класса участника, что дает возможность привлечь к олимпиаде школьников среднего школьного звена и получить хорошие результаты, осуществляя подготовку постепенно, в зависимости от возрастной группы. В-третьих, задания таких олимпиад очень близки (хотя и являются более сложными) к заданиям Государственной итоговой аттестации (в 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

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

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

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

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