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

Лекция № 7 Алгоритмы и способы их описания.

1. Понятие и свойства алгоритма.

2. Виды алгоритмов и их реализация.

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

4. Средства изображения алгоритмов.

5. Блок – схема.

 

Понятие и свойства алгоритма.

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

Свойства, которыми должен обладать алгоритм:

1. Конечность (финитность) алгоритма. Алгоритм должен приводить к решению задачи обязательно за конечное время. Последовательность правил, приведшая к бесконечному циклу, алгоритмом не является.

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

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

4. Массовость алгоритма. Это означает, если правильный результат по алгоритму получен для одних исходных данных, то правильный результат по этому же алгоритму должен быть получен и для других исходных данных, допустимых в данной задаче.

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

Виды алгоритмов и их реализация.

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

· механические, или детерминированные (жесткие);

· гибкие, или стохастические (вероятностные и эвристические).

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

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

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

В программировании алгоритмы подразделяются на три типа:

· линейный – набор команд (указаний), выполняемых последовательно друг за другом;

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

· циклический – алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными. К циклическим алгоритмам сводится большинство методов вычислений и перебора вариантов.

Вспомогательный (подчиненный) алгоритм – алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи.

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

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

Полное построение алгоритма предусматривает выполнение следующих последовательно друг за другом этапов:

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

2) построение модели;

3) разработка алгоритма;

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

5) реализация, т.е. программирование алгоритма;

6) анализ алгоритма и его сложности;

7) проверка (отладка) программы;

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

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

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