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

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

Вариант 2318643549.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

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

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

Вопрос 3

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

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

Вопрос 4

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

  1.  Да;
  2.  Нет;

Вопрос 5

Гамильтонов цикл в графе:

  1.  проходит через все вершины и ребра по одному разу
  2.  проходит через все вершины по одному разу
  3.  проходит через все ребра по одному разу

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

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