Начало
Учебные материалы
Математические основы анализа алгоритмов
Асимптотические обозначения Основные классы эффективности Индукция и инвариант Нижние границы эффективности Тривиальная нижняя граница Информационно-теоретическая нижняя граница
Индукция и инвариант
*Рекурсия* -- это такой способ организации обработки данных, при котором функция вызывает сама себя
непосредственно, либо с помощью других функций.
*Итерация* -- способ организации обработки данных, при котором определенные действия повторяются многократно,
не приводя при этом к рекурсивным вызовам.
Любой алгоритм, реализованный в рекурсивной форме, может быть переписан в итерационном виде, и наоборот.
--
Для доказательства корректности рекурсивного и итерационного алгоритма применяется *принцип индукции*, который можно сформулировать так:
Пусть `P` -- это унарное отношение, такое, что `P(i)` либо истинно, либо ложно,
Тогда `[P(0) ^^ forall n in NN: (P(n) rArr P(n + 1))] rArr forall m in NN: P(m)`, где `NN={0,1,2,...}`
Сначала проверяем, что P(0) выполняется (это можно проверить непосредственной подстановкой в формулу), затем
показываем что `forall n in NN: (P(n) rArr P(n + 1))` (индукционный шаг), из чего следует что `forall m in NN: P(m)`.
--
В качестве примера пусть `P` равно логическому утверждению «сумма первых `i`
нечетных чисел равна `i^2`». P(0) соблюдается, поскольку сумма элементов множество из 0 нечетных чисел равна 0.
Предположим теперь, что наше логическое утверждение соблюдается для `n`, то есть сумма первых `n` нечетных чисел равна `n^2`,
то есть `1 + 3 + 5 + ··· + (2n - 1) = n^2` (это наша индукционная гипотеза, или индукционное допущение).
Рассмотрим сумму первых `(n + 1)` нечетных чисел,
`1 + 3 + 5 + ··· + (2n - 1) + (2n + 1) = n^2 + (2n + 1) = (n + 1)^2`,
--
Можно начать нашу индукцию с большего значения, чем 0. Мы имеем следующий обобщенный принцип индукции:
`[P(k) ^^ forall n >= k: (P(n) rArr P(n + 1))] rArr forall m >= k: P(m)`
*Принцип полной индукции* подобен принципу индукции, за исключением того,
что на индукционном шаге мы показываем, что если `P(i)` соблюдается для всех `i <= n`,
то `Р(n + 1)` тоже соблюдается, то есть индукционный шаг сейчас равен
`forall n(forall i <= n: P(i) rArr P(n + 1))`.
--
Рассмотрим вычисление полинома `P_n(x) = a_0 x^n + a_1 x^{n-1} + ... + a_{n-1}x + a_n` в точке `x_0`.
Определим функцию `f(0) = a_0`,
`f(n) = x_0 * f(n - 1) + a_n`, при `n > 0`.
С помощью индукции можно показать, что функция `f(n)` вычисляет значение `P_n` в точке `x_0`.
В итерационном виде алгоритм можно записать так:
`r larr a_0`
**for** `i in [1...n]` **do**
`quad r larr x_0 *r + a_i`
--
##### Инвариант
*Инвариант* -- это некоторое свойство, остающееся неизменным при выполнении какого-либо преобразования.
Инвариант используется для доказательства правильности результата, полученного итерационным алгоритмом.
Для доказательства завершения итерационного алгоритма используется
*принцип наименьшего числа*, который говорит, что каждое непустое подмножество натуральных чисел должно иметь наименьший элемент.
Прямым следствием данного принципа является то, что каждая убывающая неотрицательная последовательность целых чисел
должна завершиться.
--
Рассмотрим доску размера `8xx8`, из которой были удалены две клетки из противоположных углов.
Площадь доски равна `64 - 2 = 62` клетки. Теперь предположим, что у нас 31 кость домино размером `1 xx 2`.
Мы хотим показать, что доска не может быть ими покрыта.
Исследование всех возможных покрытий доски будет чрезвычайно трудоемким. Однако, применяя
инвариант, мы рассуждаем следующим образом: раскрасим клетки
как шахматную доску. Каждая кость домино, покрывающая две смежные клетки, покрывает 1 белую и 1 черную клетку,
и, следовательно, каждое размещение покрывает столько белых клеток, сколько оно покрывает черных клеток.
Инвариант состоит в том, что после размещения каждой новой
кости домино число покрытых белых квадратов совпадает с числом покрытых
черных квадратов. Число белых клеток и число черных клеток различаются на
2 -- противоположные углы, лежащие на одной диагонали, имеют один и тот же
цвет -- и, следовательно, никакое размещение костей домино не дает покрытия.
--
При проектировании итерационных алгоритмов нужно определить:
* *Инвариант цикла* `I` -- предикат, который истинен перед выполнением цикла и после каждой его итерации.
* *Ограничивающую функцию* `h` -- неотрицательную функцию, являющуюся верхней границей числа оставшихся итераций цикла.
--
{`Q`} `S_0`; **while** `P` **do** `S`; {`R`}
где `Q` -- предусловие, `R` -- постусловие, `P` -- условие продолжения цикла, `S_0` -- операторы инициализации, `S` -- тело цикла.
Операторы `S_0` должны сделать инвариант `I` истинным, а в качестве условия продолжения цикла `P` берется
предикат `h > 0`. Тело цикла `S` обеспечивает уменьшение ограничивающей функции `h` и сохранение инварианта `I`.
--
Напишите программу, выполняющую возведение числа `a` в степень `b`.\
`Q = [a in NN ^^ b in NN]`, `R = [z = a^b]`.\
Инвариант `I = [y >= 0 ^^ z * x^y = a^b]`.\
В качестве `S_0` можно использовать следующую совокупность присваиваний `x larr a; y larr b; z larr 1`.
Условие продолжения цикла `P` нам уже по существу дано, так как очередная итерация цикла должна происходить только при `y > 0`.
Величина `y` должна уменьшаться на каждой его итерации. Уменьшение `y` каждый
раз на единицу заведомо не позволит получить достаточно эффективную программу.
По этой причине необходимо уменьшать величину `y` более быстро, например, делить величину `y` пополам при четных `y`.
--
Так как после итерации цикла инвариант должен остаться истинным, то уже зная, как меняется `y`, вычисляем, как следует изменять `z`.
В результате находим, что при четных `y` величину `x` нужно возводить в квадрат, а при нечетных -- необходимо
умножать значение переменной `z` на `x`.
`x larr a; y larr b; z larr 1`
**while** `y>0` **do**
`quad` **if** `y mod 2=0` **then**
`quad quad quad y larr y//2; x larr x^2`
`quad` **else**
`quad quad quad y larr y-1; z larr z*x`
---
##### Задания для практики
1. Вы подошли вплотную к стене, не имеющей ни начала, ни конца. Известно, что в стене есть дверь, но вы не знаете в каком направлении и как долго нужно двигаться, чтобы найти эту дверь. Заметить дверь в стене можно, только подойдя непосредственно к ней и став напротив. Разработайте алгоритм, который бы позволял находить дверь в стене методом обхода не более чем за `О(n)` шагов, где `n` - не известное заранее число шагов между вашим первоначальным положением и дверью.
2. Предположим, что у нас есть плитка (швейцарского) шоколада, состоящая из нескольких долек, расположенных в прямоугольном узоре. Наша задача – разломить плитку на дольки (она всегда ломается вдоль линий между дольками) с минимальным количеством разламываний. Сколько разламываний потребуется? Выдвиньте обоснованную догадку и докажите ее по индукции.
3. Возьмем последовательность из одного бита "0". Далее выполняем N следующих шагов. На каждом шаге бит "0" заменяем на два бита "10", а бит "1" на два бита "01". После выполнения первого шага из последовательности "0" получается последовательность "10", после второго – "0110", после третьего – "10010110", после четвертого – "0110100110010110", и так далее. Определите количество соседних битов "00" в последовательности после `N`-го шага.
4. Если в календаре выбрать месяц, в котом можно отметить квадрат 4x4, то выбрав 4 числа, которые не стоят в одной строке или столбце, и сложив их значения, мы получим одно и тоже число. Почему?
5. "Кубитовая матрица" состоит из элементов трех типов: увеличителя (увеличивающего значение, полученное сверху или слева, на 1 и передающего его соответственно вниз или вправо), уменьшителя (уменьшающего значение, полученное сверху или слева, на 1 и передающего его соответственно вниз или вправо) и сохранителя (передающего значение, полученное сверху или слева, без изменений соответственно вниз или вправо). При подаче на входы кубитовой матрицы одинаковых значений на выходах все значения будут различны. Постройте кубитовую матрицу `6 xx 6`.\
Кубитовая матрица `2 xx 2`:\
``++``\
``-0``
