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

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

Вариант 303172518.

Ваше имя*:

Вопрос 1

В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке полиномиальность в среднем доказана для следующего распределения входных данных:

  1.  стоимости произвольные, веса выбираются случайно
  2.  и стоимости и веса выбираются случайно
  3.  веса произвольные, стоимость выбираются случайно

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

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

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

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

Вопрос 7

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

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

Вопрос 8

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

  1.  
  2.  
  3.  
  4.  

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

  1.  
  2.  3
  3.  
  4.  

Вопрос 13

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

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

Вопрос 14

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


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

Вопрос 15

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

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

Вопрос 16

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 17

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


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

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 27

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

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

Вопрос 28

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

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

Вопрос 29

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

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

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

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

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

Вопрос 30

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

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