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

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

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

Список вопросов:

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