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

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

Вариант 3372463893.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

Выберите не NP-полную задачу

  1.  2SAT
  2.  3SAT
  3.  SAT
  4.  Клика (есть ли в графе клика больше заданной)
  5.  TSP-выполнимость
  6.  Сумма множеств
  7.  Вершинное покрытие

Вопрос 4

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

  1.  Да;
  2.  Нет;

Вопрос 5

Рассмотрим две задачи разрешения, P1 и P2, такие что

  • P1 сводится полиномиально по Карпу к 3SAT
  • 3SAT сводится полиномиально по Карпу к P2

Что можно утверждать?


  1.  Обе в NP-hard
  2.  Все остальные варианты — неверны.
  3.  P2 в NP, P1 в NP-hard
  4.  Обе в NP
  5.  P1 в NP, P2 в NP-hard

Вопрос 6

Выберите верное следствие:

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

Вопрос 7

Вероятностный алгоритм A, который, получая

  • вход I
  • вещественное

за время, полиномиальное от , выдает в качестве выхода , такое, что

называется:

  1.  Полностью полиномиальной аппроксимационной схемой
  2.  -полной рандомизированной аппроксимационной схемой
  3.  Полиномиальной рандомизированной аппроксимационной схемой
  4.  Полностью полиномиальной рандомизированной аппроксимационной схемой

Вопрос 8

Множество S является разрешимым, тогда и только тогда, когда существует такая машина Тьюринга T, что:

  1.  , то T останавливается и выводит 1, а если , то T зацикливается
  2.  , то T останавливается и выводит 1
  3.  , то T останавливается и выводит 0
  4.  , то T останавливается и выводит 1, а если , то T останавливается и выводит 0

Вопрос 9

Задачи 3SAT и 2SAT:

  1.  Обе в P
  2.  Первая неразрешима и вторая — NP-полна.
  3.  Первая NP-полна и вторая в P.
  4.  Обе NP-полны
  5.  Все остальные варианты — неверны.

Вопрос 10

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 11

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


  1.  ;
  2.  
  3.  ;

Вопрос 12

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

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

Вопрос 13

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

Вопрос 14

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

Вопрос 15

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

Вопрос 16

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

Вопрос 17

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

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

Вопрос 18

  1.  
  2.  
  3.  Quiz:Полиномиальный в среднем алгоритм для задачи упаковки
  4.  
  5.  

Вопрос 19

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

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

Вопрос 20

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

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

Вопрос 21

Пусть S — задача из NPC, а Q и R — тоже задачи, но про них известно только, что Q — полиномиально сводиться по Карпу к S, а S — к R.

Что будет верно?

  1.  Q — NP-полная
  2.  R — NP-полная
  3.  R — NP-трудная
  4.  Q — NP-трудная

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

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

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

Вопрос 26

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


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

Вопрос 27

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 28

Является ли пустое множество разрешимым?

  1.  Да;
  2.  Нет;

Вопрос 29

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 30

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

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

Вопрос 31

Пересечение двух каких классов окажется пустым, если окажется, что ?

  1.   и ;
  2.   и ;
  3.   и ;

Вопрос 32

Какой из этих тестов на простоту не является рандомизированным:

  1.  Все существующие тесты на простоту являются рандомизированными
  2.  Миллера-Рабина
  3.  Бейли — Померанца — Селфриджа — Уогстаффа
  4.  Бейли — Померанца — Селфриджа — Уогстаффа,
  5.  Миллера

Вопрос 33

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

  1.  
  2.  
  3.  
  4.  

Вопрос 34

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

Вопрос 35

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

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

Вопрос 36

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

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

Вопрос 37

У языков 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.  Только (I)
  5.  Все остальные варианты — неверны.

Вопрос 38

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


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

Вопрос 39

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

Вопрос 40

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