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

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

Вариант 3212250163.

Прошло 00:00:00.
Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 6

Гамильтонов цикл в графе:

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

Вопрос 7

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


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

Вопрос 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»