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

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

Вариант 1989924635.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

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

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

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

Вопрос 8

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

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

Вопрос 9

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


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

Вопрос 10

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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


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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

В работах по теории сложности алгоритм называется полиномиальным в среднем, если для входов длины n и времени работы алгоритма T, выполняется:

  1.  
  2.  
  3.  
  4.  

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

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