игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Алгоритмы и модели вычислений / Тест 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) генетические алгоритмы 




Главная / Алгоритмы и дискретные структуры / Алгоритмы и модели вычислений / Тест 9