Алгоритмы и модели вычислений - ответы
Количество вопросов - 251
Двоичное дерево, в котором значение в любой вершине больше (меньше), чем значения ее потомков, носит название
Балансирование при нахождении тупикового потока производится на дефицитных вершинах
На пересечении классов NP и co-NP лежит
Задача выполнимости булевых формул в k-конъюнктивной нормальной форме является NP-полной при значении k
Если в задаче нет полинома длины, который сверху ограничивал функцию максимума, то такая задача называется
При решении задачи многопроцессорного расписания для m процессоров с помощью метода ветвей и границ количество вершин первого уровня дерева поиска может достигать
Граф с n вершинами имеет вершинное покрытие размера k тогда и только тогда, когда данный граф имеет независимый набор размера
Для того, чтобы граф считался сетью, среди его вершин следует выделить
Языки, для которых существуют распознающие их предикаты класса P, следует отнести
Сумма длин ребер остовного дерева носит название
Класс дополнений языков из NP носит название
Если существует пара (ленточный символ - состояние), для которой существует две и более команд, такая машина Тьюринга называется
Дуги, которые расположены против направления из истока в сток, называются
Функция максимума определена на множестве
Пусть p - число вершин в данном графе. Если степень каждой вершины не меньше, чем p/2, то граф является
Гамильтонов цикл - это
Из приведенных ниже областей выберите те, в которых реализованы NP-полные задачи:
При использовании многопроцессорного алгоритма для определения порядковых номеров в списке, количество элементов с нулевыми указателями на каждой итерации
В оптимизационной задаче о клике необходимо найти в графе
К словам алфавита в задаче распознавания свойств следует от нести
Однопроцессорный алгоритм определения максимального элемента n-мерного массива имеет вычислительную сложность
Произведение времени работы процессора на количество процессоров носит название
При использовании приближенного алгоритма необходимо учитывать
Каковы общие затраты однопроцессорного алгоритма вычисления глубины вершины в двоичном дереве с количеством вершин n?
Прерывания и переключения в многопроцессорном расписании
Какое количество раз обрабатывается насыщенная дуга при нахождении тупикового потока?
Работы при многопроцессорном расписании выполняются
Оптимизационная задача о вершинном покрытии является
Метод ветвей и границ основан
Какие из приведенных ниже процедур используются в методе ветвей и границ?
Граф, в котором дуги имеют ориентацию, носит название
Граф, в котором выделен источник и сток, и каждой дуге назначена ее пропускная способность, носит название
Из приведенных ниже записей выделите условия существовавния потока в сети?
Поток максимален тогда и только тогда, когда в остаточной сети нет
Какие из приведенных ниже значений могут быть элементами матрицы инцидентности?
Если путь из вершины в сток содержит хотя бы одну насыщенную дугу, он называется
Построение начального потока алгоритма Карзанова занимает времени
Какое количество операций необходимо при замене потока в алгоритме Карзанова?
Количество обработок насыщенных дуг ограничено сверху значением
Какой алгоритм работает быстрее: Форда-Фалкерсона или Карзанова?
Из приведенных ниже характеристик выберите те, которые соответствуют работам в многопроцессорном расписании:
В многопроцессорном расписании для каждой работы следует указывать
Какое количество процессоров выполняет заданную работу в фиксированный момент времени в многопроцессорном расписании?
Слово в алгоритме упаковки имеет размер
В каком случае может применятся алгоритм упаковки?
Пропускные способности входящих в сток дуг в сети в алгоритме Танаева равны
Какой алгоритм необходимо применить к сети в алгоритме Танаева, если все выходные дуги насыщены?
Максимальное количество прерываний и переключений в алгоритме Танаева составляет
В двоичном дереве левого и правого потомка
Высота кучи определяется высотой
Высота кучи равна
К недостаткам пирамидальной сортировки следует отнести
Задача распознавания свойств характеризуется
Каким образом обозначается длина слова x в задаче распознавания свойств?
Имитация других исполнителей машиной Тьюринга осуществляется с помощью заданий
Если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила, машина Тьюринга называется
Для какого состояния машины Тьюринга не формируются правила
Рекурсивное подмножество множества всех возможных слов в алфавите формального языка носит название
По каким из приведенных ниже операций замкнуты рекурсивные языки?
Класс всех рекурсивно распознаваемых языков называется
Сложность функции в классе P, вычисляемой некоторой машиной Тьюринга, зависит
Всякую задачу, принадлежащую NP, можно решить
К NP-полным задачам следует отнести
Какое количество литералов применяется в задаче 3-выполнимости?
Какие из приведенных ниже записей соответствуют NP-полным задачам?
К элементам экземпляра задачи выполнимости следует отнести
Является ли задача выполнимости в нормальной конъюнктивной форме NP-полной?
Число входящих в вершинное покрытие вершин является его
Множество вершин является вершинным покрытием тогда и только тогда, когда его дополнение является
Простая цепь, проходящая через все вершины графа, называется
Граф является гамильтоновым тогда и только тогда, когда его замыкание представляет собой
К подклассам эквивалентности класса NP следует отнести
Пересекаются ли классы P и NPC?
Максимальный полный подграф графа называется
Размер клики определяется
Полином, ограничивающий вычислительную сложность псевдополиномиального алгоритма, зависит
Если количество операций и длины слов алгоритма ограничиваются полиномом от функции длины и функции максимума, то такой алгоритм будет
К элементам задачи о максимальном потоке в виде задачи распознавания свойств следует отнести
Какие операции используются в алгоритме Форда-Фалкерсона?
Любая NP-полная задача без числовых параметров является
К элементам входа для задачи РМПС следует отнести
Из полиномиальной сводимости для задач распознавания свойств следует
Множество NP-трудных задач обозначается
Если задача П сводится по Тьюрингу к оптимизационной, то задача П является
Существует ли полиноминально точный алгоритм решения оптимизационной задачи многопроцессорного расписания?
Цикл в сети, который проходит ровно один раз через каждый узел, носит название
Пусть граф имеет 100 вершин. Каким должно быть количество ребер, чтобы граф был деревом?
Остовное дерево - это
Остовное дерево называется минимальным, если
Метод ветвей и границ является
Из приведенных ниже записей выделите этапы метода ветвей и границ:
Если при решении задачи минимизации методом ветвей и границ нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то
В фиксированный момент времени при многопроцессорном расписании одна работа выполняется
Максимальная длительность работы на процессоре представляет собой
При решении задачи многопроцессорного расписания для m процессоров с помощью метода ветвей и границ количество вершин любого уровня дерева поиска не превышает числа
Какая величина соответствует частоте появления события?
В качестве модели многопроцессорной системы можно рассматривать
Многопроцессорная модель с исключающим чтением и исключающей записью носит название
В многопроцессорной модели, допускающей запись разнородной информации, записываться в ячейку будет информация от процессора
Чему равны общие затраты в однопроцессорном алгоритме определения порядковых номеров в списке, если вычислительная сложность определяеся величиной O(n)?
Общие затраты в многопроцессорном алгоритме для определения порядковых номеров в списке определяются величиной
К бинарным ассоциативным операциям следует отнести
Однопроцессорный алгоритм вычисления глубины вершины в двоичном дереве работает методом
Если d - максимальная высота дерева леса, то многопроцессорный алгоритм определения корня для вершины двоичного леса имеет сложность
Многопроцессорный алгоритм определения максимального элемента n-мерного массива для n2 процессоров имеет вычислительную сложность
Какова вычислительная сложность многопроцессорного алгоритма определения максимального элемента n-мерного массива для n процессоров?
При эффективной параллельной обработке префиксов из каждой группы элементов, за которую отвечает процессор, нельзя извлекать элеемнты, которые находятся
Какие операции применяются в формулах в задаче выполнимости?
Алгоритм, вычислительная сложность которого ограничена сверху полиномом от функции длины и функции максимума, носит название
Класс сложности co-NP определяется
Алгоритм Форда-Фалкерсона может работать бесконечно, если величина пропускной способности
Класс всех рекурсивных языков обозначается
При любом входе машина Тьюринга должна
Длина слов, с которым работает алгоритм Форда-Фалкерсона, выражается значением
Если задача лежит одновременно в классе NP и в классе co-NP, то она лежит
Алгоритм пирамидальной сортировки работает в худшем случае за время
Если существует NP-полная задача П1, которая сводится по Тьюрингу к задаче П2, то задача П2 является
Подмножество вершин графа, такое, что между каждой парой вершин этого подмножества существует ребро и, кроме того, это подмножество не принадлежит никакому большому подмножеству с тем же свойством, носит название
Разбиение области допустимых решений на подобласти меньших размеров в методе ветвей и границ представляет собой
Множество алгоритмов, время работы которых существенно зависит от размера входных данных, и которое уменьшается при предоставлении алгоритму некоторых дополнительных сведений, носит название
Из приведенных ниже операций выделите те, по которым рекурсивные языки замкнуты:
Задачу о максимальном потоке можно сформулировать в виде задачи
За какое время, имея n процессоров, можно сделать двусторонний список из одностороннего?
Если P не равно NP, то для оптимизационной задачи вершинного покрытия
В чем суть задачи о вершинном покрытии?
Класс всех NP-полных языков обозначается
Метод ветвей и границ используется
Общие затраты алгоритма в многопроцессорной системе представляют собой
Экземпляром задачи выполнимости является
Задача выполнимости булевых формул в 2-конъюнктивной нормальной форме имеет
Какое количество памяти необходимо для работы алгоритма Форда-Фалкерсона?
При выполнении работ переключения с одного процессора на другой
Длина интервала от нуля до момента завершения работы в задаче многопроцессорного расписания определяет
К NP-полным в сильном смысле задачам следует отнести
В худшем случае алгоритм Танаева выполняется
Директивный интервал в многопроцессорном расписании является
Какое количество ребер в дереве с n вершинами?
Число дуг в самом длинном пути, ведущем из вершины в лист, называется
Тип формального языка, называемый разрешимым по Тьюрингу, носит название
Какое количество работ выполняется одним процессором в фиксированный момент времени в многопроцессорном расписании?
Если классы P и NP равны, то любую задачу из класса NP можно будет решить
Пара узлов графа носит название
Конечное число операций алгоритма Форда-Фалкерсона выражается значением
Величина максимального потока определяется
Величина произвольного потока в сети ограничена сверху величиной
Какое количество операций занимает процедура расстановки меток в алгоритме Карзанова?
На каждом шагу алгоритма Карзанова количество частично насыщенных дуг ограничено значением
Расписание, при котором каждая работа получает в точности определенное время процессора (длительность), и выполняется в директивном интервале, носит название
Длительность каждой работы в многопроцессорном расписании должна быть равна
Какие узлы присутствуют в сети при использовании алгоритма Танаева?
Поток в сети в алгоритме Танаева интерпретируется
Чтобы полностью определить допустимое расписание в алгоритме Танаева с помощью алгоритма упаковки нужно
Извлечение элемента из кучи в худшем случае выполняется за время
Значения всех параметров в задаче распознавания свойств формируют
Рекурсивно перечислимое подмножество множества всевозможных слов над алфавитом языка представляет собой
К примерам алгоритмов класса P следует отнести
Определение факта, принадлежит ли данное слово языку, носит название
Из приведенных ниже записей выделите NP-полные задачи:
Множество вершин S графа такое, что у каждого ребра графа хотя бы один из концов входит в S, носит название
Гамильтонов путь, начальная и конечная вершины которого совпадают, называется
Если в графе степени любых двух несмежных вершин не меньше общего числа вершин в графе, то такой граф считается
Если NP не равно co-NP, то любая задача, которая лежит и в классе NP и в классе co-NP
В неориентированном графе подмножество вершин, каждые две из которых соединены ребром графа, называется
От каких из приведенных ниже элементов зависит задача с числовыми параметрами?
От выбора каких функций зависит псевдополиномиальность алгоритма?
Количество операций сложения и вычитания в алгоритме Форда-Фалкерсона составляет
Если числа, которые присутствуют в формулировке задачи, равномерно ограничены сверху константой, то на данном подмножестве индивидуальных задач псевдополиномиальный алгоритм становится
К NP-полным в сильном смысле задачам следует отнести
К оптимизационным задачам следует отнести
Множество NPH определяет
Связный граф, в котором n вершин и n-1 ребро, носит название
Каково количество компонент связности в остовном дереве графа, если в графе их n?
Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является
Множество всех возможных назначений работ на процессоры в дереве поиска представляется в виде
Если при раскрытии всех скобок и приведения подобных слагаемых в полиноме все слагаемые будут взаимоуничтожены, такой полином является
Обращение к ячейке памяти в параллельной машине с прямым доступом осуществляется
Многопроцессорная модель с исключающим чтением и одновременной записью называется
Какая многопроцессорная модель является самой удобной с точки зрения пользователя?
Если в многопроцессорной системе выполняется некоторый цикл, в котором процессоры одновременно выполняют операции, то в качестве времени работы этого цикла берется
За какое время решается задача определения порядковых номеров в списке однопроцессорным алгоритмом?
Глубина вершин двоичного дерева, у которых непосредственным предком является корень, составляет
В многопроцессорном алгоритме определения корня для вершины двоичного леса количество вершин, для которых определяется корень, на каждой итерации
При эффективной параллельной обработке префиксов из каждой группы элементов, за которую отвечает процессор, исключается
Какое количество операций необходимо для построения увеличивающегося пути?
Задача с числовыми параметрами - это задача, в которой
Количество операций алгоритма упаковки оценивается значением
Определите время, за которое можно сделать двусторонний список из одностороннего, имея процессоров, в logn раз меньше, чем n?
Для создания кучи из неупорядоченного массива входных данных необходимо
Правила перехода формируются с помощью
Сумма пропускных способностей рёбер разреза называется
Если поток в источник блокирован, то такой поток называется
Для чего применяется алгоритм Карзанова?
К характеристикам работы в многопроцессорном расписании следует отнести
Какие узлы применяются в сети при использовании алгоритма Танаева?
К достоинствам алгоритма пирамидальной сортировки следует отнести
Вопрос в задаче распознавания свойств ставится в виде
Формальный язык, для которого существует машина Тьюринга, которая останавливается на любой входной цепочке и допускает ее тогда и только тогда, когда она принадлежит языку, является
Каков размер вершинного покрытия с 10 вершинами?
Путь, содержащий каждую вершину графа ровно один раз, носит название
Функция максимума из множества индивидуальных задач принимает значение, равное
От каких из приведенных ниже функций зависит полином, ограничивающий вычислительную сложность псевдополиномиального алгоритма?
Если в алгоритме присутствуют только операции сложения и вычитания, то длина результата каждой операции
Если задача П1 сводится по Тьюрингу к задаче П2 из класса NP, то задача П1 является
Какое количество раз гамильтонов цикл проходит через каждую вершину сети, если количество узлов равно n?
Ациклический подграф данного графа, в который входят все вершины данного графа, носит название
При многопроцессорном расписании в фиксированный момент времени один процессор может выполнять
Аналог задачи многопроцессорного расписания в виде задачи распознавания свойств является
К моделям многопроцессорных систем следует отнести
Крайний справа элемент в списке при определении порядковых номеров многопроцессорными системами имеет номер
Сложность многопроцессорного алгоритма для определения порядковых номеров в списке составляет
Сложность однопроцессорного алгоритма вычисления глубины вершины в двоичном дереве с количеством вершин n составляет
Поток нулевой мощности носит название
К рекурсивным языкам следует отнести
В каком классе лежит задача линейного программирования?
Если максимальный поток в алгоритме Танаева не насытил хотя бы одну выходную дугу, то
Если сток является помеченным, то
Чтобы полностью определить допустимое расписание в алгоритме Танаева с помощью алгоритма Карзанова нужно
Что представляет собой поток в сети?
Если количество дуг в потоке выражается значением O(n2)), алгоритм Карзанова занимает времени
Какие из приведенных ниже элементов являются составляющими частями машины Тьюринга?
При решении задачи о максимальном потоке с помощью псевдополиномиального алгоритма в качестве функции максимума берется максимальное значение
Задача является NP-полной в сильном смысле, если
Оптимизационный вариант задачи о коммивояжере является
В задаче о вершинном покрытии необходимо найти
Задача многопроцессорного расписания является
Какими из приведенных ниже свойств обладает вероятность?
Какая многопроцессорная модель является самой легкой с точки зрения аппаратной поддержки?
На какой многопроцессорной модели реализовывается алгоритм определения корня для вершины двоичного леса?
Если d - максимальная высота дерева леса, n - количество вершин, то общие затраты многопроцессорного алгоритма определения корня для вершины двоичного леса составляют
Для эффективной параллельной обработки префиксов процессорами, количества p, двусторонний список разбивается
Если язык распознаваем некоторой полиномиальной машиной Тьюринга, то он называется
Задача из класса NP, к которой можно свести любую другую задачу из класса NP, называется
К NP-полным задачам следует отнести
Дуга, расположенная по ориентации потока, носит название
На каждой итерации нахождения тупикового потока сети выполняется
Какое количество памяти требуется для реализации алгоритма упаковки?
Сумма интервалов процессорного времени на выполнение работ в алгоритме Танаева представляет собой
Сколько общих элементов имеют между собой классы co-NPC и NP?
Сумма всех пропускных способностей дуг в сети носит название
Общим алгоритмическим методом для нахождения оптимальных решений различных задач оптимизации является
Из приведенных ниже записей выделите модели многопроцессорных систем:
Из приведенных ниже записей выделите составляющие части машины Тьюринга:
Глубина корня двоичного дерева равна
Множество дуг и узлов носит название
Необходимым и достаточным условием для существования клики размера k является наличие независимого множества в дополнении графа, размера не менее
Для приближенного решения оптимизационной задачи многопроцессорного расписания используют
Подобласти, образовавшиеся в результате процедуры ветвления в методе ветвей и границ, образуют дерево, называемое
Если в индивидуальной задаче нет чисел, то функция максимума для каждой задачи полагается равной
Разбиение потока на две части носит название
К составляющим частям машины Тьюринга следует отнести
В двоичном дереве с n вершинами вершины с номерами [n/2]+1… n называются