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

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

Вариант 132673150.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

Какова сложность вероятностного алгоритма Фрейвалда для проверки тождества AB=C для матриц  ?

  1.  
  2.  
  3.  
  4.  

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

Паросочетание, покрывающее все вершины графа, называется

  1.  максимальным
  2.  вершинным
  3.  сочетающим
  4.  совершенным
  5.  покрывающим
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-weekly»