0
голосов
0
ответов
59 показов

Пусть мы умеем находить ответ на вопрос: "существует ли в произвольном графе Гамильтонов цикл" за полиномиальное время. Другими словами пусть NP=P.Пус ...
0
голосов
0
ответов
76 показов
0
голосов
0
ответов
90 показов
0
голосов
0
ответов
142 показа

Структура данных поддерживает операцию, такую что последовательность из n вызовов этой операции занимает время \Тета(nlogn) в худшем случае. Какова ам ...
0
голосов
0
ответов
148 показов

Дана строка $%s$% в алфавите $%\Sigma_1$% и строка $%t$% в алфавите $%\Sigma_2$%, требуется найти инъективную функцию $%f{:}\,\Sigma_1\rightarrow\Sigm ...
1
голос
1
ответ
139 показов

Есть несколько примеров, которые очень хотелось бы понять.Первый пример, нужно найти Theta или O.Довольно логично что это Но совсем не знаю как доказа ...
0
голосов
0
ответов
154 показа

Здравствуйте, почитав math.hashcode.ru/questions/35138#35141 и наконец разобравшись в проблеме NP и P задач меня заинтересовало: существуют ли более с ...
0
голосов
1
ответ
224 показа

$%PP$% определяется как класс языков, для которых существует вероятностная МТ, такая что она выдает 1 с вероятностью большей 0.5 на словах из языка, и ...
0
голосов
0
ответов
163 показа

Дана коробка и набор карт. Карту в коробку можно положить только двумя способами. В каждой карточке есть два столбца отверстий, некоторые из которых м ...
0
голосов
0
ответов
181 показ

Поле, разделенное на n грядок, каждая из которых разделенана m ячеек. Грядки отделены друг от друга стенами; между ячейками одной грядки стен нет. В н ...
0
голосов
0
ответов
209 показов

Пусть $%R$% – коммутативное кольцо с 1 и $%f,g\in R[x,y]$%. Пусть $%f,g$% имеют степень $%\leqslant m$% относительно $%y$% и $%\leqslant n$% относител ...
0
голосов
1
ответ
429 показов

Не могу понять как можно дать оценку сложности алгоритму поиска последовательности де Брейна $%B(n,k)$%. Тут $%n$% - это количество символов в алфавит ...
0
голосов
0
ответов
196 показов

Оцените рекуррентное соотношение с помощью дерева рекурсий: $%T(n)=T(\frac{n}{9})+T(\frac{13n}{18}+10)+O(n)$%.
1
голос
0
ответов
202 показа

Рассмотрим алгоритм быстрого умножения двух двоичных чисел методом Карацубы. Получим рекуррентность для оценки полного числа всех элементарных битовых ...
на странице153050
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru