Тест по курсу «Эффективные алгоритмы для труднорешаемых задач» — вопросы

Материал из DISCOPAL
Перейти к: навигация, поиск
12345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950
51
Тест по курсу «Эффективные алгоритмы для труднорешаемых задач»

Вариант 1639574845.

Ваше имя*:

Вопрос 1

Пусть задача A — «есть ли цикл в ненаправленном графе». Рассмотрим набор утверждений.


  • (1) Задача A — в P
  • (2) Задача A — в NP
  • (3) Если задача A — NP-полна, то существует НМТ, решающая A за полиномиальное время.

Что верно?

  1.  1, 2 и 3
  2.  1 и 2
  3.  Все остальные варианты — неверны.
  4.  1 и 3
  5.  2 и 3

Вопрос 2

В чем заключается главный и несколько контринтуитивный вывод из Теоремы Блюма об ускорении?

  1.  Для любой задачи из класса EXPTIME теоретически существует оптимальный алгоритм из класса P, однако в силу ограничений формальных систем мы принципиально не можем его сконструировать.
  2.  Существуют разрешимые задачи, для которых принципиально не существует «самого эффективного» алгоритма, так как любой придуманный алгоритм можно алгоритмически ускорить.
  3.  Абсолютно любую разрешимую задачу можно алгоритмически оптимизировать до логарифмического времени , если снять жесткие ограничения на использование доступной рабочей памяти.
  4.  Переход от классической детерминированной машины Тьюринга к недетерминированной всегда гарантированно дает логарифмическое ускорение для всех без исключения задач разрешения.

Вопрос 3

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

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

Вопрос 4

Пусть S — задача из NPC, а Q и R — тоже задачи, но про них известно только, что Q — полиномиально сводиться по Карпу к S, а S — к R.

Что будет верно?

  1.  Q — NP-трудная
  2.  R — NP-трудная
  3.  Q — NP-полная
  4.  R — NP-полная

Вопрос 5

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


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

Вопрос 6

Какова вычислительная цена (штраф) при симуляции произвольной -ленточной машины Тьюринга на одноленточной машине Тьюринга?

  1.  Время работы не меняется, штрафа нет
  2.  Логарифмический штраф
  3.  Линейный штраф
  4.  Экспоненциальный штраф
  5.  Квадратичный штраф (время работы возрастает до )

Вопрос 7

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

  • P1 сводится полиномиально по Карпу к 3SAT
  • 3SAT сводится полиномиально по Карпу к P2

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


  1.  Все остальные варианты — неверны.
  2.  P1 в NP, P2 в NP-hard
  3.  Обе в NP
  4.  P2 в NP, P1 в NP-hard
  5.  Обе в NP-hard

Вопрос 8

Существует ли биекция между классами и ?

  1.  Да, существует;
  2.  Нет, не существует;
  3.  Ответ на этот вопрос нет, т.к. нам ничего неизвестно про равенство классов и ;

Вопрос 9

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

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

Вопрос 10

Какое важное следствие из «Теоремы о линейном ускорении» оправдывает повсеместное использование -нотации в теории сложности?

  1.  Подобное алгоритмическое ускорение применимо исключительно для задач, входящих в класс P, поэтому именно для них принято отбрасывать константы при оценке асимптотической сложности.
  2.  Любую машину Тьюринга можно ускорить в произвольное константное число раз за счет расширения алфавита и множества состояний, поэтому константы не имеют фундаментального значения.
  3.  Теорема строго доказывает, что время работы любого полиномиального алгоритма можно алгоритмически свести к асимптотически линейному за счет оптимизации переходов между состояниями.
  4.  Из теоремы следует, что на достаточно больших объемах входных данных полиномиальные алгоритмы всегда выполняются быстрее экспоненциальных, независимо от скрытых констант.

Вопрос 11

При определении класса NP через детерминированную машину Тьюринга используется концепция «Артура и Мерлина» (задача и сертификат/подсказка). Какие строгие требования накладываются на подсказку , чтобы задача принадлежала классу NP?

  1.  Подсказка должна содержать полный перебор всех вариантов решения, чтобы ДМТ могла выбрать лучший
  2.  Длина подсказки ограничена полиномом от длины входа , и алгоритм проверки работает за полиномиальное время
  3.  Длина должна быть константой, а проверка может занимать любое время
  4.  Проверка должна работать за константное время

Вопрос 12

Пусть

  • — задача поиска гамильтонового цикла в графе , где V — делится на 3.
  • — задача подтверждения наличия гамильтонового цикла в таком графе.

Что верно?

  1.   — NP-hard, но не .
  2.  Они обе не NP-hard.
  3.   и — NP-трудны.
  4.  Все остальные варианты — неверны.
  5.   — NP-hard, но не .

