Тест по сложности алгоритмов для 3 курса ИСПРАН — вопросы

Тест по курсу «Эффективные алгоритмы»

Вариант 1937026886.

Ваше имя*:

Возможно ли сконструировать алгоритм , который для произвольной машины Тюринга и входа определит, остановится ли данная М.Т. на заданном входе?

Нет
Формально да, но никто не знает как именно это сделать (примерно как со вполне упорядочиванием );
Да, известно чёткое описание того, как это делать;

Какие из подходов к решению вычислительно трудных задач изучались в курсе?

Построение эффективных алгоритмов методом ветвей и границ
Построение недетерминированных полиномиальных алгоритмов
Построение эффективных приближенных алгоритмов, использующих метод вероятностного округления решений релаксационных задач

Рассмотрим две задачи разрешения, P1 и P2, такие что

Что можно утверждать?

Навигация