0
голосов
0
ответов
37 показов
Отношение классов NPC к PSPACE-полных
Может ли задача из NPC принадлежать к классу PSPACE-полных
0
голосов
0
ответов
86 показов
ZPP BPP RP [закрыт]
Пусть задача о проверке двух арифметических схем на равенство не лежит в ZPP. Докажите, что тогда множество троек схем, из которых совпадают ровно две ...
0
голосов
0
ответов
96 показов
ZPP BPP RP
Пусть задача о проверке двух арифметических схем на равенство не лежит в ZPP. Докажите, что тогда множество троек схем, из которых совпадают ровно две ...
0
голосов
0
ответов
211 показов
Не могу определить bigO для алгоритма
Алгоритм для задачи о рюкзаке, внутри шага количество операций константно, то есть C, НО количество шагов зависит не только от размера входных данных, ...
0
голосов
1
ответ
405 показов
Задача на рекурсивный алгоритм.
Массив А [1..n] содержит все целые числа от 0 до п за исключением одного. Отсутствующее число можно легко определить за время О (n),располагая вспомог ...
0
голосов
0
ответов
410 показов
Однопроходный алгоритм одной задачи
Как решить данную задачу за один проход или не более чем за O(n)? Может быть с созданием предварительно какой-то структуры? Задача. Дана последователь ...
0
голосов
0
ответов
341 показ
Доказать, что множество не является рекурсивно перечислимым
Докажите, что множество A = {x | Wx не содержит чётных чисел} (где $$W_x = \{y\ |\ φ_x(y) ↓\}$$ естьобласть определения функции φx) не является рекурс ...
0
голосов
1
ответ
366 показов
Как вычислить сумму ?
Вычислите сумму $% 1 + 2⋅3 + 3⋅3^2 + 4⋅3^3 + \cdots +50⋅3^{49}$%
0
голосов
0
ответов
257 показов
Изменится ли класс, если «полиномиальное в худшем случае» заменить на «полиномиальное в среднем»?
Изменится ли класс, если «полиномиальное в худшем случае» заменить на «полиномиальное в среднем»? (скорее всего изменится, но нужно привести какой-ниб ...
0
голосов
1
ответ
333 показа
Использование БПФ для нахождения значений многочлена
Дан многочлен $%f(x)\in \mathbb{C}[x], \deg f=n-1.$% Требуется найти набор значений этого многочлена на наборе аргументов $%\{e^{ik}\}, k\in \overline ...
-1
голосов
0
ответов
591 показ
Полиномиальное время
Полиномиальное время это любое не экспонентное и не факториальное время? То есть, любое время, которое не превышает полиномиальное может быть полиноми ...
0
голосов
0
ответов
589 показов
Нужны примеры NP-полных задач
Приведите примеры NP-полных задач, которые вы знаете. Хочу порешать их для себя для саморазвития.
0
голосов
0
ответов
374 показа
Задача по геометрии
Решите пожалуйста задачку:Окружность, построенная на стороне АВ треугольника АВС как на диаметре, пересекает стороны АС и ВС в точках P и Q соответств ...
0
голосов
0
ответов
522 показа
Необходимо построить алгоритм, который находит минимальный элемент в куче на максимум
Необходимо построить алгоритм, который находит минимальный элемент в куче с максимальным свойством и доказать, что он оптимальный (т.е. если построенн ...
0
голосов
0
ответов
371 показ
Доказать приближение алгоритма
Задача: даны n предметов весом Xi и n корзин с одинаковой вместимостью V, V больше либо равно максимальному из Xj. нужно разместить все предметы в как ...
84 вопроса
Связанные метки
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.