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

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

Вариант 2298551097.

Ваше имя*:

Вопрос 1

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

  1.  округление коэффициентов
  2.  метод условного спуска
  3.  вероятностное округление
  4.  дерандомизация
  5.  PTAS-апроксимация

Вопрос 2

Какой класс ошибок допускают алгоритмы решающие задачи из класса ZPP?

  1.  трехсторонние
  2.  односторонние (при ответе «0»)
  3.  двусторонние
  4.  никакие
  5.  односторонние (при ответе «1»)
  6.  «ZPP»-ошибки

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

Какой класс ошибок допускают алгоритмы решающие задачи из класса BPP?

  1.  трехсторонние
  2.  односторонние
  3.  «BP»-ошибки
  4.  двусторонние

Вопрос 8

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

  1.  
  2.  
  3.  
  4.  

Вопрос 9

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 10

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 11

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 12

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

  1.  
  2.  
  3.  
  4.  
  5.  Нет правильного ответа

Вопрос 13

Рассмотрим модификацию задачи «Сумма размеров», разрешим даже отрицательные размеры.

Формально: Даны натуральные числа , , и число B.

Надо узнать, существует ли решение в 0/1 переменных уравнения .

Существует ли полиномиальный алгоритм для этой задачи?

  1.  Нет, полиномиального алгоритма нет
  2.  Да, есть полиномиальный алгоритм
  3.  Полиномиального нет, но есть квазиполиномиальный алгоритм

Вопрос 14

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

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

Вопрос 15

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

  1.  Немхаузера-Ульмана
  2.  Каргера-Штейна
  3.  Флойда-Уоршелла
  4.  Форда-Фалкерсона
  5.  Эдмондса-Карпа
  6.  Беллмана-Форда

Вопрос 16

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

  1.  алгоритм Немхаузера-Ульмана
  2.  метод условного спуска
  3.  динамическое программирование с отбором наиболее дорогих наборов
  4.  динамическое программирование с отбором наиболее легких наборов
  5.  алгоритм Беллмана-Форда

Вопрос 17

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

  1.  
  2.  
  3.  
  4.  

Вопрос 18

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

  1.  MIN-CUT
  2.  MAX-CUT
  3.  MAX-SAT
  4.  MIN-SAT
  5.  MAX-3SAT

Вопрос 19

С какой точностью работает модифицированный жадный алгоритм для задачи о рюкзаке из соответствующей темы?

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

Вопрос 20

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

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

Вопрос 21

Вероятностные «zero-error»-алгоритмы:

  1.  Могут ошибаться, но только в случае, если возвращают «0»
  2.  Всегда дают верный ответ в случае, если возвращают «0»
  3.  Всегда дают верный ответ
  4.  Когда дают ответ он правильный, но могут отвечать «не знаю»

Вопрос 22

Есть граф G=(V,E). Разбиение множества вершин V на непересекающиеся множества S и T называется:

  1.  Разбивка
  2.  Паросочетание
  3.  Поток
  4.  Клика
  5.  Раскладка
  6.  Разрез

Вопрос 23

Какой из этих тестов на простоту не является рандомизированным:

  1.  Бейли — Померанца — Селфриджа — Уогстаффа,
  2.  Бейли — Померанца — Селфриджа — Уогстаффа
  3.  Все существующие тесты на простоту являются рандомизированными
  4.  Миллера-Рабина
  5.  Миллера

Вопрос 24

Какой класс ошибок допускают алгоритмы решающие задачи из класса PP?

  1.  двусторонние
  2.  «PP»-ошибки
  3.  односторонние
  4.  трехсторонние

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке полиномиальность в среднем доказана для следующего распределения входных данных:

  1.  и стоимости и веса выбираются случайно
  2.  стоимости произвольные, веса выбираются случайно
  3.  веса произвольные, стоимость выбираются случайно

Вопрос 28

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


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

Вопрос 29

Какие условия на существование полиномиального в среднем алгоритма для «SAT» требуются в соответствующей теме?

Напомним, что у нас n переменных и m скобок, p — вероятность появления переменной в каждой скобке.


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 30

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


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