Алгоритмы и модели вычислений - ответы

Количество вопросов - 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?

Связный граф, в котором n вершин и n-1 ребро, носит название

Множество NPH определяет

К оптимизационным задачам следует отнести

К NP-полным в сильном смысле задачам следует отнести

Если числа, которые присутствуют в формулировке задачи, равномерно ограничены сверху константой, то на данном подмножестве индивидуальных задач псевдополиномиальный алгоритм становится

Количество операций сложения и вычитания в алгоритме Форда-Фалкерсона составляет

От выбора каких функций зависит псевдополиномиальность алгоритма?

От каких из приведенных ниже элементов зависит задача с числовыми параметрами?

В неориентированном графе подмножество вершин, каждые две из которых соединены ребром графа, называется

Если NP не равно co-NP, то любая задача, которая лежит и в классе NP и в классе co-NP

Если в графе степени любых двух несмежных вершин не меньше общего числа вершин в графе, то такой граф считается

Гамильтонов путь, начальная и конечная вершины которого совпадают, называется

Множество вершин S графа такое, что у каждого ребра графа хотя бы один из концов входит в S, носит название

Из приведенных ниже записей выделите NP-полные задачи:

Определение факта, принадлежит ли данное слово языку, носит название

К примерам алгоритмов класса P следует отнести

Рекурсивно перечислимое подмножество множества всевозможных слов над алфавитом языка представляет собой

Значения всех параметров в задаче распознавания свойств формируют

Извлечение элемента из кучи в худшем случае выполняется за время

Чтобы полностью определить допустимое расписание в алгоритме Танаева с помощью алгоритма упаковки нужно

Поток в сети в алгоритме Танаева интерпретируется

Какие узлы присутствуют в сети при использовании алгоритма Танаева?

Длительность каждой работы в многопроцессорном расписании должна быть равна

Расписание, при котором каждая работа получает в точности определенное время процессора (длительность), и выполняется в директивном интервале, носит название

На каждом шагу алгоритма Карзанова количество частично насыщенных дуг ограничено значением

Какое количество операций занимает процедура расстановки меток в алгоритме Карзанова?

Величина произвольного потока в сети ограничена сверху величиной

Величина максимального потока определяется

Конечное число операций алгоритма Форда-Фалкерсона выражается значением

Пара узлов графа носит название

Если классы P и NP равны, то любую задачу из класса NP можно будет решить

Какое количество работ выполняется одним процессором в фиксированный момент времени в многопроцессорном расписании?

Тип формального языка, называемый разрешимым по Тьюрингу, носит название

Число дуг в самом длинном пути, ведущем из вершины в лист, называется

Какое количество ребер в дереве с n вершинами?

Директивный интервал в многопроцессорном расписании является

В худшем случае алгоритм Танаева выполняется

К NP-полным в сильном смысле задачам следует отнести

Длина интервала от нуля до момента завершения работы в задаче многопроцессорного расписания определяет

При выполнении работ переключения с одного процессора на другой

Какое количество памяти необходимо для работы алгоритма Форда-Фалкерсона?

Задача выполнимости булевых формул в 2-конъюнктивной нормальной форме имеет

Экземпляром задачи выполнимости является

Общие затраты алгоритма в многопроцессорной системе представляют собой

Метод ветвей и границ используется

Класс всех NP-полных языков обозначается

В чем суть задачи о вершинном покрытии?

Если P не равно NP, то для оптимизационной задачи вершинного покрытия

За какое время, имея 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 называются