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

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

Вариант 1362638379.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

Какова точность, гарантируемая гибридным вероятностным алгоритмом из темы про вероятностное округление MAX-SAT?


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 6

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

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

Вопрос 7

Задача Коммивояжера, в которой для матрицы расстояний выполнено неравенство треугольника, называется:

  1.  Метрической
  2.  Треугольной
  3.  Эйлеровой
  4.  Евклидовой
  5.  Гамильтоновой

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

  1.  Цикл Нельсона
  2.  Эйлеров цикл
  3.  Гамильтонов цикл
  4.  Петля Нестерова
  5.  Наполеонов цикл
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-weekly»