10
ответов
Как NP-Hard отличается от NP? [Дубликат]
Я понимаю множество определений NP, NP-complete и NP-hard. Я понимаю, что если мы сможем решить NP-полную проблему, мы сможем решить все проблемы NP. Я также знаю, что проблема классифицируется как NP -...
вопрос задан: 23 July 2015 13:15
7
ответов
Как записать перечисление всех вычислимых функций?
Мотивация: я хотел бы смочь использовать игрушечное функциональное программирование на языках без функций первого порядка, при помощи натуральных чисел вместо функций. Универсальная функция является функцией f: N->...
вопрос задан: 25 November 2009 17:16
2
ответа
Важные темы в теории вычисления
Во время моих исследований в университете я должен был узнать много о теории вычисления. Я изучил предмет для трех условий. Мне пришлось нелегко, и я должен признать, что забыл много. Я задаюсь вопросом...
вопрос задан: 5 March 2010 17:22
2
ответа
NFA к вопросу DFA
Во-первых, это не вопрос, просящий алгоритм преобразовать NFA в DFA. Это знало (и доказало), который эквивалентный DFA NFA имеет самое большее 2n состояния, даже при том, что большинство времен это будет...
вопрос задан: 9 January 2010 14:59
1
ответ
Мое описание языка принимается этим DFA?
Изображение DFA: https://ibb.co/LCW99q9 Насколько я понимаю, любая строка принимается, если она содержит подстроку «abc»; все, что до, в порядке, и все, после, в порядке, включая «λ». Мой ...
вопрос задан: 30 March 2019 23:26
0
ответов
Не уверен в значении этой записи
У меня есть набор «А», и я хочу показать, что он разрешим, однако обозначения набора меня смутили. Там написано, что A = {: M - машина Тьюринга, такая что M (00) [100] = accept}. Я не уверен, что означает следующее ...
вопрос задан: 17 January 2019 14:48
0
ответов
преобразование DFA в регулярное выражение с использованием метода транзитивного замыкания
В следующем примере показан простой DFA с одним принимающим состоянием q2: на основе алгоритма R (i, j, k), показанного выше, я хочу преобразовать этот DFA в регулярное выражение, к сожалению, я не могу найти хорошего ...
вопрос задан: 16 January 2019 15:57
0
ответов
Докажите, что набор всех языков в конечном алфавите неисчислим.
Попытка внести некоторые исправления, но не уверена в этом: Докажите, что набор всех языков в Конечный алфавит неисчислим. У меня такое чувство, что это потребует использования диагонализации Кантора ...
вопрос задан: 10 December 2018 12:39
0
ответов
Ən böyük rəqəmin qalan rəqəmlərin cəm olduğu bir sıra bütün alt qruplarını sayın
Greplin meydan oxumasının 3-cü səviyyəsi ilə mübarizə aparmışam. Tanınmamışlar üçün problem budur: ən böyük rəqəmin qalanın cəmi olduğu bir sıra bütün alt qruplarını tapmalısınız ...
вопрос задан: 27 October 2018 18:36
0
ответов
Завершена ли компиляция C #4.0 -во времени?
Существует хорошо -известный факт, что шаблоны C++ являются -полными по Тьюрингу, а CSS — полными -по Тьюрингу (! )и что разрешение перегрузки C #равно NP -жесткому (даже без дженериков ). Но есть ли C #4.0 (с co/...
вопрос задан: 23 May 2017 12:31
0
ответов
Завершено ли вычисление Тьюринга на основе constexpr?
Мы знаем, что метапрограммирование шаблона C ++ завершено по Тьюрингу, а метапрограммирование препроцессора - нет. C ++ 11 дает нам новую форму метапрограммирования: вычисление функций constexpr. Является ли эта форма ...
вопрос задан: 23 May 2017 12:07
0
ответов
Примеры задач не в P и не в NP-полных, а в NP
У меня в колледже есть курс под названием «Анализ алгоритмов», где мы в настоящее время изучаем различные классы сложности - P, NP, NP-hard и т. Д. Мы уже обсуждали NP-полные проблемы как ...
вопрос задан: 13 April 2017 12:32
0
ответов
Разница между разрешимостью по Тьюрингу и разрешимостью совместно по Тьюрингу
Я действительно изо всех сил пытаюсь понять разницу между этими двумя. Из моего учебника это различие, по сути, описывает разницу, говоря, что язык является совместно узнаваемым, если он...
вопрос задан: 20 March 2017 09:39
0
ответов
что это за операторы стрелок в контекстно-свободная грамматика?
Я изучаю контекстно-свободную грамматику, и мне любопытно, что означают стрелка со звездочкой и стрелка без звезды в частях f и g, где: f - ложь. g верно.
вопрос задан: 29 February 2016 00:54
0
ответов
Is { ш | w <> w^R } над алфавитом {0,1} контекстно-свободный язык?
Мне бы очень хотелось, чтобы вы помогли решить, является ли язык всех слов в алфавите {0,1}, которые нельзя читать с обеих сторон одинаково, { w | w <> wR }, является контекстно-свободным языком (...
вопрос задан: 5 August 2012 05:43
0
ответов
Насколько водонепроницаем швейцарский сыр? [закрыто]
Представьте себе кусок швейцарского сыра в форме куба -. Моделируем сыр через сетку 20х20х20. Для простоты предположим, что каждый кубик сетки полностью состоит из сыра или полностью из воздуха. На верхнем...
вопрос задан: 1 July 2012 17:37
0
ответов
Вывод подпрограмм
Есть ли какой-нибудь документ, описывающий какой-либо алгоритм / метод вывода подпрограмм из скомпилированной программы? Другими словами: существует ли алгоритм для поиска блоков кода, которые встречаются более одного раза в ...
вопрос задан: 6 December 2011 21:39
0
ответов
Можно ли создать квайн HTML?
Согласно заголовку, можно ли создать (нетривиальный) квайн в HTML? Мое определение HTML-quine: Нетривиальный HTML-quine - это тот, который не является нулевым и использует хотя бы один HTML-тег под ...
вопрос задан: 6 December 2011 13:35
0
ответов
Есть ли разница между «конечным автоматом» и «конечным автоматом»?
Я не уверен, что понимаю, есть ли разница между конечным автоматом и Государственный аппарат? Я слишком много об этом думаю?
вопрос задан: 12 September 2011 10:11
0
ответов
Понимание распознавателей и решателей в теории вычислений
У меня возникли некоторые проблемы с пониманием того, что означает для машины распознавание и определение языка. Думаю, я близок к определениям, но не прав. Когда говорят, что машина Тьюринга Т распознает ...
вопрос задан: 14 March 2011 08:34
0
ответов
Как определить, является ли машина эквивалентом машины Тьюринга
Я нашел статью в Википедии со списком эквивалентов машины Тьюринга. Однако в нем не говорится о методе определения того, является ли данная машина эквивалентом машины Тьюринга. Нужно ли мне использовать ...
вопрос задан: 10 January 2011 09:18
0
ответов
Обеспечивается ли Provable == Decidable?
В теории вычислений используются термины Provable и Разрешаемые взаимозаменяемые? Означают ли они одно и то же? Например, вы часто сталкиваетесь с вопросом, можно ли что-то доказать, называемым решением ...
вопрос задан: 17 October 2010 02:19