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

1

2

3

4

Еженедельный по «сложности алгоритмов» для 3 курса ИСПРАН

Вариант 4276507932.

Ваше имя*:

Вопрос 1

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

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

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

Вопрос 2

Выберите общепринятое определение класса NPC (NP-полных задач).

тогда и только тогда, когда:

Вопрос 3

Является ли конкатенация двух разрешимых языков перечислимой?

Нет;
Да;

Вопрос 4

Выберите верное утверждение

Из сводимости по Карпу следует сводимость по Куку
Из сводимости по Куку следует сводимость по Карпу
Верного ответа нет

Вопрос 5

Выберите верное верное утверждение из списка ниже, если верных вариантов ответа несколько, то выберите наиболее сильный из них:

Нет верного ответа;
Из перечислимости множества следует его разрешимость;
Перечислимые и разрешимые множества никак не пересекаются;
Из разрешимости множества следует его перечислимость;

Вопрос 6

Задачи 3SAT и 2SAT:

Первая NP-полна и вторая в P.
Все остальные варианты — неверны.
Обе NP-полны
Обе в P
Первая неразрешима и вторая — NP-полна.

Вопрос 7

Выберите верное утверждение

;
;

Вопрос 8

Будет ли класс -полных задач замкнутым относительно сводимости по Карпу, если окажется, что ?

Да;
Нет;

Вопрос 9

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

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

Вопрос 10

Пересечение двух каких классов окажется пустым, если окажется, что ?

и ;
и ;
и ;