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

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

Вариант 1377123298.


Ваше имя*:


Вопрос 1

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

Вопрос 2

Какой алгоритм используется в алгоритме Кристофидеса?

  1.  Алгоритм Флойда-Уоршелла
  2.  Поиск кратчайших путей
  3.  Рюкзак-оптимальность
  4.  Поиск минимального разреза
  5.  Поиск совершенного паросочетания

Вопрос 3

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

  1.  
  2.  
  3.  
  4.  

Вопрос 4

В работах по теории сложности алгоритм называется полиномиальным в среднем, если для входов длины n и времени работы алгоритма T, выполняется:

  1.  
  2.  
  3.  
  4.  

Вопрос 5

Есть граф G=(V,E). Разбиение множества вершин V на непересекающиеся множества S и T называется:

  1.  Разрез
  2.  Разбивка
  3.  Паросочетание
  4.  Поток
  5.  Раскладка
  6.  Клика

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

Вопрос 9

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

  1.  
  2.  
  3.  
  4.  

Вопрос 10

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

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