Главная / Алгоритмы и дискретные структуры /
Алгоритмы и модели вычислений / Тест 9
Алгоритмы и модели вычислений - тест 9
Упражнение 1:
Номер 1
Функция максимума определена на множестве
Ответ:
 (1) задач с ответом "да" 
 (2) задач с ответом "нет" 
 (3) индивидуальных задач 
Номер 2
Функция максимума из множества индивидуальных задач принимает значение, равное
Ответ:
 (1) максимальному числу в задаче 
 (2) максимальной клике в графе 
 (3) максимальному числу параллельных проходов по вершинному покрытию 
Номер 3
Если в индивидуальной задаче нет чисел, то функция максимума для каждой задачи полагается равной
Ответ:
 (1) 0
 
 (2) 1
 
 (3) бесконечности 
Упражнение 2:
Номер 1
Если в задаче нет полинома длины, который сверху ограничивал функцию максимума, то такая задача называется
Ответ:
 (1) задачей с числовыми параметрами 
 (2) задачей максимальной эквивалентности 
 (3) задачей частичного возврата 
Номер 2
Задача с числовыми параметрами - это задача, в которой
Ответ:
 (1) есть минимальное вершинное покрытие с нулевой вершиной 
 (2) нет полинома длины, который сверху ограничивал функцию максимума 
 (3) максимальная клика совпадает по значениям с полиномом максимумов 
Номер 3
От каких из приведенных ниже элементов зависит задача с числовыми параметрами?
Ответ:
 (1) от функции максимума 
 (2) от полинома длины 
 (3) ни от функции максимума, ни от полинома длины 
Упражнение 3:
Номер 1
Алгоритм, вычислительная сложность которого ограничена сверху полиномом от функции длины и функции максимума, носит название
Ответ:
 (1) унимодальный 
 (2) конкатенационный 
 (3) псевдополиномиальный 
Номер 2
Полином, ограничивающий вычислительную сложность псевдополиномиального алгоритма, зависит
Ответ:
 (1) от функции длины 
 (2) от функции терминалов 
 (3) от функции разбиения 
Номер 3
От каких из приведенных ниже функций зависит полином, ограничивающий вычислительную сложность псевдополиномиального алгоритма?
Ответ:
 (1) функция возврата 
 (2) функция максимума 
 (3) функция связности 
Упражнение 4:
Номер 1
Если количество операций и длины слов алгоритма ограничиваются полиномом от функции длины и функции максимума, то такой алгоритм будет
Ответ:
 (1) жадным 
 (2) возвратным 
 (3) псевдополиномиальным 
Номер 2
Если в алгоритме присутствуют только операции сложения и вычитания, то длина результата каждой операции
Ответ:
 (1) больше длины операндов в два раза 
 (2) меньше длины операций в два раза 
 (3) не более чем на одну единицу превышает длину операндов 
Номер 3
От выбора каких функций зависит псевдополиномиальность алгоритма?
Ответ:
 (1) функции максимума 
 (2) функции длины 
 (3) от выбора функций псевдополиномиальность алгоритма не зависит 
Упражнение 5:
Номер 1
Задачу о максимальном потоке можно сформулировать в виде задачи
Ответ:
 (1) распознавания свойств 
 (2) увеличения проходимости 
 (3) пакетного моделирования 
Номер 2
К элементам задачи о максимальном потоке в виде задачи распознавания свойств следует отнести
Ответ:
 (1) сеть 
 (2) исток и сток 
 (3) пропускные способности 
Номер 3
При решении задачи о максимальном потоке с помощью псевдополиномиального алгоритма в качестве функции максимума берется максимальное значение
Ответ:
 (1) суммы индексов вершин и пропускных способностей 
 (2) пропускной способности и числа, ограничивающего максимальный поток 
 (3) величины клики и вершинного покрытия 
Упражнение 6:
Номер 1
Сумма всех пропускных способностей дуг в сети носит название
Ответ:
 (1) величина потока 
 (2) величина клики 
 (3) величина вершинного покрытия 
Номер 2
Какие операции используются в алгоритме Форда-Фалкерсона?
Ответ:
 (1) сложение 
 (2) вычитание 
 (3) умножение 
Номер 3
Количество операций сложения и вычитания в алгоритме Форда-Фалкерсона составляет
Ответ:
 (1) O(lognm)
 
 (2) O(nlogm)
 
 (3) O(nmU)
 
Упражнение 7:
Номер 1
Если числа, которые присутствуют в формулировке задачи, равномерно ограничены сверху константой, то на данном подмножестве индивидуальных задач псевдополиномиальный алгоритм становится
Ответ:
 (1) равномерным 
 (2) полиномиальным 
 (3) терминальным 
Номер 2
Задача является NP-полной в сильном смысле, если
Ответ:
 (1) она принадлежит классу NP
 
 (2) существует подзадача для этой задачи, принадлежащая NPC
 
 (3) вершинное покрытие данной в задаче сети составляется псевдополиномиальным алгоритмом 
Номер 3
Любая NP-полная задача без числовых параметров является
Ответ:
 (1) NP-завершенной 
 (2) NP-зависимой 
 (3) NP-полной в сильном смысле 
Упражнение 8:
Номер 1
К NP-полным в сильном смысле задачам следует отнести
Ответ:
 (1) задачу о коммивояжере 
 (2) задачу конкатенации подмножеств 
 (3) задачу терминального обобщения полиномов 
Номер 2
К NP-полным в сильном смысле задачам следует отнести
Ответ:
 (1) задачу многопроцессорного расписания 
 (2) задачу потоковой сводимости в графе 
 (3) задачу линеаризации вершинных покрытий 
Номер 3
К элементам входа для задачи РМПС следует отнести
Ответ:
 (1) задачи 
 (2) директивный срок 
 (3) длительности 
Упражнение 9:
Номер 1
К оптимизационным задачам следует отнести
Ответ:
 (1) задачу о разбиении 
 (2) задачу о комплексных вершинах 
 (3) задачу многопроцессорного расписания 
Номер 2
Из полиномиальной сводимости для задач распознавания свойств следует
Ответ:
 (1) сводимость по Тьюрингу 
 (2) комплексная сводимость 
 (3) вариативная сводимость 
Номер 3
Если существует NP-полная задача П1
, которая сводится по Тьюрингу к задаче П2
, то задача П2
является
Ответ:
 (1) NP-трудной 
 (2) NP-легкой 
 (3) NP-сводимой 
Упражнение 10:
Номер 1
Оптимизационный вариант задачи о коммивояжере является
Ответ:
 (1) NP-трудным 
 (2) NP-легким 
 (3) NP-вариативным 
Номер 2
Множество NP-трудных задач обозначается
Ответ:
 (1) NPC
 
 (2) NPH
 
 (3) NPX
 
Номер 3
Множество NPH
определяет
Ответ:
 (1) NP-трудные задачи 
 (2) NP-разрешимые задачи 
 (3) NP-комплексные задачи 
Упражнение 11:
Номер 1
Если задача П1
сводится по Тьюрингу к задаче П2
из класса NP
, то задача П1
является
Ответ:
 (1) NP-конечной 
 (2) NP-легкой 
 (3) NP-терминальной 
Номер 2
Если задача П сводится по Тьюрингу к оптимизационной, то задача П является
Ответ:
 (1) NP-трудной 
 (2) NP-легкой 
 (3) NP-маркированной 
Номер 3
При использовании приближенного алгоритма необходимо учитывать
Ответ:
 (1) сложность 
 (2) необходимую память 
 (3) погрешность 
Упражнение 12:
Номер 1
Длина интервала от нуля до момента завершения работы в задаче многопроцессорного расписания определяет
Ответ:
 (1) длину расписания 
 (2) модуль расписания 
 (3) коэффициент сводимости расписания 
Номер 2
Существует ли полиноминально точный алгоритм решения оптимизационной задачи многопроцессорного расписания?
Ответ:
 (1) да, существует 
 (2) нет, не существует 
 (3) только когда количество работ ограничено сверху константой 
Номер 3
Для приближенного решения оптимизационной задачи многопроцессорного расписания используют
Ответ:
 (1) эвристические алгоритмы 
 (2) муравьиные алгоритмы 
 (3) генетические алгоритмы