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

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

Вариант 153406546.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

  1.  
  2.  
  3.  
  4.  3

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

  1.  линейное
  2.  
  3.  экспоненциальное
  4.  квадратичное
  5.  полином, но степени больше 2

Вопрос 8

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

m
элементов,
n
подмножеств
p
вероятность ненулевого элемента в матрице инцидентности
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  

Вопрос 9

Формулировка (в виде ЦЛП) какой задачи приведена ниже:

  1.  MIN-SAT
  2.  MAX-3SAT
  3.  MIN-CUT
  4.  MAX-SAT
  5.  MAX-CUT

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

Вероятностные «zero-error»-алгоритмы:

  1.  Когда дают ответ он правильный, но могут отвечать «не знаю»
  2.  Могут ошибаться, но только в случае, если возвращают «0»
  3.  Всегда дают верный ответ в случае, если возвращают «0»
  4.  Всегда дают верный ответ

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

Формулировка (в виде ЦП) какой задачи приведена ниже:

  1.  MIN-SAT
  2.  MAX-CUT
  3.  MAX-3SAT
  4.  MIN-CUT
  5.  MAX-SAT

Вопрос 19

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

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

Вопрос 20

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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


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

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

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


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

Вопрос 27

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

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

Вопрос 28

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 29

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

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

Вопрос 30

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

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