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

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

Вариант 93156137.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

  1.  
  2.  
  3.  3
  4.  

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 15

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

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

Вопрос 16

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 17

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

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

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

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