1.3. Построение алгоритма решения задачи

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

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

Понятие алгоритма возникло задолго до появления ЭВМ. Слово алгоритм ведет начало от слова alqorithmy - латинской интерпретации имени знаменитого узбекского математика Аль-Хорезми. Как наука, алго­ритмизация начала выделяться среди других наук с создания в 1936 г. Э.Постом (США) и А.Тьюрингом (Англия) специальных алгоритмических систем для формализации различных процессов. Большой вклад в развитие теории алгоритмов внесли ученые Марков A.A., Колмогоров А.Н., Успенский В.А., Новиков П.С., Глушков В.М. и др.

Алгоритмизацию как науку можно разделить на две части:

• абстрактную теорию алгоритмов, занимающуюся созданием и изучением алгоритмических систем;

• прикладную теорию алгоритмов, которая на основе абстрактной теории определяет правила построения алгоритмов решения практических задач.

В прикладной теории понятие алгоритма определяется следующим образом:

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

Разработанный для решения задачи алгоритм должен обладать следующими свойствами:

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

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

3. Простотой (понятностью). Из чтения алгоритма, должно быть понятно, что должен делать пользователь, а что ЭВМ для исполнения алгоритма и как интерпретировать результаты выполнения алгоритма.

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

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

1.3.2. Средства записи алгоритма

Для чтения, а в некоторых случаях и исполнения алгоритма человеком, применяются следующие виды его записи: словесная запись, графическая схема, операторная схема, псевдокоды и алгоритмические языки.

I) Словесная запись алгоритма.

Алгоритм состоит из последовательности указаний (шагов), записанных в виде слов и формул.

Рассмотрим примеры записи алгоритма решения одной и то же задачи разными способам.

Пример. Составить алгоритм вычисления функции

Решение:

1) Взять число х .

2) Взять число а.

3) Сравнить х и а. Если x>a, то выполнить указание 4), если нет, то выполнить 5).

4) Вычислить y= х – а.

5) Присвоить y значение 0.

Достоинства словесной записи алгоритма:

• можно описать любой алгоритм, за исключением алгоритмически неразрешимых задач;

• сочетание символьно-формульного и словесного описаний обеспечивает понятность алгоритма.

Недостатки:

• низкая степень формализации задачи;

• малая компактность;

• плохая наглядность.