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

Вопрос 1

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

Вопрос 2

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

Вопрос 3

1.  
2.  
3.  
4.  3
5.  2
6.  e

Вопрос 4

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

Вопрос 5

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

Вопрос 6

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

Вопрос 7

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

Вопрос 8

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

Вопрос 9

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

Вопрос 10

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