Эффективные алгоритмы — вопросы

Материал из DISCOPAL
Перейти к: навигация, поиск
12345678910
11121314151617181920
21222324252627282930
Тест по курсу «Эффективные алгоритмы»

Вариант 2695177907.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

Паросочетание, покрывающее все вершины графа, называется

  1.  максимальным
  2.  совершенным
  3.  сочетающим
  4.  вершинным
  5.  покрывающим

Вопрос 4

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

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

Вопрос 5

Как называется задача оптимизации со следующей формулировкой:

  1.  Выпуклое программирование
  2.  Линейное программирование
  3.  Полуопределенное программирование
  4.  Целочисленное линейное программирование
  5.  Положительное линейное программирование (ПЛП)
  6.  Векторное программирование

Вопрос 6

Какой класс ошибок допускают алгоритмы решающие задачи из класса BPP?

  1.  односторонние
  2.  трехсторонние
  3.  двусторонние
  4.  «BP»-ошибки

Вопрос 7

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


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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

Как называется задача оптимизации со следующей формулировкой:

  1.  Линейное программирование
  2.  Выпуклое программирование
  3.  Векторное программирование
  4.  Полуопределенное программирование
  5.  Целочисленное линейное программирование
  6.  Положительное линейное программирование (ПЛП)

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

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

Вопрос 14

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

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

Вопрос 15

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 16

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


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

Вопрос 17

Вероятностные «zero-error»-алгоритмы:

  1.  Всегда дают верный ответ
  2.  Могут ошибаться, но только в случае, если возвращают «0»
  3.  Всегда дают верный ответ в случае, если возвращают «0»
  4.  Когда дают ответ он правильный, но могут отвечать «не знаю»

Вопрос 18

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 19

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

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

Вопрос 20

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

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

Вопрос 21

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

  1.  
  2.  
  3.  
  4.  

Вопрос 22

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 23

Какой класс ошибок допускают алгоритмы решающие задачи из класса ZPP?

  1.  двусторонние
  2.  односторонние (при ответе «0»)
  3.  никакие
  4.  односторонние (при ответе «1»)
  5.  «ZPP»-ошибки
  6.  трехсторонние

Вопрос 24

Есть граф G=(V,E). Разбиение множества вершин V на непересекающиеся множества S и T называется:

  1.  Паросочетание
  2.  Клика
  3.  Разрез
  4.  Раскладка
  5.  Разбивка
  6.  Поток

Вопрос 25

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

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

Вопрос 26

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

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

Вопрос 27

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

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

Вопрос 28

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

  1.  
  2.  
  3.  
  4.  

Вопрос 29

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

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

Вопрос 30

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

  1.  стоимости произвольные, веса выбираются случайно
  2.  веса произвольные, стоимость выбираются случайно
  3.  и стоимости и веса выбираются случайно
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Эффективные_алгоритмы-Экзамен»