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

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

Вариант 1942673151.

Ваше имя*:

Вопрос 1

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


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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

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


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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

Формулировка (в виде ЦЛП) какой задачи приведена ниже:

  1.  MAX-CUT
  2.  MIN-CUT
  3.  MIN-SAT
  4.  MAX-3SAT
  5.  MAX-SAT

Вопрос 14

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

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

Вопрос 15

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

  1.  
  2.  
  3.  
  4.  

Вопрос 16

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

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

Вопрос 17

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

  1.  
  2.  
  3.  
  4.  

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

  1.  квадратичное
  2.  полином, но степени больше 2
  3.  экспоненциальное
  4.  
  5.  линейное
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-6-course-ispras-weekly»