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

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

Вариант 2571718263.

Ваше имя*:

Вопрос 1

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 2

Предположим, открыли полиномиальный алгоритм, вычисляющий наибольшую клику в заданном графе. Что тогда будет, согласно вариантам на картинке?

NPC-GQ08.png


  1.  D
  2.  B
  3.  Все остальные варианты — неверны.
  4.  A
  5.  C

Вопрос 3

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

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

Вопрос 4

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

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

Вопрос 5

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

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

Вопрос 6

Замкнутость по какой из операций выполнена как для разрешимых, так и для перечислимых языков?

  1.  Дополнение;
  2.  Разность множеств;
  3.  Декартово произведение;

Вопрос 7

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

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

Вопрос 8

Пусть задача A — «есть ли цикл в ненаправленном графе». Рассмотрим набор утверждений.


  • (1) Задача A — в P
  • (2) Задача A — в NP
  • (3) Если задача A — NP-полна, то существует НМТ, решающая A за полиномиальное время.

Что верно?

  1.  Все остальные варианты — неверны.
  2.  1 и 2
  3.  1 и 3
  4.  2 и 3
  5.  1, 2 и 3

Вопрос 9

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


  1.  ;
  2.  ;
  3.  

Вопрос 10

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

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

Вопрос 11

Аню и Колю попросили показать, что задача X — NP-полна. Аня показала полиномиальную сводимость по Карпу от 3SAT к X, а Коля показал полиномиальную сводимость по Карпу от X к 3SAT.

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

  1.  X в NP, но не NP-полная.
  2.  Все остальные варианты — неверны.
  3.  X — NP-полная.
  4.  X — NP-трудная, но не NP-полная.
  5.  X — не NP-полная, и вообще не в NP.

Вопрос 12

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

  1.  Нет;
  2.  Да;

Вопрос 13

Что верно для NP-полных и NP-трудных задач:

  1.  Первой задачей с доказанной NP-полнотой была CircuitSAT, «the circuit satisfiability problem»
  2.  Все варианты, кроме «ничего не верно»
  3.  Если мы хотим доказать, что задача X — NP-трудна, мы берем известную NP-полную задачу Y и сводим ее полиномиально по Карпу к X.
  4.  Ничего не верно.
  5.  

Вопрос 14

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

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

Вопрос 15

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

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

Вопрос 16

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

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

Вопрос 17

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

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

Вопрос 18

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

  1.  3
  2.  
  3.  
  4.  

Вопрос 19

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

Вопрос 20

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

Вопрос 21

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

Вопрос 22

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

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

Вопрос 23

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

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

Вопрос 24

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

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

Вопрос 25

Является ли конкатенация двух разрешимых языков перечислимой?

  1.  Нет;
  2.  Да;

Вопрос 26

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

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

Вопрос 27

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

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

Вопрос 28

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

Вопрос 29

Пусть X — задача из NP. Что верно?

  1.  Если X — NP-hard, то она NP-полная
  2.  X может быть неразрешима
  3.  X — NP-трудная
  4.  Если X можно решить за полиномиальное время на ДМТ, то P=NP
  5.  Все остальные варианты — неверны.
  6.  Нет полиномиального алгоритма для X

Вопрос 30

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

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

Вопрос 31

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

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

Вопрос 32

Возможно ли сконструировать алгоритм , который для произвольной машины Тюринга и входа определит, остановится ли данная М.Т. на заданном входе?

  1.  Да, известно чёткое описание того, как это делать;
  2.  Нет
  3.  Формально да, но никто не знает как именно это сделать (примерно как со вполне упорядочиванием );

Вопрос 33

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 34

Существует ли алгоритм, который выписывает одну за другой все машины Тьюринга, которые не останавливаются, будучи запущенными на пустой ленте?

  1.  Нет
  2.  Да

Вопрос 35

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

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

Вопрос 36

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 37

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

Вопрос 38

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

Вопрос 39

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

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

Вопрос 40

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