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

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

Вариант 1194004966.

Ваше имя*:

Вопрос 1

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

  1.  
  2.  
  3.  
  4.  

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 5

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

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

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

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

  1.  
  2.  
  3.  
  4.  

Вопрос 10

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

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

Вопрос 11

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 19

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

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

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 26

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

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

Вопрос 27

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

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

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

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

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

Вопрос 28

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


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

Вопрос 29

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


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

Вопрос 30

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

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