В своей книге Рандомизированных алгоритмы , Motwani и Raghavan открыть введение с описанием их функции RandQS - Рандомизированная - где быстрой сортировкой стержень, используемый для разделения множества на две части, выбирается случайным образом . В течение некоторого времени я ломал свои мозги...
Существует ли алгоритм / систематическая процедура для проверки того, является ли язык свободным от контекста? Другими словами, учитывая язык, указанный в алгебраической форме (подумайте о чем-то вроде ), проверьте, является ли язык контекстно-свободным или нет , Представьте, что мы пишем...
У меня NP-полное решение проблемы. Учитывая пример проблемы, я хотел бы разработать алгоритм, который выводит ДА, если проблема выполнима, и НЕТ, в противном случае. (Конечно, если алгоритм не является оптимальным, он будет делать ошибки.) Я не могу найти никаких приближенных алгоритмов для таких...
Я начинаю читать книгу о вычислительной сложности и машинах Тьюринга. Вот цитата: Алгоритм (т. Е. Машина) может быть представлен в виде битовой строки, как только мы определимся с каноническим кодированием. Это утверждение представлено как простой факт, но я не могу его понять. Например, если у...
Я хочу знать, разрешима ли следующая проблема и как узнать. В каждой проблеме, которую я вижу, я могу сказать «да» или «нет», так что большинство проблем и алгоритмов разрешимы, кроме нескольких (которые представлены здесь )? Входные данные: направленный и конечный граф с вершинами и Вопрос:...
Черный ящик с f(x)f(x)f(x) означает, что я могу оценить многочлен в любой точке.f(x)f(x)f(x) Вход : черный ящик монического полинома степени .f(x)∈Z+[x]f(x)∈Z+[x]f(x) \in\mathbb{Z}^+[x]ddd Вывод: В коэффициенты многочлена .dddf(x)f(x)f(x) Мой алгоритм: пусть...
В моем курсе « Алгоритмы и структуры данных» профессора, слайды и книга ( Введение в алгоритмы, 3-е издание ) использовали слово NILдля обозначения, например, дочернего элемента узла (в дереве), который не существует. Однажды, во время лекции, вместо того, чтобы сказать NIL, мой одноклассник сказал...
Я даю вам список из nnn битвекторов шириной kkk . Ваша цель - вернуть два битовых вектора из списка, у которых нет общих единиц, или сообщить, что такой пары не существует. Например, если я дам вам [00110,01100,11000][00110,01100,11000][00110, 01100, 11000] то единственным решением будет...
Я заметил, что при реализации поисковых алгоритмов используются разные структуры данных. Например, мы используем очереди для реализации поиска в ширину, стеки для поиска в глубину и мини-кучи для реализации алгоритма A * . В этих случаях нам не нужно явно создавать дерево поиска. Но я не могу найти...
Дан плоский план G=(V,E)G=(V,E)G=(V,E) и пусть GG\mathcal{G} обозначает его вложение в плоскость st, каждое ребро которого имеет длину . Кроме того, у меня есть множество точек в которых каждая точка содержится в . Кроме того, для любой точки в верно, что существует с геодезическим расстоянием до...
Этот вопрос касается подхода к компьютерным оппонентам, который я создал и который в настоящее время используется или планируется использовать в нескольких компьютерных играх. Фон В прошлом году, когда я пытался улучшить компьютерного противника для игры под названием «Флаги Сапер» (краткое...
Я работал над следующей проблемой из этой книги . Определенный язык обработки строк предлагает примитивную операцию, которая разбивает строку на две части. Поскольку эта операция включает в себя копирование исходной строки, для строки длиной n требуется n единиц времени, независимо от...
Немного подставного лица: я специалист по информатике и работаю программистом. Итак, извините, если эта подсказка кажется несколько за пределами левого поля - я обычно играю с математической симуляцией и открываю задачи, когда мне нечего делать. Играя с гипотезой Римана , я определил, что главный...
Алгоритм минимизации DFA Бжозовского создает минимальный DFA для DFA путем:граммGG обращая все ребра в , делая начальное состояние принимающим, а принимающее - начальным, чтобы получить NFA для обратного языка,N ′граммGGN'N′N' используя конструкцию powerset, чтобы получить для обратного...
Указанные языки и , скажем , что их конкатенация является однозначной , если для всех слов , существует ровно один разложение с и , и неоднозначном иначе. (Я не знаю, есть ли установленный термин для этого свойства - трудная вещь для поиска!) В качестве тривиального примера, конкатенация с самим...
Определение : Многоугольник PPP на плоскости называется монотонным относительно прямой LLL , если каждая прямая, ортогональная LLL пересекает PпP не более двух раз. Для данного многоугольника PPP возможно ли определить, существует ли какая-либо прямая LLL такая, что многоугольник PPP является...
Я пытался придумать систему, которая оценивала бы устав организации для определения их базовой логики. Я думаю, что система предикатов первого порядка будет работать для представления правил, которые могут быть переведены из текста с помощью тегов части речи и других методов НЛП. Существует ли...
В книге Марка де Берга и др. «Вычислительная геометрия: алгоритмы и приложения» описан очень простой алгоритм грубой силы для вычисления триангуляций Делоне. Алгоритм использует понятие недопустимых ребер - ребер, которые могут отсутствовать в допустимой триангуляции Делоне и должны быть заменены...
Я изучал эти три, и я излагаю свои выводы из них ниже. Может ли кто-нибудь сказать мне, достаточно ли я их понял, или нет? Спасибо. Дейкстры алгоритм используется только тогда , когда у вас есть один источник , и вы хотите знать , наименьший путь от одного узла к другому, но не может в таких...
Вы и друг потеряли друг друга в очереди на концерт, и никто не уверен, кто из вас еще впереди. Формально каждый из них имеет некоторую целочисленную координату и может идти только к более высокой координате или оставаться на месте. Предполагая, что вы и ваш друг придерживаетесь одного и того же...