Тест по сложности алгоритмов для 3 курса ИСПРАН — вопросы

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

Вариант 1087482847.

Ваше имя*:

Вопрос 1

Найдите неверное утверждение:

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

Вопрос 2

  1.  ZPP
  2.  coRP
  3.  BPP
  4.  coZPP
  5.  PP
  6.  PSPACE
  7.  RP
  8.  NP

Вопрос 3

  1.  RP
  2.  NP
  3.  coRP
  4.  ZPP
  5.  BPP
  6.  PTAS
  7.  ALL
  8.  PP

Вопрос 4

Пусть сводится по Карпу к . Выберите верное утверждение:

  1.  Если , то ;
  2.  Если , то ;
  3.  Если , то ;

Вопрос 5

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


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

Вопрос 6

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

  1.  
  2.  
  3.  
  4.  

Вопрос 7

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

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

Вопрос 8

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

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

Вопрос 9

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

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

Вопрос 10

  1.  
  2.  FPTAS
  3.  BPP
  4.  PP
  5.  coZPP
  6.  RP
  7.  coRP
  8.  ZPP

Вопрос 11

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 12

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

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

Вопрос 13

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

  1.  Да;
  2.  Нет;

Вопрос 14

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

  1.  coZPP
  2.  coRP
  3.  ZPP
  4.  NP
  5.  BPP
  6.  PSPACE
  7.  PP
  8.  RP

Вопрос 18

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

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

Вопрос 19

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

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

Вопрос 20

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 21

Рассмотрим пару задач на графах.

P1
Для заданного графа, подтвердить или опровергнуть, что в нем есть цикл, которые посещает однократно все вершины, кроме первой, в которую надо вернутся, чтобы завершить цикл.
P2

Для заданного графа, подтвердить или опровергнуть, что в нем есть цикл, который проходит по каждому ребру точно один раз, без исключений.

  1.  Обе в NPC
  2.  Все остальные варианты — неверны.
  3.  X в NP, но не NP-полная.
  4.  P2 в NPC, P1 в P.
  5.  P1 в NPC, P2 в P.
  6.  Обе в P

Вопрос 22

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

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

Вопрос 23

Какой метод применялся в теме про подсчет выполняющих наборов для ДНФ?

  1.  Вероятностное округление
  2.  Дерандомизация вероятностного округления
  3.  Монте-Карло
  4.  Полный перебор
  5.  Динамическое программирование

Вопрос 24

Найдите неверное утверждение:

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

Вопрос 25

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

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

Вопрос 26

  1.  BPP
  2.  coZPP
  3.  ZPP
  4.  NP
  5.  RP
  6.  PP
  7.  PSPACE
  8.  coRP

Вопрос 27

Какое утверждение неверно?

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

Вопрос 28

Предположим, разумеется, что Тогда что будет верно?

  1.  
  2.  
  3.  
  4.  

Вопрос 29

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

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

Вопрос 30

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

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

Вопрос 31

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

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

Вопрос 32

У языков L1-L4 доказаны следующие полиномиальные сводимости по Карпу: «L1→L2», «L3→L2→L4» Рассмотрим утверждения:

I
Если L4 в P, то L2 в P
II
Если L1 или L3 в P, то L2 в P
III
L1 в P, тогда и только тогда, когда L3 в P
IV
Если L4 в P, то L1 в P и L3 в P.


  1.  Только (III)
  2.  Только (I) и (IV)
  3.  Только (II)
  4.  Все остальные варианты — неверны.
  5.  Только (I)

Вопрос 33

Найдите неверное утверждение:

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

Вопрос 34

Выберите верное верное утверждение из списка ниже, если верных вариантов ответа несколько, то выберите наиболее сильный из них:

  1.  Нет верного ответа;
  2.  Из разрешимости множества следует его перечислимость;
  3.  Перечислимые и разрешимые множества никак не пересекаются;
  4.  Из перечислимости множества следует его разрешимость;

Вопрос 35

  1.  coRP
  2.  PP
  3.  RP
  4.  ZPP
  5.  coZPP
  6.  PSPACE
  7.  NP
  8.  BPP

Вопрос 36

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

  1.  
  2.  
  3.  
  4.  

Вопрос 37

Выберите верное утверждение


  1.  ;
  2.  
  3.  ;

Вопрос 38

Является ли разрешимым множество натуральных чисел, не превосходящих :

  1.  Нет
  2.  Да
  3.  Неизвестно, поскольку ответ на этот вопрос следует из истинности\ложности гипотезы Римана;

Вопрос 39

Выберите верное утверждение


  1.  Верного ответа нет
  2.  Из сводимости по Карпу следует сводимость по Куку
  3.  Из сводимости по Куку следует сводимость по Карпу

Вопрос 40

  1.  coZPP
  2.  PP
  3.  NP
  4.  PSPACE
  5.  coRP
  6.  ZPP
  7.  RP
  8.  BPP
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-exam»