Тест по алгоритмам для 4 курса ИСПРАН — вопросы

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

Вариант 2356234873.

Ваше имя*:

Вопрос 1

Как расшифровывается аббревиатура PRAM?

  1.  Parallel Random Access Machine
  2.  Parallel Relational Algebra Monitor
  3.  Parallel Random Access Memory

Вопрос 2

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


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

Вопрос 3

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


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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

Какие из подходов к решению вычислительно трудных задач изучались в курсе?

  1.  Построение эффективных эвристических алгоритмов
  2.  Построение эффективных приближенных алгоритмов с оценками точности в худшем случае
  3.  Построение точных алгоритмов с субэкспоненциальными оценками сложности

Вопрос 8

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

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

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

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

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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

Какие из подходов к решению вычислительно трудных задач изучались в курсе?

  1.  Построение эффективных метаэвристик
  2.  Применение теории генетических алгоритмов
  3.  Построение эффективных вероятностных приближенных алгоритмов с оценками точности в худшем случае

Вопрос 12

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

  1.  
  2.  
  3.  
  4.  

Вопрос 13

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

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

Вопрос 14

Какие из подходов к решению вычислительно трудных задач изучались в курсе?

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

Вопрос 15

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

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

Вопрос 16

Какие из подходов к решению вычислительно трудных задач изучались в курсе?

  1.  Построение эффективных алгоритмов муравьиной колонии
  2.  Построение эффективных в среднем алгоритмов
  3.  Применение эволюционных алгоритмов

Вопрос 17

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

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

Вопрос 18

Какой метод применялся в теме про подсчет выполняющих наборов для ДНФ?

  1.  Динамическое программирование
  2.  Дерандомизация вероятностного округления
  3.  Полный перебор
  4.  Вероятностное округление
  5.  Монте-Карло

Вопрос 19

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

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

Вопрос 20

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

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

Вопрос 21

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

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 25

Представим неориентированный граф топологии «звезда», с n+1 вершинами.

Каков максимальный размер независимого множества максимального по включению?

  1.  n
  2.  n-1
  3.  2
  4.  n+1
  5.  1

Вопрос 26

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

  1.  вероятностное округление
  2.  метод условного спуска
  3.  дерандомизация
  4.  PTAS-апроксимация
  5.  округление коэффициентов

Вопрос 27

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

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

Вопрос 28

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

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

Вопрос 29

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 30

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

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

Вопрос 31

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 32

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

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

Вопрос 33

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

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

Вопрос 34

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

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

Вопрос 35

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

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

Вопрос 36

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

  1.  
  2.  
  3.  
  4.  

Вопрос 37

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

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

Вопрос 38

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

  1.  
  2.  
  3.  3
  4.  

Вопрос 39

Вероятностный алгоритм A, который, получая

  • вход I
  • вещественное

за время, полиномиальное от , выдает в качестве выхода , такое, что

называется:

  1.  Полностью полиномиальной рандомизированной аппроксимационной схемой
  2.  -полной рандомизированной аппроксимационной схемой
  3.  Полиномиальной рандомизированной аппроксимационной схемой
  4.  Полностью полиномиальной аппроксимационной схемой

Вопрос 40

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

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

Вопрос 41

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

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

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

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

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

Вопрос 42

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 43

  1.  
  2.  
  3.  
  4.  
  5.  
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-4-course-ispras»