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

Вопрос 1

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

Вопрос 2

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

Вопрос 3

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

Вопрос 4

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

Вопрос 5

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

Вопрос 6

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

Вопрос 7

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

Вопрос 8

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

Вопрос 9

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

Вопрос 10

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