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

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

Вариант 174159136.

Ваше имя*:

Вопрос 1

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

Вопрос 2

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

  1.  Построение эффективных алгоритмов муравьиной колонии
  2.  Применение эволюционных алгоритмов
  3.  Построение эффективных в среднем алгоритмов

Вопрос 3

  1.  ZPP
  2.  PTAS
  3.  NP
  4.  coRP
  5.  BPP
  6.  RP
  7.  PP
  8.  ALL

Вопрос 4

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

Вопрос 5

Задача 2SAT:

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

Вопрос 6

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

  1.  Да;
  2.  Нет;

Вопрос 7

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

Вопрос 8

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

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

Вопрос 9

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

  1.  Нет;
  2.  Да;

Вопрос 10

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


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

Что верно?

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