· постановка задачи;
· построение модели;
· разработка алгоритма;
· проверка правильности алгоритма;
· реализация алгоритма;
· анализ алгоритма и его сложности;
· написание программы на подходящем языке;
· отладка программы;
· составление документации.
Постановка задачи
Прежде чем понять задачу, следует её точно сформулировать. Это условие само по себе не является достаточным для понимания задачи, но оно абсолютно необходимо. Для плохо сформулированных задач полезны следующие вопросы:
· Понятна ли терминология, используемая в предварительной формулировке?
· Что дано? Что нужно найти? В чём состоит условие?
· Каких данных не хватает? Все ли они нужны?
· Являются ли какие-то имеющиеся данные бесполезными?
· Какие сделаны допущения?
Возможны и другие вопросы в зависимости от конкретной задачи. Часто после получения полных или частичных ответов на некоторые из вопросов их приходится ставить повторно.
Построение модели
Задача чётко поставлена, теперь нужно сформулировать для неё математическую модель. Это очень важный шаг в процессе решения, и его надо хорошо обдумать. Выбор модели существенно влияет на остальные этапы процесса решения.
Ясно, что невозможно предложить набор правил, автоматизирующих стадию моделирования. Большинство задач должно рассматриваться индивидуально. Тем не менее существует несколько полезных руководящих принципов. Выбор модели – в большей степени дело искусства, чем науки, и, вероятно, эта тенденция сохранится. Изучение удачных моделей – это наилучший способ приобрести опыт в моделировании.
Приступая к разработке модели, следует задать, по крайней мере, два основных вопроса:
· Какие математические структуры больше всего подходят для задачи?
· Существует ли решение аналогичной задачи?
Второй вопрос, возможно, самый полезный во всей математике. В контексте моделирования он часто даёт ответ на первый вопрос. Действительно, большинство решаемых в математике задач, как правило, являются модификациями уже решённых. Поскольку большинство из нас не обладает талантами великих математиков, то для продвижения вперёд приходится руководствоваться накопленным опытом.
Сначала нужно рассмотреть первый вопрос. Необходимо описать математически, что знаем, и что хотим найти. На выбор соответствующей структуры оказывают влияние следующие факторы: 1) ограниченность наших знаний относительно небольшим количеством структур; 2) удобство представления; 3) простота вычислений; 4) полезность различных операций, связанных с рассматриваемой структурой или структурами.
Сделав пробный выбор математической структуры, задачу следует переформулировать в терминах соответствующих математических объектов. Это будет одна из возможных моделей, если можно утвердительно ответить на такие вопросы:
· Вся ли важная информация задачи хорошо описана математическими объектами?
· Существует ли математическая величина, ассоциируемая с искомым результатом?
· Выявлены ли какие-нибудь полезные отношения между объектами модели?
· Можно ли работать с моделью? Удобно ли с ней работать?
Разработка алгоритма
Как только задача чётко поставлена и для неё построена модель, следует приступить к разработке алгоритма её решения. Выбор метода разработки, зачастую сильно зависящий от выбора моделей, может в значительной степени повлиять на эффективность алгоритма решения. Два разных алгоритма могут быть правильными, но очень сильно отличаться по эффективности.
Многие программисты затрачивают относительно небольшое время на стадию разработки алгоритма при создании программ – проявляется желание как можно быстрее начать писать саму программу. Однако этому побуждению не стоит поддаваться! На стадии разработки требуется тщательное обдумывание; нужно также уделить внимание двум предшествующим и первым трём следующим за стадией разработки этапам. Как и следует ожидать, все восемь перечисленных этапов являются взаимосвязанными. В особенности первые три сильно влияют на последующие, а шестой и седьмой этапы обеспечивают ценную обратную связь, которая может заставить нас пересмотреть некоторые из предшествующих этапов.
Правильность алгоритма
Доказательство правильности алгоритма – это один из наиболее трудных, а иногда и особенно утомительных этапов создания алгоритма.
Вероятно, наиболее распространенная процедура доказательства правильности программы – это прогон её на разных тестах. Если выданные программой ответы могут быть подтверждены известными или вычисленными вручную данными, возникает искушение сделать вывод, что программа «работает». Однако этот метод редко исключает все сомнения; может существовать случай, когда программа не сработает.
Можно предложить следующую методику доказательства правильности алгоритма [2]. Предположим, что алгоритм описан в виде последовательности шагов, например, от шага 0 до шага m. Постараемся предложить некое обоснование правомерности для каждого шага. В частности, может потребоваться лемма об условиях, действующих до и после пройденного шага. Затем постараемся предложить доказательство конечности алгоритма, при этом будут проверены все подходящие входные данные и получены все подходящие выходные данные. Подобный метод доказательства известен как «доказательство исчерпыванием»; это самый грубый из всех методов доказательства.
Подчеркнём тот факт, что правильность алгоритма ещё ничего не говорит о его эффективности. Исчерпывающие алгоритмы редко бывают хорошими во всех отношениях.
Реализация алгоритма
Как только алгоритм выражен, допустим, в виде последовательности шагов и есть уверенность, что он правильный, настаёт черёд реализации алгоритма, т. е. написание программы для ЭВМ.
Этот существенный шаг может быть довольно трудным. Во-первых, трудность заключается в том, что очень часто отдельно взятый шаг алгоритма может быть выражен в форме, которую трудно перевести непосредственно в конструкции языка программирования (например, для реализации данного шага потребуется целая подпрограмма). Во-вторых, реализация может оказаться трудным процессом потому, что перед тем, как начать писать программу, нужно построить целую систему структур данных для представления важных аспектов используемой модели. Чтобы сделать это, необходимо ответить, например, на такие вопросы:
· Каковы основные переменные? Каких они типов?
· Сколько нужно массивов и какой размерности?
· Имеет ли смысл пользоваться связанными списками?
· Какие нужны подпрограммы (возможно, уже записанные в памяти)?
· Каким языком программирования пользоваться?
Конкретная реализация может существенно влиять на требования к памяти и на скорость алгоритма.
Другой аспект построения программной реализации – это программирование “сверху–вниз”, которое состоит в преобразовании алгоритма в такую последовательность всё более конкретизированных алгоритмов, что окончательный вариант представляет собой программу для ЭВМ.
Сделаем одно важное замечание. Одно дело – доказать правильность конкретного алгоритма, описанного в словесной форме, другое – доказать, что данная программа, предположительно являющаяся реализацией этого алгоритма, также правильна. Таким образом, необходимо очень тщательно следить, чтобы процесс преобразования правильного алгоритма (в словесной форме) в машинную программу «заслуживал доверия».