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

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

Вариант 415472425.


Ваше имя*:


Вопрос 1

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

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

Задача 2SAT:

  1.  Все остальные варианты — неверны.
  2.  NP-полна
  3.  разрешима за константное время, т.к. любой вход для такой задачи выполним.
  4.  NP-трудна, но не NP-полна.
  5.  разрешима за полиномиальное время, но не за константное время.

Вопрос 5

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

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

Вопрос 6

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

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

Вопрос 7

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

Вопрос 8

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

Вопрос 9

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

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

Вопрос 10

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

  1.  
  2.  
  3.  
  4.