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

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

Вариант 912074287.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

Какой класс ошибок допускают алгоритмы решающие задачи из класса ZPP?

  1.  «ZPP»-ошибки
  2.  трехсторонние
  3.  односторонние (при ответе «0»)
  4.  никакие
  5.  односторонние (при ответе «1»)
  6.  двусторонние

Вопрос 3

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

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

Вопрос 4

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

  1.  
  2.  
  3.  
  4.  

Вопрос 5

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

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

Вопрос 6

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

  1.  2
  2.  3
  3.  
  4.  
  5.  
  6.  e

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

Какие условия на существование полиномиального в среднем алгоритма для «SAT» требуются в соответствующей теме?

Напомним, что у нас n переменных и m скобок, p — вероятность появления переменной в каждой скобке.


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 10

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

  1.  
  2.  3
  3.  
  4.  

Вопрос 11

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

  1.  
  2.  
  3.  Нет правильного ответа
  4.  
  5.  

Вопрос 12

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

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

Вопрос 13

Гамильтонов цикл в графе:

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

Вопрос 14

Для какой задачи в курсе использовался "метод условных вероятностей" с последовательным определением значения переменных:

  1.  TSP
  2.  MAX-CUT
  3.  Рюкзак-выполнимость
  4.  MIN-CUT
  5.  MAX-SAT
  6.  Рюкзак-оптимизация

Вопрос 15

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

Паросочетание, это подмножество...


  1.  ребер
  2.  циклов
  3.  связных подграфов
  4.  вершин

Вопрос 19

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 20

Какой класс ошибок допускают алгоритмы решающие задачи из класса PP?

  1.  двусторонние
  2.  «PP»-ошибки
  3.  трехсторонние
  4.  односторонние

Вопрос 21

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

  1.  Эдмондса-Карпа
  2.  Флойда-Уоршелла
  3.  Беллмана-Форда
  4.  Немхаузера-Ульмана
  5.  Форда-Фалкерсона
  6.  Каргера-Штейна

Вопрос 22

Какой из этих тестов на простоту не является рандомизированным:

  1.  Бейли — Померанца — Селфриджа — Уогстаффа,
  2.  Миллера-Рабина
  3.  Бейли — Померанца — Селфриджа — Уогстаффа
  4.  Все существующие тесты на простоту являются рандомизированными
  5.  Миллера

Вопрос 23

Какой класс ошибок допускают алгоритмы решающие задачи из класса BPP?

  1.  односторонние
  2.  «BP»-ошибки
  3.  двусторонние
  4.  трехсторонние

Вопрос 24

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

  1.  Точность решения в среднем —
  2.  Заполнял таблицу «наиболее выполняющими» наборами
  3.  Вероятностно подсчитывал число невыполненных наборов
  4.  Находит приближенное решение, с точностью
  5.  Подсчитывал число невыполненных наборов
  6.  Вероятностно подсчитывал число выполненных наборов

Вопрос 25

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

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

Вопрос 26

Паросочетание, покрывающее все вершины графа, называется

  1.  сочетающим
  2.  покрывающим
  3.  совершенным
  4.  вершинным
  5.  максимальным

Вопрос 27

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

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

Вопрос 28

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

  1.  PTAS-апроксимация
  2.  округление коэффициентов
  3.  метод условного спуска
  4.  вероятностное округление
  5.  дерандомизация

Вопрос 29

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 30

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

  1.  Рандомизация
  2.  Шервудские алгоритмы
  3.  Дератизация
  4.  Демократизация
  5.  Дерандомизация
  6.  Метод Монте-Карло
  7.  Метод Лас-Вегас
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Эффективные_алгоритмы-Экзамен»