Алгоритмы: построение и анализ

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

Номер 1

 Что такое сеть?

Ответ:

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

(2) множество вершин V c выделенными вершинами S T и функция math

(3) множество вершин V c выделенными вершинами S T и функция math

(4) ориентированный граф у которого на ребрах написаны положительные числа

Номер 2

 Какими свойствами обладает функция потока ?

Ответ:

(1)

(2)

(3)

(4)

(5)

Номер 3

 Как определяется остаточная сеть ?

Ответ:

(1)

(2)

(3)

(4)

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

Номер 1

 Какое утверждение верно?

Ответ:

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

(2) в остаточной сети пропускная способность ребер не меньше чем в исходной

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

Номер 2

  Какое утверждение верно?

Ответ:

(1) в остаточной сети могут быть только те ребра, которые были в исходной сети

(2) в остаточной сети могут появиться новые ребра

(3) в остаточной сети могут появиться новые вершины и ребра соединяющие их со старыми вершинами

Номер 3

 Какое утверждение верно?

Ответ:

(1)

(2)

(3)

(4)

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

Номер 1

 Какими свойствами обладает фунция предпотока?

Ответ:

(1)

(2)

(3)

(4)

(5)

Номер 2

 Какие свойства общие для функций потока и предпотока?

Ответ:

(1)

(2)

(3)

Номер 3

 Какие утверждения верны, сли ?

Ответ:

(1) u это переполненная вершина

(2) поток приходящий в вершину u больше уходящего потока

(3) поток уходящий из вершины u больше приходящего потока

(4)

и

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

Номер 1

 Какими свойствами обладает высотная фунция h?

Ответ:

(1) она равна расстоянию от вершины до стока

(2)

(3) если math

, то

(4) если math

, то

Номер 2

 Какая формальная запись соответствут условию "если ребро идет круто вниз, то по нему течет максимальный поток"?

Ответ:

(1)

(2)

(3)

Номер 3

 Пусть h - правильная высотная функция, а ребро (u,v) круто идет вниз. Какие утверждения тогда верны?

Ответ:

(1)

(2)

(3)

(4)

(5)

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

Номер 1

При выполнении каких условий можно делать операцию PUSH(u,v)?

Ответ:

(1) вершина uпереполнена

(2) ребро (u,v) принадлежит остаточной сети

(3) вершина v принадлежит нулевому уровню

(4) вершина u выше чем вершина v

Номер 2

 Чему равна величина проталкиваемого потока на шаге PUSH?

Ответ:

(1)

(2)

(3)

Номер 3

 Пусть величину d  протолкнули на шаге PUSH по ребру (u,v). Какой код тогда отвечает за изменение потоков и излишков?

Ответ:

(1)

f(u,v)-=d;
f(v,u)+=d;
e(u)-=d;
e(v)+=d;

(2)

f(u,v)+=d;
f(v,u)=-f(u,v);
e(u)-=d;
e(v)+=d;

(3)

 f(u,v)+=d;
f(v,u)-=d;
e(u)-=d;
e(v)-=d;

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

Номер 1

 При выполении каких условий можно делать операцию LIFT(v) ,?

Ответ:

(1) вершина v переполнена

(2) ельзя протолкнуть предпоток из v ни в одну другую вершину

(3) вершина v пренадлежит нулевому уровню

(4) нельзя протолкнуть предпоток в v

Номер 2

 Какое утверждение верно, если на шаге LIFT подымается вершина v?

Ответ:

(1) в остаточной сети math

(2)

только для вершин u, которые выше v

(3)

только для вершин u, которые выше v

Номер 3

 Какой псевдокод отвечает операции LIFT?

Ответ:

(1)

	LIFT(v)
{
		h(v):= 1 +

(2)

LIFT(v)
{
	h(v)+= 1; 
}

(3)


LIFT(v)
{
	h(v):= 1 +

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

Номер 1

 В чем заключается алгоритм проталкивания предпотока?

Ответ:

(1) делать по очереди LIFT и PUSH пока это возможно

(2) делать операции LIFT и PUSH пока это возможно

(3) применять операцию LIFT пока это возможно, а потом применять операцию PUSH пока это возможно

(4) применять операцию PUSH пока это возможно, а потом применять операцию LIFT пока это возможно

Номер 2

 Какие утверждения верны, если алгоритм проталкивания предпотока остановился?

Ответ:

(1) переполненных вершин нет

(2) получившийся поток является максимальным потоком

(3) величина получившегося предпотока равна величине максимального сечения

Номер 3

 Какие утверждения верны?

Ответ:

(1) пусть math

остаточная сеть на произвольном шаге алгоритма проталкивания предпотока, тогда из истока сток не достижим

(2) любой путь соединяющий исток со стоком всегда содержит круто идущее вниз ребро

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

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

Номер 1

 За какое время работает алгоритм проталкивания предпотока при оптимальной реализации?

Ответ:

(1)

(2)

(3)

Номер 2

 Что нужно для того чтобы алгоритм проталкивания предпотока работал за ?

Ответ:

(1) из пары возможных действий LIFT и PUSH всегда выбирать LIFT

(2) надо обрабатывать вершины последовательно с помощью операции DISCHARGE

(3) из пары возможных действий LIFT и PUSH всегда выбирать PUSH

Номер 3

 В алгоритме LIFT-TO-FRONT

Ответ:

(1) операции PUSH и LIFT используются апосредованно через DISCHARGE

(2) DISCHARGE для каждой вершины применяется только один раз

(3) после применения DISCHARGE вершина может быть перенесена в начало списка обрабатываемых вершин

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

Номер 1

 В строке "mississippi" строка "mi"

Ответ:

(1) является суффиксом

(2) является префиксом

(3) не является ни суффиксом, ни префиксом

Номер 2

 В строке "abaaba" строка "aba"

Ответ:

(1) является суффиксом

(2) является префиксом

(3) является и суффиксом, и префиксом

Номер 3

 В строке "abacaba" строка "ca"

Ответ:

(1) является суффиксом

(2) является префиксом

(3) не является ни суффиксом, ни префиксом

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

Номер 1

 Для образца "sissisippi" значение префикс функции

Ответ:

(1) 6

(2) 3

(3) 2

Номер 2

 Для образца "sissisippi" значение префикс функции

Ответ:

(1) 2

(2) 1

(3) 3

Номер 3

 Для образца "sissisippi" значение префикс функции

Ответ:

(1) 3

(2) 5

(3) 0

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

Номер 1

 Для строки "abcdabscabcdabia" префикс функция равна

Ответ:

(1) 000120012345001

(2) 000120012345601

(3) 00120012345601

Номер 2

 Для строки "abcdabscabcdabid" префикс функция равна

Ответ:

(1) 000120012345601

(2) 000120012345600

(3) 00120012345601

Номер 3

 Для строки "abcdabacabcdabid" префикс функция равна

Ответ:

(1) 00121012345601

(2) 000120012345601

(3) 000121012345601

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

Номер 1

 Чему равно время работы алгоритма Кнутта-Морриса-Пратта?

Ответ:

(1) O(n)

(2) O(n+m)

(3) O(nm)

Номер 2

 Чему рано время построения префикс функции для строки длины m?

Ответ:

(1) O(m)

(2) O(m^2)

(3) O(m^3)

Номер 3

 Задача поиска наименьшего периода в периодической строке длины n решается за время

Ответ:

(1) O(n²)

(2) O(n*log n)

(3) O(n)

Алгоритмы: построение и анализ - тест 7