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

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

Вариант 3200843089.


Ваше имя*:


Вопрос 1

Найдите неверное утверждение:

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  

Вопрос 2

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

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

Вопрос 3

Выберите не NP-полную задачу

  1.  SAT
  2.  TSP-выполнимость
  3.  3SAT
  4.  Вершинное покрытие
  5.  Клика (есть ли в графе клика больше заданной)
  6.  2SAT
  7.  Сумма множеств

Вопрос 4

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


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

Вопрос 5

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

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

Вопрос 6

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

  1.  линейное
  2.  экспоненциальное
  3.  полином, но степени больше 2
  4.  квадратичное
  5.  

Вопрос 7

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

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

Вопрос 8

  1.  NP
  2.  coRP
  3.  ZPP
  4.  BPP
  5.  RP
  6.  PP
  7.  PSPACE
  8.  coZPP

Вопрос 9

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 10

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

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