Еженедельный по «сложности алгоритмов» для 6 курса МФТИ — вопросы

Материал из DISCOPAL
Перейти к: навигация, поиск
1234
Еженедельный по «сложности алгоритмов» для 6 курса МФТИ

Вариант 2246292496.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке рассматривался алгоритм…

  1.  Форда-Фалкерсона
  2.  Беллмана-Форда
  3.  Немхаузера-Ульмана
  4.  Эдмондса-Карпа
  5.  Каргера-Штейна
  6.  Флойда-Уоршелла

Вопрос 4

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

  1.  Треугольной
  2.  Евклидовой
  3.  Метрической
  4.  Гамильтоновой
  5.  Эйлеровой
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-6-course-ispras-weekly»