Алгоритмы

Алгоpитм – это строго определенная последовательность действий, необходимых для решения данной задачи.

Алгоpитм имеет пять важных особенностей.

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

Название "алгоритм" берет начало от имени автора знаменитого персидского учебника по математике, Abu Abd Allah Muhammad ibn Musa al-Khwarizmı (Абу Абд Аллах Мухаммед ибн Муса аль-Хорезми) (ок. 825 г.), означающего буквально "Отец Абдуллы, Мухаммед, сын Мусы, уроженец Хорезма". Аральское море в Центральной Азии когда-то называлось озером Хорезм, и район Хорезма (Khwarizm) расположен в бассейне реки Амударьи южнее этого моря. Аль-Хорезми написал знаменитую книгу Kitab aljabr wal-muqabala (Китаб аль-джебр валь-мукабала — "Книга о восстановлении и противопоставлении"). От названия этой книги, которая была посвящена решению линейных и квадратных уравнений, произошло еще одно слово— "алгебра".

Более формальное определение:

Определим метод вычислений как четверку (Q, I, Ω, f), где Q — это множество, содержащее подмножества I и Ω, а f — функция, переводящая множество Q в себя. Кроме того, f оставляет неподвижными точки множества Ω, т.е. f(q) равно q для всех элементов q из множества Ω. Эти четыре элемента, Q, I, Ω, f, представляют соответственно состояния вычисления, ввод, вывод и правило вычислений. Каждое входное значение x из множества I определяет вычисляемую последовательность \(x_{0}, x_{1}, x_{2}, ...\) следующим образом: \(x_{0} = x\) и \(x_{k+1} = f(x_{k})\) для \(k \geq 0\). Говорят, что вычисляемая последовательность заканчивается через k шагов, если \(k\) — это наименьшее целое число, для которого \(x_{k}\) принадлежит Ω, и что она дает выходное значение \(x_{k}\) для заданного \(x\). (Заметим, что если \(x_{k}\) принадлежит Ω, то и \(x_{k+1}\) принадлежит Ω, так как в этом случае \(x_{k+1} = x_{k}\).) Некоторые вычисляемые последовательности могут никогда не заканчиваться, но алгоритм — это метод вычислений, который заканчивается через конечное число шагов для всех x из I.

Эффективный формальный алгоритм

В этой формулировке понятия "алгоритм" не содержится ограничение, касающееся эффективности. Например, \(Q\) может быть множеством бесконечных последовательностей, которые нельзя вычислить с помощью карандаша и бумаги, а \(f\) может включать операции, далеко не всегда выполнимые простому смертному. Если мы хотим ограничить понятие "алгоритм" таким образом, чтобы в нем могли содержаться только элементарные операции, то введем ограничения на элементы \(Q\), \(I\), \(Ω\) и \(f\), например, следующим образом. Пусть \(A\) — это ограниченное множество букв, а \(A^{*}\) — множество всех строк, определенных на множестве \(A\) (т.е. множество всех упорядоченных последовательностей \(x_{1}x_{2}...x_{n}\), где \(n \geq 0\) и \(x_{j}\) принадлежит \(A\) для \(1 \leq j \leq n\)). Идея заключается в следующем: закодировать состояния вычисления таким образом, чтобы они были представлены строками из множества \(A^{*}\). Теперь пусть \(N\) — целое неотрицательное число, а \(Q\) — множество всех пар \((\sigma, j)\), где \(\sigma\) принадлежит \(A^{*}\), а \(j\) — целое число, \(0 \leq j \leq N\). Пусть \(I\) — подмножество пар из \(Q\), для которых \(j = 0\), а \(Ω\) — подмножество пар из \(Q\), для которых \(j = N\). Если \(\Theta\) и \(\sigma\) — строки из \(A^{*}\), то мы будем говорить, что \(\Theta\) входит в \(\sigma\), если \(\sigma\) имеет вид \(\alpha\Theta\omega\), где \(\alpha\) и \(\omega\) — некоторые строки. И в завершение определим функцию \(f\) с помощью строк \(\Theta_{j}\), \(\phi_{j}\) и целых чисел \(a_{j}\), \(b_{j}\), \(0 \leq j < N\) следующим образом:

• \(f(\sigma, j) = (\sigma, a_{j})\), если \(\Theta_{j}\) не входит в \(\sigma\);
• \(f(\sigma, j) = (\alpha\phi_{j}\omega, b_{j})\), если \(\alpha\) является самой короткой строкой, для которой \(\sigma = \alpha\Theta_{j}\omega\);
• \(f(\sigma, N) = (\sigma, N)\)

Пример описания эффективного формального алгоритма

взят из упражнения 1.1.8 "Искусства программирования"

Пример эффективного формального алгоритма вычисления наибольшего общего делителя целых положительных чисел \(m\) и \(n\). Пусть входные данные представлены строкой \(a^{m}b^{n}\), т.е. за \(a\), взятым \(m\) раз, следует \(b\), взятое \(n\) раз.

Эффективный формальный алгоритм может выглядеть так:

Пусть \(A = {a, b, c}, N = 5\). Выполнение алгоритма закончится тогда, когда получим строку \(a^{gcd(m, n)}\).

Рассмотрим вычисление НОД для пары (6, 3), где := означает описание текущего шага, -> - действие, а => - переход на следующий шаг.

Математическая индукция

Пусть P(n) — некоторое утверждение, касающееся целого числа n. Предположим, нужно доказать, что утверждение P(n) верно для всех положительных целых чисел n. Важный метод доказательства этого факта состоит в следующем:

• a) Доказать, что P(1) верно.
• b) Доказать, что "если P(1), P(2), ..., P(n) справедливы, то P(n + 1) также справедливо"; это доказательство должно иметь силу для любого целого положительного n.

Этот метод называется доказательством методом математической индукции.

Ссылки:

• The Art of Computer Programming - Donald E. Knuth
• Марков А.А., Нагорный Н.М. - Теория алгорифмов