Методика введения понятия алгоритма

Изучаемые вопросы:

ª Определение алгоритма.

ª Свойства алгоритма.

ª Типы алгоритмических задач.

Определение и свойства алгоритма.В учебника [6] дано следующее определение алгоритма: «Алгоритм — понятное и точное предписание исполнителю выполнить конечную последовательность команд, приводящих от исходных данных к искомому результату».

В этом определении содержатся основные понятия, связанные с алгоритмом и его главные свойства. Взаимосвязь понятий отражена на рис 11.1.

Рис. 11.1. Схема функционирования исполнителя алгоритмов

Центральным объектом в этой системе является ИСПОЛНИТЕЛЬ алгоритмов. Исполнитель — это тот объект (или субъект), для управления которым составляется алгоритм. Основной характеристикой исполнителя, с точки зрения управления, является система команд исполнителя (СКИ). Это конечное множество команд, которые понимает исполнитель, т.е. умеет их выполнять.

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

Другое свойство алгоритма — точность. Всякая команда должна быть сформулирована так, чтобы определить однозначное действие исполнителя. Например, кулинарный рецепт можно рассматривать как алгоритм для исполнителя-повара по приготовлению блюда. Но если одним из пунктов в нем будет написано: «Положить несколько ложек сахара», то это пример неточной команды. Сколько ложек? каких ложек (чайных, столовых)? Каждый повар может это понимать по-своему, и результаты будут разными. Пример точной команды: «Положить 2 столовые ложки сахара».

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

Еще одно свойство, которое отражено в определении алгоритма — конечность. Оно формулируется так: исполнение алгоритма и, следовательно, получение искомого результата должно завершиться за конечное число шагов. Здесь под шагом подразумевается выполнение отдельной команды. Это свойство является предупреждением ситуации, которую программисты называют зацикливанием. Бесконечно исполняемый алгоритм безрезультатен. Поэтому свойство конечности называют еще результативностью алгоритма.

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

«Свойство массовости выражается в том, что алгоритм единым образом применяется к любой конкретной формулировке задачи, для решения которой он разработан» [20]. Другими словами, это можно назвать универсальностью алгоритма по отношению к исходным данным решаемой задачи. Заметим, что данное свойство не является необходимым свойством алгоритма, а скорее определяет качество алгоритма: универсальный алгоритм лучше неуниверсального (алгоритм решения частной задачи — тоже алгоритм!).

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

1) выполнить роль исполнителя: дан алгоритм, формально исполнить его;

2) определить исполнителя и систему команд для данного вида работы;

3) в рамках данной системы команд построить алгоритм;

4) определить необходимый набор исходных данных для решения задачи.

В качестве примера задачи первого типа можно использовать алгоритм игры Ваше, рассматриваемый в учебниках [6, 8, 15]. В книгах [8, 15] правила игры определены так: в игре используются 7, 11, 15, 19 предметов. За один ход можно брать 1, 2 или 3 предмета. Проигрывает тот игрок, который берет последний предмет. Предлагается алгоритм выигрыша для первого игрока. В книге [6] правила несколько другие. В игре используются 11, 16, 21, 26,... предметов. За один ход можно брать от 1 до 4 предметов. Рассматривается алгоритм, благодаря которому всегда выигрывает игрок, берущий вторым.

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

Задача 1. «Разгадать загадку» алгоритма, т.е. объяснить, почему второй игрок всегда выигрывает (для варианта [6])?

Решение. По данным правилам второй игрок будет всегда выигрывать, если общее число камней определяется формулой: N = 5k + 1. Здесь k — любое натуральное число.

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

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

1. Взять 1 камень.

2. Предоставить ход сопернику; соперник взял п камней.

3. Если п + 1 < 5, то взять 5 — (п + 1) камней.

4. Предоставить ход сопернику.

И далее играть по выигрышному алгоритму для второго игрока.

Следующая задача требует от учеников незаурядных математических навыков.

