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

Материал из DISCOPAL
Перейти к: навигация, поиск
12345678910
Еженедельный по «сложности алгоритмов» для 3 курса ИСПРАН

Вариант 3679756141.

Ваше имя*:

Вопрос 1

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

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

Какие из подходов к решению вычислительно трудных задач изучались в курсе?

  1.  Построение эффективных в среднем алгоритмов
  2.  Применение эволюционных алгоритмов
  3.  Построение эффективных алгоритмов муравьиной колонии

Вопрос 5

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

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

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

Вопрос 6

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

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

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

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

Вопрос 7

Пусть

  • — задача поиска гамильтонового цикла в графе , где V — делится на 3.
  • — задача подтверждения наличия гамильтонового цикла в таком графе.

Что верно?

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

Вопрос 8

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

Вопрос 9

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

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

Вопрос 10

Для какой задачи не существует (при условии ) полиномиального алгоритма:

  1.  Поиск эйлерова цикла в графе
  2.  Аппроксимация Рюкзака (Knapsack) с точностью 0.9
  3.  Кратчайшие пути в графе
  4.  Аппроксимация MAX-SAT с точностью 0.9
  5.  Аппроксимация Рюкзака (Knapsack) с точностью 0.017
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-3-course-ispras-weekly»