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

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

Номер 1

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

Ответ:

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

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

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

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

Номер 2

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

Ответ:

(1)

(2)

(3)

(4)

(5)

Номер 3

Что такое величина потока ?

Ответ:

(1)

(2)

(3)

(4)

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

Номер 1

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

Ответ:

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

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

(3) максимальный поток не ограничен

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

Номер 2

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

Ответ:

(1)

(2)

(3)

(4)

Номер 3

Если в остаточной сети существует путь соединяющий s и t, то

Ответ:

(1) он единственен

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

(3) поток не максимален

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

Номер 1

Как ищется путь в остаточной сети в алгоритме Энлмонса-Карпа

Ответ:

(1) методом поиска в ширину

(2) методом поиска в глубину

(3) с помощью ранговой эвристики

Номер 2

Что такое паросочетание?

Ответ:

(1) это разбиение вершин графа на пары

(2) это подмножество ребер двудольного графа, такое что в нем нет ребер с общими вершинами

(3) это пары вершин и инцидентных им ребер

Номер 3

Свободные вершины это...

Ответ:

(1) вершины двудольного графа, не являющиеся вершинами ребер из паросочетания

(2) вершины из которых не идет ребер

(3) вершины степени один в графе

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

Номер 1

Что такое чередующаяся цепь?

Ответ:

(1) это цепь из ребер графа, в которой нечетные ребра - это ребра из паросочетания

(2) это цепь из ребер графа, в которой четные ребра - это ребра из паросочетания

(3) это цепь нечетной длины из ребер графа в, которой четные ребра - это ребра из паросочетания

(4) это цепь нечетной длины из ребер графа, в которой четные ребра - это ребра из паросочетания

Номер 2

Что такое симметрическая разность множеств A и B?

Ответ:

(1) это элементы которые принадлежат A или B, но не принадлежат их пересечению

(2) это элементы которые принадлежат A или B

(3) это элементы которые принадлежат пересечению A и B

(4) это элементы которые не принадлежат ни A ,ни B

Номер 3

Будем искать максимальное паросочетание следующим способом: на каждом шаге ищем чередующийся путь с помощью поиска в глубину и увеличиваем имеющееся паросочетание с помощью этого пути. Пусть m и n размеры долей. Чему равно время работы алгоритма?

Ответ:

(1) min( O(n²*m), O(n*m²))

(2) O(n²*m²)

(3) max( O(n²*m), O(n*m²))

(4) O(n*m)

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

Номер 1

 Пусть  двудольный граф задан следующей матрицей $\begin{pmatrix}
1 & 1 & 1 & 1 & 1\\
0 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 0 & 1\\
\end{pmatrix}$  Чему равен размер максимального паросочетания?

Ответ:

(1) 5

(2) 4

(3) 3

(4)

Номер 2

 Пусть  двудольный граф задан следующей матрицей $\begin{pmatrix}
1 & 1 & 1 & 1 & 1\\
0 & 1 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 0 & 1\\
\end{pmatrix}$  Чему равен размер максимального паросочетания?

Ответ:

(1) 5

(2) 4

(3) 3

(4)

Номер 3

 Пусть  двудольный граф задан следующей матрицей $\begin{pmatrix}
1 & 1 & 1 & 1 & 1\\
0 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 0 & 1\\
0 & 1 & 0 & 0 & 1\\
0 & 0 & 1 & 0 & 1\\
\end{pmatrix}$  Чему равен размер максимального паросочетания?

Ответ:

(1) 5

(2) 4

(3) 3

(4) 6

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

Номер 1

Какое множество вершин называется контролирующим?

Ответ:

(1) такое, что любая вершина в графе соединена ребром с какой-то контролирующей

(2) такое, что любая вершина в графе соединена ребром с какой-то контролирующей или сама является контролирующей

(3) такое, что из любой вершины графа можно дойти до контролирующей по ребрам

Номер 2

Что известно про минимальное контролирующее множество в двудольном графе?

Ответ:

(1) его мощность не больше мощность максимального паросочетания

(2) его мощность не меньше мощность максимального паросочетания

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

(4) его мощность может быть меньше мощности максимального паросочетания

Номер 3

Какова сложность алгоритма нахождения минимального контролирующего множества в двудольном графе?

Ответ:

(1) O(n)

(2) O(n^2)

(3) O(n^3)

(4) O(n^2*log(n))

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

Номер 1

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

Ответ:

(1) вычесть из всех чисел в строке константу

(2) вычесть из всех чисел в столбце константу

(3) вычесть из всех чисел на главной диагонали константу

(4) поменять местами значения в двух соседних клетках

Номер 2

Почему мы хотим иметь матрицу в которой нет отрицательных значений и моного нулей(настолько много, что оптимальное назначение имеет нулевую стоимость)?

Ответ:

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

(2) в такой постанове задача принадлежит NP

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

Номер 3

Пусть в задаче о назначениях N работ. Все элементы матрици цен неотрицательны. В матрице цен есть подматрица размера m*n без нулевых элементов и m+n>N. Какие утверждения тогда верны?

Ответ:

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

(2) стоимость оптимального назначения работ больше нуля

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

(4) оптимального назначения не существует

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

Номер 1

Пусть на начало второго шага венгерского алгоритма мы работали со следующим двумя строками  $\begin{pmatrix}
3 & 0 & 3 & 5 & 4\\
3 & 1 & 2 & 2 & 3\\ 
\end{pmatrix}$  как будут выглядеть эти строки к концу второго шага?

Ответ:

(1)

\begin{pmatrix}
3 & 0 & 3 & 5 & 4\\
2 & 0 & 1 & 1 & 2\\ 
\end{pmatrix}

(2)

\begin{pmatrix}
2 & 0 & 2 & 4 & 3\\
1 & 0 & 0 & 0 & 1\\ 
\end{pmatrix}

(3)

\begin{pmatrix}
3 & 0 & 3 & 5 & 4\\
1 & 0 & 0 & 0 & 1\\ 
\end{pmatrix}

Номер 2

Пусть на начало второго шага венгерского алгоритма мы работали со следующим двумя строками  $\begin{pmatrix}
3 & 0 & 1 & 5 & 4\\
3 & 1 & 3 & 8 & 3\\ 
\end{pmatrix}$  как будут выглядеть эти строки к концу второго шага?

Ответ:

(1)

\begin{pmatrix}
3 & 0 & 1 & 5 & 4\\
2 & 0 & 2 & 7 & 2\\ 
\end{pmatrix}

(2)

\begin{pmatrix}
2 & -1 & 0 & 4 & 3\\
2 & 0 & 2 & 7 & 2\\  
\end{pmatrix}

(3)

\begin{pmatrix}
2 & 0 & 0 & 4 & 3\\
1 & 0 & 1 & 6 & 1\\  
\end{pmatrix}

Номер 3

Пусть на начало второго шага венгерского алгоритма мы работали со следующим двумя строками  $\begin{pmatrix}
3 & 0 & 1 & 5 & 4\\
3 & 1 & 2 & 8 & 2\\ 
\end{pmatrix}$  как будут выглядеть эти строки к концу второго шага?

Ответ:

(1)

\begin{pmatrix}
3 & 0 & 1 & 5 & 4\\
2 & 0 & 1 & 7 & 1\\  
\end{pmatrix}

(2)

\begin{pmatrix}
2 & 0 & 0 & 4 & 3\\
1 & 0 & 0 & 6 & 0\\  
\end{pmatrix}

(3)

\begin{pmatrix}
2 & 1 & 0 & 4 & 3\\
1 & 1 & 0 & 6 & 0\\  
\end{pmatrix}

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

Номер 1

Пусть на начало пятого шага венгерского алгоритма мы работали со следующими  строками  $\begin{pmatrix}
3 & 0 & 1 & 0 & 4\\
3 & 1 & 0 & 2 & 3\\ 
3 & 0 & 2 & 2 & 3\\ 
0 & 1 & 2 & 2 & 3\\ 
3 & 1 & 2 & 2 & 3\\ 
\end{pmatrix}$ .  Как будут выглядеть эти строки к концу пятого шага?

Ответ:

(1)

\begin{pmatrix}
3 & 0 & 1 & 0 & 4\\
3 & 1 & 0 & 2 & 3\\ 
3 & 0 & 2 & 2 & 3\\ 
0 & 1 & 2 & 2 & 3\\ 
2 & 0 & 1 & 1 & 2\\
\end{pmatrix}

(2)

\begin{pmatrix}
3 & 1 & 1 & 0 & 4\\
3 & 2 & 0 & 2 & 3\\ 
2 & 0 & 1 & 1 & 2\\ 
0 & 2 & 2 & 2 & 3\\ 
1 & 0 & 0 & 0 & 1\\ 
\end{pmatrix}

