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

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

Вариант 3359191951.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

  1.  
  2.  
  3.  
  4.  

Вопрос 4

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


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

Вопрос 5

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

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

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

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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


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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

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

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

Вопрос 28

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

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

Вопрос 29

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

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

Вопрос 30

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

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


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