Дано это даг. Вы хотите пометить каждый узел тем, сколько узлов доступно из него. - тривиальная верхняя граница; является нижней границей (я думаю). Есть ли лучший алгоритм? Есть ли основания полагать, что нижняя граница может быть улучшена (связана: что именно известно о нижних границах для...
Ширина дерева показывает, насколько близок график к дереву. NP-трудно вычислить ширину дерева. Наиболее известный алгоритм приближения достигает O ( войдите n----√)O(logn)O(\sqrt{{\log}n}) фактор. Теорема Курселя гласит, что любое свойство графов, определяемых в монадической логике второго порядка...
Мы знаем, что максимальный независимый набор (MIS) трудно аппроксимировать с коэффициентом для любого если P = NP. Какие существуют специальные классы графов, для которых известны лучшие алгоритмы аппроксимации?N1 - ϵn1−ϵn^{1-\epsilon}ε > 0ϵ>0\epsilon > 0 Каковы графики, для которых известны...
Первым шагом алгоритма тестирования простоты AKS является проверка, является ли входное число идеальной степенью. Похоже, что это хорошо известный факт в теории чисел, поскольку в статье это не объясняется подробно. Может кто-нибудь сказать мне, как сделать это за полиномиальное время?...
Этот вопрос перенесен из Биржи стеков информатики, потому что на него можно ответить в Теоретической бирже информатики. Мигрировал 3 года назад . В научной статье 2016 года « Реализация масштабируемого алгоритма Шора » [ 1 ] авторы учитывают 15 с только 5 кубитами, что меньше «требуемых» 8 кубитов...
Пусть L1,L2L1,L2L_1,L_2 будут двумя обычными языками, заданными NFA M1,M2M1,M2M_1,M_2 качестве входных данных. Предположим, мы хотели бы проверить, является ли L1∩L2≠∅L1∩L2≠∅L_1\cap L_2\neq \emptyset . Это можно сделать с помощью квадратичного алгоритма, который вычисляет автомат произведений...
Давайте посмотрим на будущее через 30 лет. Давайте будем оптимистичными и предположим, что области, связанные с машинным обучением, продолжают развиваться так же быстро, как мы видели за последние 10 лет. Это было бы здорово, но какова будет роль традиционной алгоритмики в таком будущем? Здесь под...
При разработке алгоритмов аппроксимации иногда решают полуопределенную программу с последующим шагом округления. Часто используемый пример, иллюстрирующий это, - Max-Cut. (См., Например, Алгоритмы аппроксимации Vijay Vazirani.) Существуют ли хорошие образовательные источники или обзоры, выходящие...
При сжатии считывания цель состоит в том, чтобы найти схемы линейного сжатия для огромных входных сигналов, которые, как известно, имеют разреженное представление, чтобы входной сигнал мог быть эффективно восстановлен из сжатия («эскиз»). Более формально, стандартная установка состоит в том, что...
Пусть G=(V,E)G=(V,E)G=(V,E) - граф. Для вершины x∈Vx∈Vx\in V , определим N(x)N(x)N(x) , чтобы быть (открытая) окрестность xxx в GGG . То есть N(x)={y∈V|{x,y}∈E}N(x)={y∈V|{x,y}∈E}N(x)=\{y\in V \,\vert\, \{x,y\}\in E\} . Определим две вершиныu,vu,vu,v вGGG какдвойники,еслиuuu иvvv имеют одинаковый...
Это похоже на « Алгоритмы из Книги ». Хотя сокращения также являются алгоритмами, я подумал, что сомнительно, что можно подумать о сокращении в ответ на вопрос об алгоритмах из книги. Отсюда отдельный запрос! Сокращения всех видов приветствуются. Я начну с действительно простого сокращения от...
Вот несколько способов проанализировать время работы алгоритма: 1) Анализ наихудшего случая: время выполнения в худшем случае. 2) Анализ среднего случая: ожидаемое время работы на случайном экземпляре. 3) Амортизированный анализ: среднее время работы в наихудшей последовательности экземпляров. 4)...
Речь идет о том, как эффективно мы можем выразить алгоритм под рукой. Мне нужно это для моего обучения студентов. Я понимаю, что нет такой вещи, как стандартный способ написания псевдокода. Разные авторы следуют различным соглашениям. Было бы полезно, если бы люди указывали на то, как они следуют и...
Я не совсем понимаю, почему почти все решатели SAT используют CNF вместо DNF. Мне кажется, что решение SAT проще с использованием DNF. В конце концов, вам просто нужно просмотреть набор импликантов и проверить, содержит ли один из них и переменную, и ее отрицание. Для CNF не существует такой...
В игре Tower Defense у вас есть сетка NxM с началом, финишем и несколькими стенами. Враги выбирают кратчайший путь от начала до конца, не проходя сквозь стены (обычно они не привязаны к сетке, но для простоты, скажем, так. В любом случае они не могут перемещаться через диагональные «дыры») Задача...
Тензор является обобщение векторов и матриц на более высокие размеры и ранг тензора также обобщает ранг матрицы. А именно, ранг тензора является минимальным числом ранга один тензоров этой суммы . Вектор и матрица являются тензорами степени 1 и 2 соответственно.TTTTTTT Элементы в происходят из поля...
Предположим, нам дано несколько непересекающихся простых многоугольников на плоскости и две точки и t вне каждого многоугольника. Задача евклидова кратчайшего пути состоит в том, чтобы вычислить евклидов кратчайший путь от s до t , который не пересекает внутреннюю часть любого многоугольника. Для...
Существуют ли проблемы в CS, где эффективные алгоритмы не известны, несмотря на теоремы существования, доказывающие, что такие эффективные алгоритмы должны существовать? Как называются эти проблемы? Где я могу узнать...
В научной статье 2002 года Мезард, Паризи и Зекчина выдвинули эвристику распространения верований для случайного 3SAT. Эксперименты показывают, что эвристика хорошо работает для соотношений ограничений на переменную, для которых вероятно существует удовлетворительное назначение. Мои вопросы: (1)...
Этот вопрос касается временной сложности алгоритма максимального потока Форда-Фулкерсона при использовании DFS для поиска путей расширения. Существует хорошо известный пример, показывающий, что при использовании DFS может потребоваться линейное число итераций в максимальном потоке, см., Например,...