31 Дек 2017 | Просмотры: 3219

Алгоритмы (теория/практика): Часть 5. Корректность алгоритмов

Привет! Давайте сегодня рассмотрим такую тему, как корректность алгоритмов. Я не хочу сейчас вводить новые понятия, поэтому настоящая тема будет базироваться только на том, что было описано до этого. Вероятно, когда статей будет больше, их порядок поменяется и некоторые статьи будут расширены. Вся история изменений будет в самом низу.

Как мы можем судить о том, что наш алгоритм действительно корректный? Корректный алгоритм – это алгоритм, способный для любых входных данных выдать результат в виде корректных выходных данных. Например, если мы рассматриваем алгоритм поиска, то результатом его работы должен быть индекс найденного элемента, либо число -1.

Для проверки корректности алгоритма существует несколько способов.

Инвариант цикла

Если речь идёт об циклических алгоритмах, то на помощь приходит инвариант цикла. Это некоторое условие, которое должно обязательно обладать тремя свойствами:

  1. Инициализация: инвариант должен быть справедливым перед первой итерацией.
  2. Сохранение: инвариант должен быть справедливым после каждой итерации.
  3. Завершение: инвариант справедлив после завершения цикла.

Для проверки корректности циклического алгоритма мы должны найти такое условие, которое будет справедливо перед началом цикла, в каждом прохождении цикла и после его завершения. И если такое условие будет найдено, но мы сможем сделать вывод о правильности нашего разрабатываемого алгоритма.

Разумеется, что инвариант должен быть связан с переменными, которые изменяются в теле цикла. То есть условие \(1\lt2\), которое, очевидно, будет соблюдаться во всех трёх случаях, не особо нам поможет.

Нахождение инварианта не всегда является очевидной задачей, поэтому давайте попробуем на примере разобраться с тем, что нужно сделать.

В прошлой статье я показал алгоритм линейного поиска – довольно примитивный, но для нашей задачи он идеально подойдет, так как это типичный пример циклического алгоритма. Для тех, кто забыл, как он выглядит, вот его код:

int linear_search(int arr[], int n, int target)
{
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == target)
        {
            return i;
        }
    }

    return -1;
}

С этим кодом связана определенная проблема, которая заключается в невозможности проверки условия после выполнения цикла в случае, если искомое значение было найдено. Поэтому давайте его перепишем следующим образом:

int linear_search2(int arr[], int n, int target)
{
    int i = 0;
    while (i < n && arr[i] != target)
    {
        i++;
    }

    return i != n ? i : -1;
}

Замечание: сначала инициализируется переменная-счетчик. Цикл while содержит в себе два условия и, если они оба выполняются, значит мы еще не достигли конца массива и элемент всё еще не найден, а значит нужно увеличить счетчик на единицу и повторить еще раз.

Рано или поздно одно из условий будет будет нарушено и цикл завершится. После чего мы возвращаем значение, если мы его нашли, либо возвращаем -1, если нет. Это делается при помощи проверки условия i != n. Если переменная-счетчик равна длине массива, то тело цикла while было выполнено n раз, а значит мы проверили весь массив. В противном случае, несколько итераций не были выполнены, а это возможно только в случае успешного нахождения позиции искомого значения.

Теперь давайте найдем инвариант цикла. Внимательно посмотрим на код и поймем. Что справедливо до начала цикла, после каждой итерации и в конце? А справедливо следующее – если мы находимся на данной конкретной итерации, значит все предыдущие попытки найти значение провалились. Итак, инвариант выглядит следующим образом:

\(arr[i-1]\neq T\), где arr - массив, i - текущее значение счетчика, T - искомое значение

Давайте теперь по порядку пройдемся и докажем справедливость подобного условия.

  • Инициализация. Значение справедливо, так как значение для индекса i - 1 не существует, а значит точно не равно T.
  • Сохранение. Если выполняется очередная итерация, значит позиция искомого значения всё еще не была найдена. Поэтому все значения для индекса j < i не будут равны T.
  • После выполнения цикла мы получим две ситуации. Либо мы нашли i, который указывает на найденный элемент, либо i = n. В любом случае, вне зависимости от того, нашли мы элемент или нет, все предыдущие элементы массива нам не подходили, а значит все значения для индекса j < i не равны T.

Зависит ли найденное условие от переменной, изменяющейся в теле цикла? Конечно, мы используем i, который, увеличиваясь на каждой итерации, поочередно указывает на каждый элемент массива до тех пор, пока значения не будет найдено, либо цикл не достигнет конца массива. Следовательно, данное условие можно с полной уверенностью считать инвариантом цикла.

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

Но мы воспользуемся более общим методом доказательства – методом математической индукции.

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

Допустим у нас есть некоторое утверждение P. Для того, чтобы доказать его истинность для всех натуральных чисел n нужно проделать несколько шагов:

  • Доказать, что P истинно в самом простом случае - для n = 1. Это называется базой индукции.
  • Далее мы предполагаем, что утверждение верно для некоторого k и доказываем, что если оно верно для k, то верно и для k + 1. Это называется шагом индукции или индукционным переходом.

Если мы это доказываем, тогда можем сделать вывод о том, что утверждение P справедливо для всех n.

Чисто математические примеры можете поискать сами, а я перейду непосредственно к алгоритмам.

Давайте для примера докажем корректность алгоритма двоичного поиска. На всякий случай приведу его код:

int binary_search(int arr[], int start, int end, int target)
{
    if (start == end)
    {
        return arr[start] == target ? start : -1;
    }

    int mid = floor(start + (end - start) / 2);

    if (target <= arr[mid]) 
    { 
        // Левая часть 
        return binary_search(arr, start, mid, target); 
    } 
    else 
    { 
        // Правая часть 
        return binary_search(arr, mid + 1, end, target); 
    } 
} 

Нам нужно найти утверждение, которое будет зависеть от n. Для доказательства корректности работы нам достаточно показать, что алгоритм завершает работу за конечное число шагов. Почему так? Если алгоритм завершается, то это означает, что функция, разбивая массив на две части и вызывая сама себя с нужным подмассивом, рано или поздно оказывается на самом нижнем уровне рекурсии, где имеет дело с массивом, содержащим один единственный элемент. Если это произошло, то алгоритму остается выполнить только операцию сравнения и вернуть значение. Доказательство операции сравнения тривиально, поэтому нам нужно удостоверится только в том, что при любых предусмотренных входных данных алгоритм корректно завершится и значение будет возвращено. Поехали.

Для начала давайте подсчитаем количество рекурсивных вызовов. Я это уже сделал, поэтому просто скажу - \(\left\lceil \log _{ 2 }{ n } \right\rceil\). Поскольку при каждом вызове функции массив разбивается на две части, то увеличение n в 2 раза лишь добавляет один единственный шаг. Мы округляем значение в большую сторону, так как mid всегда округляется (в меньшую сторону в данном случае), а значит при n, которое не кратно 2, у нас образуется двоякая ситуация, когда, в случае, если элемент расположен в правой части, алгоритм выполнит на 1 шаг больше. Для описания мы и будем использовать этот «худший» случай.

В итоге доказательство сводится к тому, что нужно определить, что корректно выполняется самый нижний уровень рекурсии (когда вызывается функция с одним элементом), а после чего доказать, что самый нижний уровень действительно достижим.

  • \(\left\lceil \log _{ 2 }{ n } \right\rceil=0\). При вызове функции с массивом из одного элемента цепочка вызовов прекращается, так как алгоритм натыкается на оператор return, который возвращает позицию найденного элемента, либо -1.
  • Далее предполагаем, что наше утверждение верно для k = n.
  • Докажем, что результатом \(\left\lceil \log _{ 2 }{ k+1 } \right\rceil\) будет натуральное число - k является натуральным числом, а логарифм любого натурального числа не может быть отрицательным числом. Получившийся ответ округляется в большую сторону, что также делает его натуральным числом.

Следующая статья

Алгоритмы (теория/практика): Часть 6.1. "Разделяй и властвуй"

Предыдущая статья

Алгоритмы (теория/практика): Часть 4. Начинаем анализировать