Алгоритмы и программы

Алгоритмы и программы.

Алгоритм - это некоторое правило преобразования информации, применение которого к заданной (исходной) информации приводит к резуль­тату - новой информации. Так, например, применение правила сложения дробей к 1/2 и 2/3 приводит к результату 5/6. Основное внимание в теории алгоритмов уделяется методам задания (описания, констру­ирования) алгоритмов.

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

Характерные свойства алгоритмов.

Понятию алгоритма присущи следующие свойства:

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

Понятие элементарности поэтому относительно. Так, в алгоритме примера 1 содержится команда вычисления НОД двух чисел. Это означает, что Исполнитель умеет находить НОД, причем алгоритм вычисления (алгоритм Евклида или какой нибудь другой) скрыт от человека, составляющего алгоритмы для этого Исполнителя. Если набор команд Исполнителя не содержит команды вычисления НОД, вычисление НОД должно быть определено в виде алгоритма.

Пример: Алгоритм Евклида вычисления наибольшего общего делителя целых положительных чисел A и B: НОД(A, B).

Вход A, B;

Вычислить U = A;

Вычислить V = B;

Пока U <> V выполнять

Если U < V

то Вычислить V = V - U

иначе Вычислить U = U - V;

Вычислить D = U.

Выход: D - наибольший общий делитель A и B.

В этом примере использована команда повторения.Она имеет вид

Пока <Условие> выполнять <Команда>

Выполняя эту команду, Исполнитель проверяет истинность Условия. Если Усло­вие истин­но, Исполнитель выполняет Команду, указанную после слова выпол­нять и повторяет проверку Условия. Выполнение Команды и проверка Условия повторяются до тех пор, пока Условие истин­­но. Если Условие ложно, Исполнитель переходит к выполнению команды, следующей за командой пов­то­рения. В этом же примере использована еще одна разновидность команды ветвления - команда вида

Если <Условие> то <Команда 1> иначе < Команда 2>

Выполняя эту команду, Исполнитель проверяет Условие. Если Условие выполнено, выпол­няется Команда 1, в противном случае выполняется команда 2. Далее Исполнитель переходит к сле­дующей команде. Заметим, что команда повторения, как и команды ветвления, содержат в себе другие команды.

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

Так, в исполнении алгоритма в примере 3 возможны ветвления, которые, однако, одно­значно определены условиями D < 0, D = 0.

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

Так, в примере 2 описан алгоритм сложения любых двух дробей. Одна-единственная задача, решаемая Исполнителем в данный момент, определена значениями исходных данных A, B, C, D. Изменение исходных данных означает решение другой задачи из этого же класса задач.

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

4. Результативность. Исполение любого алгоритма должно быть закончено через конеч­ное число шагов (т.е. выполнение конечного числа команд) с некоторым результатом. Так, в примере 2 результат - точка E - середина отрезка AB. Алгоритм примера 3 выдает результат “Решений нет “ даже в том случае, когда уравнение не имеет действительных корней, поскольку его дискриминант меньше нуля.