Задача 3. Попробуйте провести математический анализ игры Баше в общем случае для N камней. Определите правила игры (т. е. сколько камней можно брать за один ход), при котором имеется выигрышный алгоритм. Опишите этот алгоритм в виде последовательности команд.

Решение. Выигрышный алгоритм для второго игрока можно построить только в тех случаях, когда исходное число камней (N) представимо в виде: N = Х´К+ 1, где X и К— натуральные числа. По правилам игры за один ход можно брать от 1 до X— 1 камней. Второй игрок будет всегда выигрывать, если своим ходом он будет дополнять число камней, взятых соперником, до X. Например, пусть N = 25. Это значение можно представить: 25 = 4´6 + 1. Следовательно, правило игры должно быть таким: за один ход можно брать 1— 2— 3 камня. А для того, чтобы второй игрок всегда выигрывал, в свой ход он должен дополнять ход соперника до 4 камней.

Следующая задача относится ко второму типу из приведенной выше классификации.

Задача 4.Назвать исполнителя следующего вида работы — выдача заработной платы; определить СКИ исполнителя.

Решение. Очевидно, исполнителя можно назвать «Кассир». Система команд, которые он должен уметь выполнять, следующая:

— найти в ведомости получателя;

— посчитать деньги;

— выдать деньги.

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

При построении СКИ решаются две проблемы: проблема элементарности команд и проблема полноты системы команд. Система команд исполнителя называется полной, если она содержит весь минимально-необходимый набор команд, позволяющий построить любой алгоритм в том классе задач, на который ориентирован исполнитель.

Рассмотрим еще один пример задания второго типа.

Задача5. Описать систему команд исполнителя «Геометр», который мог бы выполнять геометрические построения с помощью циркуля и линейки.

Решение. Ученикам знаком класс задач, которые в геометрии называются задачами на построение с помощью линейки, циркуля и карандаша. Полной системой команд для исполнителя «Геометр» является следующий список:

1. Провести отрезок прямой между двумя данными точками.

2. Установить раствор циркуля, равный длине данного отрезка.

3. Установить ножку циркуля в данную точку.

4. Провести окружность.

5. Выделить общие точки двух линий (пересечения или касания). Обратите внимание на элементарность каждой команды. Делить их на более простые не имеет смысла.

Следующая задача относится к третьему типу.

Задача 6.Записать для Геометра алгоритм решения следующей задачи: дан отрезок АВ; построить окружность, для которой отрезок АВ является диаметром.

Решение.

АлгоритмОКРУЖНОСТЬ ДАННОГО ДИАМЕТРА

Начало

установить ножку циркуля в т. А

установить раствор циркуля, равный АВ

провести окружность установить ножку циркуля в т. В

провести окружность

выделить точки пересечения окружностей: т. Сит. D

провести отрезок CD

выделить точку пересечения АВ и CD: т. О

установить ножку циркуля в т. О

установить раствор циркуля, равный ОВ

провести окружность

Конец

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

Задания четвертого типа относятся к проблеме постановки задач на построение алгоритмов. Для выполнения требуемой работы — решения данной задачи — необходим не только алгоритм, но и полный набор исходных данных, что отражено на приведенном выше рис. 11.1. Это могут быть какие-то материальные объекты (например, детали для сборки устройства; продукты для приготовления блюда и пр.) или информация (числовые данные для расчетов). Вот некоторые задачи на определение полного набора данных.

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

Ответ: количество каждого вида купленных товаров и цена рдиницы товара (1 кг или 1 штуки).

Задача 8.Определить полный набор данных для вычисления лесячной платы за расход электроэнергии.

Ответ: показания счетчика в конце предыдущего и в конце настоящего месяца, стоимость 1 квт/часа.

Задача 9.Определить полный набор данных для вычисления времени падения кирпича с крыши дома.

Ответ: высота дома, ускорение свободного падения (без учета сопротивления воздуха).

Не нашли, что искали? Воспользуйтесь поиском по сайту: