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

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

Вариант 2372454305.

Ваше имя*:

Вопрос 1

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

  1.  вершинным
  2.  сочетающим
  3.  покрывающим
  4.  максимальным
  5.  совершенным

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

Для чего применяется «дерандомизация»:

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

Вопрос 6

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

  1.  Применение эволюционных алгоритмов
  2.  Построение эффективных в среднем алгоритмов
  3.  Построение эффективных алгоритмов муравьиной колонии

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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


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