Предположим, у нас есть матрица n на n. Можно ли изменить порядок строк и столбцов так, чтобы мы получили верхнетреугольную матрицу? Этот вопрос мотивирован этой проблемой: положительный топологический порядок Первоначальная проблема решения, по крайней мере, так же сложна, как эта, поэтому...
Пусть . Мы хотим оценить среднее значение , то есть: .f E [ f ( n ) ] = 2 - n ∑ x ∈ { 0 , 1 } n f ( x )f:{0,1}n→(2−n,1]f:{0,1}n→(2−n,1]f \colon \lbrace 0,1 \rbrace ^ n \to (2^{-n},1]fffE[f(n)]=2−n∑x∈{0,1}nf(x)E[f(n)]=2−n∑x∈{0,1}nf(x)\mathbb{E}[f(n)]=2^{-n}\sum_{x\in \lbrace 0,1 \rbrace ^ n}f(x)...
Каковы некоторые известные результаты для нахождения точного n-мерного подмассива внутри n-мерного массива? В 1D это просто проблема соответствия строк, KMP делает это за линейное время. В 2D эта статья показала, что это можно сделать за линейное время с небольшим дополнительным пространством....
Я ищу хороший обзор алгоритмов и сложности линейной алгебры (операции типа ранга, обратные, собственные значения, ... для логических, и целых / рациональных матриц) с акцентом на параллельные ( иерархия N C ) и полимерные алгоритмы , Я не мог найти недавний.FpFp\mathbb{F}_pNCNCNC Знаете ли вы...
В классе сложности есть некоторые проблемы, предположительно не входящие в класс N C , то есть проблемы с детерминированными параллельными алгоритмами. Проблема максимального потока является одним из примеров. И есть проблемы, СЧИТАЕМЫЕ быть в N C , но доказательство еще не...
Допустим, что язык является P- плотно-близким, если существует алгоритм с полиномиальным временем, который правильно определяет почти на всех входах.LLLLLLL Другими словами, существует P , такое, что обращается в нуль, что означает Это также означает, что на равномерном случайном входе алгоритм...
Я недавно прочитал это краткое изложение проблем, связанных с выполнением различий между деревьями, и мне стало интересно узнать, каково состояние этой проблемы. Кроме того, предположим, что между разрешенными операциями редактирования находится традиционный узел добавления / удаления, для...
Коллега, который работает над генетическим программированием, задал мне следующий вопрос. Сначала я попытался решить ее, основываясь на жадном подходе, но потом подумал, что нашел контрпример к жадному алгоритму. Итак, я подумал, что стоит упомянуть здесь. Рассмотрим два полинома, которые...
Кто-нибудь может мне помочь со следующей проблемой? Я хочу найти некоторые значения a i , b jai,bja_i,b_j (mod NNN ), где i = 1 , 2 , … , K , j = 1 , 2 , … , Ki=1,2,…,K,j=1,2,…,Ki=1,2,…,K, j=1,2,…,K (например, К = 6K=6K=6 ), учитывая список значений К 2K2K^2 которые соответствуют различиям a i - b...
Locked . Этот вопрос и его ответы заблокированы, потому что вопрос не по теме, но имеет историческое значение. В настоящее время он не принимает новые ответы или взаимодействия. Какие алгоритмы используются чаще всего? Пожалуйста, напишите один алгоритм для каждого ответа, постарайтесь, чтобы ваш...
Я искал наиболее эффективный (потоковый ??) алгоритм, который сообщает мне «k» наиболее часто встречающихся элементов в потоке данных в любой момент времени. Этот пост: «Разделяй и властвуй» алгоритмы потока данных заинтересовали меня. Например, предположим, что есть числа:...
Справочная информация: Чао Сюй некоторое время назад опубликовал следующий вопрос: « Существуют ли какие-либо известные алгоритмы сортировки сравнения, которые не сводятся к сортировке сетей, так что каждый элемент сравнивается раз?O(logn)O(logn)O(\log n) ». Кажется, мы немного застряли в...
Для конкретности рассмотрим LP для решения игры с нулевой суммой для двух игроков, где у каждого игрока есть действий. Предположим, что каждая запись матрицы выплат имеет самое большее 1 в абсолютном значении. Для простоты давайте не будем делать предположений об ограниченности.nnnAAA Предположим,...
Какова наиболее известная сложность для вычисления точного расстояния редактирования между двумя строками одинаковой длины с использованием рабочего пространства, которое является сублинейным по размеру ввода? Я предполагаю, что вход хранится в каком-то формате только для чтения. Это ранее...
Как известно, вычисление постоянной Чигера для графика , также известного как изопериметрическая постоянная (поскольку это, по сути, минимальное отношение площади / объема), является NP-полным. Вообще это приблизительно. Мне интересно узнать, известны ли точные полиномиальные алгоритмы для...
Вам дан граф с вершинами. Это может быть двудольный, если хотите. Существует наборов ребер (скажем, дизъюнкт). Меня интересует проблема нахождения как можно меньшего (или даже меньшего) подмножества , такого, чтобы индуцированный граф имел хотя бы одно ребро из каждого класса , для ,G = ( V,...
В своей статье (стр. 503) Гарей и Джонсон замечают: ... может существовать NP-полная задача, которая не является NP-полной в строгом смысле и не разрешима алгоритмом псевдополиномиального времени ... Кто-нибудь знает некоторые возможные проблемы со свойствами, упомянутыми выше? Я думаю, что...
Существует множество алгоритмов, которые могут анализировать грамматику без контекста за . Используя матричное умножение, можно даже пойти асимптотически быстрее, чем это.O(n3)O(n3)O(n^3) Тем не менее, все алгоритмы для разбора произвольных CFG, которые я знаю, имеют использование пространства в...
Предположим, что TTT - дерево постоянной степени, структура которого мы не знаем. Проблема состоит в том, чтобы вывести дерево , задавая запросы в форме: «Находится ли узел на пути от узла к узлу ?». Предположим, что на каждый запрос оракул может ответить в постоянное время. Мы знаем значение ,...
Похоже, что для некоторых задач NP-Hard много работы по разработке быстрых экспоненциальных алгоритмов с точным временем (т. Е. Результатов вида: Алгоритм A решает задачу за время O (c ^ n), причем c мало). Похоже, что для решения некоторых сложных задач (например, « Измерить и победить»: простой...