Автор статьи
Валерия
Эксперт по сдаче вступительных испытаний в ВУЗах
Какое количество памяти необходимо для работы алгоритма Форда-Фалкерсона?
- O(n2U)
- (Правильный ответ) O(n2 log2(U))
- O(n2)
Граф, в котором выделен источник и сток, и каждой дуге назначена ее пропускная способность, носит название
- контейнер
- орграф
- (Правильный ответ) сеть
Какое количество операций необходимо при замене потока в алгоритме Карзанова?
- O(2m2-1)
- (Правильный ответ) O(m)
- O(m/2)
Какое количество операций занимает процедура расстановки меток в алгоритме Карзанова?
- O(2m-1)
- O(m2)
- (Правильный ответ) O(m)
На каждой итерации нахождения тупикового потока сети выполняется
- (Правильный ответ) достройка
- конвергенция
- (Правильный ответ) балансирование
Для чего применяется алгоритм Карзанова?
- (Правильный ответ) для нахождения максимального потока
- для нахождения максимального разреза
- для насыщения вершин
Конечное число операций алгоритма Форда-Фалкерсона выражается значением
- O(nlog(m)U)
- O(Umlog(n))
- (Правильный ответ) O(nmU)
Построение начального потока алгоритма Карзанова занимает времени
- (Правильный ответ) O(m)
- O(log(m))
- O(2m)
Множество дуг и узлов носит название
- суппорт
- (Правильный ответ) граф
- терминал
В многопроцессорном расписании для каждой работы следует указывать
- (Правильный ответ) номер процессора
- (Правильный ответ) интервал выполнения
- тип данных
В каком случае может применятся алгоритм упаковки?
- при разных директивных интервалах
- (Правильный ответ) при одинаковых директивных интервалах
- при нулевых директивных интервалах
Какие узлы применяются в сети при использовании алгоритма Танаева?
- (Правильный ответ) узлы-интервалы
- узлы-терминалы
- (Правильный ответ) узлы-работы
В двоичном дереве левого и правого потомка
- (Правильный ответ) имеет любая вершина, кроме листа
- не может иметь ни одна вершина
- имеет любая вершина
Максимальное количество прерываний и переключений в алгоритме Танаева составляет
- m
- 2m
- (Правильный ответ) m-1
Чтобы полностью определить допустимое расписание в алгоритме Танаева с помощью алгоритма Карзанова нужно
- O(lgn) операций
- O(2n) операций
- (Правильный ответ) O(n3) операций
Тип формального языка, называемый разрешимым по Тьюрингу, носит название
- формализованный язык
- (Правильный ответ) рекурсивный язык
- детерминантный язык
Имитация других исполнителей машиной Тьюринга осуществляется с помощью заданий
- модуля сдвига параметров
- конечного алфавита
- (Правильный ответ) правил перехода
Задача из класса NP, к которой можно свести любую другую задачу из класса NP, называется
- NP-модифицированной
- (Правильный ответ) NP-полной
- NP-корректной
При любом входе машина Тьюринга должна
- переписывать все правила
- (Правильный ответ) останавливаться
- заменять символы алфавита
Рекурсивно перечислимое подмножество множества всевозможных слов над алфавитом языка представляет собой
- вариативно распознаваемый формальный язык
- модульно распознаваемый формальный язык
- (Правильный ответ) рекурсивно распознаваемый формальный язык
Каким образом обозначается длина слова x в задаче распознавания свойств?
- {x}
- (Правильный ответ) |x|
- [x]
Рекурсивное подмножество множества всех возможных слов в алфавите формального языка носит название
- конкатенационный рекурсивный язык
- (Правильный ответ) формальный рекурсивный язык
- терминальный рекурсивный язык
Класс всех рекурсивно распознаваемых языков называется
- (Правильный ответ) RE
- RG
- RF
Какие из приведенных ниже записей соответствуют NP-полным задачам?
- (Правильный ответ) вершинное покрытие
- (Правильный ответ) клика
- (Правильный ответ) Гамильтонов цикл
Класс сложности co-NP определяется
- для одного языка
- для двух языков
- (Правильный ответ) для множества языков
Задача выполнимости булевых формул в k-конъюнктивной нормальной форме является NP-полной при значении k
- меньше 3
- больше 4
- (Правильный ответ) не меньше 3
О сайте
Поделитесь в соцсетях: