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

1

2

3

4

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

Вариант 3632382655.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

Беллмана-Форда
Эдмондса-Карпа
Флойда-Уоршелла
Каргера-Штейна
Форда-Фалкерсона
Немхаузера-Ульмана

Вопрос 3

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

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

Вопрос 4

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

Вопрос 5

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

Вопрос 6

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

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

Вопрос 7

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

Вопрос 8

Вопрос 9

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

Вопрос 10

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

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