27
ответов
Почему программы не могут быть доказаны?
Почему компьютерная программа не может быть доказана, как математическая формулировка может? Математическое доказательство создается на других доказательствах, которые создаются еще от большего количества доказательств и на вниз к аксиомам - они...
вопрос задан: 10 June 2012 10:12
18
ответов
Код должен быть коротким/кратким? [закрытый]
При записи математического доказательства одна цель состоит в том, чтобы продолжить сжимать доказательство. Доказательство становится более изящным, но не обязательно более читаемое. Сжатие переводит в лучшее понимание, как...
вопрос задан: 4 June 2009 18:22
9
ответов
Что является доказательством (N – 1) + (N – 2) + (N – 3) +… + 1 = N * (N – 1) / 2 [закрыто]
Я получил эту формулу из книги по структуре данных в алгоритме пузырьковой сортировки. Я знаю, что мы (n-1) * (n раз), но почему деление на 2? Может кто-нибудь, пожалуйста, объясните мне это или дайте подробную ...
вопрос задан: 20 March 2010 18:47
8
ответов
Официально проверяя правильность алгоритма
В первую очередь, действительно ли это только возможно на алгоритмах, которые не имеют никаких побочных эффектов? Во-вторых, где я мог узнать об этом процессе, каких-либо хороших книгах, статьях, и т.д.?
вопрос задан: 27 January 2010 19:01
7
ответов
Какова Насосная Лемма в терминах Неспециалиста?
Я видел этот вопрос и был любопытен относительно того, чем насосная лемма была (Википедия не помогла многому). Я понимаю, что это - в основном теоретическое доказательство, которое должно быть верно для языка для...
вопрос задан: 23 May 2017 10:31
7
ответов
Объясните доказательство Виная Деолаликар, что P! = NP [закрыто]
Недавно в лаборатории HP в Vinay Deolalikar появилась информация о том, что P! = NP. Может ли кто-нибудь объяснить, как это доказательство работает для нас менее математически ...
вопрос задан: 13 April 2017 14:17
7
ответов
Как делают Вы “получаете его” когда дело доходит до доказательств? [закрытый]
Когда мы начинаем входить в дизайн алгоритма и более дискретные темы информатики, мы заканчиваем тем, что имели необходимость доказать вещи все время. Каждый раз я видел, что кто-то спрашивает, как стать действительно хорошим в...
вопрос задан: 27 August 2009 12:45
6
ответов
Доказательство правильности алгоритмов мультипотока
Алгоритмы мультипотока особенно трудно разработать/отладить/доказать. Алгоритм Dekker является главным примером того, как трудно это может быть должно разработать корректный синхронизируемый алгоритм. Современная работа Tanenbaum...
вопрос задан: 17 September 2008 22:54
5
ответов
Запись доказательства для алгоритма
Привет парни я пытаюсь сравнить 2 алгоритма и думал, что могу попытаться записать доказательство для них!!! (моя математика сосет так следовательно вопрос), Обычно на нашем математическом уроке в прошлом году, нам дали бы...
вопрос задан: 16 November 2013 14:10
4
ответа
Как доказать (forall x, P x/\Q x)-> (forall x, P x)
Как каждый доказывает (forall x, P x/\Q x)-> (forall x, P x) в Coq? Попытка в течение многих часов и не может выяснить, как сломать антецедент к чему-то, что может переварить Coq. (Я - newb...
вопрос задан: 27 October 2019 20:59
4
ответа
Доказательство, что денежный алгоритм назначения Fowler корректен
У Martin Fowler есть Денежный класс, который имеет денежную подпрограмму распределения. Эта стандартная программа выделяет деньги согласно данному списку отношений, не теряя значения посредством округления. Это распространяет любого...
вопрос задан: 7 January 2014 16:45
4
ответа
Функциональные доказательства (Haskell)
Я перестал работать при чтении RWH; и не один для выхода я заказал Haskell: Ремесло Функционального программирования. Теперь мне любопытно на предмет этих функциональных доказательств на странице 146. Конкретно я пытаюсь доказать 8.5.1...
вопрос задан: 15 July 2010 03:00
4
ответа
доказательства о регулярных выражениях
Кто-либо знает какие-либо примеры следующего? Разработки доказательства о регулярных выражениях (возможно расширенный с помощью обратных ссылок) в помощниках доказательства (таких как Coq). Программы в зависимо введенном...
вопрос задан: 8 June 2009 13:03
3
ответа
Как определить высоту дерева рекурсии от рекуррентного соотношения?
Как каждый идет об определении высоты дерева рекурсии, созданного при контакте со временем выполнения повторения? Как это отличается от определения высоты регулярного дерева? сопроводительный текст http://...
вопрос задан: 29 August 2009 15:47
2
ответа
Общее доказательство эквивалентности двух FSMs в конечный промежуток времени?
Общее доказательство существует для эквивалентности двух (детерминированных) конечных автоматов, которая всегда занимает конечный промежуток времени? Таким образом, учитывая два FSMs, может Вы доказывать, что, учитывая те же исходные данные они будут...
вопрос задан: 31 October 2009 11:24
1
ответ
Как реализовать `forall` (математику) на процедурном или оо-языке
Я пытаюсь понять, как реализовать forall на процедурном или OO языке, таком как Ruby или JavaScript Например (это Coq): Аксиома точка: Тип. Аксиома: Тип. Аксиома Ложь_в: Точка - > ...
вопрос задан: 1 March 2019 06:49
1
ответ
Как я могу доказать эту теорему Хаскелла уровня типа?
Что касается листинга 1, как мне доказать, что выполняется аксиома уровня типа (t a) = (t (getUI (t a)))? Данные в листинге 1 Continuant a = Continuant производного (Show, Eq) класса UI a ...
вопрос задан: 18 January 2019 20:29
1
ответ
Вопрос о бесконтекстном языке (качающий лемму)
Я знаю, что это непосредственно не связано с программированием, но я задавался вопросом, знает ли кто-либо, как применить насосную лемму к следующему доказательству: Покажите что L = {(a^n) (b^n) (c^m): n! =m} не является контекстом...
вопрос задан: 19 September 2012 16:27
0
ответов
Конгруэнтность для гетерогенного равенства
Я пытаюсь использовать гетерогенное равенство, чтобы доказать утверждения, включающие этот индексированный тип данных: data Counter: ℕ → Set where cut: (ij: ℕ) → Counter (Suc i + j) I was возможность писать свои доказательства, используя ...
вопрос задан: 28 September 2019 17:02
0
ответов
Доказательство того, что проблема остановки является NP-сложной?
В этом ответе на вопрос об определениях NP, NP-hard и NP -complete, Джейсон утверждает, что проблема остановки является классической NP-сложной проблемой. Это проблема, которая дает ...
вопрос задан: 18 December 2018 06:52
0
ответов
Доказать эффективность повторных вызовов преемника () в двоичных деревьях?
Мне нужна подсказка для этого упражнения из книги алгоритмов CLRS: Докажите, что независимо от того, с какого узла мы начинаем в двоичном дереве поиска высотой h , k последовательных вызовов Tree-Successor занимают O (k + h) раз.
вопрос задан: 29 November 2018 17:55
0
ответов
докажите, что n = Big-O (1) с помощью индукции
Я знаю, что соотношение n = Big-O (1) неверно. Но если мы используем индукцию с участием Big-O, это можно доказать. Но заблуждение состоит в том, что мы не можем ввести Big-O. Но мой вопрос в том, как мы можем опровергнуть это отношение ...
вопрос задан: 19 September 2012 22:22
0
ответов
Нотация Big Oh O ((log n) ^ k) = O (log n)?
В нотации большого O это O ((log n) ^ k) = O (log n), где k - некоторая константа (например, число логарифмических циклов for), правда? Мой профессор сказал мне, что это утверждение было правдой, однако он сказал это ...
вопрос задан: 18 September 2012 10:58
0
ответов
Использование большого -O для доказательства того, что N^2 равно O (2^N)
Я ясно вижу, что N^2 ограничено c2^N, но как мне доказать это, используя формальное определение большого -O. Я могу просто доказать это с помощью М.И. Вот моя попытка.. По определению для любого n>n0 существует...
вопрос задан: 12 July 2012 07:15
0
ответов
Стабильная сортировка сравнением с O(n *log(n))времени и O(1)пространственной сложностью
Просматривая список алгоритмов сортировки в Википедии, я заметил, что есть нет стабильной сортировки сравнением, которая имеет O(n*log(n))(наихудший-случай)время-сложность и O(1)(наихудший-случай)пространство-сложность....
вопрос задан: 19 March 2012 20:37
0
ответов
Общие стратегии доказательства для демонстрации правильности рекурсивных функций?
Мне интересно, существует ли какое-либо правило / схема действий при доказательстве правильности алгоритма? Например, у нас есть функция $ F $, определенная на натуральных числах и определенная ниже: function F (n, k)
...
вопрос задан: 2 March 2012 18:40
0
ответов
Доказательство индукцией псевдокода
Я действительно не понимаю, как можно использовать доказательство индукцией на псевдокоде. Кажется, это не работает так же, как его использование в математических уравнениях. Я пытаюсь подсчитать количество целых чисел, которые ...
вопрос задан: 8 October 2011 21:49
0
ответов
Будет ли возможность объявлять функции Lisp «чистыми» быть полезными?
Я много читал о Haskell в последнее время, и преимущества, которые оно происходит от чисто функционального языка. (Я не заинтересован в обсуждении монадских для Lisp), это имеет смысл для меня (...
вопрос задан: 31 August 2011 18:01
0
ответов
Is this always true: fmap (foldr f z) . sequenceA = foldr (liftA2 f) (pure z)
import Prelude hiding (foldr) import Control.Applicative
import Data.Foldable
import Data.Traversable left, right :: (Applicative f, Traversable t) => (a -> b -> b) -> b -> t (f a) -&...
вопрос задан: 19 May 2011 10:12
0
ответов
Контракты кода C #: что можно проверить статически, а что нет ?
Я могу сказать, что довольно хорошо знаком с Code Contracts: я прочитал и понял большую часть руководства пользователя и уже довольно давно использую их, но у меня все еще есть вопросы. Когда я ищу ...
вопрос задан: 17 February 2011 10:40