Вопросы по теме 'proof'
Почему все грамматики LL(1) являются LR(1)?
Общеизвестно, что любая LL(1)-грамматика также является LR(1), но я нигде не могу найти строгого доказательства этого. Я слышал некоторые высокоуровневые обзоры доказательства (например, что, поскольку грамматика LL(1) определяет свои продукты только...
1548 просмотров
schedule
03.04.2022
Конкретный пример, показывающий, что монады не замкнуты по композиции (с доказательством)?
Хорошо известно, что аппликативные функторы замкнуты относительно композиции, а монады - нет. Однако у меня возникли проблемы с поиском конкретного контрпримера, показывающего, что монады не всегда складываются.
Этот ответ дает [String -> a]...
4978 просмотров
schedule
21.08.2023
Может ли кто-нибудь помочь мне с этим доказательством, используя лемму о накачке?
Я только начал читать о лемме о накачке и знаю, как провести несколько доказательств, в основном от противного. Это только этот конкретный вопрос, на который я, кажется, не нахожу ответа. Я понятия не имею, с чего начать. Я могу предположить, что...
1961 просмотров
schedule
25.02.2022
Как сделать допущение второго случая доказательства Изабель / Изар случаями, явно имеющими место?
У меня есть доказательство Изабель, построенное следующим образом:
proof (cases "n = 0")
case True
(* lots of stuff here *)
show ?thesis sorry
next
case False
(* lots of stuff here too *)
show ?thesis sorry
qed
Первый случай на...
769 просмотров
schedule
18.08.2023
Другой способ индукции списков, требующих доказательства
Я дал индуктивное определение списков (называемых listkind ), чтобы облегчить мне доказательство конкретной теоремы индукцией по listkind , а не по списку.
Inductive listkind {X}: list X -> Prop :=
| l_nil : listkind []
| l_one : forall a:X,...
591 просмотров
schedule
17.04.2022
Каков инвариант цикла для этого кода?
Мне нужно придумать инвариант цикла для данного фрагмента кода:
//pre: x & y >= 0
//post: z = x^y
//computes pow(x, y), x^y
int pow(int x, int y){
int z = 1;
while(y > 0){
if(y%2==0){
y /= 2;
x =...
244 просмотров
schedule
28.08.2022
Докажите по индукции, что инвариант цикла выполняется
//Precondition: n > 0
//Postcondition: returns the minimum number of decial digits
// necessary to write out the number n
int countDigits(int n){
1. int d = 0;
2. int val = n;
3. while(val != 0){
4. val = val / 10;...
134 просмотров
schedule
16.05.2022
Доказательство правильности алгоритма
Мне было интересно, может ли кто-нибудь помочь мне ответить на этот вопрос. Это из предыдущей экзаменационной работы, и мне не помешало бы знать ответ, готовый к экзамену этого года.
Этот вопрос кажется настолько простым, что я полностью теряюсь,...
313 просмотров
schedule
25.05.2022
Нужно ли мне неоднородное равенство?
Краткая предыстория: я реализую контексты и переименования, используя индексы де Брейна, а затем расширяю эти понятия с помощью «неопределенного» имени, написанного ε. Неопределенное имя индуцирует частичный порядок имен в Γ, а также переименований...
400 просмотров
schedule
28.03.2022
Почему Coq не допускает инверсии, разрушения и т. Д., Когда целью является Тип?
При refine запуске программы я попытался завершить доказательство с помощью inversion гипотезы False , когда целью была Type . Вот сокращенная версия доказательства, которое я пытался сделать.
Lemma strange1: forall T:Type, 0>0 ->...
2207 просмотров
schedule
03.04.2022
Для графа G с уникальными весами ребер все ли максимальные остовные деревья графа G являются максимальным узким местом?
Полная версия этого вопроса цитируется ниже:
Пусть G - связный граф с n вершинами, m ребрами с различными весами ребер. Пусть T - дерево G с n вершинами и n-1 ребром (то есть остовное дерево), и определим ребро узкого места T как ребро T с...
868 просмотров
schedule
07.11.2022
Объединение undef и списка равно undef - доказательство Haskell
Как можно доказать, что для любого списка xs верно следующее:
undefined ++ xs = undefined
65 просмотров
schedule
24.10.2023
Agda: имитируйте тактику перезаписи Coq
У меня есть некоторый опыт использования Coq, и сейчас я изучаю Agda. Я работаю над доказательством правильности сортировки вставками и дошел до точки, когда я хотел бы выполнить что-то похожее на тактику перезаписи Coq. В настоящее время у меня...
468 просмотров
schedule
08.09.2023
Как доказать оптимальность этого жадного алгоритма?
Даны N целых чисел. Каждое из этих чисел можно увеличить или уменьшить один раз не более чем на заданное натуральное число L. Если после каждой операции какие-либо числа становятся равными, мы считаем их одним числом. Задача состоит в том, чтобы...
135 просмотров
schedule
15.04.2023
Минимальное остовное дерево. уникальное минимальное ребро против неуникального доказательства
Итак, у меня есть упражнение, которое я должен доказать или опровергнуть:
1) если e - ребро минимального веса в связном графе G такое, что не все ребра обязательно различны, то каждое минимальное остовное дерево графа G содержит e
2) То же, что...
1547 просмотров
schedule
12.11.2022
упорядочить числа, чтобы сформировать наибольшее число - доказательство алгоритма
Существует хорошо известная алгоритмическая проблема с заданным массивом чисел, например. [1, 20, 3, 14] расположите числа таким образом, чтобы они образовывали наибольшее возможное число, в данном случае 320141 .
На SO и других сайтах есть...
900 просмотров
schedule
09.12.2022
Докажите, что преемник Y узла X, если у X нет правого потомка, является младшим предком узла X.
Я изучаю CS в университете, и у меня есть вопрос, который я не могу доказать.
Докажите, что преемник Y узла X в BST, когда X не имеет правого потомка, является младшим предком X , то есть левый потомок также является предком X ....
689 просмотров
schedule
09.06.2023
Модифицированная версия Миллера-Рабина для проверки детерминированной простоты?
В тесте Миллера-Рабина используется k . случайные целые числа для проверки на простоту.
Согласно CLRS, 3 rd Edition, стр. 971:
Теорема 31.38.
Если n — нечетное составное число, то количество свидетелей составности n не меньше (n — 1)/2....
148 просмотров
schedule
26.07.2023
Устойчив ли следующий алгоритм?
Этот алгоритм стабилен или нет? Я проверил значение стабильной и нашел кое-что на этом сайте. Если я правильно понял, что-то (мы говорим об алгоритмах сортировки) стабильно, когда 2 вещи с одинаковыми ключами появляются в одном и том же порядке на...
55 просмотров
schedule
12.08.2023
Unsat ядро от Z3 (версия 4)
Я использую Ocaml API Z3 версии 4.0 в течение последнего года или около того, в основном теорию битового вектора. Теперь мне нужно извлечь неподтвержденные ядра после выполнения Z3.solver_check, и, к сожалению, в версии 4 такой возможности нет. Я...
137 просмотров
schedule
19.03.2023
