Эффективные алгоритмы — вопросы

Материал из DISCOPAL
Перейти к: навигация, поиск
12345678910
Тест по курсу «Эффективные алгоритмы»

Вариант 1568067377.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

Вопрос 7

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 8

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

Вопрос 9

Паросочетание, это подмножество...


  1.  циклов
  2.  вершин
  3.  связных подграфов
  4.  ребер

Вопрос 10

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