Теория и методика обучения и воспитания (по областям и уровням образования) | Мир педагогики и психологии №12 (65) Декабрь 2021

УДК 37.011.33

Дата публикации 30.12.2021

Алгоритмы без программ на уроках информатики

Лялин Андрей Васильевич
преподаватель кафедры прикладной математики и информатики, Вятский государственный университет, РФ, г.Киров

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

Algorithms without Programs at the Computer Science Lessons

Lialin Andrei Vasilevich
Lecturer of Applied Mathematics and Computer Science Department, Vyatka State University, Russia, Kirov

Abstract: Оne of the key content lines of school informatics, namely algorithmicization and programming, is analogous to the activities of a scientist. Therefore school informatics has big potential in the intellectual development of pupils. But there are many unsolved problems in teaching this line. For example, there is no smooth transition between algorithmization and programming. They are studied in textbooks at the same time. There are no tasks that ask pupils to discover an algorithm, execute it manually, but not to write a program for it. Although the content of computer science allows to formulate them. The article gives an example of a system of such tasks.
Keywords: school informatics, algorithm, program, system of tasks, scientific method, development of intelligence.

Правильная ссылка на статью
Лялин А.В. Алгоритмы без программ на уроках информатики // Мир педагогики и психологии: международный научно-практический журнал. 2021. № 12 (65). Режим доступа:https://scipress.ru/pedagogy/articles/algoritmy-bez-programm-na-urokakh-informatiki.html (Дата обращения: 30.12.2021)

Информатика постоянно развивается, обзаводится новыми областями, междисциплинарными связями и приложениями. Это отразилось и на школьной информатике. В ней сформировалось, как минимум, семь «содержательных линий» [1].

1. Информация и информационные процессы.

2. Представление информации.

3. Устройство компьютера.

4. Моделирование и формализация.

5. Алгоритмизация и программирование.

6. Информационные технологии.

7. Социальная информатика.

Ещё в 60-е годы прошлого века польский педагог Винценты Оконь показал, что «образование тем успешнее и тем больше развивает интеллект, чем больше ученик попадает на тот путь, по которому идёт учёный в ходе исследования» [2, с.54].

Именно линия  «алгоритмизация и программирование», среди этого разнообразия линий школьной информатики,  позволяет школьникам пройти по пути учёного, «в миниатюре», по тем же этапам, а значит, развивает их интеллект [3].

«Мне до сих пор кажется, что опыт составления программ самое ценное, что может получить школьник на уроках информатики. Не с точки зрения будущей профессии, ведь мало кто будет программистом, а с точки зрения интеллектуального развития» – писал математик и соавтор одного из учебников по информатике Александре Ханиевич Шень [4].

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

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

Далее мы приводим пример таких задач.

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

Найдите минимальный суммарный штраф и сам путь для такого поля (рис.1).

Рисунок 1. Клетчатое поле для задачи 1

Решение

Сначала найдём ответы для простейших подзадач. На их основе построим ответы для всё более сложных подзадач, пока не получим ответ для всей задачи. Этот метод называется динамическим программированием.

Обозначим таблицу со штрафами буквой P. В общем виде в ней n строк и m столбцов. Заведём дополнительную таблицу F тех же размеров, чтобы запоминать ответы для подзадач. Пусть F[i,j] – это минимальный штраф от начальной клетки до клетки (i, j). Наша цель – найти f[n,m]. Заполняем F постепенно (рис.1.1).

Рисунок 1.1. Решение задачи 1

Очевидно, F[1,1]=P[1,1].

В любую клетку первой строки, начиная со второй клетки, можно прийти только из клетки слева от неё. Поэтому первую строку таблицы F заполняем по формуле F[1,j]=F[1,j-1]+P[1,j]. К минимальному штрафу, который мы заплатим, добираясь до клетки слева, прибавляем штраф в самой клетке.

В любую клетку первого столбца, начиная со второй клетки, можно прийти только из клетки над ней. Поэтому первый столбец таблицы F заполняем по формуле  F[i,1]=F[i-1,1]+P[i,1].

В любую другую клетку можно прийти либо из клетки слева от неё, либо из клетки выше её. Выгоднее выбрать ту, где штраф минимальный. Поэтому заполняем оставшуюся часть таблицы F, строка за строкой, по формуле F[i,j]=min{F[i,j-1], F[i-1,j]}+P[i,j]. В итоге, f[n,m]=15.

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

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

Найдите минимальный суммарный штраф и сам путь для такого поля (рис.2).

Рисунок 2. Клетчатое поле для задачи 2

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

Найдите минимальный суммарный штраф и сам путь для такого поля (рис.3).

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

Найдите минимальный суммарный штраф и сам путь для такого поля (рис.3).

Рисунок 3. Клетчатое поле для задачи 3

Задача 4. Есть клетчатое поле. Нужно пройти из левой верхней в нижнюю правую. При этом из клетки разрешается шагать в клетку справа или снизу.

Найдите, сколько различных путей существует для такого поля (рис.4).

Рисунок 4. Клетчатое поле для задачи 4

Задача 5. Есть клетчатое поле. В опасных клетках стоит -1. В безопасных 0. Нужно пройти из левой верхней в нижнюю правую. При этом из клетки разрешается шагать в клетку справа или снизу, если, конечно, она безопасная. На опасные ступать нельзя.

Найдите, сколько различных путей существует для такого поля (рис.5).

Рисунок 5. Клетчатое поле для задачи 5

Задача 6. Есть клетчатое поле. В опасных клетках стоит -1. В безопасных указан штраф за их прохождение. Нужно пройти из левой верхней в нижнюю правую так, чтобы получить минимальный суммарный штраф. При этом из любой безопасной клетки разрешается шагать в клетку справа или снизу, а на опасные ступать нельзя.

Найдите минимальный суммарный штраф и сам путь для такого поля (рис.6).

Рисунок 6. Клетчатое поле для задачи 6

Задача 7. Есть клетчатое поле. Нужно пройти из левой верхней в нижнюю правую. При этом из клетки разрешается шагать в клетку справа или снизу и обязательно посетить указанную клетку.

Найдите, сколько различных путей существует для такого поля (рис.7).

Рисунок 7. Клетчатое поле для задачи 7

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

Найдите минимальный суммарный штраф и сам путь для такого поля (рис.8).

Рисунок 8. Клетчатое поле для задачи 8

Задача 9. Есть клетчатое поле. Нужно пройти из левой верхней в нижнюю правую. При этом из клетки разрешается прыгать на любую клетку справа или на любую клетку снизу.

Найдите, сколько различных путей существует для такого поля (рис.9).

Рисунок 9. Клетчатое поле для задачи 9

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

Найдите минимальный суммарный штраф и сам путь для такого поля (рис.10).

Рисунок 10. Клетчатое поле для задачи 10

Задача 11. Новогодняя. Есть клетчатое поле. Для каждой клетки указано, сколько там мандаринов. Разрешено из любой клетки шагать в клетку справа или снизу. Нужно пройти из левой верхней в нижнюю правую так, чтобы получить максимум мандаринов. Сначала путь совершает Матвей. После него – Маша и собирает мандарины из тех, что остались.

Найдите, какое наибольшее число мандаринов сможет собрать Маша после Матвея для такого поля (рис.11).

Рисунок 11. Клетчатое поле для задачи 11

Заметим, что приведённая последовательность задач является системой, а не простым набором. Они связаны общим методом решения и общим сюжетом, а также следуют в порядке усложнения, что позволяет ученикам многие из них решить самостоятельно. Кроме того, вся система получены из первой задачи, которая изначально была сформулирована как задача по программированию [5, c.96].

Примеры других задач на придумывание и выполнение алгоритма, но без программирования можно найти в [6 – 10].


Список литературы

1. Маркушевич М.В. Влияние содержательной линии «Формализация и моделирование» на методику преподавания информатики в основной школе // Информатика и образование. 2020. № 5. С. 5–11.
2. Оконь В. Основы проблемного обучения. – М.: Просвещение, 1968. – 208 с.
3. Лялин А.В. Информатика и развитие интеллекта школьников // Мир педагогики и психологии: международный научно-практический журнал. 2020. № 12 (53). Режим доступа: https://scipress.ru/pedagogy/articles/informatika-i-razvitie-intellekta-shkolnikov.html. (Дата обращения: 20.12.2021).
4. Шень А.Х. Информатика: Былое и думы // Компьютерра. 2001. №34(411). С. 22–26.
5. Окулов С. М. Программирование в алгоритмах. – М.: Бином. Лаборатория знаний, 2013. – 384 c.
6. Андреева Е.В. , Кириенко Д. П. Олимпиады по информатике для 7–8-х классов нового формата, или как привлечь не программирующих школьников к олимпиадам // Информатика. 2016. №3. С. 4–17.
7. Лялин А. В. Эффективность алгоритмов на уроках информатики // Современная педагогика. 2016. №11. Режим доступа: http://pedagogika.snauka.ru/2016/11/6313. (Дата обращения: 20.12.2021).
8. Лялин A. B., Окулов С. М., Котельникова А. В. Системы задач на уроках информатики // Мир педагогики и психологии: международный научно-практический журнал. 2017. №11. С. 83–87. Режим доступа: http://scipress.ru/pedagogy/wp-content/uploads/2017/11/Мир-педагогики-и-психологии-1116.pdf (Дата обращения: 20.12.2021).
9. Kubica, M., Radoszewski, J. Algorithms without Programming // Olympiads in Informatics. 2010. Vol. 4, P. 52–66.
10. Clark, D., Clapper, M. The Australian Informatics Competition // Olympiads in Informatics. 2014. Vol. 8. P. 179–189.

Расскажите о нас своим друзьям: