С.Ф. Тюрин, Ю.А. Аляев ДИСКРЕТНАЯ МАТЕМАТИКА ТЕСТ-ДРАЙВ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ И МАТЕМАТИЧЕСКОЙ ЛОГИКЕ

(3): додекаэдра (4): Лабиринта Минотавра

t11. Для полного графа без петель с 4 вершинами полный перебор решения задачи коммивояжера составляет

(1): 24 варианта (2): 4 варианта (3): 16 вариантов (4): 6 вариантов

t12. Для полного графа без петель с 4 вершинами дерево обхода вершин решения задачи коммивояжера составляет

(1): 24 варианта (2): 4 варианта (3): 16 вариантов (4): 6 вариантов

t13. Для полного графа без петель с n вершинами полный перебор решения задачи коммивояжера составляет … вариантов

(1): n!

(2): (n + 1)! (3): (n – 1)! (4): (2n)!

t14. Для полного графа без петель с n вершинами дерево обхода вершин решения задачи коммивояжера составляет … вариантов

(1): n!

(2): (n + 1)! (3): (3n)! (4): (n – 1)!

Уровень – сложный

t15. К гамильтоновым графам относится граф (1): Барака (2): Дирака

71

(3): Поста (4): Тьюринга

t16. К гамильтоновым графам относится граф

(1): Оре (2): Буля

(3): Моргана (4): Маркова

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

(1): p/2 (2): p (3): p/3 (4): 2p

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

(1): больше p (2): меньше 2p

(3): меньше p – 1 (4): меньше p

2.3. Экстремальные задачи, оптимизационные задачи

Уровень – легкий

t1. Экстремальная задача – это задача

(1): нахождения значения параметра в экстремальных условиях внешней среды

(2): отыскания экстремала с заданными свойствами (3): нахождения экстремала в экстремальных условиях внешней

среды (4): нахождения максимального или минимального значения не-

которого математического объекта

72

t2. Экстремальной не является задача

(1): минимизации переключательной функции (2): коммивояжера (3): анализа марковской цепи (4): о Ханойской башне

t3. Транспортная задача обеспечивает … товаров (1): минимизацию стоимости доставки (2): максимизацию стоимости доставки (3): минимизацию вероятности недоставки (4): максимизацию вероятности доставки

t4. Транспортная задача обеспечивает минимизацию (1): количества товаров (2): вероятности недоставки товаров в заданное время

(3): вероятности доставки товаров в заданное время (4): времени доставки товаров

t5. Решение транспортной задачи в терминах теории графов предполагает

(1): задание транспортной цепи (2): задание транспортных маршрутов

(3): устранение транспортных пробок (4): задание транспортной сети

t6. В транспортной сети находится (1): неполный поток (2): полный поток (3): полный исток (4): неполный сток

t7. Поток втранспортнойсети называется полным, если он… дугу (1): содержит полную (2): содержит насыщенную

73

(3): содержит неполную (4): не содержит пустую

t8. Дуга называется насыщенной, если поток в ней (1): меньше пропускной способности (2): больше пропускной способности (3): равен пропускной способности (4): не равен нулю

t9. Дуга называется ненасыщенной, если поток в ней (1): меньше пропускной способности (2): равен пропускной способности (3): больше пропускной способности (4): равен нулю

t10. В задачах дискретной оптимизации переменные принимают (1): целочисленные значения (2): только значения 0 или 1 (3): непрерывные значения

(4): только положительные значения

Уровень – средний

t11. Алгоритм нахождения максимального потока в транспортной сети – это алгоритм

(1): Эйлера – Гамильтона (2): Форда – Фалкерсона (3): Маркова – Ляпунова (4): Канторовича

t12. Алгоритм нахождения максимального потока в транспортной сети заключается в постепенном

(1): увеличении потока, пока он не станет максимальным (2): уменьшении потока (3): разрезании сети

(4): введении новых истоков, пока не будет найдет максимальный поток

74

t13. Разрез транспортной сети – это

(1): линия, разрывающая все пути от истока к данной вершине (2): линия, разрывающая все пути от данной вершины к стоку (3): получение из одной дуги двух (4): линия, разрывающая все пути от истока к стоку

t14. Минимальный разрез транспортной сети – это

(1): линия, разрывающая все пути от истока к стоку минимальной пропускной способности

(2): линия, разрывающая все пути от истока к данной вершине минимальной длины

(3): линия, разрывающая все пути от данной вершины к стоку минимальной стоимости

(4): получение из одной дуги дуги минимальной пропускной способности

t15. Максимальный поток в транспортной сети равен (1): минимальному разрезу (2): максимальному разрезу

(3): среднему значению потоков из всех разрезов (4): сумме потоков всех разрезов

Уровень – сложный

t16. Поток в транспортной сети называется полным, если

(1): каждый путь от истока к стоку содержит хотя бы одну ненасыщенную дугу

(2): каждый путь от истока к стоку содержит хотя бы одну насыщенную дугу

(3): все дуги насыщенны (4): все дуги ненасыщенны

t17. Построение паросочетаний с минимальной суммой весов – это экстремальная задача

(1): о свадьбах (2): коммивояжера

75

(3): о Ханойской башне (4): о назначениях

t18. Процесс увеличения потока в алгоритме нахождения максимального потока в транспортной сети состоит в разметке … возможно увеличение потока

(1): вершин индексами, указывающими путь, на котором не (2): дуг индексами, указывающими путь, на котором (3): вершин индексами, указывающими путь, на котором (4): дуг индексами, указывающими путь, на котором не

t19. Если хi – уже помеченная вершина при выполнении алгоритма Форда – Фалкерсона, то все непомеченные вершины, в которые идут ненасыщенные дуги из хi, помечаются индексом

(1): –i

(2): + (i – 1) (3): – (i + 1) (4): +i

t20. Если хi – уже помеченная вершина при выполнении алгоритма Форда – Фалкерсона, то все непомеченные вершины, из которых идут дуги в вершину хi, помечаются индексом

(1): +i (2): –i

(3): – (i – 1) (4): + (i + 1)

2.4. Комбинаторная оптимизация, метод ветвей и границ

Уровень – легкий

t1. Метод решения оптимизационной задачи путем анализа всех вариантов называется

(1): полный анализ (2): метод изящной силы

76

(3): полный перебор (4): жадный алгоритм

t2. Метод решения оптимизационной задачи путем анализа всех вариантов называется

(1): метод грубой силы (2): полный синтез (3): метод Парето (4): щедрый алгоритм

t3. Метод ветвей и границ – это метод решения задачи дискретной оптимизации

(1): с полным перебором вариантов (2): с полным перебором вариантов в виде дерева

(3): с полным перебором вариантов в виде граничного дерева (4): с отсевом подмножеств вариантов, явно не содержащих оп-

тимальных решений

t4. Метод ветвей и границ был предложен для решения задачи (1): целочисленного линейного программирования (2): линейного программирования (3): коммивояжера (4): о Ханойской башне

t5. Метод ветвей и границ включает (1): одну процедуру ветвления

(2): одну процедуру нахождения оценок (границ)

(3): три основных процедуры: ветвления, нахождения оценок (границ) и дробления

(4): две основных процедуры: ветвления и нахождения оценок (границ)

t6. Процедура ветвления состоит

(1): в разбиении области допустимых решений на области больших размеров

(2): уменьшенииразмерностизадачи до двух вариантов: n – 2, n – 1

77

(3): разбиении области допустимых решений на подобласти меньших размеров

(4): уменьшении размерности задачи до трех вариантов: n – 3, n – 2, n – 1

t7. Процедура нахождения оценок состоит в поиске … границ для оптимального значения на подобласти допустимых решений

(1): только верхних (2): верхних и нижних (3): только нижних (4): верхних и нижних

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

(1): жадным (2): нежадным (3): грубым (4): щедрым

t9. Оптимизационный алгоритм, сложность которого описывается полиномиальной функцией от размерности задачи, называется

(1): NP

(2): E

(3): P

(4): NP-полным

t10. Оптимизационный алгоритм, который реализуется путем случайного выбора варианта с полиномиальной проверкой найденного решения, называется

(1): P

(2): NP

(3): E

(4): NP-полным

78

t11. Основная проблема комбинаторной оптимизации заключается в поиске ответа на вопрос

(1): P = E?

(2): E = NP? (3): E = NP + P? (4): P = NP?

t12. Метод половинного разбиения – это частный случай (1): задачи коммивояжера (2): задачи о Ханойской башне (3): метода ветвей и границ (4): задачи о свадьбах

Уровень – средний

t13. При половинном разбиении n блоков, если остаток r,

то …, где m – степень числа 2 (1): n + r = 2m

(2): n + r = 2m + 1 (3): n – r = 2m (4): n – r =2m + 1

t14. При половинном разбиении n блоков, если остаток r, m – степень числа 2, минимальное число проверок равно

(1): m (2): m + 1 (3): n (4): r

t15. При половинном разбиении n блоков, если остаток r, m – степень числа 2, среднее число проверок равно

(1): m + 2 r/n (2): m + r/n (3): r + m/n (4): m – 2r/n

79

t16. При половинном разбиении n блоков, если остаток r, m – степень числа 2, максимальное число проверок равно

(1): m + 1 (2): m (3): n – m (4): r – m

t17. Генетический алгоритм оптимизации не включает (1): создание начальной популяции (2): селекцию (3): скрещивание и/или мутацию (4): стагнацию

t18. Парето-оптимизация заключается в нахождении (1): границы Парето в виде сравнимых вариантов (2): множества Парето всех возможных вариантов (3): границы Парето в виде несравнимых вариантов (4): тождества Парето

Уровень – сложный

t19. Для задачи минимизации по методу ветвей и границ, если нижняя границы области А больше, чем верхняя граница ранее рассмотренной области В, то

(1): В может быть исключена из рассмотрения (2): А может быть исключена из рассмотрения (3): найдено решение и процесс закончен (4): А и В могут быть исключены из рассмотрения

t20. Для задачи минимизации по методу ветвей и границ, если нижняя граница узла дерева ветвления совпадает с верхней, то

(1): это значение является минимумом (2): узел исключается из рассмотрения (3): решение не найдено

(4): этот узел подлежит дальнейшему ветвлению

80