Еженедельный по «сложности алгоритмов» для 3 курса ИСПРАН — вопросы

Вопрос 1

1.  Построение эффективных эвристических алгоритмов
2.  Построение точных алгоритмов с субэкспоненциальными оценками сложности
3.  Построение эффективных приближенных алгоритмов с оценками точности в худшем случае

Вопрос 2

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

Вопрос 3

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

Вопрос 4

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

Вопрос 5

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

Вопрос 6

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

Вопрос 7

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

Вопрос 8

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

Вопрос 9

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

Вопрос 10

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