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

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

Вариант 2509612257.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

Метод многократного запуска вероятностного алгоритма, с целью уменьшения вероятности ошибки называется:

  1.  «отладка вероятности»
  2.  «вероятностная амплификация»
  3.  «дерандомизация»
  4.  «антирандомизация»

Вопрос 5

В работах по теории сложности алгоритм называется полиномиальным в среднем, если для входов длины n и времени работы алгоритма T, выполняется:

  1.  
  2.  
  3.  
  4.  

Вопрос 6

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


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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

  1.  дерандомизация
  2.  жадный алгоритм для рюкзака
  3.  алгоритм Кристофидеса
  4.  динамическое программирование с отбором наиболее легких наборов

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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


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

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

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

  1.  
  2.  
  3.  
  4.  

Вопрос 28

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

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

Вопрос 29

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

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

Вопрос 30

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

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