Еженедельный по «сложности алгоритмов» для 6 курса МФТИ — вопросы

Вопрос 1

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

Вопрос 2

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

Вопрос 3

1.  метод условного спуска
2.  динамическое программирование с отбором наиболее дорогих наборов
3.  алгоритм Беллмана-Форда
4.  алгоритм Немхаузера-Ульмана
5.  динамическое программирование с отбором наиболее легких наборов

Вопрос 4

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