Алгоритмы

Алго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)}\).

j	θ_j	φ_j	b_j	a_j	Комментарий
0	ab	(Пустая строка)	1	2	Удалить одно a и одно b либо перейти к 2.
1	(Пустая строка)	c	0	0	Добавить c с левого края, перейти к 0.
2	a	b	2	3	Заменить все a на b .
3	c	a	3	4	Заменить все c на a .
4	b	b	0	5	Если b еще остались, повторить.

Рассмотрим вычисление НОД для пары (6, 3)

, где :=

означает описание текущего шага, ->

- действие, а =>

- переход на следующий шаг.

Итерация 1	Итерация 2
0 := aaaaaabbb -> aaaaabb => 1	0 := aaabbb -> aabb => 1
1 := aaaaabb -> caaaaabb => 0	1 := aabb -> caabb => 0
0 := caaaaabb -> caaaab => 1	0 := caabb -> cab => 1
1 := caaaab -> ccaaaab => 0	1 := cab -> ccab => 0
0 := ccaaaab -> ccaaa => 1	0 := ccab -> cc => 1
1 := ccaaa -> cccaaa => 0	1 := cc -> ccc => 0
0 := cccaaa => 2	0 := ccc => 2
2 := cccaaa -> cccbbb => 3	2 := ccc -> ccc => 3
3 := cccbbb -> aaabbb => 4	3 := ccc -> aaa => 4
4 := aaabbb => 0	4 := aaa => 5

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

Пусть 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
• Марков А.А., Нагорный Н.М. - Теория алгорифмов