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

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

Вариант 2518474173.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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


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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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


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

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 20

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

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