§3. Запись алгоритмов
Мы будем предполагать, что читатель знаком, хотя бы в общих чертах, с каким-нибудь языком программирования высокого уровня. Алгоритмы будем записывать на некотором специальном языке, который назовем упрощенным Паскалем, являющимся неформальной версией языка Паскаль.
Упрощенный Паскаль отличается от всех принятых языков программирования тем, что он разрешает использовать, любой тип математических предписаний, если только их значения понятны, а перевод в операторы Паскаля или любого другого языка высокого уровня очевиден. В этом языке возможно использование любого типа данных: тип данных какой-либо переменной и ее область действия должны быть ясны либо по ее названию, либо по контексту.
В упрощенном Паскале применяются традиционные конструкции математики и языков программирования такие, как выражения, условия, операторы и процедуры. Операторы языки Паскаль используются, как правило, в соответствии с правилами языка Паскаль, но иногда будут применяться неформальные конструкции такие, как, например, циклы for х ϵ X do Р, т.е. выполнять оператор Р для всех элементов х множества X в произвольной последовательности: x[ij ↔ x[j] — переставить i-ый и j-ый элементы массива; или описание типа: "пусть х — наименьший элемент множества X".
Будем также предполагать, что все операторы, записанные в одной строке алгоритма, образуют один составной оператор. Поэтому ключевые слова begin и end, идентифицирующие этот оператор, будут опускаться.
Предполагается, что читатель знаком с такими структурами данных, как массивы, списки, очереди и стеки. При работе с очередями и стеками будем использовать следующие обозначения:
СТЕК
х — поместить значение переменной х в
стек;
х
СТЕК — переменной х присвоить значение
вершины стека
СТЕК
— удалить вершину стека;
ОЧЕРЕДЬ
х — включить х в очередь;
х
ОЧЕРЕДЬ — переменной х присвоить
значение первого элемента очереди;
ОЧЕРЕДЬ — удалить первый элемент очереди.
Строки алгоритма будем обычно нумеровать с тем, чтобы можно было указать на "цикл 10", "блок 7." и т.п.
С тем, чтобы пояснить только что сказанное, разберем легкий пример. Пусть требуется написать алгоритм, который по заданному числовому множеству X, выдает значение минимального элемента этого множества — minX. Вот, например, как можно это сделать.
АЛГОРИТМ 1.1. ВЫБОР МИНИМАЛЬНОГО ЭЛЕМЕНТА
Данные: числовое множество X.
Результат: число minX - минимальный элемент X
begin
minX := +∞;
for х ϵ X do
if x < minX then minX := x;
end.
Разумеется, читателя не должен смущать оператор присваивания, стоящий в строке 2. Здесь имеется в виду, что переменной minX присвоено самое большое машинное число. Если множество X задано в виде массива с именем X длины n то строки 3 и 4 алгоритма могут быть записаны так:
3'. for i:=1 to n do
4'. if X[i] < minX then minX:= X[i]:
Поясним на этом же примере понятие сложности алгоритм Размером этой задачи естественно считать n — количество элементов во множестве X. Цикл в строках 3-4 работает ровно n раз. В строке 4 при каждом шаге цикла осуществляется одна операция сравнения и, в худшем случае, одна операция присваивания. Таким образом, в строках 3 и 4 проводится не более чем 2n операций. С учетом оператора присваивания в строке 2 получаем, что число шагов алгоритма не превосходит 2n+1. Значит сложность этого алгоритма есть О(n).
Алгоритмы такой сложности принято называть ничейными.
Повсюду в дальнейшем будем использовать следующие обозначения. Для произвольного вещественного числа х через |_x_|(читается дно х) и |¯х¯| (потолок х) будем обозначить соответственно наибольшее целое число, не превосходящее х, и наименьшее целое, не меньшее х. Например, |_2,5_| = 2, |_-2,5_| = -3, |_3,2_| = 4, |_-3,2_| = -3.
Все логарифмы, встречающиеся в пособии, являются логарифмами чисел по основанию 2. поэтому вместо log2x будем писать logx. Символ обозначает начало и конец доказательства какого – либо утверждения.