Вопросы об общих методах и приемах доказательства множественных теорем. Когда вы спрашиваете о доказательстве одного утверждения, используйте вместо этого теги, относящиеся к тому, о чем идет речь.
Существует множество вопросов о том, как анализировать время выполнения алгоритмов (см., Например, анализ времени выполнения и анализ алгоритма ). Многие из них похожи, например, те, которые запрашивают анализ затрат на вложенные циклы или алгоритмы «разделяй и властвуй», но большинство ответов,...
Я слышал о (структурной) индукции. Это позволяет вам строить конечные структуры из более мелких и дает вам доказательные принципы для рассуждений о таких структурах. Идея достаточно ясна. Но как насчет коиндукции? Как это работает? Как можно сказать что-либо убедительное о бесконечной структуре?...
Есть много способов доказать, что язык не является регулярным , но что мне нужно сделать, чтобы доказать, что какой-то язык является регулярным? Например, если мне дано, что регулярно, как я могу доказать, что следующее регулярно?LLLL'L′L' L': = { w ∈ L : u v = w для u ∈ Σ*∖ L и v ∈...
В теории вычислимости и сложности (и, возможно, в других областях) сокращения являются повсеместными. Существует много видов, но принцип остается тем же: показать, что одна проблема L1L1L_1 , по крайней мере, так же трудна, как и другая проблема L2L2L_2 путем сопоставления экземпляров из с...
Я планирую провести зимний курс по разному количеству тем, одной из которых будут составители. Теперь я столкнулся с этой проблемой, думая о заданиях, которые нужно давать на протяжении всего квартала, но это поставило меня в тупик, поэтому я мог бы вместо этого использовать его в качестве примера....
Я понимаю доказательство неразрешимости проблемы остановки (приведенное, например, в учебнике Пападимитриу), основанное на диагонализации. Хотя доказательство является убедительным (я понимаю каждый его шаг), оно не является для меня интуитивным в том смысле, что я не понимаю, как кто-то может его...
Когда я объяснял доказательство Бейкера-Гилла-Соловая, что существует оракул, с которым мы можем иметь, , и оракул, с помощью которого мы можем иметь P ≠ N P другу, возник вопрос, почему такие методы плохо подходят для доказательства проблемы P ≠ N P , и я не мог дать удовлетворительный ответ.P = N...
У меня есть жадный алгоритм, который, я подозреваю, может быть правильным, но я не уверен. Как мне проверить, правильно ли это? Какие методы использовать для доказательства правильности жадного алгоритма? Существуют ли общие модели или методы? Я надеюсь, что это станет справочным вопросом, на...
Каждая неразрешимая проблема, о которой я знаю, попадает в одну из следующих категорий: Проблемы, которые неразрешимы из-за диагонализации (косвенная самостоятельная ссылка). Эти проблемы, такие как проблема остановки, неразрешимы, потому что вы можете использовать предполагаемое определение языка...
Я прохожу сложный курс, и у меня возникают проблемы с сокращением числа проблем с NPC. Как я могу найти сокращения между проблемами? Есть ли общий трюк, который я могу использовать? Как мне подойти к проблеме, которая требует от меня доказать, что проблема в...
Есть много способов доказать, что язык не является контекстно-свободным, но как мне доказать, что язык не является контекстно-независимым? Какие методы существуют, чтобы доказать это? Очевидно, один из способов - показать контекстную грамматику для языка. Существуют ли какие-либо систематические...
Моя проблема в том, как я могу доказать, что грамматика однозначна? У меня есть следующие грамматики: S→statement∣if expression then S∣if expression then S else SS→statement∣if expression then S∣if expression then S else SS → statement ∣ \mbox{if } expression \mbox{ then } S ∣ \mbox{if } expression...
У меня есть два способа составить список предметов в случайном порядке, и я хотел бы определить, являются ли они одинаково справедливыми (беспристрастными). Первый метод, который я использую, состоит в том, чтобы создать весь список элементов, а затем выполнить случайное перемешивание (скажем,...
Конструктивистская логика - это система, которая исключает Закон Исключенной Среды, а также Двойное Отрицание как аксиомы. Это описано в Википедии здесь и здесь . В частности, система не допускает доказательств от противного. Мне интересно, кто-нибудь знаком с тем, как это влияет на результаты,...
Учитывая любую вычислительную проблему, является ли задача нахождения нижних границ для такого вычисления действительно возможной? Я полагаю, что все сводится к тому, как определяется один вычислительный шаг и какую модель мы используем для доказательства, но, учитывая это, действительно ли мы...
Задание формальных языков с помощью формальных грамматик является частой задачей: нам нужны грамматики не только для описания языков, но также для их анализа или даже для правильной науки . Во всех случаях важно, чтобы грамматика под рукой была правильной , то есть генерировала именно нужные слова....
Я ищу объяснение того, как можно доказать, что две модели вычислений эквивалентны. Я читал книги по этому вопросу, за исключением того, что доказательства эквивалентности опущены. У меня есть базовое представление о том, что означает, что две модели вычислений эквивалентны (представление автоматов:...
В математике есть много доказательств существования, которые неконструктивны, поэтому мы знаем, что определенный объект существует, хотя мы не знаем, как его найти. Я ищу похожие результаты в информатике. В частности: есть ли проблема, которую мы можем доказать, что она разрешима, не показывая...
Прежде чем читать «Искусство компьютерного программирования» (TAOCP) , я не углублялся в эти вопросы. Я бы использовал псевдокод для описания алгоритмов, понимания их и оценки времени выполнения только по порядку роста. TAOCP тщательно меняет свое мнение. TAOCP использует английский, смешанный с...
Основная теорема является прекрасным инструментом для решения определенных видов повторений . Тем не менее, мы часто замазываем неотъемлемую часть при его применении. Например, во время анализа Mergesort мы с радостью T(n)=T(⌊n2⌋)+T(⌈n2⌉)+f(n)T(n)=T(⌊n2⌋)+T(⌈n2⌉)+f(n)\qquad T(n) =...