Подразделы

Другие разделы

Дата и время

05/04/2025 23:48:24

Авторизация

Математические основы анализа алгоритмов

Асимптотические обозначения Основные классы эффективности Индукция и инвариант Нижние границы эффективности Тривиальная нижняя граница Информационно-теоретическая нижняя граница

Индукция и инвариант

Индукция

Рекурсия – это такой способ организации обработки данных, при котором функция вызывает сама себя непосредственно, либо с помощью других функций.

Итерация – способ организации обработки данных, при котором определенные действия повторяются многократно, не приводя при этом к рекурсивным вызовам.

Любой алгоритм, реализованный в рекурсивной форме, может быть переписан в итерационном виде, и наоборот.

Для доказательства корректности рекурсивного и итерационного алгоритма применяется принцип индукции, который можно сформулировать так:

Пусть $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$

Задания для практики

Вы подошли вплотную к стене, не имеющей ни начала, ни конца. Известно, что в стене есть дверь, но вы не знаете в каком направлении и как долго нужно двигаться, чтобы найти эту дверь. Заметить дверь в стене можно, только подойдя непосредственно к ней и став напротив. Разработайте алгоритм, который бы позволял находить дверь в стене методом обхода не более чем за $О(n)$ шагов, где $n$ - не известное заранее число шагов между вашим первоначальным положением и дверью.
Предположим, что у нас есть плитка (швейцарского) шоколада, состоящая из нескольких долек, расположенных в прямоугольном узоре. Наша задача – разломить плитку на дольки (она всегда ломается вдоль линий между дольками) с минимальным количеством разламываний. Сколько разламываний потребуется? Выдвиньте обоснованную догадку и докажите ее по индукции.
Возьмем последовательность из одного бита "0". Далее выполняем N следующих шагов. На каждом шаге бит "0" заменяем на два бита "10", а бит "1" на два бита "01". После выполнения первого шага из последовательности "0" получается последовательность "10", после второго – "0110", после третьего – "10010110", после четвертого – "0110100110010110", и так далее. Определите количество соседних битов "00" в последовательности после $N$ -го шага.
Если в календаре выбрать месяц, в котом можно отметить квадрат 4x4, то выбрав 4 числа, которые не стоят в одной строке или столбце, и сложив их значения, мы получим одно и тоже число. Почему?
"Кубитовая матрица" состоит из элементов трех типов: увеличителя (увеличивающего значение, полученное сверху или слева, на 1 и передающего его соответственно вниз или вправо), уменьшителя (уменьшающего значение, полученное сверху или слева, на 1 и передающего его соответственно вниз или вправо) и сохранителя (передающего значение, полученное сверху или слева, без изменений соответственно вниз или вправо). При подаче на входы кубитовой матрицы одинаковых значений на выходах все значения будут различны. Постройте кубитовую матрицу $6 xx 6$ .
Кубитовая матрица $2 xx 2$ :
++
-0

Назад