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

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

Вариант 3820622614.

Ваше имя*:

Вопрос 1

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

Вопрос 2

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

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

Вопрос 3

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

Вопрос 4

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

Вопрос 5

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 6

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

  1.  динамическое программирование с отбором наиболее легких наборов
  2.  метод условного спуска
  3.  алгоритм Беллмана-Форда
  4.  динамическое программирование с отбором наиболее дорогих наборов
  5.  алгоритм Немхаузера-Ульмана
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-weekly»