Начало разработки алгоритма

Разделы: Информатика

В основе разработки алгоритма исходной задачи лежит следующая аксиома.

Аксиома о возможности построения алгоритма решения исходной задачи, она требует:

  1. задача может быть решена только в рамках формальной логики, поэтому текст задачи, для которой строится алгоритм, должен быть полным и допускать только однозначную трактовку, то есть задача должна быть формализована;
  2. каждый шаг построенного алгоритма должен быть однозначно понят исполнителем алгоритма,
  3. разрабатываемый алгоритм должен использовать только систему команд исполнителя, то есть каждый шаг алгоритма для исполнителя должен быть не только понятен, но и выполнимым;
  4. разработанный алгоритм должен быть. конечным.

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

Алгоритм решения задачи

Одним из основных алгоритмов является алгоритм решения задачи. В настоящее время существует множество всевозможных его вариантов. Авторы предлагают следующий алгоритм решения (любой решаемой) задачи, запишем его в виде сценария с детализацией:

Начало алгоритма

1. Постановка задачи:

  • анализ текста исходной задачи,
  • построение модели исследуемого объекта (или процесса) в рамках формальной логики и соответствующих естественно – научных представлений;
  • формализация текста задачи;

2. Построение алгоритма (для формализованной задачи):

  • разработка алгоритма,
  • его представление,
  • тестирование алгоритма;

Реализация алгоритма:

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

Составление документации (если есть необходимость).

КОНЕЦ АЛГОРИТМА

Рассмотрим в качестве примера постановки задачи следующую задачу.

Задача.
Имеется шляпа, галоши, трансформатор, секундомер. Определить высоту здания.

1.

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

2.

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

3.

Формулируем задачу:

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

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

Далее для формализованной задачи можно разрабатывать алгоритм решения.

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

Рассмотрим возможности построения алгоритма формализованной задачи.

Принцип нисходящего проектирования алгоритма

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

Принцип нисходящего проектирования алгоритма состоит в иерархически – последовательной разработке алгоритма от сложного к простому. Схематически стандартно предлагается следующее.

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

Основным следствием принципа нисходящего проектирования алгоритма (по мнению авторов) является следующее утверждение, относящееся к самому первому уровню детализации алгоритма:

Следствие. Для любого исполнителя, любая решаемая задача может быть разбита на три подзадачи:

  • ввод (исходной) информации,
  • обработка информации,
  • вывод результатов.

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

Подобное разбиение мы видим при решении задач физики, математики, химии и т. д. (дано…решение [в буквенном виде…числовое решение]…ответ) названия разные – суть одна.

Это определяется тем, что исходные данные вводятся извне. Данным исполнителем проводится обработка информации. Результат обработки выводится на внешние носители информации. Наиболее четко это видно на вычислительных задачах.

Таким образом, самый верхний уровень необходимо рассматривать как один неделимый блок – формулировка исходной (формализованной) задачи. Далее самый первый уровень детализации необходимо представляется тремя подзадачами. Назовем это ТРИЕДИНОЙ ЗАДАЧЕЙ АЛГОРИТМИКИ. Она едина потому, что каждая из подзадач отдельно от остальных не имеет смысла. И это три задачи, так как каждая из них достаточно замкнута, имеет свои особенности и, поэтому, может разрабатываться отдельно от остальных. А так как задач ВводаИнформации и ВыводаРезультатов ограниченное количество и они решаются отдельно, то далее принцип нисходящего проектирования алгоритма применяется только к задаче ОбработкиИнформации.

Триединая задача алгоритмики

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

Опр. ТРИЕДИНОЙ ЗАДАЧЕЙ АЛГОРИТМИКИ называется совокупность подзадач первого уровня детализации исходной формализованной задачи:

  • ВводИнформации,
  • ОбработкаИнформации,
  • ВыводРезультатов.

Каждую из этих задач можно рассматривать в данном алгоритме как вспомогательный алгоритм. В приложениях №№ 1, 2 (Приложение 1, Приложение 2) рассмотрены задачи Ввода/Вывода для простой переменной. Важно отметить, что разработку алгоритма любой решаемой задачи не только можно, а чаще и необходимо, начинать с триединой задачи алгоритмики.

В дальнейшем геометрическое представление триединой задачи удобно делать в виде:

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

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

НАЧАЛО_АЛГОРИТМА

  1. ВводИнформации(<имена_переменных_входного_потока>).
  2. ОбработкаИнформации(<имена_переменных_Входного_потока>; <имена_переменных_Выходного_потока>).
  3. ВыводРезультатов(<имена_переменных_Выходного_потока>).

КОНЕЦ_АЛГОРИТМА

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

Обобщая изложенное, можно утверждать, что…

В основе разработки алгоритма исходной задачи лежит следующая аксиома.

Аксиома о возможности построения алгоритма решения исходной задачи требует:

  1. задача может быть решена только в рамках формальной логики, поэтому текст задачи, для которой строится алгоритм, должен быть полным и допускать только однозначную трактовку, то есть задача должна быть формализована;
  2. каждый шаг построенного алгоритма должен быть однозначно понят исполнителем алгоритма,
  3. разрабатываемый алгоритм должен использовать только систему команд исполнителя, то есть каждый шаг алгоритма для исполнителя должен быть не только понятен, но и выполнимым;
  4. разработанный алгоритм должен быть . конечным.

Авторы предлагают следующий алгоритм решения (любой решаемой) задачи:

НАЧАЛО АЛГОРИТМА

  1. Постановка задачи:
  2. Построение алгоритма (по формализованной задаче):
  3. Реализация алогоритма.
  4. Составление документации (если есть необходимость).

КОНЕЦ АЛГОРИТМА

Первым шагом в построении алгоритма является, согласно принципа нисходящего проектирования алгоритма, ТРИЕДИНАЯ ЗАДАЧА АЛГОРИТМИКИ – это алгоритм решения формализоанной задачи. Он представляет исходную формализованную задачу как совокупность трех подзадач (вспомогательных алгоритмов):

НАЧАЛО АЛГОРИТМА

  • ВводИнформации,
  • ОбработкаИнформации,
  • ВыводРезультатов.

КОНЕЦ АЛГОРИТМА

При этом задачи ВводаИнформации и ВыводаРезультатом можно и нужно решать самостоятельно.

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