(3)

\begin{pmatrix}
3 & 1 & 1 & 0 & 4\\
3 & 2 & 0 & 2 & 3\\ 
2 & 0 & 1 & 1 & 2\\ 
0 & 2 & 2 & 2 & 3\\ 
1 & 0 & 0 & 0 & 1\\  
\end{pmatrix}

(4)

\begin{pmatrix}
2 & 1 & 1 & 0 & 3\\
2 & 2 & 0 & 2 & 2\\ 
1 & 0 & 1 & 1 & 1\\ 
0 & 3 & 3 & 3 & 3\\ 
0 & 0 & 0 & 0 & 0\\  
\end{pmatrix}

Номер 3

Пусть на начало пятого шага венгерского алгоритма мы работали со следующим двумя строками  $\begin{pmatrix}
3 & 0 & 1 & 0 & 4\\
3 & 1 & 0 & 2 & 3\\ 
3 & 0 & 2 & 2 & 3\\ 
0 & 1 & 2 & 2 & 3\\ 
3 & 2 & 2 & 1 & 2\\ 
\end{pmatrix}$  как будут выглядеть эти строки к концу пятого шага?

Ответ:

(1)

\begin{pmatrix}
3 & 0 & 1 & 0 & 4\\
3 & 1 & 0 & 2 & 3\\ 
3 & 0 & 2 & 2 & 3\\ 
0 & 1 & 2 & 2 & 3\\ 
2 & 1 & 1 & 0 & 1\\
\end{pmatrix}

(2)

\begin{pmatrix}
2 & 0 & 0 & 0 & 3\\
3 & 2 & 0 & 3 & 3\\ 
3 & 0 & 2 & 3 & 3\\ 
0 & 2 & 2 & 3 & 3\\ 
1 & 0 & 0 & 0 & 0\\ 
\end{pmatrix}

(3)

\begin{pmatrix}
1 & 0 & 0 & 0 & 2\\
2 & 2 & 0 & 3 & 2\\ 
2 & 0 & 2 & 3 & 2\\ 
0 & 3 & 3 & 4 & 3\\ 
0 & 0 & 0 & 0 & 0\\ 
\end{pmatrix}

(4)

\begin{pmatrix}
2 & 1 & 1 & 0 & 3\\
2 & 2 & 0 & 2 & 2\\ 
1 & 0 & 1 & 1 & 1\\ 
0 & 3 & 3 & 3 & 3\\ 
0 & 0 & 0 & 0 & 0\\  
\end{pmatrix}

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

Номер 1

Вбирите верные утверждения

Ответ:

(1) альфа-бета отсечения это эвристика

(2) альфа-бета отсечения это точный алгоритм

(3) применение альфа-бета отсечений гарантированно увеличивает глубину продумывания в 2 раза

(4) применение альфа-бета отсечений в среднем увеличивает глубину продумывания в 2 раза

Номер 2

Какие идеи могут улучшить алгоритм поиска лучшего хода в "middle game" позиции?

Ответ:

(1) альфа-бета отсечения

(2) упорядочивание просматриваемых ходов по эвристическому признаку

(3) эвристическое отсечение

(4) кэширование

(5) пристрелка в узком окне

Номер 3

В чем заключается эффект горизонта?

Ответ:

(1) программа не замечает вилки

(2) атаки соперника могут идти дальше чем глубина продумывания, и поэтому программы может не заметить улучшение своей позиции

(3) глубина продумывания ограничена

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

Номер 1

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

Ответ:

(1) macro

(2) scale

(3) local

(4) meta

Номер 2

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

Ответ:

(1) macro

(2) scale

(3) local

(4) meta

Номер 3

Какие теги соответствуют генетическим алгоритмам?

Ответ:

(1) macro

(2) scale

(3) local

(4) meta

(5) competition

(6) gready

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

Номер 1

Сколько различных позиций (реальных шахматных) в задаче "эндшпиль" из лекции?

Ответ:

(1) 64*64

(2) 63*62

(3) 63*62*2

(4) 64*63*2

Номер 2

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

Ответ:

(1) macro

(2) scale

(3) local

(4) meta

(5) cache

Номер 3

Какова сложность по памяти задачи "эндшпиль"?

Ответ:

(1) O(64)

(2) O(64²)

(3) O(64³)

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