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

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

Вариант 3148933969.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

  1.  
  2.  
  3.  3
  4.  

Вопрос 15

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

  1.  
  2.  
  3.  
  4.  

Вопрос 16

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


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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

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

Вопрос 21

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

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

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

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

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

Вопрос 22

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

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

Вопрос 23

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


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

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

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

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

Вопрос 28

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 29

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 30

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

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