Проверка правильности алгоритмов.

Question

Я смотрел сообщения о stackoverflow о проверке правильности различных алгоритмов, и все они, похоже, доказывают алгоритм X или Y. Я студент-информатик, и я понял, что многие студенты CS (включая меня) борются с этой концепцией, и я не нашел никаких сообщений, объясняющих общий подход к проверке правильности программ/алгоритмов. Wiki и Youtube оба не очень полезны, поскольку оба имеют очень ограниченное количество информации о текущем предмете.

Не могли бы вы объяснить, шаг за шагом «общий» подход (если есть), чтобы доказать правильность алгоритмов, объясняя на пути инварианты, что петли являются для, почему это иногда достаточно, чтобы доказать, что алгоритм частично правильно, а не полностью, со всеми небольшими деталями и нюансами, не оставляя ничего интересного. И чтобы убедиться, что кто-то может понять эту концепцию, давайте докажем правильность алгоритма бинарного поиска (самым общим способом).

int binSearch(int[] a, int x) { 
    int l = 0; 
    int r = a.length - 1; 
    int m = 0; 
    while (l <= r && a[m] != x) { 
     m = (l + r)/2; 
     if (a[m] > x) 
      r = m - 1; 
     else if (a[m] < x) 
      l = m + 1; 
    } 
    if (a[m] == x) 
     return m 
    else 
     return -1; 

Answer 1

Существует различие между алгоритмом и его реализацией на определенном языке программирования. Также вполне возможно правильно реализовать алгоритм, пока вы не можете «доказать», что это правильно! (Вы можете написать правильный двоичный поиск, не зная, почему он всегда будет работать для отсортированного списка.)

Давайте выпишем алгоритм для вашего примера: бинарный поиск.

В отсортированном списке п элементов длиной, искомое значение х может иметь место в этом списке, или это не может.

«Длина» в списке, то есть границы между ними, где х могут присутствовать, могут быть представлены индексы л и г таким образом, что оно гарантировано, что если х является в списке он будет находиться между l и r (включительно), и если это не между этими значениями (опять же включительно), оно не будет во всем списке. Это всегда справедливо для списка отсортированных. Ранняя проверка может заключаться в проверке, если x ниже первого значения элемента или выше последнего; если да, то это «вне границ», и все готово.

1. Если длина фрагмента списка, связанного л и г 1 элемент только тогда, если element[l] = x значение поиска будет найден, то он не находится в списке.

2. Если длина фрагмента списка больше 1, выбрать случайный элемент между л и г (обычно, средняя точка выбрана). Его значение может быть меньше, равно или больше x.

3. Поскольку мы знаем, что в отсортированном списке х может быть где-то между л и г (если он находится в списке), вы можете обновить либо Lилиг (в зависимости от результата этапа № 2) и общего заявления elem [l] < = x < = elem [r] будет по-прежнему будет истинным. Один из эля [L] = х < < = эль [м] и Эля [м] < < = х = эль [г] должны быть истинными, который определяет, какие конечный пункт можно перемещать.

4. Каждое изменение л будет двигаться в направлении его г; каждое изменение r перемещает его в направлении l. Повторяйте с шага # 1 до тех пор, пока интервал l..r будет только 1 элемент длинным, и, таким образом, шаг № 1 - true.

Поскольку каждое сравнение необходимо обновления либо л или г к другим, фрагменту списка будет короче на каждой итерации. Следовательно, логически, он будет иметь длину 1 и шаг № 1 остановит алгоритм, и выбранное значение будет как можно ближе к значению x (в том смысле, что нижний элемент имеет значение менее x, а верхний элемент имеет значение больше x).

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

Это логическое доказательство функционирования двоичного поиска (то есть, оно всегда будет возвращать желаемый результат), но двоичного поиска только. Другие алгоритмы нуждаются в разных доказательствах.

Как-то я понимаю, что вы ищете доказательство доказательств: «проверка правильности разных алгоритмов». Это как раз о Святом Граале вычислений. Вы должны прочитать теорему Тьюринга о прекращении (которая, если я правильно помню, заявляет, что такой вещи нет).