Алгоритмическая спецификация задачи

Алгоритмическая спецификация задачи

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

Для каждой проблемы нам также нужно обозначить входы  и выходы . Это должно быть сделано формальным образом.

Но сначала давайте рассмотрим, можно ли перенести эти понятия в повседневную жизнь.

Примеры спецификации алгоритма

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

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

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

Пример  1

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

Спецификация проблемы:

Данные:
m  - место, где мы хотим построить дома
p - план строительства домов и их размещение на участке
b - субподрядчики и предоставленные ими материалы

Результат:
d  - дома построены на участке
n - количество домов

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

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

Пример  2

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

Спецификация проблемы:

Данные:
a  - более длинная сторона прямоугольника, положительное действительное число
b - более короткая сторона прямоугольника, положительное действительное число

Результат:
p  - площадь прямоугольника.

Алгоритм вычисления площади прямоугольника является одним из самых основных. Мы указали, что  a и b поскольку входы должны удовлетворять определенным условиям, в этом случае они должны быть положительными вещественными числами. a Добавление этой информации может показаться излишним, но  мы указываем, что только эти два числа  b считаются допустимыми входными данными.

Конечно, мы можем включить в алгоритм ситуацию, в которой кто-то дал бы другие данные, и тогда мы могли бы также по-другому сформулировать спецификацию алгоритма.

Помните, что при некорректных входных данных результат алгоритма может быть неверным.

Пример  3

Запишите алгоритм вычисления квадратного корня.

Спецификация проблемы:

Данные:
a  - целое число

Результат:
p  - квадратный корень числаa

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

Однако с формальной точки зрения у нас нет причин сомневаться, поскольку мы можем извлечь квадратный корень из отрицательного числа (используя мнимые числа). Следовательно, алгоритм с такой спецификацией может существовать и возвращать правильные результаты.

Важный!

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

Словарь

алгоритм

правило процедуры, ведущее (за конечное время) к решению данной проблемы

входные данные)

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

вывод (результат)

набор данных, полученный в результате алгоритма; для алгоритма площади фигуры это будет площадь фигуры

спецификация алгоритмической задачи (спецификация алгоритма)

описание проблемы, которую нужно решить с помощью входов и выходов