Описание тега loop-invariant
In formal program verification, loop invariants are expressed in formal predicate logic and used to prove properties of loops and, by extension, algorithms employing loops (usually correctness properties). A loop invariant should be true on entry into a loop and is guaranteed to remain true after every iteration of the loop.
1
ответ
Дафни: повернутая область проверки массива методом
Это доказательство дает бесконечный цикл в верификаторе Дафниса: // Status: verifier infinite loop // rotates a region of the array by one place forward method displace(arr: array<int>, start: nat, len: nat) returns (r: array<int>) requi…
12 янв '16 в 02:47
7
ответов
Петлевой инвариант линейного поиска
Как видно из раздела Введение в алгоритмы ( http://mitpress.mit.edu/algorithms), в упражнении говорится следующее: Вход: массив A[1...n] Вывод: i, где A[i]=v или NIL, если не найден Напишите псевдокод для LINEAR-SEARCH, который просматривает последо…
07 апр '11 в 17:20
3
ответа
Определить инвариант цикла?
Я не совсем понимаю, как определить инвариант цикла. Я понимаю, что это то, что верно до цикла, после цикла и во время каждой итерации цикла, но это все. Вот примерная проблема, над которой я работаю, как бы вы нашли инвариант этого цикла? i, temp :…
08 апр '14 в 03:57
1
ответ
Это правильный инвариант для этого цикла?
Это псевдокод для линейного поиска в массиве, возвращающего индекс i если желаемый элемент e в массиве A найден, NIL в противном случае (это из книги CLRS, 3-е издание, упражнение 2.1-3): LINEAR_SEARCH (A, e) for i = 1 to A.length if A[i] == e retur…
03 мар '16 в 16:59
1
ответ
Frama-C/WP не может доказать цикл, инвариантный с \at
У меня проблемы с проверкой двух инвариантов цикла: loop invariant \forall integer i; 0 <= i < (\at(n, Pre) - n) ==> ((char*)m2)[i] == \at(((char*)m1)[i], Pre); loop invariant \forall integer i; 0 <= i < (\at(n, Pre) - n) ==> ((cha…
23 мар '13 в 19:10
1
ответ
Как построить и обосновать цикл-инвариант, который позволяет показать частичную корректность
Мне нужно построить и обосновать инвариант цикла с заданной спецификацией: {n > 0} P {q = | {j: a[j]=x and 0 <= j < n} |} где |A| является числом элементов множества A. Это означает, что q равно числу элементов из массива a, которые равны x…
11 дек '18 в 22:19
1
ответ
Инварианты петли с перерывами
Я пытаюсь понять, как инварианты цикла взаимодействуют с разрывами. CLRS 3e (pg19) описывает инвариант цикла как требующий, чтобы Если он равен true до итерации цикла, он остается истинным до следующей итерации. Итак, учитывая следующий тривиальный …
04 янв '19 в 22:46
2
ответа
Инвариант петли (Java)
У меня есть следующий код, чтобы перевернуть цифры в целое число: public class integerReversal { public static int reverseNum(int number){ int reversed = 0; int remainder; //{I: ; B: number > 0} while (number > 0){ remainder = number % 10; num…
27 янв '15 в 03:45
2
ответа
Инвариант цикла для функции для вычисления факториалов
Мне трудно правильно определить инвариант цикла для следующей функции: F(y) X <-- 1 while (y > 1) do x <-- x * y y <-- y - 1 return (x) Я определил инвариант цикла, чтобы быть x = 1 OR x = y! поскольку это утверждение верно как предварит…
05 дек '11 в 23:11
1
ответ
Нахождение инварианта цикла - Тройка Хоара
Из следующего кода мне нужно вывести / выбрать инвариант цикла. (|true|) x = 0 ; s = 0 ; while ( x <= n ) { s = s + x ; x = x + 1 ; } (|s = n(n + 1)/2|) Решение дано было s = (x-1)*x/2 ∧ (x ≤ n +1) Я не совсем понимаю, как он достиг решения выше.…
15 апр '18 в 16:13
2
ответа
Инвариантное доказательство цикла по алгоритму умножения
В настоящее время я застрял в цикле инвариантного доказательства в моем домашнем задании Алгоритм, который мне нужен, чтобы доказать правильность, таков: Multiply(a,b) x=a y=0 WHILE x>=b DO x=x-b y=y+1 IF x=0 THEN RETURN(y) ELSE RETURN(-1) Я попы…
26 окт '18 в 14:59
1
ответ
Экспоненциальный метод в dafny: инвариант может не поддерживаться
Я начал изучать Дафни, и я только изучил инварианты. У меня есть этот код: function pot(m:int, n:nat): int { if n==0 then 1 else if n==1 then m else if m==0 then 0 else pot(m,n-1) * m } method Pot(m:int, n:nat) returns (x:int) ensures x == pot(m,n) …
18 авг '17 в 02:01
1
ответ
Что такое инвариант цикла данной программы?
Я не знаю, как найти инвариант цикла. Я не уверен, с чего начать. Может кто-нибудь найти инвариант цикла данной программы и объяснить ваш метод, пожалуйста. {n ≥ 0 ∧ i = 0} while i < n − 1 loop b[i] := a[i + 1]; i:=i + 1 end loop {∀j.(0 ≤ j < …
20 мар '18 в 04:31
2
ответа
ValueError в тензорном потоке while_loop инварианты формы
import tensorflow as tf cluster_size = tf.constant(6) # size of the cluster m = tf.constant(6) # number of contigs (column size) n = tf.constant(3) # number of points in a single contigs (column size) contigs_index = tf.reshape(tf.range(0, m, 1, dty…
04 авг '17 в 19:53
1
ответ
Что такое инвариант цикла в следующем коде
Что такое инвариант (ы) цикла в этом примере кода?Это фрагмент кода, реализованный на языке программирования C: //pre-condition m,n >= 0 x=m; y=n; z=0; while(x!=0){ if(x%2==0){ x=x/2; y=2*y; } else{ x=x-1; z=z+y; } }//post-condition z=mn Вот мои …
03 окт '11 в 07:06
1
ответ
Доказательство корректности с помощью инварианта цикла (индукция)
Я написал свою собственную тривиальную маленькую функцию (php для удобства) и надеялся, что кто-то может помочь структурировать доказательство по индукции для него, просто чтобы я мог получить очень простое представление об этом. function add_number…
24 фев '12 в 01:49
0
ответов
Определение инварианта цикла для рекурсивной функции
Предположим, у вас есть функция, которая возвращает разницу в длине между двумя массивами, однако она использует не обычные методы для определения длины, а рекурсивную функцию.Можете ли вы помочь мне найти инвариант цикла? Я понимаю, что инвариант ц…
14 май '18 в 20:59
1
ответ
То, что не меняется в алгоритме
k :=0 for i ←1 to n c←a[i] k←k+1 это алгоритм, чтобы узнать количество элементов
12 фев '17 в 12:53
3
ответа
Как найти петлю инвариант Java
Я пытаюсь найти инвариант циклов (например, в следующем коде), я действительно не знаю, как найти инвариант в целом. Может ли кто-нибудь помочь мне с тем, как найти инвариант, а также помочь мне найти его для следующего кода? Спасибо public static i…
09 июн '13 в 09:25
0
ответов
Различные способы нахождения петлевого инварианта
Я пытаюсь найти инвариант цикла этого кода. Обычно я бы на самом деле просматривал код со входом и пытался выяснить это. Но этот подход не всегда работает. Просто интересно, есть ли лучший способ найти инвариант цикла? Любой совет будет высоко ценит…
06 дек '13 в 02:33