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

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

Вариант 1881592379.

Ваше имя*:

Вопрос 1

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

Вопрос 2

Выберите верное утверждение


  1.  Из сводимости по Куку следует сводимость по Карпу
  2.  Верного ответа нет
  3.  Из сводимости по Карпу следует сводимость по Куку

Вопрос 3

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

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

Вопрос 4

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


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

Вопрос 5

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

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