Полное построение алгоритма

1.1. Введение

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

Такую цель легче сформулировать, чем реализовать. Мир программирования усеян останками программ, которые когда-то считались готовым продуктом, ио впоследствии оказались неправильньши, неэффективньши, непонятными или непригодными по какой-то другой причине. Возможно, простейшее объяснение этого факта заключается в том, что ЭВМ - относительно новый и сложный инструмент, и требуется время для того, чтобы научиться хорошо им пользоваться. Не так легко овладеть ЭВМ как мощным инструментом для решения задач, особенно математических.

Цель этой главы - сделать первую попытку объяснить понятие полного построения алгоритма, основными этапами которого являются:

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

2. Построение модели.

3. Разработка алгоритма.

4. Проверка правильности алгоритма.

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

6. Анализ алгоритма и его сложности.

7. Проверка программы.

8. Составление документации.

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

1.2. Алгоритмы

Каждый, кто решал задачи с помощью ЭВМ, имеет некоторое интуитивное представление о значении слова «алгоритм». Кое-кто даже утверждает, что это одно из важнейших понятий вычислительной математики. «Официальное» определение из последнего (1971) издания

Оксфордского словаря английского языка гласит, что «algorithm» - это ошибочное написание слова «algorism», в свою очередь algorism считается более или менее синонимичным алгебре и арифметике, и это определение датируется девятым веком. Очевидно, современное употребление термина пока еще ограничено кругом людей, связанных с ЭВМ.

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

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

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

Очевидно, что в нашем определении есть некоторые недостатки. Можно избежать большинства этих недостатков, определив «математические машины» с очень точно указанными возможностями. Тогда мы скажем, что алгоритм - это некоторая процедура, которая может выполняться такой машиной. Подобные попытки определения алгоритма очень глубоки и трудны математически, и они слишком негибки для наших целей.

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

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

так). Такой компьютер может выполнять хранимую программу, которая состоит из допустимой последовательности команд, охватывающих все стандартные арифметические операции, операции сравнения, переходы и т. д. Обычно мы будем считать,, что .каждая такая команда выполняется за единицу времени. Простыми описаниями часть памяти может быть организована в одно-, двух- и трехмерные массивы (матрицы). Мы будем пользоваться языком Фортран в качестве модели возможностей нашей машины, когда нужно будет что-то конкретизировать.

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

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

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

Запись А-В означает оператор присваивания, т. е. переменной Л присваивается текущее значение В.

Algorithm МАХ. Даны N действительных чисел в одномерном массиве R{\), Ri2).....RiN), найти такие М и J, что

M=R{J)= max R{K).

1<K<N

В случае когда два или более элементов R имеют наибольшее значение, запоминается наименьшее значение J.

Шаг 0. [Установка в начальное состояние, или инициализация]

Set M<-Ri\); and /1. Шаг J. [iV=l?] If yv=l then STOP fi

В этом алгоритме fi и od используются соответственно для обозначения конца конструкций if и do. Более детально это будет обсуждаться в разд, 2,1.