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

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

Вариант 901467968.


Ваше имя*:


Вопрос 1

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 2

В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке полиномиальность в среднем доказана для следующего распределения входных данных:

  1.  веса произвольные, стоимость выбираются случайно
  2.  стоимости произвольные, веса выбираются случайно
  3.  и стоимости и веса выбираются случайно

Вопрос 3

Цикл, проходящий через все вершины графа, называется

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

Вопрос 4

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

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