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