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

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

Вариант 1922803383.

Ваше имя*:

Вопрос 1

Какова наилучшая сложность алгоритма из темы про FPTAS-алгоритмы для рюкзака?

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 2

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

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

Вопрос 3

В работах по теории сложности алгоритм называется полиномиальным в среднем, если для входов длины n и времени работы алгоритма T, выполняется:

  1.  
  2.  
  3.  
  4.  

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

Какой алгоритм используется только в лучшем из рассмотренных в теме FPTAS-алгоритмов для рюкзака?

  1.  алгоритм Кристофидеса
  2.  дерандомизация
  3.  жадный алгоритм для рюкзака
  4.  динамическое программирование с отбором наиболее легких наборов

Вопрос 8

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

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

Вопрос 9

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 10

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

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