Вопрос 13

Выберите верное следствие:

  1.  Из перечислимости множества следует его ко-перечислимость;
  2.  Из разрешимости множества следует его ко-разрешимость;
  3.  Ничего из этого не является верным;

Вопрос 14

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

  1.  Нет;
  2.  Да;

Вопрос 15

Какой ключевой аргумент используется для доказательства того, что ?

  1.  Машина, использующая полиномиальную память , имеет экспоненциальное количество уникальных конфигураций. Если она сделает больше шагов, то неизбежно повторит конфигурацию и зациклится.
  2.  В теории асимптотической сложности алгоритмов полином, возведенный в степень произвольной константы, всегда растет асимптотически медленнее, чем экспоненциальная функция от того же полинома.
  3.  Фундаментальная теорема Сэвича строго доказывает, что детерминированная и недетерминированная память эквивалентны с точностью до квадрата, что в итоге и дает экспоненциальный рост по времени.
  4.  Любую вычислительную задачу, требующую для своего решения полиномиальной памяти, всегда можно тривиально решить полным обходом дерева всех возможных вариантов за экспоненциальное время.

Вопрос 16

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

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

Вопрос 17

Задача 2SAT:

  1.  Все остальные варианты — неверны.
  2.  NP-полна
  3.  разрешима за полиномиальное время, но не за константное время.
  4.  NP-трудна, но не NP-полна.
  5.  разрешима за константное время, т.к. любой вход для такой задачи выполним.

Вопрос 18

Выберите корректное утверждение относительно классов сложности:

  1.  
  2.  
  3.  
  4.  

Вопрос 19

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

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

Вопрос 20

Выберите задачу, которая доказанно разрешима в классе экономной памяти :

  1.  Определение выполнимости булевой формулы, заданной в конъюнктивной нормальной форме (задача 3SAT)
  2.  Проверка правильности скобочной последовательности (язык правильно вложенных скобок )
  3.  Поиск гамильтонова цикла в произвольном неориентированном графе (задача SHAM)
  4.  Нахождение оптимального решения для задачи целочисленного линейного программирования (ЦЛП)

Вопрос 21

Почему верно базовое включение ?

  1.  Данное утверждение в корне неверно, так как правильное фундаментальное соотношение является обратным: пространственная сложность всегда строго вложена во временную сложность.
  2.  За один такт работы машина Тьюринга может сдвинуть головку только на одну ячейку, поэтому за времени она физически не успеет «потрогать» больше чем ячеек памяти.
  3.  В современных вычислительных архитектурах доступ к ячейкам памяти является существенно более дорогостоящей операцией по сравнению с процессорным временем, затрачиваемым на вычисления.
  4.  Согласно теореме Блюма об ускорении, затраченное алгоритмическое время всегда можно пропорционально сжать до объема использованной рабочей памяти путем расширения ленточного алфавита.

Вопрос 22

Каким стандартным методом исходная задача оптимизации (например, поиск кратчайшего маршрута коммивояжёра) полиномиально сводится к соответствующей задаче разрешения (есть ли маршрут длины не более B)?

  1.  Двоичным (бинарным) поиском по ответу
  2.  Поиском в глубину (DFS)
  3.  Сведением по Карпу
  4.  Симплекс-методом
  5.  Преобразованием Цейтина
  6.  Сведением по Куку

Вопрос 23

Множество S является разрешимым, тогда и только тогда, когда существует такая машина Тьюринга T, что:

  1.  , то T останавливается и выводит 1, а если , то T зацикливается
  2.  , то T останавливается и выводит 1
  3.  , то T останавливается и выводит 1, а если , то T останавливается и выводит 0
  4.  , то T останавливается и выводит 0

Вопрос 24

Является ли пустое множество разрешимым?

  1.  Да;
  2.  Нет;

Вопрос 25

Почему при сведении задачи SAT к 3SAT (разбиение длинных скобок на короткие) применяется преобразование Цейтина с введением новых переменных, а не стандартное применение законов дистрибутивности булевой алгебры?

  1.  Стандартное раскрытие скобок может привести к экспоненциальному росту длины формулы, а преобразование Цейтина увеличивает размер лишь полиномиально
  2.  Законы дистрибутивности не сохраняют выполнимость исходной формулы
  3.  Это просто историческая традиция, сложность обеих процедур одинакова
  4.  Преобразование Цейтина позволяет заодно избавиться от всех отрицаний в формуле

Вопрос 26

Существует ли алгоритм, который выписывает одну за другой все машины Тьюринга, которые не останавливаются, будучи запущенными на пустой ленте?

  1.  Да
  2.  Нет

