Лекция (СиАОД) 8. Лекция 8 Красников Степан Альбертович Москва 2022
 Скачать 2.53 Mb.
|
Структуры и алгоритмы обработки данных Лекция 8Красников Степан АльбертовичМосква 2022 Распознание рекурсии В программировании рекурсия понимается как мощная стратегия, позволяющая разрабатывать простые, компактные и изящные алгоритмы решения вычислительных задач. Говорят, что объект или понятие рекурсивны, когда в его состав входят более простые или меньшие подобные ему элементы. Примеры рекурсивных объектов Распознание рекурсии Рекурсию можно понимать, как процесс определения понятий через их собственные определения. Таким способом можно выразить многие математические формулы и определения. Самые очевидные примеры – последовательности, n-й член которых задаётся некоторой формулой или процедурой, использующей предыдущие члены. Рассмотрим следующее рекурсивное определение: sn = sn–1 + sn–2 Видно, что формула рекурсивна, так как определяемый ею объект s появляется в обеих частях уравнения. Таким образом, элементы последовательности явно определяются через самих себя. Декомпозиция задачи Основная задача рекурсивного мышления и программирования – дать наши собственные рекурсивные определения объектам, понятиям, функциям, задачам и т. д. И если первый шаг обычно сводится к выявлению начальных условий, то главная задача состоит в определении рекурсивных условий. В связи с этим важно усвоить понятия декомпозиции задачи и индукции. Декомпозиция – важное понятие в информатике, играющее главную роль не только в рекурсивном программировании, но и в решении задач вообще. Суть её состоит в разложении сложной задачи на меньшие и более простые подзадачи, которые проще выразить, вычислить, закодировать и решить. После чего решения подзадач используются для получения решения более сложной исходной задачи. Рекурсивное решение задачи Рекурсивный код Для использования рекурсии при разработке алгоритмов крайне важно знать, как разбить задачу на меньшие себе подобные и определить рекурсивные методы. Как только это сделано, дальше уже не составит труда преобразовать определения в код, особенно для таких базовых типов данных, как целые и вещественные числа, символы или логические (булевы) значения. Рассмотрим функцию, которая суммирует первые n целых положительных (натуральных) чисел. Обычный условный оператор – единственная управляющая конструкция, необходимая для реализации рекурсивной функции. Кроме того, внутри его тела обязательно должно быть имя функции, означающее рекурсивный вызов. Таким образом, мы говорим, что функция вызывает саму себя, или обращается к самой себе, и потому рекурсивна. Листинг 1. Суммирование первых n натуральных чисел Рекурсивный код Функции вычисления суммы первых n натуральных чисел в разных языках программирования Рекурсивный код Приведем листинг, соответствующий следующему рекурсивному определению: Рекурсивная функция использует каскадный условный оператор для выбора одного из двух начальных (строки 2–5) и рекурсивных условий (строки 6–11), где два последних дважды вызывает саму рекурсивную функцию. Рекурсивный код Закодируем функцию, вычисляющую n-е число Фибоначчи согласно стандартному определению: В листинге приводится соответствующий код, где оба начальных условия проверяются в логическом выражении условного оператора. Рекурсивный код Реализация функции Фибоначчи: требует большего количества действий. Если начальные условия идентичны, суммирование в рекурсивном условии нуждается в операторе цикла или иной функции для вычисления суммы значений F(1), F(2), ..., F(n – 2). В листинге приводится возможное решение с использованием цикла for. Результат сложения можно сохранить во вспомогательной переменной-сумматоре aux с начальным значением 1 (строка 5). Цикл for просто добавляет к вспомогательной переменной члены F(i) для i = 1, …, n – 2 (строки 6–7). В итоге функция возвращает вычисленное и сохранённое в aux число Фибоначчи. Индукция В математике доказательства методом индукции – это важный инструмент обоснования истинности некоторого утверждения. Простейшие доказательства касаются формул, зависящих от некоторого положительного (или неотрицательного) целого числа n. В таких случаях доказательства проверяют истинность формул для любого допустимого значения n. Метод индукции предполагает два шага:
Если можно доказать истинность обоих шагов, то согласно индукции из этого следует, что утверждение справедливо для всех n ≥ n0. Утверждение должно быть истинным для n0, а затем – для n0 + 1, n0 + 2 и так далее для каждого следующего шага индукции. Индукция Рассмотрим сумму первых n положительных чисел. Попробуем доказать справедливость следующего равенства (гипотеза индукции), содержащего квадратный полином: Начальное условие, очевидно, истинно, так как S(1) = 1(1 + 1)/2 = 1. А на шаге индукции мы должны показать, имеет ли силу при условии, что (*) верна. Для начала запишем S(n + 1) как (*) Затем, считая, что имеет силу (*), заменим сумму полиномом: Откуда видно, что (**) истинна, и на этом доказательство закончено. (**) Типы рекурсии. Линейная рекурсия Линейный тип рекурсии появляется, когда методы вызывают себя только однажды. Есть два типа линейно-рекурсивных методов, однако мы будем применять термин «линейная рекурсия», когда имеем дело с методами, которые так или иначе обрабатывают результат рекурсивно- го вызова до выдачи или возврата своего собственного результата. Например, функция вычисления факториала относится к этой категории, так как выполняет только один рекурсивный вызов, а результат подзадачи умножается на n, чтобы получить результат функции. Задача вычисления суммы первых n положительных целых чисел тоже является очевидным примерами линейной рекурсии. Следующая функция представляет собой другой пример функции Фибоначчи: где Φ = (1 + √5)/2 ≈ 1.618 – константа, известная под названием «золотое сечение», а ⌊ · ⌋ обозначает нижнюю границу. В этом случае F(n) = f(n) - n-е число Фибоначчи. Типы рекурсии. Хвостовая рекурсия Второй тип линейной рекурсии называют «хвостовой рекурсией». Методы, относящиеся к этой категории, также вызывают себя лишь однажды, но рекурсивный вызов – это последнее действие в рекурсивном условии. Следовательно, оно никак не влияет на результат рекурсивного вызова. Для примера рассмотрим следующую хвостовую рекурсивную функцию: В рекурсивном условии метод просто возвращает результат рекурсивного вызова, который не входит в математическое или логическое выражение. Поэтому рекурсивное условие определяет лишь отношение между наборами параметров, для которых функция возвращает одно и то же значение. Выполняя рекурсивные вызовы, алгоритм лишь изменяет параметры, пока нет возможности получить решение из начального условия. В этом случае числа Фибоначчи F(n) могут быть получены из f(n, 1, 1). Типы рекурсии. Множественная рекурсия Рекурсия множественного типа возникает, когда в каком-то рекурсивном условии метод вызывает себя несколько раз. Если метод вызывает себя дважды, то такой тип рекурсии называют «двойной рекурсией» («binary recursion»). Из приведённых ранее примеров к данному типу рекурсии относятся, например, функция Фибоначчи Следующая функция использует множественную рекурсию для альтернативного определения чисел Фибоначчи, где F(n) = f(n): Такой тип рекурсии обычно возникает в алгоритмах, разработанных согласно стратегии «разделяй и властвуй» Типы рекурсии. Взаимная рекурсия Говорят, что несколько методов относится к типу взаимно-рекурсивных, если они могут вызывать друг друга циклически. Например, функция f может вызывать другую функцию g, которая, в свою очередь, может вызвать третью функцию h, которая может завершаться вызовом первой функции f. Такую рекурсию называют ещё «косвенной», поскольку метод вызывает себя не непосредственно внутри своего тела, а через циклическую цепочку вызовов. Например, рассмотрим две следующие функции Фибоначчи: Ясно, что A рекурсивна, так как вызывает саму себя, но рекурсия в B – косвенная, так как вызывает A, которая, в свою очередь, вызывает B. Таким образом, рекурсия возникает из-за того, что вызов B может породить другие вызовы B (в более простых экземплярах задачи). Эти функции также могут применяться для генерации чисел Фибоначчи. В частности, F(n) = B(n) + A(n). Типы рекурсии. Вложенная рекурсия Вложенный тип рекурсии возникает, когда аргумент рекурсивной функции содержит другой рекурсивный вызов. Рассмотрим следующую функцию Фибоначчи: Второй параметр рекурсивного вызова – выражение, включающее в себя еще один рекурсивный вызов функции. В этом случае числа Фибоначчи F(n) могут быть получены из f(n, 0). Такой тип рекурсии редок, но появляется в некоторых задачах и контекстах, связанных с хвостовой рекурсией. Временнáя сложность вычислений Временнáя сложность алгоритма – это теоретическая оценка времени или количества операций, необходимых для решения задачи. Временнáя сложность определяется некоторой функцией T, зависящей от исходного размера задачи и подсчитывающей количество операций для выполнения конкретной задачи. В информатике эффективность алгоритмов обычно определяется поведением функции T при достаточно больших размерах задачи. Более того, ключевым фактором становится скорость роста функции T при стремлении размера задачи к бесконечности. Порядок роста функций Функция T(n) оценки времени выполнения алгоритма может содержать несколько слагаемых, которые по-разному влияют на её значение для заданного размера задачи n. Пусть, например, T(n) = 0,5n2 + 2000n + 50 000. При небольших значениях n все слагаемые почти в равной степени влияют на рост T(n). Однако с увеличением n первое слагаемое (0,5n2) начинает влиять на рост функции значительно больше, чем два других (даже вместе взятых). Следовательно, порядок роста функции характеризуется её старшим членом. Порядок роста функции определяется её старшим членом. Для T(n) = 0,5n2 + 2000n + 50 000 порядок роста – квадратичный, поскольку для больших значений n её старший член 0,5n2, очевидно, доминирует над младшими (даже взятыми вместе) Порядок роста функций На рисунке приведены графики наиболее распространённых функций, характеризующих порядок роста вычислительной сложности. Для достаточно больших значений n их можно упорядочить следующим образом: 1 < log n < n < n log n < n2 < n3 < 2n < n! Задачи, которые не могут быть решены за полиномиальное время, обычно считаются трудноразрешимыми, так как время их выполнения довольно велико даже при умеренных размерах. Напротив, задачи, которые могут быть решены за полиномиальное время, считаются легкоразрешимыми. Однако граница между лёгкими и трудными задачами довольно условна. Рекуррентные соотношения Время выполнения или количество операций, выполняемых рекурсивным алгоритмом, определяется рекуррентными соотношениями (или просто рекуррентностью), то есть некоторой математической рекурсивной функцией T, определяющей стоимость вычисления этого алгоритма. Рассмотрим код из листинга, который суммирует первые n положительных целых чисел. Во-первых, число операций, которые он должен выполнить, очевидно, зависит от входного параметра n. Следовательно, T будет функцией n. В начальном условии (при n = 1) метод выполняет основные действия, приведённые на рисунке. Рекуррентные соотношения Перед их выполнением программа должна сохранить низкоуровневую информацию (например, параметры или адрес возврата). Считаем, что это требует a0 единиц времени, где a0 – просто константа. Следующее действие – проверка условия со временем выполнения a1. Поскольку результат – True, следующее действие – это переход к третьей строке метода, который требует a2 единиц времени. Наконец, на последнем шаге метод возвращает значение 1, требуя a3 единиц времени. Итого при n = 1 методу нужно a = a0 + a1 + a2 + a3 единиц времени. Таким образом, можно считать, что T(1) = a. Точное значение a для асимптотической сложности вычисления метода безразлично. Важно только то, что a – постоянная величина, не зависящая от n. Рекуррентные соотношения Действия при выполнении рекурсивного условия (когда n > 1) приведены на рисунке. Пусть – общее время выполнения основных действий (сохранение низкоуровневой информации, проверка условия, переход к рекурсивному условию, вычитание единицы из n, добавление n к результату рекурсивного вызова и возвращение результата), также являющееся константой, точное значение которой не важно для асимптотической сложности вычисления. Но, кроме b, необходимо оценить время на рекурсивный вызов. Поскольку он решает полную задачу размера n – 1, можно определить его как T(n –1), а всё рекуррентное соотношение T(n) можно определить следующим образом: где, например, T(3) = T(2) + b = T(1) + b + b = a + 2b. Рекуррентные соотношения Хотя T правильно описывает стоимость вычисления алгоритма, выяснить порядок её роста непросто из-за её рекурсивности. Поэтому следующим шагом анализа будет преобразование рекурсивной функции в эквивалентную нерекурсивную формулу. Этот процесс называют «решением» рекуррентного соотношения. В данном случае нетрудно видеть, что T(n) – линейная функция n: T(n) = b(n – 1) + a = b · n – b + a ∈ Θ(n). |