Главная /
Алгоритмы и дискретные структуры /
Алгоритмы и модели вычислений
Алгоритмы и модели вычислений - ответы на тесты Интуит
Правильные ответы выделены зелёным цветом.
Все ответы: Рассматриваются некоторые теоретические проблемы, возникающие при разработке математического обеспечения вычислительных систем. Изучаются такие фундаментальные проблемы, как теория потоков в сетях, анализ сложности алгоритмов и сложности дискретных задач. Рассмотрены методы решения переборных задач. Даны алгоритмы решения некоторых задач на параллельной машине с произвольным доступом.
Все ответы: Рассматриваются некоторые теоретические проблемы, возникающие при разработке математического обеспечения вычислительных систем. Изучаются такие фундаментальные проблемы, как теория потоков в сетях, анализ сложности алгоритмов и сложности дискретных задач. Рассмотрены методы решения переборных задач. Даны алгоритмы решения некоторых задач на параллельной машине с произвольным доступом.
Смотрите также:
Если P не равно NP, то для оптимизационной задачи вершинного покрытия
(1) существует полиномиальный алгоритм решения
(2) не существует приближенного алгоритма решения
(3) соответствие классов NPH и NPC определяется с помощью сведения по Тьюрингу
В качестве модели многопроцессорной системы можно рассматривать
(1) генетический осциллятор с коррекцией входа
(2) параллельную машину с прямым доступом
(3) логарифмический дифференциатор с выбором меток
Множество дуг и узлов носит название
(1) суппорт
(2) граф
(3) терминал
Из приведенных ниже характеристик выберите те, которые соответствуют работам в многопроцессорном расписании:
(1) длительность
(2) комплексность
(3) потоковость
Задача распознавания свойств характеризуется
(1) детерминизмом
(2) списком параметров
(3) вопросами
К NP-полным задачам следует отнести
(1) задачу конкретизации параметров
(2) задачу выполнимости
(3) задачу разбиения
Функция максимума определена на множестве
(1) задач с ответом "да"
(2) задач с ответом "нет"
(3) индивидуальных задач
Цикл в сети, который проходит ровно один раз через каждый узел, носит название
(1) гамильтонов цикл
(2) эйлеров цикл
(3) цикл Лагранжа
Из приведенных ниже записей выделите модели многопроцессорных систем:
(1)
EREW
(2)
CRCW
(3)
GRGW Граф, в котором выделен источник и сток, и каждой дуге назначена ее пропускная способность, носит название
(1) контейнер
(2) сеть
(3) орграф
При выполнении работ переключения с одного процессора на другой
(1) невозможны
(2) приведут к выходу из строя оборудования
(3) допускаются
Значения всех параметров в задаче распознавания свойств формируют
(1) слово
(2) контейнер
(3) логику
Экземпляром задачи выполнимости является
(1) массив идентификаторов
(2) булева формула
(3) список констант
Если в задаче нет полинома длины, который сверху ограничивал функцию максимума, то такая задача называется
(1) задачей с числовыми параметрами
(2) задачей максимальной эквивалентности
(3) задачей частичного возврата
Связный граф, в котором
n вершин и n-1 ребро, носит название
(1) дерево
(2) остов
(3) клика
В многопроцессорной модели, допускающей запись разнородной информации, записываться в ячейку будет информация от процессора
(1) с наибольшим быстродействием
(2) с наименьшим номером
(3) с наименьшим откликом
Из приведенных ниже записей выделите условия существовавния потока в сети?
(1) неотрицательность
(2) баланс
(3) допустимость
Какое количество процессоров выполняет заданную работу в фиксированный момент времени в многопроцессорном расписании?
(1) 1
(2) 2
(3) множество
Из приведенных ниже записей выделите составляющие части машины Тьюринга:
(1) конечный алфавит
(2) входной алфавит
(3) терминальный алфавит
Является ли задача выполнимости в нормальной конъюнктивной форме NP-полной?
(1) да, является
(2) нет, не является
(3) является только для комплексных аргументов
Алгоритм, вычислительная сложность которого ограничена сверху полиномом от функции длины и функции максимума, носит название
(1) унимодальный
(2) конкатенационный
(3) псевдополиномиальный
Ациклический подграф данного графа, в который входят все вершины данного графа, носит название
(1) комплексное дерево
(2) вершинное покрытие
(3) остовное дерево
Если в многопроцессорной системе выполняется некоторый цикл, в котором процессоры одновременно выполняют операции, то в качестве времени работы этого цикла берется
(1) степень полуисхода цикла
(2) количество итераций
(3) максимальное число петлевых вычислений
Дуга, расположенная по ориентации потока, носит название
(1) реверсная
(2) стандартная
(3) прямая
Длительность каждой работы в многопроцессорном расписании должна быть равна
(1) величине директивного интервала
(2) модулю работы
(3) коэффициенту связности
Правила перехода формируются с помощью
(1) алгоритма, реализуемого машиной Тьюринга
(2) конечного алфавита символов
(3) функций корректировки соответствия параметров
Множество вершин
S графа такое, что у каждого ребра графа хотя бы один из концов входит в S, носит название
(1) коронарное покрытие
(2) вершинное покрытие
(3) аддитивное покрытие
Если количество операций и длины слов алгоритма ограничиваются полиномом от функции длины и функции максимума, то такой алгоритм будет
(1) жадным
(2) возвратным
(3) псевдополиномиальным
Сумма длин ребер остовного дерева носит название
(1) длина дерева
(2) мощность дерева
(3) рекурсия дерева
Крайний справа элемент в списке при определении порядковых номеров многопроцессорными системами имеет номер
(1)
1
(2)
0
(3)
n Поток максимален тогда и только тогда, когда в остаточной сети нет
(1) петель
(2) кратных дуг
(3) увеличивающего пути
Какое количество памяти требуется для реализации алгоритма упаковки?
(1)
O(n)
(2)
O(nlgT)
(3)
O(lgT) Для какого состояния машины Тьюринга не формируются правила
(1) для начального
(2) для заключительного
(3) для нулевого
В чем суть задачи о вершинном покрытии?
(1) в нахождении наибольшего вершинного покрытия
(2) в нахождении минимального вершинного покрытия
(3) в определении степени вхождения вершин в вершинном покрытии
Задачу о максимальном потоке можно сформулировать в виде задачи
(1) распознавания свойств
(2) увеличения проходимости
(3) пакетного моделирования
Общим алгоритмическим методом для нахождения оптимальных решений различных задач оптимизации является
(1) метод строк и столбцов
(2) метод ветвей и границ
(3) метод конечноразностных полиномов
При использовании многопроцессорного алгоритма для определения порядковых номеров в списке, количество элементов с нулевыми указателями на каждой итерации
(1) уменьшается на 1
(2) увеличивается вдвое
(3) остается неизменным
Длина слов, с которым работает алгоритм Форда-Фалкерсона, выражается значением
(1)
O(lg(U))
(2)
O(log2(U))
(3)
O(ln(U)) Какие узлы применяются в сети при использовании алгоритма Танаева?
(1) узлы-интервалы
(2) узлы-работы
(3) узлы-терминалы
Класс всех рекурсивных языков обозначается
(1)
R
(2)
RL
(3)
RF Путь, содержащий каждую вершину графа ровно один раз, носит название
(1) Эйлеров цикл
(2) Гамильтонов цикл
(3) Марковский цикл
Сумма всех пропускных способностей дуг в сети носит название
(1) величина потока
(2) величина клики
(3) величина вершинного покрытия
Какие из приведенных ниже процедур используются в методе ветвей и границ?
(1) процедура ветвления
(2) процедура формирования рекурсивных циклов
(3) процедура векторизации
К бинарным ассоциативным операциям следует отнести
(1) сложение
(2) умножение
(3) целочисленное деление
Если путь из вершины в сток содержит хотя бы одну насыщенную дугу, он называется
(1) возвратным
(2) блокированным
(3) конструктивным
Сумма интервалов процессорного времени на выполнение работ в алгоритме Танаева представляет собой
(1) величину потока
(2) модуль мощности работ
(3) суммарный коэффициент заполнения
К рекурсивным языкам следует отнести
(1) регулярные языки
(2) контекстно-свободные языки
(3) контекстно-зависимые языки
Пусть
p - число вершин в данном графе. Если степень каждой вершины не меньше, чем p/2, то граф является
(1) гамильтоновым
(2) параллельным
(3) остовным
Если числа, которые присутствуют в формулировке задачи, равномерно ограничены сверху константой, то на данном подмножестве индивидуальных задач псевдополиномиальный алгоритм становится
(1) равномерным
(2) полиномиальным
(3) терминальным
Подобласти, образовавшиеся в результате процедуры ветвления в методе ветвей и границ, образуют дерево, называемое
(1) деревом связей
(2) деревом выборки
(3) деревом поиска
Однопроцессорный алгоритм вычисления глубины вершины в двоичном дереве работает методом
(1) конечного ветвления
(2) аналитического соответствия
(3) двойного обхода
Балансирование при нахождении тупикового потока производится на дефицитных вершинах
(1) максимального ранга
(2) минимального ранга
(3) нулевого ранга
Максимальное количество прерываний и переключений в алгоритме Танаева составляет
(1)
2m
(2)
m
(3)
m-1 Класс всех рекурсивно распознаваемых языков называется
(1)
RG
(2)
RE
(3)
RF Класс дополнений языков из NP носит название
(1)
co-NP
(2)
re-NP
(3)
a-NP К NP-полным в сильном смысле задачам следует отнести
(1) задачу о коммивояжере
(2) задачу конкатенации подмножеств
(3) задачу терминального обобщения полиномов
Работы при многопроцессорном расписании выполняются
(1) без прерываний
(2) без переключений
(3) с рекурсиями
На какой многопроцессорной модели реализовывается алгоритм определения корня для вершины двоичного леса?
(1)
EREW
(2)
CRSW
(3)
CREW Величина произвольного потока в сети ограничена сверху величиной
(1) модуля пропускной способности
(2) величиной произвольного разреза
(3) объемом вершин потока
В худшем случае алгоритм Танаева выполняется
(1) за
O(n) операций
(2) за
O(n2)
(3) за
O(n3) К примерам алгоритмов класса P следует отнести
(1) выяснение связности графов
(2) алгоритмы целочисленного деления
(3) перемножение матриц
Если задача лежит одновременно в классе
NP и в классе co-NP, то она лежит
(1) в классе
N
(2) в классе
P
(3) в классе
NCP К оптимизационным задачам следует отнести
(1) задачу о разбиении
(2) задачу о комплексных вершинах
(3) задачу многопроцессорного расписания
Максимальная длительность работы на процессоре представляет собой
(1) модуль сложности процессорного расписания
(2) длину процессорного расписания
(3) коэффициент быстродействия
Если
d - максимальная высота дерева леса, n - количество вершин, то общие затраты многопроцессорного алгоритма определения корня для вершины двоичного леса составляют
(1)
O(dn)
(2)
O(nlog2d)
(3)
O(n+d-1) Какое количество операций занимает процедура расстановки меток в алгоритме Карзанова?
(1)
O(m2)
(2)
O(2m-1)
(3)
O(m) Число дуг в самом длинном пути, ведущем из вершины в лист, называется
(1) высотой
(2) мощностью
(3) модулем
Множество алгоритмов, время работы которых существенно зависит от размера входных данных, и которое уменьшается при предоставлении алгоритму некоторых дополнительных сведений, носит название
(1) класс
PC
(2) класс
NP
(3) класс
DP Пересекаются ли классы
P и NPC?
(1) да, пересекаются
(2) нет, не пересекаются
(3) только в классе
co-NP Оптимизационный вариант задачи о коммивояжере является
(1) NP-трудным
(2) NP-легким
(3) NP-вариативным
Множество всех возможных назначений работ на процессоры в дереве поиска представляется в виде
(1) узлов
(2) корня
(3) листьев
Какова вычислительная сложность многопроцессорного алгоритма определения максимального элемента n-мерного массива для
n процессоров?
(1)
O(1)
(2)
O(n)
(3)
O(logn) Количество обработок насыщенных дуг ограничено сверху значением
(1)
log(m)
(2)
m
(3)
m2 Высота кучи равна
(1)
O(logn)
(2)
O(n)
(3)
O(n2) Задача из класса
NP, к которой можно свести любую другую задачу из класса NP, называется
(1) NP-корректной
(2) NP-полной
(3) NP-модифицированной
Максимальный полный подграф графа называется
(1) остовом
(2) проходом
(3) кликой
Если задача
П1 сводится по Тьюрингу к задаче П2 из класса NP, то задача П1 является
(1) NP-конечной
(2) NP-легкой
(3) NP-терминальной
Если при раскрытии всех скобок и приведения подобных слагаемых в полиноме все слагаемые будут взаимоуничтожены, такой полином является
(1) рандомизированным
(2) тождественно равным нулю
(3) детерминированным
Для эффективной параллельной обработки префиксов процессорами, количества p, двусторонний список разбивается
(1) на
p-1 групп
(2) на
p групп
(3) на
p+1 групп Алгоритм пирамидальной сортировки работает в худшем случае за время
(1)
O(n)
(2)
O(logn)
(3)
O(nlogn) Класс всех NP-полных языков обозначается
(1) NPC
(2) PN
(3) Co-P
В оптимизационной задаче о клике необходимо найти в графе
(1) клику максимального размера
(2) клику минимального размера
(3) клику нулевого размера
Длина интервала от нуля до момента завершения работы в задаче многопроцессорного расписания определяет
(1) длину расписания
(2) модуль расписания
(3) коэффициент сводимости расписания
Оптимизационная задача о вершинном покрытии является
(1) NP-трудной
(2) NP-легкой
(3) NP-неопределенной
Обращение к ячейке памяти в параллельной машине с прямым доступом осуществляется
(1) по времени исполнения
(2) по типу данных
(3) по адресу
Пара узлов графа носит название
(1) дуга
(2) ветвь
(3) константа
К характеристикам работы в многопроцессорном расписании следует отнести
(1) коэффициент суммарного потока
(2) директивный интервал
(3) модуль величины потока
Вопрос в задаче распознавания свойств ставится в виде
(1) конкатенации свойств
(2) предиката
(3) параллельных вычислений
Из приведенных ниже записей выделите NP-полные задачи:
(1) задача 3-выполнимости
(2) задача 3-тождественности
(3) задача 3-сочетания
Функция максимума из множества индивидуальных задач принимает значение, равное
(1) максимальному числу в задаче
(2) максимальной клике в графе
(3) максимальному числу параллельных проходов по вершинному покрытию
Гамильтонов цикл - это
(1) минимальный путь в сети от истока к стоку
(2) цикл, который проходит ровно один раз через каждый узел
(3) обратное вершинное покрытие
Многопроцессорная модель с исключающим чтением и исключающей записью носит название
(1)
ASAD
(2)
EREW
(3)
CRWR Для того, чтобы граф считался сетью, среди его вершин следует выделить
(1) источник
(2) лидера группы
(3) сток
Прерывания и переключения в многопроцессорном расписании
(1) являются необходимыми
(2) не требуют временных издержек
(3) производятся согласно реверсному порядку
Каким образом обозначается длина слова x в задаче распознавания свойств?
(1)
{x}
(2)
[x]
(3)
|x| К элементам экземпляра задачи выполнимости следует отнести
(1) имена переменных
(2) скобки
(3) операции
Задача с числовыми параметрами - это задача, в которой
(1) есть минимальное вершинное покрытие с нулевой вершиной
(2) нет полинома длины, который сверху ограничивал функцию максимума
(3) максимальная клика совпадает по значениям с полиномом максимумов
Какое количество ребер в дереве с
n вершинами?
(1)
n
(2)
n-1
(3)
2n-1 Какая многопроцессорная модель является самой легкой с точки зрения аппаратной поддержки?
(1)
EREW
(2)
CREW
(3)
CRCW Поток нулевой мощности носит название
(1) циркуляция
(2) конкатенация
(3) диссоциация
Какое количество работ выполняется одним процессором в фиксированный момент времени в многопроцессорном расписании?
(1) одна
(2) более трех
(3) множество
Какие из приведенных ниже элементов являются составляющими частями машины Тьюринга?
(1) пустой символ
(2) модификатор ввода
(3) функция перехода
Задача выполнимости булевых формул в k-конъюнктивной нормальной форме является NP-полной при значении k
(1) не меньше 3
(2) больше 4
(3) меньше 3
Полином, ограничивающий вычислительную сложность псевдополиномиального алгоритма, зависит
(1) от функции длины
(2) от функции терминалов
(3) от функции разбиения
Остовное дерево - это
(1) совокупность вершин с максимальными пропускными способностями
(2) ациклический подграф данного графа, в который входят все вершины данного графа
(3) клика, имеющая наименьшую мощность
Произведение времени работы процессора на количество процессоров носит название
(1) общие затраты алгоритма
(2) мощность алгоритма
(3) вычислительная сложность алгоритма
Дуги, которые расположены против направления из истока в сток, называются
(1) обратными
(2) возвратными
(3) аддитивными
Слово в алгоритме упаковки имеет размер
(1)
O(lgT)
(2)
O(T)
(3)
O(2T) Если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила, машина Тьюринга называется
(1) корректирующей
(2) параметризированной
(3) детерминированной
Число входящих в вершинное покрытие вершин является его
(1) степенью
(2) объемом
(3) размером
Если в алгоритме присутствуют только операции сложения и вычитания, то длина результата каждой операции
(1) больше длины операндов в два раза
(2) меньше длины операций в два раза
(3) не более чем на одну единицу превышает длину операндов
Остовное дерево называется минимальным, если
(1) имеет минимальную длину
(2) имеет минимальное количество вершин
(3) имеет минимальное количество ребер
За какое время решается задача определения порядковых номеров в списке однопроцессорным алгоритмом?
(1)
O(nlogn)
(2)
O(logn)
(3)
O(n) Какое количество операций необходимо для построения увеличивающегося пути?
(1)
O(n)
(2)
O(log(n))
(3)
O(n2) В каком случае может применятся алгоритм упаковки?
(1) при нулевых директивных интервалах
(2) при одинаковых директивных интервалах
(3) при разных директивных интервалах
При любом входе машина Тьюринга должна
(1) переписывать все правила
(2) заменять символы алфавита
(3) останавливаться
Множество вершин является вершинным покрытием тогда и только тогда, когда его дополнение является
(1) терминальным графом
(2) независимым набором
(3) кликой
К элементам задачи о максимальном потоке в виде задачи распознавания свойств следует отнести
(1) сеть
(2) исток и сток
(3) пропускные способности
Метод ветвей и границ является
(1) конкатенационным
(2) рекурсивным
(3) комбинаторным
Сложность многопроцессорного алгоритма для определения порядковых номеров в списке составляет
(1)
O(log2n)
(2)
O(nlog2n)
(3)
O(2log2n) Какие из приведенных ниже значений могут быть элементами матрицы инцидентности?
(1)
0
(2)
-1
(3)
1 Поток в сети в алгоритме Танаева интерпретируется
(1) как процессорное время
(2) как пропускная способность
(3) как модуль работ
Рекурсивное подмножество множества всех возможных слов в алфавите формального языка носит название
(1) конкатенационный рекурсивный язык
(2) формальный рекурсивный язык
(3) терминальный рекурсивный язык
Простая цепь, проходящая через все вершины графа, называется
(1) когнитивной
(2) гамильтоновой
(3) темперной
Какие операции используются в алгоритме Форда-Фалкерсона?
(1) сложение
(2) вычитание
(3) умножение
Из приведенных ниже записей выделите этапы метода ветвей и границ:
(1) нахождение оценок
(2) скаляризация
(3) ветвление
Глубина корня двоичного дерева равна
(1) 0
(2) 1
(3) -1
Если поток в источник блокирован, то такой поток называется
(1) конечным
(2) разностным
(3) тупиковым
Если максимальный поток в алгоритме Танаева не насытил хотя бы одну выходную дугу, то
(1) нет выхода по мощности для работ
(2) допустимого расписания не существует
(3) такой алгоритм неверно составлен
По каким из приведенных ниже операций замкнуты рекурсивные языки?
(1) замыкание Клини
(2) конкатенация
(3) объединение
Если в графе степени любых двух несмежных вершин не меньше общего числа вершин в графе, то такой граф считается
(1) рекурсивным
(2) гамильтоновым
(3) вариативным
Задача является NP-полной в сильном смысле, если
(1) она принадлежит классу
NP
(2) существует подзадача для этой задачи, принадлежащая
NPC
(3) вершинное покрытие данной в задаче сети составляется псевдополиномиальным алгоритмом
Если при решении задачи минимизации методом ветвей и границ нижняя граница для подобласти
A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то
(1) подобласть
A может быть исключена из дальнейшего рассмотрения
(2) подобласть
B не рассматривается для потенциального решения
(3) метод ветвей и границ не может быть реализован
Сложность однопроцессорного алгоритма вычисления глубины вершины в двоичном дереве с количеством вершин n составляет
(1)
O(1)
(2)
O(n)
(3)
O(logn) Величина максимального потока определяется
(1) самым широким местом в сети
(2) самым узким местом в сети
(3) любым местом в сети
Чтобы полностью определить допустимое расписание в алгоритме Танаева с помощью алгоритма Карзанова нужно
(1)
O(lgn) операций
(2)
O(2n) операций
(3)
O(n3) операций Рекурсивно перечислимое подмножество множества всевозможных слов над алфавитом языка представляет собой
(1) рекурсивно распознаваемый формальный язык
(2) модульно распознаваемый формальный язык
(3) вариативно распознаваемый формальный язык
Класс сложности
co-NP определяется
(1) для одного языка
(2) для двух языков
(3) для множества языков
К NP-полным в сильном смысле задачам следует отнести
(1) задачу многопроцессорного расписания
(2) задачу потоковой сводимости в графе
(3) задачу линеаризации вершинных покрытий
При многопроцессорном расписании в фиксированный момент времени один процессор может выполнять
(1) только одну работу
(2) две и более работ
(3) множество работ
Если d - максимальная высота дерева леса, то многопроцессорный алгоритм определения корня для вершины двоичного леса имеет сложность
(1)
O(d)
(2)
O(dlog2d)
(3)
O(log2d) Если сток является помеченным, то
(1) существует увеличивающийся путь
(2) разрез является максимальным
(3) алгоритм Форда-Фалкерсона является зацикленным
В двоичном дереве с n вершинами вершины с номерами
[n/2]+1… n называются
(1) контейнерами
(2) листьями
(3) потомками
Сложность функции в классе
P, вычисляемой некоторой машиной Тьюринга, зависит
(1) от длины слова
(2) от типа алфавита
(3) от модуля считывания
На пересечении классов
NP и co-NP лежит
(1) класс
P
(2) класс
NC
(3) класс
RNP Из полиномиальной сводимости для задач распознавания свойств следует
(1) сводимость по Тьюрингу
(2) комплексная сводимость
(3) вариативная сводимость
Аналог задачи многопроцессорного расписания в виде задачи распознавания свойств является
(1) NP-полной задачей
(2) NP-однозначной задачей
(3) NP-вариативной задаче
Однопроцессорный алгоритм определения максимального элемента n-мерного массива имеет вычислительную сложность
(1)
O(logn)
(2)
O(n+1)
(3)
O(n) Какое количество операций необходимо при замене потока в алгоритме Карзанова?
(1)
O(m)
(2)
O(m/2)
(3)
O(2m2-1) Двоичное дерево, в котором значение в любой вершине больше (меньше), чем значения ее потомков, носит название
(1) стек
(2) куча
(3) массив
Всякую задачу, принадлежащую
NP, можно решить
(1) за линейное время
(2) за экспоненциальное время
(3) за логарифмическое время
Сколько общих элементов имеют между собой классы
co-NPC и NP?
(1) 1
(2) множество
(3) ни одного
Множество NP-трудных задач обозначается
(1)
NPC
(2)
NPH
(3)
NPX При решении задачи многопроцессорного расписания для m процессоров с помощью метода ветвей и границ количество вершин первого уровня дерева поиска может достигать
(1)
m
(2)
m-1
(3)
m+1 За какое время, имея
n процессоров, можно сделать двусторонний список из одностороннего?
(1)
O(1)
(2)
O(n)
(3)
O(logn) На каждом шагу алгоритма Карзанова количество частично насыщенных дуг ограничено значением
(1)
m
(2)
2n2
(3)
3mn Для создания кучи из неупорядоченного массива входных данных необходимо
(1)
O(n) операций
(2)
O(nlogn) операций
(3)
O(2n) операций Определение факта, принадлежит ли данное слово языку, носит название
(1) задача распознавания
(2) задача включения
(3) задача принадлежности
Подмножество вершин графа, такое, что между каждой парой вершин этого подмножества существует ребро и, кроме того, это подмножество не принадлежит никакому большому подмножеству с тем же свойством, носит название
(1) контейнер
(2) клика
(3) пробой
Если задача П сводится по Тьюрингу к оптимизационной, то задача П является
(1) NP-трудной
(2) NP-легкой
(3) NP-маркированной
Какими из приведенных ниже свойств обладает вероятность?
(1) вероятность события больше или равна нулю
(2) вероятность в пустом множестве равна 1
(3) вероятность объединения событий равна сумме их вероятностей
При эффективной параллельной обработке префиксов из каждой группы элементов, за которую отвечает процессор, исключается
(1) один элемент
(2) не менее двух элементов
(3) половина элементов, округленная в меньшую сторону
Если количество дуг в потоке выражается значением
O(n2)), алгоритм Карзанова занимает времени
(1)
O(n)
(2)
O(n2)
(3)
O(n3) К недостаткам пирамидальной сортировки следует отнести
(1) сложность реализации
(2) неустойчивость
(3) плохое сочетание с кэшированием
Из приведенных ниже областей выберите те, в которых реализованы NP-полные задачи:
(1) теория расписаний
(2) математическое программирование
(3) теория чисел
Размер клики определяется
(1) степенью полуисходов в графе
(2) количеством вершин в ней
(3) числом проходов по вершинному покрытию
Существует ли полиноминально точный алгоритм решения оптимизационной задачи многопроцессорного расписания?
(1) да, существует
(2) нет, не существует
(3) только когда количество работ ограничено сверху константой
В задаче о вершинном покрытии необходимо найти
(1) минимальное вершинное покрытие
(2) максимальное вершинное покрытие
(3) нулевое вершинное покрытие
К моделям многопроцессорных систем следует отнести
(1)
EREW
(2)
ERSW
(3)
ESWR Граф, в котором дуги имеют ориентацию, носит название
(1) конечный
(2) структурный
(3) ориентированный
Директивный интервал в многопроцессорном расписании является
(1) временным
(2) векторным
(3) скалярным
К словам алфавита в задаче распознавания свойств следует от нести
(1) "да"
(2) 0
(3) ,
Какие из приведенных ниже записей соответствуют NP-полным задачам?
(1) Гамильтонов цикл
(2) вершинное покрытие
(3) клика
Если в индивидуальной задаче нет чисел, то функция максимума для каждой задачи полагается равной
(1)
0
(2)
1
(3) бесконечности
Какое количество раз гамильтонов цикл проходит через каждую вершину сети, если количество узлов равно n?
(1)
n-1
(2)
n
(3)
1 Многопроцессорная модель с исключающим чтением и одновременной записью называется
(1)
ERCW
(2)
CRCW
(3)
EWRW Что представляет собой поток в сети?
(1) функцию
(2) матрицу
(3) симплекс
В многопроцессорном расписании для каждой работы следует указывать
(1) номер процессора
(2) тип данных
(3) интервал выполнения
К составляющим частям машины Тьюринга следует отнести
(1) начальное состояние
(2) конечное состояние
(3) конечное состояние с неизвестным ответом
Какие операции применяются в формулах в задаче выполнимости?
(1) исключающее "или"
(2) "не"
(3) "или"
От каких из приведенных ниже элементов зависит задача с числовыми параметрами?
(1) от функции максимума
(2) от полинома длины
(3) ни от функции максимума, ни от полинома длины
Пусть граф имеет 100 вершин. Каким должно быть количество ребер, чтобы граф был деревом?
(1) 100
(2) 101
(3) 99
Какая многопроцессорная модель является самой удобной с точки зрения пользователя?
(1)
EREW
(2)
ERCW
(3)
CRCW Разбиение потока на две части носит название
(1) вариация
(2) разрез
(3) терминация
Расписание, при котором каждая работа получает в точности определенное время процессора (длительность), и выполняется в директивном интервале, носит название
(1) вариативное
(2) идеальное
(3) допустимое
Имитация других исполнителей машиной Тьюринга осуществляется с помощью заданий
(1) конечного алфавита
(2) модуля сдвига параметров
(3) правил перехода
Задача выполнимости булевых формул в 2-конъюнктивной нормальной форме имеет
(1) логарифмическое решение
(2) экспоненциальное решение
(3) полиномиальное решение
От каких из приведенных ниже функций зависит полином, ограничивающий вычислительную сложность псевдополиномиального алгоритма?
(1) функция возврата
(2) функция максимума
(3) функция связности
Каково количество компонент связности в остовном дереве графа, если в графе их
n?
(1)
n-1
(2)
n
(3)
n+1 Общие затраты алгоритма в многопроцессорной системе представляют собой
(1) общее количество итераций цикла на каждом процессоре
(2) максимальную пропускную способность процессоров
(3) произведение времени работы процессора на количество процессоров
Сумма пропускных способностей рёбер разреза называется
(1) объемом разреза
(2) маркировкой разреза
(3) величиной разреза
Количество операций алгоритма упаковки оценивается значением
(1)
O(n)
(2)
O(logn)
(3)
O(n2) Если существует пара (ленточный символ - состояние), для которой существует две и более команд, такая машина Тьюринга называется
(1) недетерминированной
(2) маркированной
(3) вариативной
Каков размер вершинного покрытия с 10 вершинами?
(1)
10
(2)
log10
(3)
210-1 От выбора каких функций зависит псевдополиномиальность алгоритма?
(1) функции максимума
(2) функции длины
(3) от выбора функций псевдополиномиальность алгоритма не зависит
Метод ветвей и границ используется
(1) только для точного поиска решений
(2) только для приближенного поиска решений
(3) как для точного, так и для приближенного поиска решений
Чему равны общие затраты в однопроцессорном алгоритме определения порядковых номеров в списке, если вычислительная сложность определяеся величиной
O(n)?
(1)
O(1)
(2)
O(n)
(3)
O(logn) Конечное число операций алгоритма Форда-Фалкерсона выражается значением
(1)
O(nmU)
(2)
O(nlog(m)U)
(3)
O(Umlog(n)) Какие узлы присутствуют в сети при использовании алгоритма Танаева?
(1) узлы-маркеры
(2) узлы-интервалы
(3) узлы-коннекторы
Тип формального языка, называемый разрешимым по Тьюрингу, носит название
(1) рекурсивный язык
(2) формализованный язык
(3) детерминантный язык
Граф с n вершинами имеет вершинное покрытие размера k тогда и только тогда, когда данный граф имеет независимый набор размера
(1)
nlogk
(2)
n-k
(3)
2n-k2 При решении задачи о максимальном потоке с помощью псевдополиномиального алгоритма в качестве функции максимума берется максимальное значение
(1) суммы индексов вершин и пропускных способностей
(2) пропускной способности и числа, ограничивающего максимальный поток
(3) величины клики и вершинного покрытия
Метод ветвей и границ основан
(1) на поиске минимума и максимума функции на множестве допустимых значений
(2) на определении связных ребер разных классов соответствия
(3) на составлении матрицы инцидентности по принципу неполного вхождения ребер
Общие затраты в многопроцессорном алгоритме для определения порядковых номеров в списке определяются величиной
(1)
O(log2n)
(2)
O(n)
(3)
O(nlog2n) Какое количество памяти необходимо для работы алгоритма Форда-Фалкерсона?
(1)
O(n2)
(2)
O(n2 log2(U))
(3)
O(n2U) Пропускные способности входящих в сток дуг в сети в алгоритме Танаева равны
(1) модулю возврата действия
(2) коэффициенту семантической нагрузки
(3) процессорному времени на одну работу
Формальный язык, для которого существует машина Тьюринга, которая останавливается на любой входной цепочке и допускает ее тогда и только тогда, когда она принадлежит языку, является
(1) ковалентным
(2) вариативным
(3) рекурсивным
Гамильтонов путь, начальная и конечная вершины которого совпадают, называется
(1) гамильтоновым циклом
(2) гамильтоновым разрезом
(3) гамильтоновым перебором
Количество операций сложения и вычитания в алгоритме Форда-Фалкерсона составляет
(1)
O(lognm)
(2)
O(nlogm)
(3)
O(nmU) Разбиение области допустимых решений на подобласти меньших размеров в методе ветвей и границ представляет собой
(1) процедуру детерминации
(2) процедуру полиномизации
(3) процедуру ветвления
Глубина вершин двоичного дерева, у которых непосредственным предком является корень, составляет
(1) 0
(2) 1
(3) 2
На каждой итерации нахождения тупикового потока сети выполняется
(1) балансирование
(2) конвергенция
(3) достройка
Какой алгоритм необходимо применить к сети в алгоритме Танаева, если все выходные дуги насыщены?
(1) алгоритм симплекса
(2) алгоритм упаковки
(3) алгоритм Мейера
Из приведенных ниже операций выделите те, по которым рекурсивные языки замкнуты:
(1) пересечение
(2) дополнение
(3) разность
Граф является гамильтоновым тогда и только тогда, когда его замыкание представляет собой
(1) гамильтонов граф
(2) остовный граф
(3) планарный граф
Любая NP-полная задача без числовых параметров является
(1) NP-завершенной
(2) NP-зависимой
(3) NP-полной в сильном смысле
Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является
(1) минимумом функции
(2) максимумом функции
(3) нулем функции
Каковы общие затраты однопроцессорного алгоритма вычисления глубины вершины в двоичном дереве с количеством вершин
n?
(1)
O(n-1)
(2)
O(n)
(3)
O(nlogn) Алгоритм Форда-Фалкерсона может работать бесконечно, если величина пропускной способности
(1) натуральное число
(2) иррациональное число
(3) отрицательное число
Чтобы полностью определить допустимое расписание в алгоритме Танаева с помощью алгоритма упаковки нужно
(1)
O(lgn) операций
(2)
O(n) операций
(3)
O(n2) операций Если язык распознаваем некоторой полиномиальной машиной Тьюринга, то он называется
(1) полиномиально распознаваемым
(2) полиномиально конкретизированным
(3) полиномиально структурированным
Если
NP не равно co-NP, то любая задача, которая лежит и в классе NP и в классе co-NP
(1) является NP-полной
(2) не может быть NP-полной
(3) является NP-тривиальной
К элементам входа для задачи РМПС следует отнести
(1) задачи
(2) директивный срок
(3) длительности
В фиксированный момент времени при многопроцессорном расписании одна работа выполняется
(1) только одним процессором
(2) двумя или более процессорами
(3) множеством процессоров
В многопроцессорном алгоритме определения корня для вершины двоичного леса количество вершин, для которых определяется корень, на каждой итерации
(1) уменьшается на единицу
(2) увеличивается вдвое
(3) остается неизменным
Построение начального потока алгоритма Карзанова занимает времени
(1)
O(m)
(2)
O(2m)
(3)
O(log(m)) В двоичном дереве левого и правого потомка
(1) имеет любая вершина
(2) не может иметь ни одна вершина
(3) имеет любая вершина, кроме листа
Языки, для которых существуют распознающие их предикаты класса
P, следует отнести
(1) к классу
NPC
(2) к классу
P
(3) к классу
PP К подклассам эквивалентности класса
NP следует отнести
(1)
NPC
(2)
SP
(3)
PP Если существует NP-полная задача
П1, которая сводится по Тьюрингу к задаче П2, то задача П2 является
(1) NP-трудной
(2) NP-легкой
(3) NP-сводимой
Задача многопроцессорного расписания является
(1) NP-зависимой
(2) NP-трудной
(3) NP-легкой
Многопроцессорный алгоритм определения максимального элемента n-мерного массива для
n2 процессоров имеет вычислительную сложность
(1)
O(n)
(2)
O(nlogn)
(3)
O(logn) Какое количество раз обрабатывается насыщенная дуга при нахождении тупикового потока?
(1)
1
(2)
2
(3)
m-1 Высота кучи определяется высотой
(1) листов
(2) маркеров
(3) корневого узла
Если классы
P и NP равны, то любую задачу из класса NP можно будет решить
(1) за
O(1) времени
(2) за полиномиальное время
(3) за экспоненциальное время
В каком классе лежит задача линейного программирования?
(1)
co-NPE
(2)
RNP
(3)
P Множество
NPH определяет
(1) NP-трудные задачи
(2) NP-разрешимые задачи
(3) NP-комплексные задачи
При решении задачи многопроцессорного расписания для m процессоров с помощью метода ветвей и границ количество вершин любого уровня дерева поиска не превышает числа
(1)
2m
(2)
2m-1
(3)
m Определите время, за которое можно сделать двусторонний список из одностороннего, имея процессоров, в
logn раз меньше, чем n?
(1)
O(1)
(2)
O(n-1)
(3)
O(logn) Для чего применяется алгоритм Карзанова?
(1) для нахождения максимального потока
(2) для нахождения максимального разреза
(3) для насыщения вершин
Извлечение элемента из кучи в худшем случае выполняется за время
(1)
O(2n-1)
(2)
O(n)
(3)
O(logn) К NP-полным задачам следует отнести
(1) задачу о выполнимости булевых формул
(2) задачу о вершинном покрытии
(3) задачу о клике
В неориентированном графе подмножество вершин, каждые две из которых соединены ребром графа, называется
(1) дуплексом
(2) симплексом
(3) кликой
При использовании приближенного алгоритма необходимо учитывать
(1) сложность
(2) необходимую память
(3) погрешность
Какая величина соответствует частоте появления события?
(1) вероятность
(2) параметричность
(3) рекурсивность
При эффективной параллельной обработке префиксов из каждой группы элементов, за которую отвечает процессор, нельзя извлекать элеемнты, которые находятся
(1) в начале группы
(2) в конце группы
(3) рядом
Какой алгоритм работает быстрее: Форда-Фалкерсона или Карзанова?
(1) Форда-Фалкерсона
(2) Карзанова
(3) одинаково
К достоинствам алгоритма пирамидальной сортировки следует отнести
(1) наличие доказанной оценки худшего случая
O(logn)
(2) всего
O(1) дополнительной памяти в специфических случаях
(3) хорошее сочетание с подкачкой памяти
Какое количество литералов применяется в задаче 3-выполнимости?
(1) не менее 2
(2) 3
(3) более 4
Необходимым и достаточным условием для существования клики размера
k является наличие независимого множества в дополнении графа, размера не менее
(1)
k-1
(2)
k
(3)
2k Для приближенного решения оптимизационной задачи многопроцессорного расписания используют
(1) эвристические алгоритмы
(2) муравьиные алгоритмы
(3) генетические алгоритмы