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

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

Вариант 739431456.

Ваше имя*:

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

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

Что верно для NP-полных и NP-трудных задач:

Первой задачей с доказанной NP-полнотой была CircuitSAT, «the circuit satisfiability problem»
Все варианты, кроме «ничего не верно»
Если мы хотим доказать, что задача X — NP-трудна, мы берем известную NP-полную задачу Y и сводим ее полиномиально по Карпу к X.
Ничего не верно.

Рассмотрим пару задач на графах.

P1: Для заданного графа, подтвердить или опровергнуть, что в нем есть цикл, которые посещает однократно все вершины, кроме первой, в которую надо вернутся, чтобы завершить цикл.
P2

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

Навигация