Вопрос 27

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

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

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

  1.  P1 в NPC, P2 в P.
  2.  Обе в NPC
  3.  Все остальные варианты — неверны.
  4.  X в NP, но не NP-полная.
  5.  Обе в P
  6.  P2 в NPC, P1 в P.

Вопрос 28

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

  1.  Декартово произведение;
  2.  Разность множеств;
  3.  Дополнение;

Вопрос 29

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


  1.  
  2.  ;
  3.  ;

Вопрос 30

Как, согласно конспекту лекции, существование квантовых компьютеров влияет на Тезис Чёрча-Тьюринга?

  1.  Никак не влияют, квантовые компьютеры не расширяют класс вычислимых функций, а сверхтьюринговые вычисления остаются фантастикой
  2.  Квантовые компьютеры переводят все задачи из NP в класс P, делая тезис неактуальным
  3.  Квантовые компьютеры опровергают тезис, так как они могут вычислять невычислимые по Тьюрингу функции
  4.  Тезис Чёрча-Тьюринга был изменен в 1990-х годах, чтобы исключить квантовые эффекты

Вопрос 31

Какое строгое включение гарантированно следует из Теоремы об иерархии по времени (Time Hierarchy Theorem)?

  1.  Класс полиномиальных задач строго вложен в класс экспоненциальных:
  2.  Класс полиномиальных задач строго вложен в класс недетерминированных полиномиальных:
  3.  Класс задач, требующих логарифмической памяти, строго вложен в класс полиномиальных по времени:
  4.  Класс недетерминированных полиномиальных задач строго вложен в класс задач с полиномиальной памятью:

Вопрос 32

Предположим, разумеется, что Тогда что будет верно?

  1.  
  2.  
  3.  
  4.  

Вопрос 33

Пусть X — задача из NP. Что верно?

  1.  Если X — NP-hard, то она NP-полная
  2.  X — NP-трудная
  3.  Нет полиномиального алгоритма для X
  4.  Все остальные варианты — неверны.
  5.  X может быть неразрешима
  6.  Если X можно решить за полиномиальное время на ДМТ, то P=NP

Вопрос 34

У языков L1-L4 доказаны следующие полиномиальные сводимости по Карпу: «L1→L2», «L3→L2→L4» Рассмотрим утверждения:

I
Если L4 в P, то L2 в P
II
Если L1 или L3 в P, то L2 в P
III
L1 в P, тогда и только тогда, когда L3 в P
IV
Если L4 в P, то L1 в P и L3 в P.


  1.  Только (I) и (IV)
  2.  Только (II)
  3.  Только (III)
  4.  Все остальные варианты — неверны.
  5.  Только (I)

Вопрос 35

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

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

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  

Вопрос 36

В чем заключается ключевое концептуальное отличие полиномиальной сводимости по Карпу от сводимости по Куку?

  1.  Сводимость по Куку сохраняет замкнутость класса NP, а сводимость по Карпу — нет
  2.  Сводимость по Карпу требует отображения входов одной задачи во входы другой (), в то время как сводимость по Куку допускает многократный «вызов подпрограммы» решения другой задачи
  3.  Сводимость по Карпу может использовать экспоненциальное время для преобразования
  4.  Сводимость по Куку работает только для задач оптимизации, а по Карпу — для задач разрешения

Вопрос 37

Из какого фундаментального факта напрямую следует существование функций, невычислимых по Тьюрингу?

  1.  Множество всех машин Тьюринга счётно (), а множество всех булевых функций над натуральными числами континуально ()
  2.  Проблема остановки сводится к задаче SAT за полиномиальное время
  3.  Диагональный аргумент Кантора доказывает, что множество рациональных чисел несчётно
  4.  Множество всех машин Тьюринга континуально, а множество всех алгоритмов счётно
  5.  Машины Тьюринга не могут генерировать случайные числа

Вопрос 38

При доказательстве неразрешимости (или трудности) новой задачи с помощью метода сведения, в каком направлении должно строиться это сведение?

  1.  Известную сложную/неразрешимую задачу (например, HALT) нужно свести к новой исследуемой задаче
  2.  Новую исследуемую задачу нужно свести к любой разрешимой задаче из класса P
  3.  Направление не имеет значения, так как сведение — это симметричное отношение эквивалентности
  4.  Новую исследуемую задачу нужно свести к известной сложной/неразрешимой задаче

Вопрос 39

Выберите не NP-полную задачу

  1.  SAT
  2.  Сумма множеств
  3.  2SAT
  4.  3SAT
  5.  Клика (есть ли в графе клика больше заданной)
  6.  Вершинное покрытие
  7.  TSP-выполнимость

Вопрос 40

