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

Упражнение 1:

Номер 1

Множество дуг и узлов носит название

Ответ:

(1) суппорт

(2) граф

(3) терминал

Номер 2

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

Ответ:

(1) дуга

(2) ветвь

(3) константа

Номер 3

Граф, в котором дуги имеют ориентацию, носит название

Ответ:

(1) конечный

(2) структурный

(3) ориентированный

Упражнение 2:

Номер 1

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

Ответ:

(1) контейнер

(2) сеть

(3) орграф

Номер 2

Для того, чтобы граф считался сетью, среди его вершин следует выделить

Ответ:

(1) источник

(2) лидера группы

(3) сток

Номер 3

Что представляет собой поток в сети?

Ответ:

(1) функцию

(2) матрицу

(3) симплекс

Упражнение 3:

Номер 1

Из приведенных ниже записей выделите условия существовавния потока в сети?

Ответ:

(1) неотрицательность

(2) баланс

(3) допустимость

Номер 2

Поток нулевой мощности носит название

Ответ:

(1) циркуляция

(2) конкатенация

(3) диссоциация

Номер 3

Разбиение потока на две части носит название

Ответ:

(1) вариация

(2) разрез

(3) терминация

Упражнение 4:

Номер 1

Дуга, расположенная по ориентации потока, носит название

Ответ:

(1) реверсная

(2) стандартная

(3) прямая

Номер 2

Дуги, которые расположены против направления из истока в сток, называются

Ответ:

(1) обратными

(2) возвратными

(3) аддитивными

Номер 3

Сумма пропускных способностей рёбер разреза называется

Ответ:

(1) объемом разреза

(2) маркировкой разреза

(3) величиной разреза

Упражнение 5:

Номер 1

Поток максимален тогда и только тогда, когда в остаточной сети нет

Ответ:

(1) петель

(2) кратных дуг

(3) увеличивающего пути

Номер 2

Какое количество операций необходимо для построения увеличивающегося пути?

Ответ:

(1) O(n)

(2) O(log(n))

(3) O(n²)

Номер 3

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

Ответ:

(1) O(nmU)

(2) O(nlog(m)U)

(3) O(Umlog(n))

Упражнение 6:

Номер 1

Длина слов, с которым работает алгоритм Форда-Фалкерсона, выражается значением

Ответ:

(1) O(lg(U))

(2) O(log₂(U))

(3) O(ln(U))

Номер 2

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

Ответ:

(1) 0

(2) -1

(3) 1

Номер 3

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

Ответ:

(1) O(n²)

(2) O(n² log₂(U))

(3) O(n²U)

Упражнение 7:

Номер 1

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

Ответ:

(1) возвратным

(2) блокированным

(3) конструктивным

Номер 2

Если поток в источник блокирован, то такой поток называется

Ответ:

(1) конечным

(2) разностным

(3) тупиковым

Номер 3

На каждой итерации нахождения тупикового потока сети выполняется

Ответ:

(1) балансирование

(2) конвергенция

(3) достройка

Упражнение 8:

Номер 1

Балансирование при нахождении тупикового потока производится на дефицитных вершинах

Ответ:

(1) максимального ранга

(2) минимального ранга

(3) нулевого ранга

Номер 2

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

Ответ:

(1) самым широким местом в сети

(2) самым узким местом в сети

(3) любым местом в сети

Номер 3

Алгоритм Форда-Фалкерсона может работать бесконечно, если величина пропускной способности

Ответ:

(1) натуральное число

(2) иррациональное число

(3) отрицательное число

Упражнение 9:

Номер 1

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

Ответ:

(1) модуля пропускной способности

(2) величиной произвольного разреза

(3) объемом вершин потока

Номер 2

Если сток является помеченным, то

Ответ:

(1) существует увеличивающийся путь

(2) разрез является максимальным

(3) алгоритм Форда-Фалкерсона является зацикленным

Номер 3

Построение начального потока алгоритма Карзанова занимает времени

Ответ:

(1) O(m)

(2) O(2m)

(3) O(log(m))

Упражнение 10:

Номер 1

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

Ответ:

(1) O(m²)

(2) O(2m-1)

(3) O(m)

Номер 2

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

Ответ:

(1) O(m)

(2) O(m/2)

(3) O(2m²-1)

Номер 3

Какое количество раз обрабатывается насыщенная дуга при нахождении тупикового потока?

Ответ:

(1) 1

(2) 2

(3) m-1

Упражнение 11:

Номер 1

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

Ответ:

(1) log(m)

(2) m

(3) m²

Номер 2

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

Ответ:

(1) m

(2) 2n²

(3) 3mn

Номер 3

Для чего применяется алгоритм Карзанова?

Ответ:

(1) для нахождения максимального потока

(2) для нахождения максимального разреза

(3) для насыщения вершин

Упражнение 12:

Номер 2

Если количество дуг в потоке выражается значением O(n²)), алгоритм Карзанова занимает времени

Ответ:

(1) O(n)

(2) O(n²)

(3) O(n³)

Номер 3

Какой алгоритм работает быстрее: Форда-Фалкерсона или Карзанова?

Ответ:

(1) Форда-Фалкерсона

(2) Карзанова

(3) одинаково

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