Конспект лекций по методике преподавания информатики, читаемых Микеровой Л.Н.

Информация готовится к публикации

(Автор приносит извинения за отсутствие ссылок на используемую литературу, т.к.этот материал еще обрабатывается и будут дополнения, в том числе и литература)

Неразрешенные алгоритмы

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

Например, только в XIX веке было доказано, что с помощью циркуля и линейки (т.е. исполнителя, допустимыми действиями которого являются геометрические построения с использованием циркуля, неограниченным раствором и бесконечной линейки без деления) нельзя решить задачу удвоения куба и трисекции угла (т.е. построить соответствующие алгоритмы). А ведь эти задачи известны с глубокой древности еще древними грекам было известно, что эти две задачи решаются с помощью других инструментов, иначе говоря, других исполнителей.

Можно поставить перед учениками вопрос: а существует ли такая задача, для решения которой нет алгоритма, каким бы ни был исполнитель? Что бы ответить на этот вопрос потребовалось создать новую науку - теорию алгоритмов. Теория алгоритмов - довольно молодая наука. Довольно интересно ученикам будет проследить ее развитие:
Её зарождение можно проследить в работах Брауэра и Вейля, опубликованных в 20-е годы XX века. В 1636 г. А. Черч, А. М. Тьюринг и Э.Л. Пост независимо друг от друга дали строгие определения понятия алгоритма, различающиеся по форме, но эквивалентные друг другу. Тогда же ими были построены первые примеры задач, для которых в принципе не существует решающих их алгоритмов. Такие алгоритмы получили название алгоритмически неразрешимых алгоритмов. Одним из наиболее ярких примеров алгоритмически не решенных задач является задача поиска целочисленных решений произвольного алгебраического уравнения с целыми коэффициентами. Вопросы существования алгоритма решения таких уравнений был сформулирован Давидом Пельбертом в 1900 году. И лишь в 1970 году наш соотечественник Ю. В. Матиясевич доказал отсутствие такого алгоритма.

Примеры алгоритмов с различными исполнителями

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

Задача 1

Это старинная задача под названием "Волк, коза и капуста"
Крестьянин стоит на левом берегу с волком, козой и капустой. Ему нужно перевести все это на правый берег, но его лодка слишком мала: он может взять только одного пассажира - либо волка, либо козу, либо капусту. И еще - если на одном береге оставить волка козу, то волк съест козу, а если оставить козу и капусту, то коза съест капусту. Только в присутствии крестьянина он не безобразничают. Как тут поступить?

Разобрав этот задачу, ученикам станет ясно, что исполнителем этого алгоритма будет крестьянин.

Задача 2

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

- Отмерить литр воды.

- Взять две ёмкости: двух и трёх литровые банки, и предложить Водолею при помощи этих банок отмерить литр воды.

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

- Имеется одна пяти и одна восьми литровая ёмкость. Используя эти ёмкости, Водолей должен наполнить однолитровую банку.

Задача 3

Данный исполнитель будет интересен ученикам 9 - 11 классов. Предположим у нас есть прибор, назовем его Удвоитель. На нем имеется экран с двумя клавишами. На экране написано число (обычно это число 0). При нажатии на первую кнопку число изображенное на экране увеличивается на 1, а при нажатии на вторую кнопку умножается на два. Здесь будет уместным разобрать с учениками примеры типа:

- Получите с помощью Удвоителя число 9.

- Получить число 17 меньше чем за 7 шагов.

- На экране написано число 4. Получить из него число 15 меньше, чем за 6 шагов.

Ученикам можно предложить в качестве соревнований (или на оценку) составить алгоритм получения какой-нибудь цифры за меньшее количество шагов.

Задача 4

Работать с предложенным ниже исполнителем будет интересно ученикам любого класса. Особенно полезно это будет тем ученикам, которые параллельно на уроках математики изучают "координатную ось".
На горизонтальной прямой, на одинаковом расстоянии друг от друга , нанесены точки. Одну из точек обозначим числом 0. Точки справа от неё обозначим числами - 1,2,3,4, ... . А точки слева числами - -1,-2,-,3,-4, ... . Такую прямую будем называть числовой осью. На числовой оси живёт исполнитель Кузнечик, будем обозначать его буквой К .

В начальный момент кузнечик находится в точке 0 числовой оси. Он может прыгать на три единицы вперёд и на две единицы назад.

- Составьте алгоритм, который переводит Кузнечика из точки 0 в точку 7.

- Перевести Кузнечика из точки 0 в точку 2.

- Заставить Кузнечика побывать по одному разу в каждой из точек 1,2,3,4,5, не выходя за приделы отрезка от 0 до 5.

- Кузнечик начал выполнение программы в точке 0, а закончил в точке 2. Затем та же программа была выполнена ещё раз. Где теперь оказался кузнечик?