Внимание ! Вопросы к тесту выложены исключительно в ознакомительных целях: количество вопросов может не совпадать с действительным, актуальность не поддерживается,- за решением теста Welcome to the cashier! Множество дуг и узлов носит название
терминал граф суппорт
Пара узлов графа носит название
ветвь константа дуга
Граф, в котором дуги имеют ориентацию, носит название
конечный структурный ориентированный
Что представляет собой поток в сети?
функцию симплекс матрицу
Граф, в котором выделен источник и сток, и каждой дуге назначена ее пропускная способность, носит название
сеть контейнер орграф
Для того, чтобы граф считался сетью, среди его вершин следует выделить
сток источник лидера группы
Поток нулевой мощности носит название
диссоциация конкатенация циркуляция
Разбиение потока на две части носит название
терминация разрез вариация
Сумма пропускных способностей рёбер разреза называется
Директивный интервал в многопроцессорном расписании является
временным скалярным векторным
В многопроцессорном расписании для каждой работы следует указывать
номер процессора тип данных интервал выполнения
При выполнении работ переключения с одного процессора на другой
невозможны допускаются приведут к выходу из строя оборудования
Прерывания и переключения в многопроцессорном расписании
являются необходимыми производятся согласно реверсному порядку не требуют временных издержек
Какое количество процессоров выполняет заданную работу в фиксированный момент времени в многопроцессорном расписании?
1 множество 2
Расписание, при котором каждая работа получает в точности определенное время процессора (длительность), и выполняется в директивном интервале, носит название
допустимое идеальное вариативное
Какое количество работ выполняется одним процессором в фиксированный момент времени в многопроцессорном расписании?
множество одна более трех
Количество операций алгоритма упаковки оценивается значением
O(n) O(n2) O(logn)
Слово в алгоритме упаковки имеет размер
O(lgT) O(T) O(2T)
Длительность каждой работы в многопроцессорном расписании должна быть равна
модулю работы величине директивного интервала коэффициенту связности
В каком случае может применятся алгоритм упаковки?
при нулевых директивных интервалах при одинаковых директивных интервалах при разных директивных интервалах
Какие узлы присутствуют в сети при использовании алгоритма Танаева?
узлы-интервалы узлы-маркеры узлы-коннекторы
Какое количество памяти требуется для реализации алгоритма упаковки?
O(nlgT) O(lgT) O(n)
Поток в сети в алгоритме Танаева интерпретируется
как процессорное время как пропускная способность как модуль работ
Пропускные способности входящих в сток дуг в сети в алгоритме Танаева равны
коэффициенту семантической нагрузки модулю возврата действия процессорному времени на одну работу
Какие узлы применяются в сети при использовании алгоритма Танаева?
узлы-работы узлы-интервалы узлы-терминалы
Сумма интервалов процессорного времени на выполнение работ в алгоритме Танаева представляет собой
суммарный коэффициент заполнения величину потока модуль мощности работ
Какой алгоритм необходимо применить к сети в алгоритме Танаева, если все выходные дуги насыщены?
функций корректировки соответствия параметров алгоритма, реализуемого машиной Тьюринга конечного алфавита символов
Если существует пара (ленточный символ - состояние), для которой существует две и более команд, такая машина Тьюринга называется
недетерминированной вариативной маркированной
Тип формального языка, называемый разрешимым по Тьюрингу, носит название
детерминантный язык формализованный язык рекурсивный язык
Для какого состояния машины Тьюринга не формируются правила
для заключительного для нулевого для начального
При любом входе машина Тьюринга должна
переписывать все правила останавливаться заменять символы алфавита
Класс всех рекурсивных языков обозначается
RL RF R
Рекурсивное подмножество множества всех возможных слов в алфавите формального языка носит название
формальный рекурсивный язык конкатенационный рекурсивный язык терминальный рекурсивный язык
Формальный язык, для которого существует машина Тьюринга, которая останавливается на любой входной цепочке и допускает ее тогда и только тогда, когда она принадлежит языку, является
рекурсивным ковалентным вариативным
Из приведенных ниже операций выделите те, по которым рекурсивные языки замкнуты:
Разность пересечение дополнение
По каким из приведенных ниже операций замкнуты рекурсивные языки?
замыкание Клини объединение конкатенация
К рекурсивным языкам следует отнести
контекстно-свободные языки контекстно-зависимые языки регулярные языки
Рекурсивно перечислимое подмножество множества всевозможных слов над алфавитом языка представляет собой
вариативно распознаваемый формальный язык модульно распознаваемый формальный язык рекурсивно распознаваемый формальный язык
Если язык распознаваем некоторой полиномиальной машиной Тьюринга, то он называется
Сложность функции в классе P, вычисляемой некоторой машиной Тьюринга, зависит
от длины слова от типа алфавита от модуля считывания
Если классы P и NP равны, то любую задачу из класса NP можно будет решить
за O(1) времени за полиномиальное время за экспоненциальное время
Множество алгоритмов, время работы которых существенно зависит от размера входных данных, и которое уменьшается при предоставлении алгоритму некоторых дополнительных сведений, носит название
класс PC класс DP класс NP
Всякую задачу, принадлежащую NP, можно решить
за логарифмическое время за экспоненциальное время за линейное время
К NP-полным задачам следует отнести
задачу о вершинном покрытии задачу о выполнимости булевых формул задачу о клике
Задача из класса NP, к которой можно свести любую другую задачу из класса NP, называется
NP-полной NP-корректной NP-модифицированной
Определение факта, принадлежит ли данное слово языку, носит название
задача распознавания задача включения задача принадлежности
Из приведенных ниже областей выберите те, в которых реализованы NP-полные задачи:
теория чисел теория расписаний математическое программирование
Класс всех NP-полных языков обозначается
NPC Co-P PN
Какое количество литералов применяется в задаче 3-выполнимости?
Пусть p - число вершин в данном графе. Если степень каждой вершины не меньше, чем p/2, то граф является
остовным параллельным гамильтоновым
Граф является гамильтоновым тогда и только тогда, когда его замыкание представляет собой
планарный граф гамильтонов граф остовный граф
Если в графе степени любых двух несмежных вершин не меньше общего числа вершин в графе, то такой граф считается
вариативным гамильтоновым рекурсивным
Если NP не равно co-NP, то любая задача, которая лежит и в классе NP и в классе co-NP
является NP-полной является NP-тривиальной не может быть NP-полной
Класс сложности co-NP определяется
для одного языка для двух языков для множества языков
Класс дополнений языков из NP носит название
a-NP co-NP re-NP
К подклассам эквивалентности класса NP следует отнести
SP PP NPC
На пересечении классов NP и co-NP лежит
класс NC класс RNP класс P
Если задача лежит одновременно в классе NP и в классе co-NP, то она лежит
в классе NCP в классе P в классе N
Сколько общих элементов имеют между собой классы co-NPC и NP?
ни одного 1 множество
Пересекаются ли классы P и NPC?
да, пересекаются нет, не пересекаются только в классе co-NP
В каком классе лежит задача линейного программирования?
RNP P co-NPE
Подмножество вершин графа, такое, что между каждой парой вершин этого подмножества существует ребро и, кроме того, это подмножество не принадлежит никакому большому подмножеству с тем же свойством, носит название
контейнер клика пробой
В неориентированном графе подмножество вершин, каждые две из которых соединены ребром графа, называется
дуплексом кликой симплексом
Максимальный полный подграф графа называется
проходом остовом кликой
Размер клики определяется
степенью полуисходов в графе количеством вершин в ней числом проходов по вершинному покрытию
В оптимизационной задаче о клике необходимо найти в графе
Необходимым и достаточным условием для существования клики размера k является наличие независимого множества в дополнении графа, размера не менее
2k k-1 k
Если в индивидуальной задаче нет чисел, то функция максимума для каждой задачи полагается равной
0 бесконечности 1
Функция максимума из множества индивидуальных задач принимает значение, равное
максимальному числу параллельных проходов по вершинному покрытию максимальному числу в задаче максимальной клике в графе
Внимание ! Вопросы к тесту выложены исключительно в ознакомительных целях: количество вопросов может не совпадать с действительным, актуальность не поддерживается,- за решением теста Welcome to the cashier! Функция максимума определена на множестве
индивидуальных задач задач с ответом "нет" задач с ответом "да"
Если в задаче нет полинома длины, который сверху ограничивал функцию максимума, то такая задача называется
задачей частичного возврата задачей с числовыми параметрами задачей максимальной эквивалентности
Задача с числовыми параметрами - это задача, в которой
нет полинома длины, который сверху ограничивал функцию максимума есть минимальное вершинное покрытие с нулевой вершиной максимальная клика совпадает по значениям с полиномом максимумов
От каких из приведенных ниже элементов зависит задача с числовыми параметрами?
от функции максимума ни от функции максимума, ни от полинома длины от полинома длины
Полином, ограничивающий вычислительную сложность псевдополиномиального алгоритма, зависит
от функции длины от функции терминалов от функции разбиения
Алгоритм, вычислительная сложность которого ограничена сверху полиномом от функции длины и функции максимума, носит название
От каких из приведенных ниже функций зависит полином, ограничивающий вычислительную сложность псевдополиномиального алгоритма?
функция возврата функция максимума функция связности
Если количество операций и длины слов алгоритма ограничиваются полиномом от функции длины и функции максимума, то такой алгоритм будет
жадным псевдополиномиальным возвратным
От выбора каких функций зависит псевдополиномиальность алгоритма?
от выбора функций псевдополиномиальность алгоритма не зависит функции максимума функции длины
Если в алгоритме присутствуют только операции сложения и вычитания, то длина результата каждой операции
больше длины операндов в два раза не более чем на одну единицу превышает длину операндов меньше длины операций в два раза
При решении задачи о максимальном потоке с помощью псевдополиномиального алгоритма в качестве функции максимума берется максимальное значение
суммы индексов вершин и пропускных способностей величины клики и вершинного покрытия пропускной способности и числа, ограничивающего максимальный поток
К элементам задачи о максимальном потоке в виде задачи распознавания свойств следует отнести Сеть исток и сток пропускные способности
Задачу о максимальном потоке можно сформулировать в виде задачи
пакетного моделирования увеличения проходимости распознавания свойств
Какие операции используются в алгоритме Форда-Фалкерсона?
вычитание умножение сложение
Сумма всех пропускных способностей дуг в сети носит название
величина клики величина вершинного покрытия величина потока
Количество операций сложения и вычитания в алгоритме Форда-Фалкерсона составляет
O(lognm) O(nlogm) O(nmU)
Задача является NP-полной в сильном смысле, если
существует подзадача для этой задачи, принадлежащая NPC вершинное покрытие данной в задаче сети составляется псевдополиномиальным алгоритмом она принадлежит классу NP
Любая NP-полная задача без числовых параметров является
NP-завершенной NP-полной в сильном смысле NP-зависимой
Если числа, которые присутствуют в формулировке задачи, равномерно ограничены сверху константой, то на данном подмножестве индивидуальных задач псевдополиномиальный алгоритм становится
равномерным полиномиальным терминальным
К NP-полным в сильном смысле задачам следует отнести
задачу терминального обобщения полиномов задачу конкатенации подмножеств задачу о коммивояжере
К NP-полным в сильном смысле задачам следует отнести
Если P не равно NP, то для оптимизационной задачи вершинного покрытия
не существует приближенного алгоритма решения соответствие классов NPH и NPC определяется с помощью сведения по Тьюрингу существует полиномиальный алгоритм решения
Оптимизационная задача о вершинном покрытии является
NP-неопределенной NP-трудной NP-легкой
Какое количество раз гамильтонов цикл проходит через каждую вершину сети, если количество узлов равно n?
1 n-1 n
Гамильтонов цикл - это
минимальный путь в сети от истока к стоку цикл, который проходит ровно один раз через каждый узел обратное вершинное покрытие
Цикл в сети, который проходит ровно один раз через каждый узел, носит название
эйлеров цикл гамильтонов цикл цикл Лагранжа
Какое количество ребер в дереве с n вершинами?
2n-1 n-1 n
Связный граф, в котором n вершин и n-1 ребро, носит название
остов дерево клика
Пусть граф имеет 100 вершин. Каким должно быть количество ребер, чтобы граф был деревом?
99 101 100
Ациклический подграф данного графа, в который входят все вершины данного графа, носит название
Каково количество компонент связности в остовном дереве графа, если в графе их n?
n-1 n+1 n
Остовное дерево - это
совокупность вершин с максимальными пропускными способностями клика, имеющая наименьшую мощность ациклический подграф данного графа, в который входят все вершины данного графа
Метод ветвей и границ используется
как для точного, так и для приближенного поиска решений только для приближенного поиска решений только для точного поиска решений
Сумма длин ребер остовного дерева носит название
мощность дерева длина дерева рекурсия дерева
Остовное дерево называется минимальным, если
имеет минимальное количество вершин имеет минимальную длину имеет минимальное количество ребер
Общим алгоритмическим методом для нахождения оптимальных решений различных задач оптимизации является
метод строк и столбцов метод ветвей и границ метод конечноразностных полиномов
Метод ветвей и границ является
конкатенационным комбинаторным рекурсивным
Из приведенных ниже записей выделите этапы метода ветвей и границ:
ветвление нахождение оценок скаляризация
Разбиение области допустимых решений на подобласти меньших размеров в методе ветвей и границ представляет собой
Какие из приведенных ниже процедур используются в методе ветвей и границ?
процедура ветвления процедура формирования рекурсивных циклов процедура векторизации
Если при решении задачи минимизации методом ветвей и границ нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то
подобласть B не рассматривается для потенциального решения метод ветвей и границ не может быть реализован подобласть A может быть исключена из дальнейшего рассмотрения
Подобласти, образовавшиеся в результате процедуры ветвления в методе ветвей и границ, образуют дерево, называемое
деревом поиска деревом выборки деревом связей
Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является
нулем функции минимумом функции максимумом функции
При многопроцессорном расписании в фиксированный момент времени один процессор может выполнять
только одну работу две и более работ множество работ
В фиксированный момент времени при многопроцессорном расписании одна работа выполняется
двумя или более процессорами множеством процессоров только одним процессором
Работы при многопроцессорном расписании выполняются
с рекурсиями без прерываний без переключений
Задача многопроцессорного расписания является
NP-зависимой NP-трудной NP-легкой
Максимальная длительность работы на процессоре представляет собой
длину процессорного расписания модуль сложности процессорного расписания коэффициент быстродействия
Аналог задачи многопроцессорного расписания в виде задачи распознавания свойств является
NP-вариативной задаче NP-однозначной задачей NP-полной задачей
При решении задачи многопроцессорного расписания для m процессоров с помощью метода ветвей и границ количество вершин первого уровня дерева поиска может достигать
m-1 m m+1
Множество всех возможных назначений работ на процессоры в дереве поиска представляется в виде
листьев узлов корня
При решении задачи многопроцессорного расписания для m процессоров с помощью метода ветвей и границ количество вершин любого уровня дерева поиска не превышает числа
m 2m-1 2m
Какая величина соответствует частоте появления события?
вероятность рекурсивность параметричность
Какими из приведенных ниже свойств обладает вероятность?
вероятность в пустом множестве равна 1 вероятность объединения событий равна сумме их вероятностей вероятность события больше или равна нулю
Если при раскрытии всех скобок и приведения подобных слагаемых в полиноме все слагаемые будут взаимоуничтожены, такой полином является
Обращение к ячейке памяти в параллельной машине с прямым доступом осуществляется
по времени исполнения по типу данных по адресу
В качестве модели многопроцессорной системы можно рассматривать
логарифмический дифференциатор с выбором меток генетический осциллятор с коррекцией входа параллельную машину с прямым доступом
К моделям многопроцессорных систем следует отнести
ERSW ESWR EREW
Из приведенных ниже записей выделите модели многопроцессорных систем:
GRGW EREW CRCW
Многопроцессорная модель с исключающим чтением и исключающей записью носит название
CRWR EREW ASAD
Многопроцессорная модель с исключающим чтением и одновременной записью называется
EWRW ERCW CRCW
Какая многопроцессорная модель является самой легкой с точки зрения аппаратной поддержки?
CREW EREW CRCW
Какая многопроцессорная модель является самой удобной с точки зрения пользователя?
CRCW ERCW EREW
В многопроцессорной модели, допускающей запись разнородной информации, записываться в ячейку будет информация от процессора
с наименьшим номером с наименьшим откликом с наибольшим быстродействием
Произведение времени работы процессора на количество процессоров носит название
общие затраты алгоритма вычислительная сложность алгоритма мощность алгоритма
Если в многопроцессорной системе выполняется некоторый цикл, в котором процессоры одновременно выполняют операции, то в качестве времени работы этого цикла берется
количество итераций максимальное число петлевых вычислений степень полуисхода цикла
Общие затраты алгоритма в многопроцессорной системе представляют собой
общее количество итераций цикла на каждом процессоре максимальную пропускную способность процессоров произведение времени работы процессора на количество процессоров
За какое время решается задача определения порядковых номеров в списке однопроцессорным алгоритмом?
O(logn) O(n) O(nlogn)
Чему равны общие затраты в однопроцессорном алгоритме определения порядковых номеров в списке, если вычислительная сложность определяеся величиной O(n)?
O(logn) O(n) O(1)
Крайний справа элемент в списке при определении порядковых номеров многопроцессорными системами имеет номер
0 1 n
Общие затраты в многопроцессорном алгоритме для определения порядковых номеров в списке определяются величиной
O(nlog2n) O(log2n) O(n)
При использовании многопроцессорного алгоритма для определения порядковых номеров в списке, количество элементов с нулевыми указателями на каждой итерации
остается неизменным уменьшается на 1 увеличивается вдвое
Сложность многопроцессорного алгоритма для определения порядковых номеров в списке составляет
O(2log2n) O(nlog2n) O(log2n)
К бинарным ассоциативным операциям следует отнести
целочисленное деление умножение сложение
Глубина вершин двоичного дерева, у которых непосредственным предком является корень, составляет
0 1 2
Однопроцессорный алгоритм вычисления глубины вершины в двоичном дереве работает методом
Сложность однопроцессорного алгоритма вычисления глубины вершины в двоичном дереве с количеством вершин n составляет
O(1) O(logn) O(n)
Каковы общие затраты однопроцессорного алгоритма вычисления глубины вершины в двоичном дереве с количеством вершин n?
O(n-1) O(n) O(nlogn)
Если d - максимальная высота дерева леса, то многопроцессорный алгоритм определения корня для вершины двоичного леса имеет сложность
O(log2d) O(dlog2d) O(d)
На какой многопроцессорной модели реализовывается алгоритм определения корня для вершины двоичного леса?
CREW CRSW EREW
В многопроцессорном алгоритме определения корня для вершины двоичного леса количество вершин, для которых определяется корень, на каждой итерации
уменьшается на единицу остается неизменным увеличивается вдвое
Однопроцессорный алгоритм определения максимального элемента n-мерного массива имеет вычислительную сложность
O(n) O(n+1) O(logn)
Если d - максимальная высота дерева леса, n - количество вершин, то общие затраты многопроцессорного алгоритма определения корня для вершины двоичного леса составляют
O(dn) O(n+d-1) O(nlog2d)
За какое время, имея n процессоров, можно сделать двусторонний список из одностороннего?
O(1) O(logn) O(n)
Какова вычислительная сложность многопроцессорного алгоритма определения максимального элемента n-мерного массива для n процессоров?
O(n) O(1) O(logn)
Определите время, за которое можно сделать двусторонний список из одностороннего, имея процессоров, в logn раз меньше, чем n?
O(1) O(logn) O(n-1)
При эффективной параллельной обработке префиксов из каждой группы элементов, за которую отвечает процессор, исключается
половина элементов, округленная в меньшую сторону один элемент не менее двух элементов
При эффективной параллельной обработке префиксов из каждой группы элементов, за которую отвечает процессор, нельзя извлекать элеемнты, которые находятся
в начале группы рядом в конце группы
Для эффективной параллельной обработки префиксов процессорами, количества p, двусторонний список разбивается
на p групп на p-1 групп на p+1 групп
Задача выполнимости булевых формул в 2-конъюнктивной нормальной форме имеет
логарифмическое решение экспоненциальное решение полиномиальное решение
Вы можете обратится к нам напрямую, через:
По Skype: molodoyberkut По Telegram: @MolodoyBerkut По ICQ: 657089516