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

Вопрос 1

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

Вопрос 2

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

Вопрос 3

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

Вопрос 4

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

Вопрос 5

1.  Применение эволюционных алгоритмов
2.  Построение эффективных в среднем алгоритмов
3.  Построение эффективных алгоритмов муравьиной колонии

Вопрос 6

1.  максимальным
2.  совершенным
3.  покрывающим
4.  вершинным
5.  сочетающим

Вопрос 7

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

Вопрос 8

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

Вопрос 9

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

Вопрос 10

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