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

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

Вариант 2239194542.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

  1.  
  2.  
  3.  
  4.  3

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

  1.  
  2.  
  3.  
  4.  

Вопрос 6

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

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

Вопрос 7

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 8

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

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

Вопрос 9

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

  1.  Евклидовой
  2.  Эйлеровой
  3.  Треугольной
  4.  Гамильтоновой
  5.  Метрической

Вопрос 10

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


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

Вопрос 11

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

  1.  
  2.  
  3.  
  4.  

Вопрос 12

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

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

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

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

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

  1.  Рюкзак-оптимизация
  2.  MAX-CUT
  3.  Рюкзак-выполнимость
  4.  MAX-SAT
  5.  MIN-CUT
  6.  TSP
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-6-course-ispras-weekly»