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

Вопрос 1

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

Вопрос 2

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

Вопрос 3

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

Вопрос 4

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

Вопрос 5

1.  сочетающим
2.  максимальным
3.  покрывающим
4.  вершинным
5.  совершенным

Вопрос 6

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

Вопрос 7

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

Вопрос 8

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

Вопрос 9

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

Вопрос 10

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