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

Вопрос 1

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

Вопрос 2

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

Вопрос 3

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

Вопрос 4

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

Вопрос 5

Вопрос 6

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

Вопрос 7

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

Вопрос 8

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

Вопрос 9

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

Вопрос 10

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