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

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

Вариант 3532383822.

Ваше имя*:

Вопрос 1

  1.  PP
  2.  BPP
  3.  PSPACE
  4.  NP
  5.  ZPP
  6.  coZPP
  7.  coRP
  8.  RP

Вопрос 2

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

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

Вопрос 3

Рассмотрим модификацию задачи «Сумма размеров», разрешим даже отрицательные размеры.

Формально: Даны натуральные числа , , и число B.

Надо узнать, существует ли решение в 0/1 переменных уравнения .

Существует ли полиномиальный алгоритм для этой задачи?

  1.  Нет, полиномиального алгоритма нет
  2.  Полиномиального нет, но есть псевдополиномиальный алгоритм
  3.  Полиномиального нет, но есть квазиполиномиальный алгоритм
  4.  Да, есть полиномиальный алгоритм

Вопрос 4

  1.  NP
  2.  PSPACE
  3.  coZPP
  4.  RP
  5.  ZPP
  6.  coRP
  7.  BPP
  8.  PP

Вопрос 5

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

  1.  Построение эффективных эвристических алгоритмов
  2.  Построение эффективных приближенных алгоритмов с оценками точности в худшем случае
  3.  Построение точных алгоритмов с субэкспоненциальными оценками сложности

Вопрос 6

  1.  NP
  2.  BPP
  3.  RP
  4.  PSPACE
  5.  ZPP
  6.  coZPP
  7.  PP
  8.  coRP

Вопрос 7

Сложность алгоритма динамического программирования для задачи о рюкзаке, который «помнит» о наиболее «легких» допустимых решениях:

  1.  Нет правильного ответа
  2.  
  3.  
  4.  
  5.  

Вопрос 8

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

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

Вопрос 9

Какова сложность вероятностного алгоритма Фрейвалда для проверки тождества AB=C для матриц  ?

  1.  
  2.  
  3.  
  4.  

Вопрос 10

С какой точностью работает модифицированный жадный алгоритм для задачи о рюкзаке из соответствующей темы?

  1.  
  2.  Этот алгоритм не гарантирует никакой точности решения;
  3.  
  4.  3
  5.  0.878
  6.  2

Вопрос 11

В теме про полиномиальный в среднем алгоритм для «SAT» мы применяли формулу…


  1.  Беллмана-Форда
  2.  Флойда-Уоршолла
  3.  Форда-Фалкерсона
  4.  Включений-Исключений
  5.  Немхаузера-Ульмана

Вопрос 12

В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке полиномиальность в среднем доказана для следующего распределения входных данных:

  1.  и стоимости и веса выбираются случайно
  2.  веса произвольные, стоимость выбираются случайно
  3.  стоимости произвольные, веса выбираются случайно

Вопрос 13

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

  1.  
  2.  
  3.  
  4.  

Вопрос 14

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

  1.  Да
  2.  Нет

Вопрос 15

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

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

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

Вопрос 16

В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке рассматривался алгоритм, который оперирует множеством…

  1.  допустимых наборов
  2.  наборов максимальной стоимости для каждого веса
  3.  доминирующих наборов
  4.  недопустимых наборов
  5.  наборов минимального веса для каждой стоимости
  6.  набранных отборов
  7.  отборных наборов

Вопрос 17

Задача 2SAT:

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

Вопрос 18

Сложность алгоритма динамического программирования для задачи о рюкзаке, который «помнит» о наиболее «дорогих» допустимых решениях:

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 19

Найдите неверное утверждение:

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  

Вопрос 20

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

  1.  дерандомизация
  2.  динамическое программирование с отбором наиболее легких наборов
  3.  жадный алгоритм для рюкзака
  4.  алгоритм Кристофидеса
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-weekly»