Еженедельный по «сложности алгоритмов» для 6 курса МФТИ — вопросы

Материал из DISCOPAL
Перейти к: навигация, поиск
12345678910
11121314151617181920
Еженедельный по «сложности алгоритмов» для 6 курса МФТИ

Вариант 2215609096.

Ваше имя*:

Вопрос 1

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

  1.  
  2.  
  3.  
  4.  3

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

Эйлеров цикл в графе:

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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

  1.  Рюкзак-оптимальность
  2.  Поиск кратчайших путей
  3.  Поиск совершенного паросочетания
  4.  Поиск минимального разреза
  5.  Алгоритм Флойда-Уоршелла
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-6-course-ispras-weekly»