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

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

Вариант 284208876.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

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

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

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

Вопрос 8

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 9

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

  1.  
  2.  
  3.  
  4.  

Вопрос 10

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

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

Вопрос 11

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

  1.  Применение эволюционных алгоритмов
  2.  Построение эффективных в среднем алгоритмов
  3.  Построение эффективных алгоритмов муравьиной колонии

Вопрос 12

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


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

Вопрос 13

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


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

Вопрос 14

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

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