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

Вопрос 1

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

Вопрос 2

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

Вопрос 3

Вопрос 4

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

Вопрос 5

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

Вопрос 6

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

Вопрос 7

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

Вопрос 8

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

Вопрос 9

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

Вопрос 10

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