Описание тега proof-of-correctness

Вопросы с тегом
Формальный математический аргумент о том, что алгоритм соответствует своей спецификации, т. Е. Он всегда производит правильный вывод для любого разрешенного ввода.
1 ответ

Как я могу использовать доказательство, которое я сделал в Idris, чтобы сообщить компилятору, что моя подпись типа верна?

У меня есть функция count в idris, определенная как: count : Eq a => a -> Vect n a -> Nat count x [] = Z count x (y::ys) = with (x == y) | True = S (count x ys) | False = count x ys И подтверждение максимального значения может вернуть: coun…
16 июн '18 в 02:09
1 ответ

Математическая техника для перевода рекурсии в цикл while()?

То, что я ищу, - это некоторая математическая теория, освещающая, как можно перевести произвольную конечную рекурсию в какую-то while(...) цикл традиционный в ООП. Или, в другом случае, как можно доказать, что данная рекурсия не может быть переведен…
12 мар '18 в 13:10
2 ответа

Как работает алгоритм для самой длинной возрастающей подпоследовательности [O(nlogn)]?

Я нашел алгоритм, упомянутый в Руководстве автостопщика по конкурсам программирования (примечание: эта реализация предполагает, что в списке нет дубликатов): set<int> st; set<int>::iterator it; st.clear(); for(i=0; i<n; i++) { st.inse…
14 дек '13 в 20:41
1 ответ

Необходимость и достаточность против обоснованности и полноты

Я пытаюсь выучить доказательства. Я сталкивался с этими 4 терминами. Я пытаюсь связать все. A: X>Y B: Y<X Necessary Condition B implies A Sufficient Condition A implies B А также A = { set of statements} Q= a statement Soundness if A derives Q…
11 дек '14 в 19:08
1 ответ

Ленивая оценка правильности и целостности (Coq)

Как следует из названия, мой вопрос касается доказательства правильности и полноты ленивых вычислений арифметических выражений в Coq. Теорем, которые я хотел бы доказать, всего три: Вычисления дают только канонические выражения как результаты. Теоре…
19 дек '13 в 23:40
1 ответ

Доказательство правильности программы

Функция рекурсивно находит и возвращает наименьший элемент из массива, который имеет целочисленные элементы Min(A, b, e) if (b=e) return A[b] m = (b+e)/2 // floor is taken x = Min(A, b, m) y = Min(A, m +1, e) If(x < y) return x else return y Моим…
06 ноя '15 в 00:48
1 ответ

Алгоритм: взвешенные суммы при вращении

Извините, я надеюсь, что это не слишком далеко от темы для stackru. У меня есть алгоритм, который я хотел бы доказать, правильно, или найти контрпример, если это не так. Здесь проблема. У меня есть набор строго положительных весов: w1, w2, w3, ... w…
01 авг '17 в 13:17
0 ответов

Доказательство алгоритма обратного удаления

Правильно ли это доказательство, которое представлено на странице википедии https://en.wikipedia.org/wiki/Reverse-delete_algorithm (внизу страницы)? ПСЕВДОКОД 1 function ReverseDelete(edges[] E) 2 sort E in decreasing order 3 Define an index i ← 0 4…
27 фев '15 в 06:00
1 ответ

Формальное подтверждение правильности решения Greedy для торговли вином (SPOJ)?

Не поймите меня неправильно, если вы разместите вопрос о проблеме на онлайн-судье. Я просто хочу знать, как доказать правильность решения. Следующая проблема - проблема торговли вином. Там написано, что на расстоянии в единицу стоит ряд домов, и каж…
27 июн '14 в 11:58
1 ответ

Какой язык программирования предназначен для тестирования параллельных алгоритмов?

Мой коллега написал программу, которая доказывает, что некоторые условия не будут выполнены после тестирования алгоритма, выполняющего несколько параллельных потоков, пытающихся найти последовательность, которая может вызвать нежелательное условие. …
28 май '17 в 18:07
1 ответ

Доказательство правильности в формальной логике

Мне было интересно, если кто-нибудь может помочь мне ответить на этот вопрос. Это из предыдущей экзаменационной работы, и я смог узнать ответ, готовый к экзамену этого года. Этот вопрос кажется настолько простым, что я полностью теряюсь, что именно …
24 май '12 в 21:37
1 ответ

Доказательство правильности типа "разделяй и властвуй"

Предположим, у нас есть метод сортировки: void DD_sort(int a[], int x, int y, int size_a) { if(x == y){ return; } else if(y == x+1){ if(a[x] > a[y]){ /* swap the content */ return; } } else{ int s = floor((y+1-x)/3); DD_sort(a, x, y-s, s); DD_sor…
22 сен '14 в 00:49
2 ответа

Оптимальная подструктура

Я пытаюсь получить более полное представление об использовании оптимального свойства субструктуры в динамическом программировании, но я не понял, почему мы должны доказать, что любое оптимальное решение проблемы содержит в себе оптимальные решения п…
27 фев '14 в 11:44
1 ответ

Доказательство по индукции с использованием +2

Мне интересно, если этот вариант доказательства по индукции является правильным стандартное доказательство по индукции утверждает, что если уравнение / алгоритм работает для n, и вы можете доказать, что оно работает для n+1, то вы можете предположит…
27 окт '13 в 18:13
4 ответа

Как найти петлю инварианта и доказать правильность?

int i, temp; a is an array of integers [1...100] i = 1; while i < 100 if a[i] > a[i+1] temp = a[i] a[i] = a[i+1] a[i+1] = temp i = i+1 У меня проблемы с пониманием того, как найти инварианты цикла и написать для них формальное утверждение. Так…
03 дек '13 в 17:10
2 ответа

Доказательство правильности алгоритма

Мне было интересно, если кто-нибудь может помочь мне ответить на этот вопрос. Это из предыдущей экзаменационной работы, и я смог узнать ответ, готовый к экзамену этого года. Этот вопрос кажется настолько простым, что я полностью теряюсь, что именно …
27 апр '14 в 11:23
1 ответ

Любые уловки, чтобы избавиться от шаблонного при построении доказательств абсурдного предиката на перечислениях?

Допустим, у меня есть data Fruit = Apple | Banana | Grape | Orange | Lemon | {- many others -} и предикат этого типа, data WineStock : Fruit -> Type where CanonicalWine : WineStock Grape CiderIsWineToo : WineStock Apple который не подходит для Ba…
31 янв '16 в 23:56
2 ответа

Почему этот алгоритм не соответствует своей спецификации? Как попытаться доказать его правильность?

Напишите метод getLargeAndSmallLetters, который возвращает строку, содержащую все прописные и строчные буквы ASCII в следующей форме (заглавные и строчные буквы, разделенные пробелом, группы букв, разделенные запятой, без запятой в конце): A a, B b,…
28 ноя '17 в 20:40
1 ответ

Как я могу доказать правильность следующего алгоритма?

Рассмотрим следующий алгоритм min, который принимает списки x,y в качестве параметров и возвращает z-й наименьший элемент в объединении x и y. Предварительные условия: X и Y - отсортированные списки целых в порядке возрастания, и они не пересекаются…
21 мар '13 в 22:30
1 ответ

Нужна помощь в проверке инварианта цикла (простая сортировка пузырьков, частичная корректность)

Алгоритм сортировки пузырьков (псевдокод): Input: Array A[1...n] for i <- n,...,2 do for j <- 2,...,i do if A[j - 1] >= A[j] then swap the values of A[j-1] and A[j]; Я не уверен, но мое доказательство, кажется, работает, но слишком запутанн…
10 июл '18 в 02:37