Инвариант цикла Дафни не поддерживается циклом th

я должен создать условия pre и pos для метода вставки класса кучи, куча должна быть minHeap и должна быть завершена, мой инвариант имеет ошибку, которая гласит: «этот инвариант цикла может не поддерживаться циклом ."

    class Heap {
var size: nat
var heap: array<int>
method insert (x: int)
    modifies heap
    requires 0 < size < heap.Length - 1
    requires minHeap(heap, size)
    requires x > 0
    requires isComplete(heap, size)
    ensures minHeap(heap, size + 1)
    ensures isComplete(heap, size + 1)
    ensures exists i :: 0 < i < size + 1 && x == heap[i]
    {
        // Insert the new item at the end of the array 
        var pos:= size + 1;
        // Percolate up
        while pos > 1 && x < heap[pos/2]
        invariant 1 <= pos < heap.Length
        invariant forall i :: pos < i <= size + 1 ==> heap[i] < heap[i/2]
        {

            heap[pos] := heap[pos/2];
            pos:= pos/2;
        }
        heap[pos] := x;
    }

    predicate minHeap(h: array<int>, index: nat)
    reads h
    requires 0 < index < h.Length 
    {
        forall i :: 1 < i < index ==> h[i/2] < h[i]
    } 

    predicate isComplete(h: array<int>, index: nat)
    reads h 
    requires 0 < index < h.Length
    {
        forall i :: 1 <= i <= index ==> h[i] > 0
    }
  }   

Может кто-нибудь помочь мне?


person Yes it's me    schedule 25.11.2018    source источник


Ответы (1)


Предположим, что инвариант цикла выполняется в начале итерации, когда pos равно 100. Тогда ты знаешь

forall i :: 100 < i <= size+1 ==> heap[i] < heap[i/2]

в начале итерации цикла. То есть вы что-то знаете о heap[i] для всех i больше 100 (до size+1). Итерация цикла теперь устанавливает heap[100] в значение heap[50] и устанавливает pos в 50. Чтобы доказать, что инвариант цикла сохраняется, теперь вам нужно показать:

forall i :: 50 < i <= size+1 ==> heap[i] < heap[i/2]

Но это условие, конечно, не выполняется. Одна проблема заключается в том, что это не выполняется для i == 100, потому что heap[100] равно heap[50], а не строго меньше heap[50], как утверждает ваш инвариант цикла. Другая проблема заключается в том, что у вас нет информации о значениях heap[51], ..., heap[99], а ваш инвариант цикла говорит, что вы намерены каждое из них также удовлетворять heap[i] < heap[i/2].

Итак, вам нужно переосмыслить либо свою программу, либо инвариант, либо и то, и другое.

person Rustan Leino    schedule 30.11.2018