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

1

2

3

4

Тест по курсу «Эффективные алгоритмы»

Вариант 730304375.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

Дерандомизация
Дератизация
Метод Монте-Карло
Рандомизация
Метод Лас-Вегас
Шервудские алгоритмы
Демократизация

Вопрос 4

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

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

Вопрос 5

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

Вопрос 6

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

наборов минимального веса для каждой стоимости
наборов максимальной стоимости для каждого веса
набранных отборов
отборных наборов
недопустимых наборов
допустимых наборов
доминирующих наборов

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

3

Вопрос 10

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