Эффективные алгоритмы — вопросы

Материал из DISCOPAL
Перейти к: навигация, поиск
12345678910
Тест по курсу «Эффективные алгоритмы»

Вариант 4272463904.

Ваше имя*:

Вопрос 1

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 2

В теме про полиномиальный в среднем алгоритм для «SAT» мы применяли формулу…


  1.  Включений-Исключений
  2.  Беллмана-Форда
  3.  Флойда-Уоршолла
  4.  Форда-Фалкерсона
  5.  Немхаузера-Ульмана

Вопрос 3

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

  1.  
  2.  
  3.  
  4.  

Вопрос 4

Эйлеров цикл в графе:

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

Вопрос 5

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

  1.  
  2.  
  3.  
  4.  

Вопрос 6

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

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

Вопрос 7

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

  1.  
  2.  3
  3.  
  4.  

Вопрос 8

С какой точностью работает «чисто» жадный алгоритм для задачи о рюкзаке («хватать предметы по убыванию удельной стоимости, пока не кончится место в рюкзаке»)?

  1.  3
  2.  2
  3.  Этот алгоритм не гарантирует никакой точности решения
  4.  
  5.  0.878
  6.  

Вопрос 9

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

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

Вопрос 10

Метод многократного запуска вероятностного алгоритма, с целью уменьшения вероятности ошибки называется:

  1.  «дерандомизация»
  2.  «антирандомизация»
  3.  «вероятностная амплификация»
  4.  «отладка вероятности»
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Эффективные_алгоритмы»