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

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

Вариант 2289885214.

Ваше имя*:

Вопрос 1

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


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

Что верно?

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

Вопрос 2

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

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

Вопрос 3

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

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

Вопрос 4

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

Вопрос 5

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

  1.  
  2.  
  3.  
  4.  

Вопрос 6

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

  1.  Аппроксимация Рюкзака (Knapsack) с точностью 0.87
  2.  Поиск гамильтонового цикла в графе из n-вершин, не хуже чем в n-раз от оптимального.
  3.  Аппроксимация Рюкзака (Knapsack) с точностью 0.1488
  4.  Поиск эйлерова цикла в графе из n-вершин, не хуже чем в n-раз от оптимального.
  5.  Кратчайший путь в графе с точностью

Вопрос 7

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

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

Вопрос 8

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


  1.  ;
  2.  ;
  3.  

Вопрос 9

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

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

Вопрос 10

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