Лекция 2. Способы записи алгоритмов

Решение любой задачи на ЭВМ состоит из нескольких этапов, основными из которых являются следующие (модель «Семь +»):

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

2. формализация задачи (математическая постановка);

3. выбор или разработка численного метода решения;

4. разработка алгоритма (алгоритмизация);

5. составление программы;

6. отладка и тестирование;

7. внедрение и поддержка.

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

Постановка задачи. На этом этапе анализируется:

· конечная цель решения задачи;

· существует ли решение задачи и единственно ли оно;

· общие свойства рассматриваемого объекта или явления;

· возможности конкретной ЭВМ и системы программирования.

Формализация задачи. На этом этапе строится математическая модель рассматриваемого явления:

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

· определяется специфика и объем исходных данных;

· вводится система условных обозначений.

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

Алгоритмизация. Как правило, составление алгоритма проводится методом "проб и ошибок", проходит несколько этапов детализации. В практике могут использоваться различные способы описания алгоритма, из которых наибольшее распространение получили:

· словесная запись алгоритмов;

· блок-схемы;

· R-схемы;

· структурограммы.

Программирование (кодирование) - это перевод алгоритма в форму, допускающую ввод данных в машину и последующий их перевод на машинный язык.

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

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

Поддержка - процесс усовершенствования внедренной программы. Сюда входит три вида деятельности:

· обнаружение и исправление ранее не замеченных ошибок;

· внесение изменений в программу (модификация) с целью повышения ее производительности;

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

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

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

2. Определенность. Это означает, что каждое правило алгоритма строго однозначно и исполнитель должен быть в состоянии выполнить каждую команду алгоритма в строгом соответствии с ее назначением.

3. Результативность алгоритма предполагает, что его исполнение сводится к выполнению конечного числа действий и всегда приводит к некоторому результату.

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

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

1. Словесное описание алгоритма на естественном языке (вербальная форма).

2. Построчная запись алгоритма (более строгое описание на естественном языке).

3. Представление алгоритма в виде блок-схемы.

4. Способ изображения алгоритма с помощью структурограммы (схема Насси-Шнейдермана).

5. Запись алгоритма на каком-либо языке программирования.

Рассмотрим особенности каждой из этих форм на примере алгоритмизации задачи нахождения наибольшего общего делителя (НОД) двух целых положительных чисел методом последовательного вычитания (алгоритм Евклида).