Набор заданий для знакомства с параллельными вычислениями в конкурсе "ТРИЗформашка"



Авторы: Плаксин Михаил Александрович 1, кандидат физико-математических наук, доцент
Иванова Наталия Геннадьевна 2
Русакова Ольга Леонидовна 3, кандидат физико-математических наук, доцент, Почетный работник высшего профессионального образования РФ
1 Национальный исследовательский университет Высшая школа экономики (Пермский филиал) , 2 Муниципальное автономное общеобразовательное учреждение "Лицей №10" г. Перми, 3 ФГБОУ ВПО "Пермский государственный национальный исследовательский университет"
Доклад посвящен начальному знакомству с параллельными вычислениями в средней школе. В качестве площадки для апробации методики изучения темы используется "ТРИЗформашка" - ежегодный Интернет-конкурс для учащихся средней школы и студентов. Описываются задания на параллельные вычисления, которые в последние три года давались на конкурсе, накопленный опыт и дальнейшие планы.

Параллельные вычисления – одно из главных направлений развития computer science. На сегодня актуальной задачей является разработка меттдики изучения этой темы в средней школе. Но перед включением 'njq методики в школьную программу ей апробация необходима . В качестве площадки для апробации предлагается конкурс «ТРИЗформашка».

Конкурс «ТРИЗформашка» – это ежегодный Интернет-конкурс по информатике, системному анализу и ТРИЗ для учащихся средней школы и студентов [5] (сайт www.trizformashka.ru). В марте 2015 г. конкурс состоялся в 15-й раз.

Последние три года конкурс включает задания на параллельные вычисления [2, 3, 4, 6, 7]. Это задания следующих типов:

1.   Исполнение параллельных алгоритмов. Дается описание работы нескольких бригад, которые совместно строят некое сооружение. Требуется определить результата строительства, найти ошибки в алгоритме, оценить минимальные возможные сроки строительства и т.п. В качестве дальнего предшественника таких задач можно рассматривать  исполнителя «Стройка», который почти 20 лет назад был предложен в курсе «Алгоритмика» [1].

2.   Построение параллельных алгоритмов. Используется специально разработанная компьютерная игра «Танковый экипаж». Экипаж танка состоит из трех человек: наводчика, водителя и заряжающего. Требуется запрограммировать их совместные действия по выполнению боевой задачи.

3.   Чтение и понимнаие сетевого графика. Дается сетевой график, описывающий строительство некоего сооружения (мост, крепость). Требуется определить, что именно будет построено, сколько это потребует времени и рабочей силы, как будет выглядеть стройка через указанное время и т.п.

4.   Ярусно-параллельные формы. Дается схема некого сооружения (здания, лабиринта) и трудозатраты, связанные со строительством его частей. Требуется оценить минимальное время, рабочую силу, затраты и т.п.

5.   Согласование работы по ресурсам. Несколько персонажей готовят себе обед, используя для этого различную кухонную утварь в течение разного времени. Требуется, во-первых, распараллелить работу каждого персонажа (ставим варить суп, а пока он варится, стряпаем котлеты), во-вторых, согласовать работу нескольких персонажей на одной кухне (при ограниченном наборе ресурсов), в-третьих, составить график использования разных ресурсов разными персонажами.

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

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

Задания воспринимаются участниками конкурса как достаточно сложные. Количество выполнявших их команд колеблется от 10% до 40%  участников конкурса.

По мнению авторов, конкурс «ТРИЗформашка» оправдал себя в качестве апробационной площадки для отработки методики освоения параллелизма в средней школе и будет использоваться в этом качестве и дальше.

Доклад содержит описание заданий, предлагавшихся на конкурсе в течение трех лет, оценку их сложности, анализ решений, предложенных участниками конкурса, анализ допущенных ими ошибок, описание перспектив «параллельной тематики» на конкурсе «ТРИЗформашка».

Список использованных источников
  1. Алгоритмика: 5-7 классы: Учебник и задачник для общеобразоват. учебных заведений /А.К. Звонкин, А.Г. Кулаков, С.К. Ландо, А.Л. Семенов, А.Х. Шень. – М.: Дрофа, 1996.
  2. Дитер М.Л., Плаксин М.А. Параллельные вычисления в школьной информатике. Игра «Стройка». //Информатика в школе: прошлое, настоящее и будущее.: материалы Всеросс. науч.-метод. конф. по вопросам применения ИКТ в образовании, 6-7 февраля 2014 г. /Перм. гос. нац. иссл. ун-т. – Пермь, 2014. – С.258-261.
  3. Иванова Н.Г., Плаксин М.А., Русакова О.Л. Задачи на параллельное программирование в конкурсе «ТРИЗформашка-2013». //Информационные технологии в образовании. XXIII Международная конференция-выставка: Сборник трудов. Ч.II. – М.: Издательский отдел факультета ВМК МГУ им.М.В.Ломоносова, 2013. С.9-10.
  4. Иванова Н.Г., Плаксин М.А., Русакова О.Л. Конкурс «ТРИЗформашка» как площадка для апробации заданий на параллельное программирование. //Информатика в школе: прошлое, настоящее и будущее.: материалы Всеросс. науч.-метод. конф. по вопросам применения ИКТ в образовании, 6-7 февраля 2014 г. /Перм. гос. нац. иссл. ун-т. – Пермь, 2014. – С.233-236.
  5. Иванова Н.Г., Плаксин М.А., Русакова О.Л. ТРИЗформашка. //Информатика. N05 (606), 1-15.03.2010. С.3-19.
  6. Кучев А.Д., Плаксин М.А. Параллельные вычисления в школьной информатике. Игра «Танковый экипаж». //Информатика в школе: прошлое, настоящее и будущее.: материалы Всеросс. науч.-метод. конф. по вопросам применения ИКТ в образовании, 6-7 февраля 2014 г. /Перм. гос. нац. иссл. ун-т. – Пермь, 2014. – С.241-243.
  7. Плаксин М.А. О методике начального знакомства с параллельными вычислениями в средней школе. //Информатика в школе: прошлое, настоящее и будущее.: материалы Всеросс. науч.-метод. конф. по вопросам применения ИКТ в образовании, 6-7 февраля 2014 г. /Перм. гос. нац. иссл. ун-т. – Пермь, 2014. – С.256-258.
Тип выступления  Устное выступление
Уровень образования  Основное общее
Ключевые слова  информатика, параллельное программирование, методика, начальная школа, конкурс, ТРИЗформашка