Рассмотрены примеры построения рекурсивных алгоритмов, проведена оценка их эффективности, показана значимость метода математической индукции, как инструмента анализа алгоритмов, также установлена взаимосвязь метода математической индукции и рекурсии.
В настоящее время происходят серьезные изменения в школьном образовании, оно становится личностно ориентированным, стремится удовлетворить интересы и образовательные потребности каждого школьника путем широкой дифференциации содержания образования. В старших классах дифференциация содержания образования происходит за счет различных сочетаний курсов трех типов: базовых, профильных и элективных. Именно элективные курсы связаны с удовлетворением индивидуальных образовательных интересов, потребностей и склонностей каждого школьника. Одними из факторов, определяющих содержание элективных курсов по информатике, являются интенсивный характер межпредметных связей информатики с другими учебными предметами, а также интегрирующая роль информатики в содержании общего образования человека [1].
Целью данной статьи является рассмотрение темы «Индукция и рекурсия», которая может быть изучена в рамках элективного курса естественно математического профиля. Выбор именно этой темы обусловлен большим познавательным и развивающим потенциалом, заложенным в фундаментальных свойствах рекурсивности многих объектов и процессов окружающей действительности.
В общем случае рекурсию можно рассматривать как наличие в некотором упорядоченном множестве объектов ссылок друг на друга, замыкающихся на начальный объект. Это позволяет провести аналогию между рекурсией и методом математической индукции.
Показав учащимся использование метода математической индукции для анализа эффективности рекурсивных алгоритмов, мы по существу подводим их к выводу, что информатика – это не обособленный предмет, что в основе информатики лежит математический аппарат. Так же это позволяет рассмотреть вопрос о выборе оптимального алгоритма для решения задачи. Очевидно, что умение выбирать эффективный и правильный метод решения задачи является важным не только в обучении, но и в практической деятельности.
Математическая индукция
Метод математической индукции (метод полной математической индукции) представляет собой способ индуктивно дедуктивного умозаключения, опирающегося на аксиому (основное свойство) ряда натуральных чисел, которую можно упрощенно сформулировать следующим образом: в каждом непустом множестве натуральных чисел существует наименьшее число.
Метод математической индукции используется в тех случаях, когда требуется доказать, что некоторое предложение P(n) справедливо для всех натуральных чисел n (множеством истинности предиката P(n) является множество натуральных чисел).
Применение метода математической индукции сводится к реализации трех этапов:
1. (База индукции) Проверить истинность P(1).
2. (Индуктивное предположение) Сделать предположение, что данный факт имеет место при n = k, то есть истинно P(k).
3. (Шаг индукции) Доказать теорему: если предположить существование доказываемого факта при n = k, то он имеет место и при n = k + 1, то есть истинно P(k + 1).
После реализации этих шагов делается вывод об истинности P(n) для всех натуральных n.
Рекурсия
Рекурсию можно рассматривать как метод разработки алгоритмов, суть которого сводится к следующему. Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова. Наконец, их решения комбинируются, и получается решение исходной задачи. Алгоритм, который получается в результате, то есть алгоритм вызывающий сам себя (прямо или косвенно) называется рекурсивным.
В общем случае, под рекурсией можно понимать наличие в некотором упорядоченном множестве объектов ссылок друг на друга, замыкающихся на начальный объект. Тогда решение сложной задачи можно рассматривать как решение более простых задач того же класса, в итоге сводящихся к первоначальной. Кажущаяся бесконечность и незавершенность ссылок может быть опровергнута путем рассмотрения вопроса о количестве рекурсивных обращений (глубине рекурсии). Важнейшей особенностью объекта, которая позволяет назвать его рекурсивным, является наличие в нем некоторой базы (базовых составляющих), доступной для непосредственного изучения, а также наличие внутренних связей во множестве всех составляющих объекта, которые позволяют любую из составляющих объекта выразить через базу по некоторой единой схеме. Использование рекурсивных объектов при решении прикладных задач позволяет вести речь о рекурсивных методах и алгоритмах. Из всего сказанного выше можно сделать вывод о необходимости более детального изучения рекурсии в рамках предметной области «Информатика».
Можно отметить сходство математической индукции и рекурсии. Метод математической индукции можно рассматривать как способ, позволяющий знание о свойствах некоторых натуральных чисел обобщить на весь натуральный ряд. Рекурсия же позволяет рассматривать решение сложной задачи как решение более простых задач того же класса, в итоге сводящихся к первоначальной, то есть позволяет обрабатывать большие и сложные наборы данных, основываясь на возможности обработки меньших или менее сложных наборов данных. Математическая индукция – это стандартный шаблон рассуждений для понимания рекурсивных процедур, это один из наиболее доступных способов анализа эффективности рекурсивных алгоритмов.
Анализируя эффективность алгоритма можно стараться найти точное количество выполняемых им действий, но в большинстве случаев достаточно дать некоторую оценку времени работы алгоритма при стремлении размера входа к бесконечности. Оценивая время работы рекурсивной процедуры, мы часто приходим к соотношению, которое выражает это время через время работы той же процедуры на входных данных меньшего размера. Такие соотношения называются рекуррентными. Одним из способов решить рекуррентное соотношение, то есть найти асимптотическую оценку для его решения является метод подстановки. Идея этого метода проста: «угадать» ответ и доказать его по индукции [2]. Рассмотрим несколько примеров применения метода математической индукции для доказательства эффективности алгоритмов.
Пример 1. Бинарный поиск.
Предположим, что нам нужно найти некоторый элемент в отсортированном массиве. Идея бинарного поиска состоит в следующем. Сравниваем искомый элемент со средним элементом в массиве, если искомый больше среднего, то продолжаем поиск в правой половине массива, иначе – в левой. Повторяем рекурсивное разбиение массива до тех пор, пока искомый элемент не будет найден. Опишем рекурсивную процедуру бинарного поиска binary_search (A, p, r) элемента b в части массива A[p…r] на языке Pascal (предполагаем, что элемент b присутствует в массиве A):
procedure binary_search (A: mas; p, r: integer);
begin
if p < r then q := (p + r) div 2;
if b < A[q] then binary_search (A, p, q – 1)
else if b > A[q] then binary_search (A, q + 1, r)
else writeln(‘Искомый элемент: ’, A[q], ‘его номер: ‘, q);
end;
Осуществить поиск во всем массиве можно с помощью вызова binary_search (A, 1, n), где n – длина массива А. Будем считать, что n – это степень двойки. Проанализируем эффективность этой процедуры.
Но в начале рассмотрим несколько понятий. Через T(n) будем обозначать время выполнения процедуры с исходным значением n. Под записью f(n) = (g(n)) будем понимать, что функция g(n) является асимптотической оценкой для функции f(n), то есть найдутся такие константы c1, c2 > 0 и такое число n0, что для всех n ≥ n0 выполняются неравенства 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n).
Запишем рекуррентное соотношение для оценки времени работы процедуры. Так как n – это степень двойки, то на каждом шаге поиска массив делится на две равные части. Заметим, что разбиение на части (вычисление границ p, q, q + 1 и r), так же как и поиск числа b (сравнение) требует времени (1). Тогда получаем следующее рекуррентное соотношение для времени работы процедуры:
??? (1.1)
Будем опускать начальное условие, имея в виду, что для небольших n T(n) = (1). Тогда рекуррентное соотношение (1.1) запишется в виде
T(n) = T([n/2]) + (1). (1.2)
Это допустимо, так как начальное условие (значение T(1)) влияет только на постоянный множитель, но не на порядок роста функции T(n).
Можно предположить, что асимптотическая оценка этого соотношения будет следующей T(n) = (log2 n). Докажем это по индукции. В качестве параметра индукции выберем степень двойки k.
1. (База индукции) при k = 0 соотношение не выполняется, так как log2 1 = 0. Но вспомним, что асимптотическая оценка должна выполняться для всех номеров, начиная с некоторого номера n0. Проверим k = 1 получаем T(2) = T(1) + (1) ≤ 0 + С2 = С2 log2 2. Аналогично, T(2) ≥ С1 log2 2. Таким образом, база индукции выполняется.
2. (Индуктивное предположение) Пусть оценка верна при k – 1, обозначим 2k через m, тогда верны следующие неравенства
c1 log2 [m/2] ≤ T([m/2]) ≤ c2 log2 [m/2].
4. (Шаг индукции) Докажем, что оценка выполняется и при k, то есть верно
c1 log2 m ≤ T(m) ≤ c2 log2 m.
Из рекуррентного соотношения (1.2) следует, что
T(m) = T([m/2]) + (1),
используя индуктивное предположение, получаем нижнюю оценку
T(m) ≥ c1 log2 [m/2] + (1) = c1 log2 m – c1 log2 2 + (1) ≥
≥ c1 log2 m – c1 + С1 ≥ c1 log2 m,
если взять С1 ≥ с1.
Аналогично можно получить и верхнюю оценку
T(m) ≤ c2 log2 [m/2] + (1) = c2 log2 m – c2 log2 2 + (1) ≤ c2 log2 m.
если взять С2 ≤ с2.
Таким образом, мы доказали, что T(n) = (log2 n), где n является степенью двойки. Можно показать, что это утверждение справедливо и при произвольном целом n. Очевидно, что для любого натурального числа n, справедливы неравенства 2k < n < 2k+1. Для значения n1 = 2k + 1 утверждение верно. Тогда для рассматриваемого n в худшем случае добавляется еще одно сравнение n < n1, и оценка также будет верна. При переходе к другому основанию логарифма логарифм просто будет домножаться на некоторую константу, поэтому основание логарифма можно не указывать и принять T(n) = (log n).
Рассмотрим еще один пример использования метода математической индукции.
Пример 2. Сортировка слиянием [3].
Пусть надо отсортировать массив. Разобьем эту задачу на три подзадачи. Сначала мы разбиваем массив на две половины меньшего размера. Затем отсортировываем каждую из половин отдельно. Затем соединяем два упорядоченных массива в один. И повторяем рекурсивное разбиение задачи на меньшие подзадачи до тех пор, пока длина массива не станет равна единице (любой массив длины единица можно считать упорядоченным). Напишем теперь рекурсивную процедуру сортировки слиянием Merge_Sort (A, p, r), которая сортирует участок A[p…r] массива А, не меняя остальную часть массива.
procedure Merge_Sort(A: mas; p, r: integer);
begin
if p < r then q := (p + r) div 2;
if p < q then Merge_Sort(A, p, q);
if q < r – 1 then Merge_Sort(A, q + 1, r);
Merge(A, p, q, r)
end;
Процедура Merge (A, p, q, r) соединяет уже отсортированные участки массива A[p…q] и A[q + 1…r] в один участок A[p…r].
Весь массив можно отсортировать с помощью вызова Merge_Sort (A, 1, n), где n – длина массива А. Так же, как и в предыдущем примере рассмотрим тот случай, когда n есть степень двойки. В этом случае в процессе сортировки сначала произойдет слияние пар элементов в отсортированные участки длины 2, затем слияние таких участков в отсортированные участки длины 4, и так далее до n, на последнем шаге соединяются два отсортированных участка длины n/2.
Так как длина массива – это степень двойки, то на каждом шаге сортируемый участок делится на две равные половины. Разбиение на части (вычисление границ p, q и q + 1, r) требует времени (1), а соединение двух отсортированных частей требует времени (n). Получаем следующее рекуррентное соотношение для оценки времени работы процедуры
??? (2.1)
Перепишем соотношение (2.1) в следующем виде
T(n) = T([n/2]) + (n). (2.2)
Можно предположить, что асимптотическая оценка соотношения (2.2) будет следующей T(n) = (n log2 n). Докажем это соотношение по индукции. В качестве параметра индукции, так же как и в предыдущем примере, выберем степень двойки k.
1. (База индукции) проверим k = 1 получаем
T(2) = T(1) + (2) ≤ 0 + 2 С2 = 2 С2 log2 2.
Аналогично, T(2) ≥ 2 С1 log2 2. Таким образом, база индукции выполняется.
2. (Индуктивное предположение) Пусть оценка верна при k – 1, обозначим 2k через m, тогда
c1 [m/2] log2 [m/2] ≤ T([m/2]) ≤ c2 [m/2] log2 [m/2].
5. (Шаг индукции) Докажем, что оценка выполняется и при k, то есть верно
c1 m log2 m ≤ T(m) ≤ c2 m log2 m.
Из рекуррентного соотношения (2.2) следует, что
T(m) = T([m/2]) + (m),
используя индуктивное предположение, получаем нижнюю оценку
T(m) ≥ c1 [m/2] log2 [m/2] + (m) = c1 m log2 m – c1 m log2 2 + (m) ≥
≥ c1 m log2 m – c1 m + С1 m ≥ c1 log2 m,
если взять С1 ≥ с1.
Аналогично получаем верхнюю оценку
T(m) ≤ c2 [m/2] log2 [m/2] + (m) = c2 m log2 m –
– c2 m log2 2 + C2 m ≤ c2 m log2 m,
если взять С2 ≤ с2.
Таким образом, мы доказали, что T(n) = (n log n). (Для натурального n, не являющегося степенью двойки соотношение доказывается аналогично предыдущему примеру.)
Таким образом, можно отметить тесную взаимосвязь рекурсии и индукции. Математическая индукция по существу является стандартным шаблоном рассуждений для анализа рекурсивных и циклических (как частного случая рекурсивных) алгоритмов. Без понимания индуктивного строения множества натуральных чисел (на котором основан метод математической индукции) не возможно понимание и грамотное использование рекурсии и цикла. Взаимосвязь рекурсии и индукции особенно отчетливо проявляется при анализе рекурсивных алгоритмов (оценке эффективности, доказательстве правильности работы). В свою очередь рассмотрение вопроса анализа алгоритмов имеет и самостоятельное значение, так как позволяет привести в систему знания по математике и программированию, обоснованно выбирать оптимальный способ решения задачи. Рассмотрение в школьном курсе информатики рекурсивного метода как альтернативного метода решения задач, способствует реализации принципа развивающего обучения. И только на основе изучения понятийного аппарата рекурсии, основных опорных схем рекурсивных вычислений, практического применения рекурсивных алгоритмов при решении задач, анализа эффективности таких алгоритмов можно говорить о процессе выработки у учащихся интеллектуальных и практических умений и навыков, интуиции при выборе метода решения задачи.
Примечания
1. Кузнецов, А. А. Информатика в профильной школе [Текст] / А. А. Кузнецов, Л. О. Филатова // Информатика и образование. 2003. № 6.
2. Кормен, Т. Алгоритмы: построение и анализ [Текст] / Т. Кормен, Ч. Лейзерсон, Р. Ривест. М., 2000. С. 59 62.
3. Там же. С. 26 29.
Даже летом нужно понимать, что подарки новогодние это одни из самых ожидаемых сюрпризов, о которых мечтают все дети.
