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

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

Вариант 2840614619.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

Как называется задача оптимизации со следующей формулировкой:

  1.  Выпуклое программирование
  2.  Положительное линейное программирование (ПЛП)
  3.  Векторное программирование
  4.  Полуопределенное программирование
  5.  Линейное программирование
  6.  Целочисленное линейное программирование

Вопрос 4

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

Вопрос 5

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

  1.  
  2.  
  3.  
  4.  

Вопрос 6

Эйлеров цикл в графе:

  1.  проходит через все вершины по одному разу;
  2.  проходит через все ребра по одному разу;
  3.  проходит через все вершины и~ребра по одному разу;

Вопрос 7

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

Вопрос 8

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

Вопрос 9

В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке полиномиальность в среднем доказана для следующего распределения входных данных:

  1.  веса произвольные, стоимость выбираются случайно
  2.  стоимости произвольные, веса выбираются случайно
  3.  и стоимости и веса выбираются случайно

Вопрос 10

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