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

Языки L_1, L_2, ..., L_2018 задаются регулярными выражениями. Необходимо построить полиномиальный алгоритм, который бы проверял, что пересечение их вс ...
0
голосов
1
ответ
96 показов

Докажите, что при любом натуральном $%k\geqslant 4$% можно заполнить таблицу $%k\times k$% различными целыми числами от 1 до $%k^2$% так, чтобы никаки ...
1
голос
0
ответов
242 показа

Приведите примеры NP-полных задач, которые вы знаете. Хочу порешать их для себя для саморазвития.
2
голоса
0
ответов
96 показов

Имеется 11 камней и специальные весы, с помощью которых за одно взвешивание можно узнать суммарный вес любых двух камней. За какое наименьшее количест ...
0
голосов
0
ответов
76 показов

Верно ли, что грамматика, где все правила вывода имеют вид A → xB, A → Bx, A →x; A, B ∈ N; x ∈ Σ ∪ {ε} порождает регулярный язык?
0
голосов
0
ответов
80 показов

Нужно построить машину тьюринга с полиномиальным временем выполнения, проверяющую, является ли слово палиндромом. Есть идея сравнивать первый и послед ...
1
голос
1
ответ
143 показа

Задача такая - доказать, что если число $%\alpha$% перечислимо снизу, то существует последовательность $%z_{1}, z_{2}, \dots \in \mathbb{Q}$%, предел ...
3
голоса
1
ответ
167 показов

Имеются 4 гайки, среди которых могут быть радиоактивные. Детектор позволяет определить, сколько из помещенных в него гаек радиоактивны. Как узнать, ка ...
0
голосов
1
ответ
216 показов

Даны n точек на плоскости $%(𝑥_1, 𝑦_1),(𝑥_2, 𝑦_2), . . . ,(𝑥_𝑛, 𝑦_𝑛)$%. И дано число k. Из этих $%n$% точек нужно накрыть как минимум $%k$% штук круго ...
0
голосов
0
ответов
194 показа

Существуют ли невычислимые частичные функции f,g: N -> N (не всюду определенные), т.ч. вычислима функция h с условием h(x) = f(x)*g(x) для всех x \ ...
2
голоса
0
ответов
176 показов

Приветствую, уважаемые форумчане. Не знаю, можно ли задавать тут вопросы по алгоритмам. Имеется n карточек, они стоят в ряд. Карточки двух цветов: бел ...
0
голосов
0
ответов
278 показов

За 7 ходов поменяйте монеты местами, передвигая их из одного прямоугольника в другой по чёрным линиям, соединяющим прямоугольники. При этом можно пере ...
2
голоса
1
ответ
255 показов

При помощи алгоритма Берлекэмпа разложить на неприводимые множители х^125 - x^25 + 1 над полем GF(5, 2)
1
голос
0
ответов
147 показов

Будет ли корректна теорема Кука, если в формулировке задачи о КНФ-выполнимости слово "выполняется" заменить на "тождественно ложна"?Теорема Кука утвер ...
0
голосов
0
ответов
95 показов

Реализовать программу машины Тюринга и проверить её работоспособность на 3-5 примерах.F(x)=x×12
на странице153050
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru