Как построить и обосновать цикл-инвариант, который позволяет показать частичную корректность

Question

Мне нужно построить и обосновать инвариант цикла с заданной спецификацией:

{n > 0} P {q = | {j: a[j]=x and 0 <= j < n} |}

где |A| является числом элементов множества A. Это означает, что q равно числу элементов из массива a, которые равны x.

Код P указан как:

{
int i = 0, q = 0;
while (i != n){
    if (a[i] == x)
        q = q + 1;
    i = i + 1;
}

Я знаю, что инвариант цикла должен быть истинным:

• до начала цикла
• перед каждой итерацией цикла
• после завершения цикла

но я понятия не имею, как мне найти правильный инвариант цикла, который позволил бы мне показать частичную корректность P впоследствии. Я уже пытался просмотреть каждую отдельную итерацию цикла и переменных для случайных n, x и a[0...n-1], чтобы увидеть, какие объединенные значения являются постоянными во время работы цикла, но это не помогло.

Answer 1

Посмотрите на ваш код внимательно. В начале, q 0, и он только растет, когда вы найдете новые элементы, которые == x, Так

q = | {j: a[j]=x and 0 <= j < i} |

является частью вашего инварианта. Обратите внимание, что в вашей спецификации у вас было < n вместо < i, Также обратите внимание, что при завершении цикла i == n, Так что это также будет действовать в начале. Это также будет правдой в любой момент: пока все хорошо. Что-то еще отсутствует? Да, мы должны также заявить, что

0 <= i <= n - потому что это описывает диапазон значений I (в противном случае, i будет свободно выходить за пределы массива).

Это все? Да - нет другого состояния цикла, чтобы описать. Следовательно, ваш полный инвариант выглядит

q = | {j: a[j]=x and 0 <= j < i} | and 0 <= i <= n

Решая эти упражнения, вы можете попробовать эти 2 шага:

• попробуйте описать простым текстом, что происходит в алгоритме: "Я подметаю i от 0 до n-1, останавливаясь на n, и в любой момент я держу в q количество x что я нашел в массиве ". Все переменные, включенные в цикл должны быть упомянуты!
• переведите этот простой текст в математику, а также убедитесь, что ваше пост-условие отражено в инварианте, обычно заменяя n счетчиком цикла (в этом случае i)

В качестве мысленного эксперимента попробуйте написать инвариант с эквивалентным циклом (но с перебором от конца к началу):

{
int i = n-1, q = 0;
while (i >= 0){
    if (a[i] == x)
        q = q + 1;
    i = i - 1;
}

Наведите курсор мыши для ответа (но сначала попытайтесь выяснить это).

q = | {j: a[j]=x and i < j < n} | and -1 <= i < n Обратите внимание на различные ограничения, отражающие, что i подметает по-разному; но та же общая структура