Учитывая регулярный язык (NFA, DFA, грамматика или регулярное выражение), как можно посчитать количество принимаемых слов на данном языке? Интерес представляют как «ровно n букв», так и «не более n букв». У Маргареты Акерман есть две статьи по теме перечисления слов, принятых NFA, но я не смог...
Каковы будут последствия #P = FP? Меня интересуют как практические, так и теоретические последствия. С практической точки зрения меня особенно интересуют последствия для искусственного интеллекта. Указатели на бумаги или книги более чем приветствуются. Пожалуйста, не говорите, что #P = FP...
Я не теоретик информатики, но думаю, что проблема реального мира здесь. Проблема У моей компании есть несколько подразделений по всей стране. Мы предложили сотрудникам возможность работать на другом блоке. Но есть условие: общее количество работников на единицу не может измениться. Это означает: мы...
Знаете ли вы какие-либо современные вики, посвященные задачам оптимизации NP, с их наилучшим приближением и результатом твердости? Судя по отзывам, можно предположить, что такого ресурса нет (см. В конце этого вопроса два близких варианта). - добавлено 8 февраля. Поскольку за последние два...
Я сформулировал следующую проблему сегодня, играя с моим GPS. Вот : Пусть - ориентированный граф такой, что если то , т. является ориентацией основного неориентированного графа. Рассмотрим следующие операции:e = ( u , v ) ∈ E ( v , u ) ∉ E GG(V,E)G(V,E)G(V,E)e=(u,v)∈Ee=(u,v)∈Ee=(u,v) \in...
В связи с загадкой Slither Link мне было интересно: предположим, что у меня сетка квадратных ячеек, и я хочу найти простой цикл ребер сетки, равномерно случайным образом среди всех возможных простых циклов.n×nn×nn\times n Один из способов сделать это - использовать цепь Маркова, состояния которой...
Что известно о сложности следующей задачи: Дано: рациональные числа .x1<x2<…<xnx1<x2<…<xnx_1 < x_2 < \dotso < x_n Вывод: целые числа .y1≤y2≤…≤yny1≤y2≤…≤yny_1 \le y_2 \le \dotso \le y_n Цель: минимизировать где∑1≤i<j≤ne(i,j),∑1≤i<j≤ne(i,j),\sum_{1 \le i < j \le n} e(i,j),e (...
SAT решатели очень важны при алгебраических атаках , например, walksat и minisat . Тем не менее, при решении проблем с эталонными тестами, имеющихся здесь, существует огромная разница в производительности - Walksat намного быстрее, чем minisat для этих задач. Почему это? Эта реализация walksat,...
Мне нужно рассчитать бегущую медиану: Ввод: , , вектор .k ( x 1 , x 2 , … , x n )NnnКkk( х1, х2, … , ХN)(x1,x2,…,xn)(x_1, x_2, \dotsc, x_n) Вывод: vector , где - это медиана .y i ( x i , x i + 1 , … , x i + k - 1 )( у1, у2, ... , уn - k + 1)(y1,y2,…,yn−k+1)(y_1, y_2, \dotsc, y_{n-k+1})Yяyiy_i( хя,...
Обычно каждый строит граф, а затем задает вопросы о разложении собственных значений матрицы смежности (или некоторого близкого родственника, такого как лапласиан ) (также называемого спектрами графа ). Но как насчет обратной проблемы? Учитывая собственных значений, можно (эффективно) найти граф,...
Том III книги Кнута « Искусство компьютерного программирования» (глава 5, стих 3.2) включает в себя следующую таблицу, в которой перечислено точное минимальное количество сравнений, необходимых для выбора наименьшего элемента TTt из несортированного набора размера NNn для всех 1 ≤ t ≤ n ≤...
Я хочу сделать первый SAT решатель. Я знаю соревнования SAT и конференцию SAT, и на эту тему очень много работ. Я стартер, перегруженный стартер. С чего мне начать? В конце концов я хочу продвинуть современное состояние. Мне нужен совет специалиста о том, как начать, чтобы я не тратил свое время на...
Даны Nnn подмножеств S1, … , SNS1,…,SnS_1,\ldots,S_n из { 1 , … , д}{1,…,d}\{1,\ldots,d\} . Проверьте, есть ли множества Sя, SJSi,SjS_i,S_j с Sя⊊ SJSi⊊SjS_i \subsetneq S_j . (Если так, найдите пример, если нет, просто скажите «нет») Тривиальное решение этой проблемы проходит через все пары наборов...
Алгоритм Копперсмита – Винограда - это асимптотически самый быстрый известный алгоритм для умножения двух квадратных матриц. Время выполнения их алгоритма - который является самым известным на сегодняшний день. Какова пространственная сложность этого алгоритма? Это в ?O ( n 2,337 ) Θ ( n 2 )n ×...
Редактировать: я сначала неправильно сформулировал свое ограничение (2), теперь оно исправлено. Я также добавил больше информации и примеров. С некоторыми коллегами, изучающими какой-то другой алгоритмический вопрос, мы смогли свести нашу проблему к следующей интересной проблеме, но мы не смогли...
Проблема стабильного брака: http://en.wikipedia.org/wiki/Stable_marriage_problem Мне известно, что для случая SMP возможны многие другие стабильные браки, кроме одного, возвращенного алгоритмом Гейла-Шепли. Однако, если нам дается только , число мужчин / женщин, мы задаем следующий вопрос: можем ли...
Учитывая огромную базу данных разрешенных слов (отсортированных по алфавиту) и слово, найдите слово из базы данных, которая является ближайшей к данному слову с точки зрения расстояния Левенштейна. Наивный подход, конечно, состоит в том, чтобы просто вычислить левенштейновское расстояние между...
Существует ли естественный параллельный аналог красно-черных деревьев со схожими или даже не очень худшими свойствами для обновлений, хотя он достаточно эффективен для работы? В целом, что мы можем сделать лучше для параллельного поиска с обновлениями?...
Граф H является ядром, если любой гомоморфизм из H в себя является биекцией. Подграф H группы G является ядром группы G, если H является ядром и существует гомоморфизм от G к H. http://en.wikipedia.org/wiki/Core_%28graph_theory%29 Учитывая граф G, какой самый известный точный алгоритм, чтобы найти...
Первым шагом алгоритма тестирования простоты AKS является проверка, является ли входное число идеальной степенью. Похоже, что это хорошо известный факт в теории чисел, поскольку в статье это не объясняется подробно. Может кто-нибудь сказать мне, как сделать это за полиномиальное время?...