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

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

Вариант 3422709038.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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


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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

  1.  
  2.  
  3.  
  4.  

Вопрос 7

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

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

Вопрос 8

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


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

Вопрос 9

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 10

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

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

Вопрос 11

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 12

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

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

Вопрос 13

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 14

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

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

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

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

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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 18

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

  1.  
  2.  
  3.  
  4.  

Вопрос 19

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 20

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

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

Вопрос 21

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

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

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

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

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

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

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

Вопрос 28

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

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

Вопрос 29

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

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

Вопрос 30

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

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