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

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

Вариант 1090360900.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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


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

Вопрос 3

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

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

Вопрос 4

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

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

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

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

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

Вопрос 5

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 6

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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


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

Вопрос 14

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

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

Вопрос 15

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 20

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

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