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

Материал из DISCOPAL
Перейти к: навигация, поиск
1234
Еженедельный по «сложности алгоритмов» для 6 курса МФТИ

Вариант 4035130616.


Ваше имя*:


Вопрос 1

Какие из подходов к решению вычислительно трудных задач изучались в курсе?

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

Вопрос 2

Эйлеров цикл в графе:

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

Вопрос 3

Какой алгоритм используется в рассмотренных FPTAS-алгоритмах для рюкзака?

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

Вопрос 4

Какой алгоритм используется в алгоритме Кристофидеса?

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