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

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

Вариант 2113620431.

Прошло 00:00:02.
Ваше имя*:

Вопрос 1

С какой точностью работает «чисто» жадный алгоритм для задачи о рюкзаке («хватать предметы по убыванию удельной стоимости, пока не кончится место в рюкзаке»)?

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

Вопрос 2

В теме про полиномиальный в среднем алгоритм для «SAT» мы применяли формулу…


  1.  Включений-Исключений
  2.  Беллмана-Форда
  3.  Форда-Фалкерсона
  4.  Немхаузера-Ульмана
  5.  Флойда-Уоршолла

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

Для чего применяется «метод условных вероятностей»:

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

Вопрос 9

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

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

Вопрос 10

Какова сложность вероятностного алгоритма Фрейвалда для проверки тождества AB=C для матриц  ?

  1.  
  2.  
  3.  
  4.  
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Эффективные_алгоритмы»