Алгоритмы

1.1 Основные определения: алгоритм, вход, результат; понятие правильного и неправильного алгоритма; псевдокод

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

1) Быть простым для понимания, перевода в программный код и отладки;

2) Эффективно использовать вычислительные ресурсы.

Алгоритм считают правильным (correct), если на любом допустимом входе он заканчивает работу и выдает результат, удовлетворяющий требованиям задачи. В этом случае говорят, что алгоритм решает (solve) данную вычислительную задачу. Неправильный алгоритм для некоторого входа может вообще не остановиться или дать неправильный результат. Алгоритм может быть описан различными способами, в том числе и при помощи псевдокода, принадлежащего более высокому уровню абстракции по сравнению с языками программирования высокого уровня (C#, Pascal, Basic и т.д.). В математическом пакете MathCAD при написании кода функций, определяемых пользователем, используется нотация, напоминающая описываемый ниже псевдокод.

Таблица 1.1 - Соглашения, лежащие в основе псевдокода

№	Описание
	Отступ от левого поля указывает на уровень вложенности (это позволяет отказаться от применения begin и end)
	Комментарий обозначается символом “►”.
	Циклы while, for, repeat и условные конструкции имеют тот же смысл, что и в языке Pascal.
	Символ “¬” имеет смысл оператора присваивания.
	Запись i ¬ j ¬ e обозначает j ¬ e; i ¬ j или i ¬ e.
	Переменная, обозначающая массив или объект, считается указателем на составляющие его данные.
	Все переменные (по-умолчанию) – локальные.
	Оператор доступа к элементу массива пишется в квадратных скобках [].
	Запись “A[1.. j ]” обозначает A[1], A[2], A[3]..A[ j ].
	Доступ к полю (field) объекта (object): field [ object ].
	Параметры в подпрограмму передаются по-значению (by value), но при передаче объекта его свойства копируются в виде указателей. Т.е. если в качестве параметра передается объект x, то присваивание x ¬ y снаружи заметить нельзя, а f [ x ] ¬ 5 можно.

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

Листинг 1.1 – Псевдокод алгоритма сортировки вставками

procedure InsertSort(n: integer;

var A: array[1..n] of integer);

var

i, j, Tmp: integer;

begin

for i:= 2 to n do begin

{Сохраняем текущий элемент}

Tmp:= A[i];

{Сдвигаем элементы, большие, чем текущий}

j:= i-1;

while (A[j] > Tmp) and (j > 1) do begin

A[j+1]:= A[j];

j:= j-1;

end;

{Вставляем текущий элемент}

A[j+1]:= Tmp;

end;

end;

Листинг 1.2 – Сортировка вставками