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

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

Вариант 436934972.

Ваше имя*:

Вопрос 1

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


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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

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

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

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

Вопрос 7

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


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

Вопрос 8

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

Формулировка (в виде ЦЛП) какой задачи приведена ниже:

  1.  MAX-3SAT
  2.  MAX-SAT
  3.  MAX-CUT
  4.  MIN-CUT
  5.  MIN-SAT

Вопрос 12

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

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

Вопрос 13

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

  1.  
  2.  
  3.  
  4.  3

Вопрос 18

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 19

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 20

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

  1.  Применение теории генетических алгоритмов
  2.  Построение эффективных метаэвристик
  3.  Построение эффективных вероятностных приближенных алгоритмов с оценками точности в худшем случае
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-6-course-ispras-weekly»