Что представляет собой Универсальная машина Тьюринга (УМТ) в контексте данного курса?

  1.  «Захардкоженный» интерпретатор, способный прочитать описание любой другой машины Тьюринга и симулировать её работу
  2.  Абстрактная машина, которая использует бесконечное количество лент для вычисления невычислимых функций
  3.  Это машина Тьюринга, способная за конечное время решить проблему остановки для любой другой машины
  4.  Все остальные варианты — неверны.
  5.  Историческая машина (Turing Bombe), построенная в Блетчли-парке для взлома шифров «Энигмы»

Вопрос 41

Почему при оценке пространственной сложности (например, для класса ) ячейки входной ленты не учитываются в общей потребляемой памяти?

  1.  Входная лента в подобных задачах разрешения используется исключительно для записи итогового бинарного ответа, следовательно, она всегда занимает строго константный объем памяти .
  2.  Иначе минимальная пространственная сложность всегда была бы не меньше (так как нужно прочитать вход), и мы не смогли бы изучать сублинейные классы памяти.
  3.  Входная лента по определению формальной модели является бесконечной в обе стороны, и её прямой учет неизбежно привел бы к оценке памяти как бесконечной для любого алгоритма.
  4.  В классической модели одноленточной машины Тьюринга выделенная входная лента физически отсутствует, поэтому концептуально невозможно учитывать её как отдельный ресурс памяти.

Вопрос 42

Как задача 2SAT решается за линейное время ?

  1.  Путем применения преобразования Цейтина к каждой скобке
  2.  Путем сведения к задаче вершинного покрытия (Vertex Cover) и жадного обхода
  3.  Запуском симплекс-метода, так как 2SAT это частный случай линейного программирования
  4.  Построением графа импликаций и поиском компонент сильной связности (например, через DFS), чтобы убедиться, что и не лежат в одном цикле

Вопрос 43

К чему приводит предположение о существовании машины Тьюринга , способной разрешить проблему остановки на пустом слове (задачу HALT_0)?

  1.  К созданию алгоритма, работающего быстрее, чем Универсальная машина Тьюринга
  2.  К доказательству того, что классы P и NP совпадают
  3.  К противоречию, так как с её помощью можно было бы разрешить общую проблему остановки (HALT), сконструировав машину с «вшитыми» входными данными
  4.  К доказательству несчётности множества всех машин Тьюринга
  5.  Все остальные варианты — неверны

Вопрос 44

Является ли разрешимым множество натуральных чисел, не превосходящих :

  1.  Да
  2.  Неизвестно, поскольку ответ на этот вопрос следует из истинности\ложности гипотезы Римана;
  3.  Нет

Вопрос 45

Аню и Колю попросили показать, что задача X — NP-полна. Аня показала полиномиальную сводимость по Карпу от 3SAT к X, а Коля показал полиномиальную сводимость по Карпу от X к 3SAT.

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

  1.  Все остальные варианты — неверны.
  2.  X — NP-полная.
  3.  X — не NP-полная, и вообще не в NP.
  4.  X в NP, но не NP-полная.
  5.  X — NP-трудная, но не NP-полная.

Вопрос 46

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

NPC-GQ08.png


  1.  C
  2.  D
  3.  Все остальные варианты — неверны.
  4.  A
  5.  B

Вопрос 47

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

  1.   и ;
  2.   и ;
  3.   и ;

Вопрос 48

Пусть сводится по Карпу к . Выберите верное утверждение:

  1.  Если , то ;
  2.  Если , то ;
  3.  Если , то ;

Вопрос 49

Как соотносятся классы сложности задач обычного Линейного программирования (ЛП) и Целочисленного линейного программирования (ЦЛП / ILP)?

  1.  ЛП принадлежит классу P, а ЦЛП является NP-полной задачей
  2.  Обе задачи являются NP-полными
  3.  ЛП принадлежит классу P, а ЦЛП является PSPACE-полной задачей
  4.  ЦЛП принадлежит классу P, а ЛП является NP-полной задачей
  5.  Обе задачи принадлежат классу P

Вопрос 50

Существует ли алгоритм, который выписывает одну за другой все машины Тьюринга, которые останавливаются, будучи запущенными на пустой ленте?

  1.  Нет
  2.  Да

Вопрос 51

При полиномиальном сведении задачи 3ESAT к задаче о Вершинном покрытии (Vertex Cover) строится граф из «гаджетов». Если исходная 3-КНФ имеет переменных и дизъюнкций (скобок), чему будет равен лимит-отсечка (бюджет ) вершинного покрытия, подтверждающий выполнимость формулы?

  1.  
  2.  
  3.  
  4.  
  5.  
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-innopolis-exam»