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

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

Вариант 1116443275.


Ваше имя*:


Вопрос 1

Выберите общепринятое определение класса NPC (NP-полных задач).

тогда и только тогда, когда:

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

Вопрос 2

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

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

Вопрос 3

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

Вопрос 4

Вероятностные «zero-error»-алгоритмы:

  1.  Когда дают ответ он правильный, но могут отвечать «не знаю»
  2.  Всегда дают верный ответ в случае, если возвращают «0»
  3.  Могут ошибаться, но только в случае, если возвращают «0»
  4.  Всегда дают верный ответ

Вопрос 5

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

Вопрос 6

Существует ли алгоритм, который выписывает одну за другой все машины Тьюринга, которые не останавливаются, будучи запущенными на пустой ленте?

  1.  Да
  2.  Нет

Вопрос 7

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

  1.  
  2.  экспоненциальное
  3.  линейное
  4.  полином, но степени больше 2
  5.  квадратичное

Вопрос 8

Какие условия на существование полиномиального в среднем алгоритма для «SAT» требуются в соответствующей теме?

Напомним, что у нас n переменных и m скобок, p — вероятность появления переменной в каждой скобке.


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 9

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

Вопрос 10

Цикл, проходящий через все ребра графа по одному разу, называется

  1.  Гамильтонов цикл
  2.  Эйлеров цикл
  3.  Наполеонов цикл
  4.  Цикл Нельсона
  5.  Петля Нестерова