Языки L_1, L_2, ..., L_2018 задаются регулярными выражениями. Необходимо построить полиномиальный алгоритм, который бы проверял, что пересечение их вс ...
Докажите, что при любом натуральном $%k\geqslant 4$% можно заполнить таблицу $%k\times k$% различными целыми числами от 1 до $%k^2$% так, чтобы никаки ...
Имеется 11 камней и специальные весы, с помощью которых за одно взвешивание можно узнать суммарный вес любых двух камней. За какое наименьшее количест ...
Нужно построить машину тьюринга с полиномиальным временем выполнения, проверяющую, является ли слово палиндромом. Есть идея сравнивать первый и послед ...
Задача такая - доказать, что если число $%\alpha$% перечислимо снизу, то существует последовательность $%z_{1}, z_{2}, \dots \in \mathbb{Q}$%, предел ...
Имеются 4 гайки, среди которых могут быть радиоактивные. Детектор позволяет определить, сколько из помещенных в него гаек радиоактивны. Как узнать, ка ...
Даны n точек на плоскости $%(𝑥_1, 𝑦_1),(𝑥_2, 𝑦_2), . . . ,(𝑥_𝑛, 𝑦_𝑛)$%. И дано число k. Из этих $%n$% точек нужно накрыть как минимум $%k$% штук круго ...
Существуют ли невычислимые частичные функции f,g: N -> N (не всюду определенные), т.ч. вычислима функция h с условием h(x) = f(x)*g(x) для всех x \ ...
Приветствую, уважаемые форумчане. Не знаю, можно ли задавать тут вопросы по алгоритмам. Имеется n карточек, они стоят в ряд. Карточки двух цветов: бел ...
За 7 ходов поменяйте монеты местами, передвигая их из одного прямоугольника в другой по чёрным линиям, соединяющим прямоугольники. При этом можно пере ...
Будет ли корректна теорема Кука, если в формулировке задачи о КНФ-выполнимости слово "выполняется" заменить на "тождественно ложна"?Теорема Кука утвер ...