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

Вопрос 1

Вопрос 2

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

Вопрос 3

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

Вопрос 4

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

Вопрос 5

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

Вопрос 6

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

Вопрос 7

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

Вопрос 8

1.  связных подграфов
2.  вершин
3.  ребер
4.  циклов

Вопрос 9

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

Вопрос 10

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