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

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

Вариант 3115836737.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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


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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 13

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

  1.  
  2.  
  3.  
  4.  

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

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