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

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

Вариант 3088695411.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

  1.  
  2.  
  3.  
  4.  

Вопрос 15

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

  1.  
  2.  3
  3.  
  4.  

Вопрос 16

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

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

Вопрос 17

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

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