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

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

Вариант 3340484650.

Ваше имя*:

Вопрос 1

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

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

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

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

Вопрос 10

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

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

Вопрос 11

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


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

Вопрос 12

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

  1.  
  2.  
  3.  
  4.  

Вопрос 24

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

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

Вопрос 25

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

  1.  
  2.  3
  3.  
  4.  

Вопрос 26

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 27

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

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

Вопрос 28

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

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

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

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

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

Вопрос 29

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

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

Вопрос 30

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

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