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

Вопрос 1

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

Вопрос 2

Вопрос 3

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

Вопрос 4

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

Вопрос 5

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

Вопрос 6

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

Вопрос 7

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

Вопрос 8

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

Вопрос 9

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

Вопрос 10

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