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

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

Вариант 2622242589.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 15

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

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

Вопрос 16

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

  1.  Точность решения в среднем —
  2.  Подсчитывал число невыполненных наборов
  3.  Заполнял таблицу «наиболее выполняющими» наборами
  4.  Вероятностно подсчитывал число невыполненных наборов
  5.  Вероятностно подсчитывал число выполненных наборов
  6.  Находит приближенное решение, с точностью
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-6-course-ispras-weekly»