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

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

Вариант 940727557.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

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

Вопрос 3

Какой класс ошибок допускают алгоритмы решающие задачи из класса PP?

  1.  двусторонние
  2.  односторонние
  3.  трехсторонние
  4.  «PP»-ошибки

Вопрос 4

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

Вопрос 5

Какой класс ошибок допускают алгоритмы решающие задачи из класса ZPP?

  1.  двусторонние
  2.  односторонние (при ответе «0»)
  3.  «ZPP»-ошибки
  4.  односторонние (при ответе «1»)
  5.  трехсторонние
  6.  никакие

Вопрос 6

Пусть задача A — «есть ли цикл в ненаправленном графе». Рассмотрим набор утверждений.


  • (1) Задача A — в P
  • (2) Задача A — в NP
  • (3) Если задача A — NP-полна, то существует НМТ, решающая A за полиномиальное время.

Что верно?

  1.  1, 2 и 3
  2.  1 и 3
  3.  Все остальные варианты — неверны.
  4.  1 и 2
  5.  2 и 3

Вопрос 7

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

Вопрос 8

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

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

Вопрос 9

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

  1.  вероятностное округление
  2.  PTAS-апроксимация
  3.  округление коэффициентов
  4.  дерандомизация
  5.  метод условного спуска

Вопрос 10

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

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