Эффективные алгоритмы — вопросы

Материал из DISCOPAL
Перейти к: навигация, поиск
12345678910
Тест по курсу «Эффективные алгоритмы»

Вариант 794034882.


Ваше имя*:


Вопрос 1

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 2

Задача Коммивояжера, в которой для матрицы расстояний выполнено неравенство треугольника, называется:

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

Вопрос 3

Есть граф G=(V,E). Разбиение множества вершин V на непересекающиеся множества S и T называется:

  1.  Клика
  2.  Раскладка
  3.  Паросочетание
  4.  Поток
  5.  Разбивка
  6.  Разрез

Вопрос 4

Для чего применяется «дерандомизация»:

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

Вопрос 5

В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке рассматривался алгоритм, который оперирует множеством…

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

Вопрос 6

Как называется задача оптимизации со следующей формулировкой:

  1.  Целочисленное линейное программирование
  2.  Векторное программирование
  3.  Положительное линейное программирование (ПЛП)
  4.  Выпуклое программирование
  5.  Линейное программирование
  6.  Полуопределенное программирование

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

С какой точностью работает модифицированный жадный алгоритм для задачи о рюкзаке из соответствующей темы?

  1.  0.878
  2.  Этот алгоритм не гарантирует никакой точности решения;
  3.  2
  4.  3
  5.  
  6.  

Вопрос 10

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

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