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

Вопрос 1

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

Вопрос 2

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

Вопрос 3

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

Вопрос 4

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

Вопрос 5

1.  Метод Лас-Вегас
2.  Демократизация
3.  Метод Монте-Карло
4.  Шервудские алгоритмы
5.  Дерандомизация
6.  Рандомизация
7.  Дератизация

Вопрос 6

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

Вопрос 7

1.  Треугольной
2.  Евклидовой
3.  Метрической
4.  Гамильтоновой
5.  Эйлеровой

Вопрос 8

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

Вопрос 9

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

Вопрос 10

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