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

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

Вариант 2953412182.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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


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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

  1.  
  2.  
  3.  
  4.  

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

  1.  Дератизация
  2.  Шервудские алгоритмы
  3.  Дерандомизация
  4.  Рандомизация
  5.  Метод Монте-Карло
  6.  Метод Лас-Вегас
  7.  Демократизация
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-weekly»