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

Материал из DISCOPAL
Перейти к: навигация, поиск
12345678910
Еженедельный по «сложности алгоритмов» для 3 курса ИСПРАН

Вариант 1187039647.


Ваше имя*:


Вопрос 1

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

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

Вопрос 2

Для чего применяется «метод условных вероятностей»:

  1.  Демократизация
  2.  Метод Монте-Карло
  3.  Шервудские алгоритмы
  4.  Метод Лас-Вегас
  5.  Рандомизация
  6.  Дератизация
  7.  Дерандомизация

Вопрос 3

Какие из подходов к решению вычислительно трудных задач изучались в курсе?

  1.  Построение эффективных приближенных алгоритмов, использующих метод вероятностного округления решений релаксационных задач
  2.  Построение эффективных алгоритмов методом ветвей и границ
  3.  Построение недетерминированных полиномиальных алгоритмов

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

Формулировка (в виде ЦЛП) какой задачи приведена ниже:

  1.  MIN-CUT
  2.  MAX-CUT
  3.  MAX-3SAT
  4.  MAX-SAT
  5.  MIN-SAT

Вопрос 7

Какие из подходов к решению вычислительно трудных задач изучались в курсе?

  1.  Построение эффективных приближенных алгоритмов с оценками точности в худшем случае
  2.  Построение точных алгоритмов с субэкспоненциальными оценками сложности
  3.  Построение эффективных эвристических алгоритмов

Вопрос 8

Для какой задачи в курсе использовался "метод условных вероятностей" с последовательным определением значения переменных:

  1.  Рюкзак-оптимизация
  2.  TSP
  3.  MAX-SAT
  4.  Рюкзак-выполнимость
  5.  MIN-CUT
  6.  MAX-CUT

Вопрос 9

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

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

Вопрос 10

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


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