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

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

Вариант 1440483967.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

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

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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


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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 14

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


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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

  1.  
  2.  
  3.  
  4.  3

Вопрос 18

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

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

Вопрос 19

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

  1.  Немхаузера-Ульмана
  2.  Флойда-Уоршелла
  3.  Беллмана-Форда
  4.  Эдмондса-Карпа
  5.  Каргера-Штейна
  6.  Форда-Фалкерсона

Вопрос 20

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

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