Еженедельный по «сложности алгоритмов» для 6 курса МФТИ — вопросы

Материал из DISCOPAL
Перейти к: навигация, поиск
12345678910
11121314151617181920
Еженедельный по «сложности алгоритмов» для 6 курса МФТИ

Вариант 573201694.

Ваше имя*:

Вопрос 1

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

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 2

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

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

Вопрос 3

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

  1.  Построение точных алгоритмов с субэкспоненциальными оценками сложности
  2.  Построение эффективных эвристических алгоритмов
  3.  Построение эффективных приближенных алгоритмов с оценками точности в худшем случае

Вопрос 4

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

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

Вопрос 5

В теме про полиномиальный в среднем алгоритм для «SAT» наш алгоритм…

  1.  Точность решения в среднем —
  2.  Вероятностно подсчитывал число выполненных наборов
  3.  Вероятностно подсчитывал число невыполненных наборов
  4.  Находит приближенное решение, с точностью
  5.  Заполнял таблицу «наиболее выполняющими» наборами
  6.  Подсчитывал число невыполненных наборов

Вопрос 6

  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 7

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

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

Вопрос 8

Эйлеров цикл в графе:

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

Вопрос 9

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

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

Вопрос 10

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

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

Вопрос 11

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

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

Вопрос 12

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

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

Вопрос 13

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

  1.  
  2.  
  3.  
  4.  

Вопрос 14

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


  1.  
  2.  
  3.  
  4.  
  5.  

Вопрос 15

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

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

Вопрос 16

Если алгоритму из темы про полиномиальный в среднем алгоритм упаковки подать на вход единичную матрицу инцидентности, он, если считать от длины входа, затратит время …

  1.  квадратичное
  2.  экспоненциальное
  3.  
  4.  полином, но степени больше 2
  5.  линейное

Вопрос 17

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

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

Вопрос 18

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

  1.  
  2.  
  3.  
  4.  

Вопрос 19

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

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

Вопрос 20

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

  1.  Петля Нестерова
  2.  Цикл Нельсона
  3.  Гамильтонов цикл
  4.  Наполеонов цикл
  5.  Эйлеров цикл
Источник — «https://discopal.ispras.ru/Служебная:MediawikiQuizzer/Algs-6-course-ispras-weekly»