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

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

Вариант 2348535209.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

  1.  
  2.  
  3.  
  4.  

Вопрос 4

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 5

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


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

Вопрос 6

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

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

Вопрос 7

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

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

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

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

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

Вопрос 8

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

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

Вопрос 9

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

  1.  
  2.  
  3.  
  4.  

Вопрос 10

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

  1.  трехсторонние
  2.  «PP»-ошибки
  3.  двусторонние
  4.  односторонние
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Эффективные_алгоритмы»