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

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

Вариант 2532415913.

Ваше имя*:

Вопрос 1

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 15

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

  1.  3
  2.  
  3.  
  4.  

Вопрос 16

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

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

Вопрос 17

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 18

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

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

Вопрос 19

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

  1.  
  2.  
  3.  
  4.  

Вопрос 20

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

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

Вопрос 21

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

Рассмотрим модификацию задачи «Сумма размеров», разрешим даже отрицательные размеры.

Формально: Даны натуральные числа , , и число B.

Надо узнать, существует ли решение в 0/1 переменных уравнения .

Существует ли полиномиальный алгоритм для этой задачи?

  1.  Да, есть полиномиальный алгоритм
  2.  Нет, полиномиального алгоритма нет
  3.  Полиномиального нет, но есть квазиполиномиальный алгоритм

Вопрос 25

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 26

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 27

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

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

Вопрос 28

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

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

Вопрос 29

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

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

Вопрос 30

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

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