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

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

Номер 1

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

Ответ:

(1) никакие k из них не лежат ни в одном k-2 мерном подпространстве

(2) точки не лежат нив одном n-2 мерном подпространстве, где n это число точек

(3) никакие 4 из них не лежат ни в одном 2 мерном подпространстве

(4) никакие 2 точки не лежат на одной прямой

Номер 2

Пусть k точек в  заданы векторами . Какое выражение соответствкет условию того что это система общего положения?

Ответ:

(1)

det \begin{pmatrix} 
\vec{v_1} & 1  \\
\ldots & \ldots \\
\vec{v_k} & 1  \\
\end{pmatrix} = 0

(2)

det \begin{pmatrix}
\vec{v_1} & 1  \\
\ldots & \ldots \\
\vec{v_k} & 1  \\
\end{pmatrix} = 1

(3)

det \begin{pmatrix}
\vec{v_1}   \\
\ldots \\
\vec{v_k}   \\
\end{pmatrix} = 0

(4)

det \begin{pmatrix}
\vec{v_1}   \\
\ldots \\
\vec{v_k}   \\
\end{pmatrix} = 1

Номер 3

 Пусть k точек в  заданы векторами . Какое выражение соответствует условию того что это система общего положения?

Ответ:

(1)

det \begin{pmatrix}
\vec{v_1} & 2  \\
\vec{v_2} & 2  \\
\ldots & \ldots \\
\vec{v_k} & 2  \\
\end{pmatrix} = 0

(2)

det \begin{pmatrix}
\vec{v_1} & 1  \\
\vec{v_2} & 2  \\
\ldots & \ldots \\
\vec{v_k} & k  \\
\end{pmatrix} = 0

(3)

det \begin{pmatrix}
1 & \vec{v_1}  \\
1 & \vec{v_2}  \\
\ldots & \ldots \\
1 & \vec{v_k}  \\
\end{pmatrix} = 0

(4)

det \begin{pmatrix}
\vec{v_1} & 1  \\
\vec{v_2} & 1  \\
\ldots & \ldots \\
\vec{v_k} & 1  \\
\end{pmatrix} = 1

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

Номер 1

Что такое симплекс?

Ответ:

(1) это набор точек общего положения

(2) это многогранник, вершины которого являются точками общего положения

(3) это тетраэдр или треугольник

Номер 2

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

Ответ:

(1) любое подмножество вершин симплекса задает симплекс меньшей размерности

(2) грани симплекса являются симлексами

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

Номер 3

Какие из следующих множеств являются симплексами?

Ответ:

(1) октайдер

(2) отрезок

(3) прямая

(4) триугольник

(5) тетрайдер

(6) куб

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

Номер 1

Пусть веса ребер полного графа заданы матрицей  $A= \begin{pmatrix}
- & 2 & 4 & 5 \\
2 & - & 1 & 1 \\
4 & 1 & - & 3 \\
5 & 1 & 3 & - \\
\end{pmatrix}$ . В каком порядке жадный алгоритм будет выбирать ребра максимального покрывающего поддерева?

Ответ:

(1) сперва ребро (1,4), потом ребро (1,3) и последним ребро (1,2)

(2) сперва ребро (1,4), потом ребро (1,3) и последним ребро (3,4)

(3) сперва ребро (1,3), потом ребро (1,4) и последним ребро (1,2)

(4) сперва ребро (1,2), потом ребро (1,3) и последним ребро (1,4)

Номер 2

Пусть веса ребер полного графа заданы матрицей  $A= \begin{pmatrix}
- & 6 & 4 & 3 \\
6 & - & 3 & 5 \\
4 & 3 & - & 1 \\
3 & 5 & 1 & - \\
\end{pmatrix}$ . В каком порядке жадный алгоритм будет выбирать ребра максимального покрывающего поддерева?

Ответ:

(1) сперва ребро (1,4), потом ребро (1,3) и последним ребро (1,2)

(2) сперва ребро (1,2), потом ребро (2,4) и последним ребро (1,3)

(3) сперва ребро (2,4), потом ребро (1,2) и последним ребро (1,3)

(4) сперва ребро (1,2), потом ребро (1,3) и последним ребро (1,4)

Номер 3

Пусть веса ребер полного графа заданы матрицей  $A= \begin{pmatrix}
- & 100 & -4 & -5 \\
100 & - & -2 & -1 \\
-4 & -2 & - & -3 \\
-5 & -1 & -3 & - \\
\end{pmatrix}$ . В каком порядке жадный алгоритм будет выбирать ребра максимального покрывающего поддерева?

Ответ:

(1) сперва ребро (1,4), потом ребро (1,3) и последним ребро (1,2)

(2) сперва ребро (1,2), потом ребро (2,4) и последним ребро (1,3)

(3) сперва ребро (2,4), потом ребро (1,2) и последним ребро (1,3)

(4) сперва ребро (1,2), потом ребро (2,4) и последним ребро (2,3)

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

Номер 1

Какие утверждения верны для следующей матрицы  $A= \begin{pmatrix}
0 & 1 & 0 & 0 & 1 \\
1 & 0 & 0 & 1 & 0\\
0 & 0 & 1 & 0 & 1\\
1 & 1 & 1 & 1 & 0\\
\end{pmatrix}$ ?

Ответ:

(1) эта матрица может быть транспонированной матрицей ицедентности какого-то графа

(2) столбцы этой матрицы линейно зависимы

(3) строки этой матрицы линейно зависимы

(4) строки этой матрици линейно зависимы над GF(2)

Номер 2

Какие утверждения верны для следующей матрицы  $A= \begin{pmatrix}
0 & 1 & 1 & 1 & 0 \\
1 & 0 & 0 & 1 & 0\\
0 & 0 & 1 & 0 & 1\\
1 & 1 & 1 & 1 & 0\\
\end{pmatrix}$ ?

Ответ:

(1) эта матрица может быть транспонированной матрицей ицедентности какого-то графа

(2) столбцы этой матрицы линейно зависимы

(3) строки этой матрицы линейно зависимы

(4) строки этой матрици линейно зависимы над GF(2)

Номер 3

Какие утверждения верны для следующей матрицы  $A= \begin{pmatrix}
1 & 1 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 & 0\\
0 & 0 & 1 & 0 & 1\\
0 & 0 & 1 & 1 & 0\\
1 & 1 & 0 & 0 & 0\\
\end{pmatrix}$ ?

Ответ:

(1) эта матрица может быть матрицей ицедентности какого-то графа

(2) столбцы этой матрицы линейно зависимы

(3) строки этой матрицы линейно зависимы

(4) строки этой матрици линейно зависимы над GF(2)

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

Номер 1

Какое условие соответствует тому, в наборе ребер есть цикл?

Ответ:

(1) строки соответствующие этим ребрам в матрице инцедентности линейно зависимы

(2) строки соответствующие этим ребрам в матрице инцедентности линейно зависимы над GF(2)

(3) строки в матрице инцедентности для графа содержащего эти ребра линейно зависимы над GF(2)

Номер 2

Если набор строк в матрице инцедентности линейно независим над GF(2), то

Ответ:

(1) в соответствующем наборе ребер есть цикл

(2) число ребер в этом наборе нечетно

(3) соответствующий набор ребер ацикличен

Номер 3

Если в графе степень всех вершин равна двум, то

Ответ:

(1) в графе нет циклов

(2) в графе обязательно найдется цикл

(3) в графе могут быть циклы, и может их не быть

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

Номер 1

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

Ответ:

(1) make_set

(2) find_set

(3) unite

Номер 2

Какая операция отвечает за нахождение представителя множества в "структуре неперсекающихся множеств"?

Ответ:

(1) make_set

(2) find_set

(3) unite

Номер 3

Какая операция отвечает за объединение двух множеств в "структуру неперсекающихся множеств"?

Ответ:

(1) make_set

(2) find_set

(3) unite

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

Номер 1

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

Ответ:

(1) всевозможные ациклические наборы ребер в графе G

(2) всевозможные циклические наборы ребер в графе G

(3) всевозможные наборы ребер в графе G, такие что удаление всех ребер в наборе оставляет граф связным

Номер 2

Что такое матроид?

Ответ:

(1) пара из множества math

и системы подмножеств в math

, удовлетворяющая трем аксиомам матроидов

(2) набор линейнонезависимых подстрок в матрице

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

Номер 3

Как формулируется третья аксиома матроидов?

Ответ:

(1) Если math

и мощность math

больше мощности math

, то существует math

такой, что math

(2) Если math

и мощность math

больше мощности math

, то существует math

такой, что math

(3) Если math

, то существует math

такой, что math

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

Номер 1

Что такое покрывающее дерево?

Ответ:

(1) это дерево, которое содержит все вершины

(2) это дерево, которое является подграфом и содержит все вершины

(3) это дерево, которое содержит все ребра

Номер 2

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

Ответ:

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

(2) если граф связен, то покрывающеее дерево существует

(3) покрывающее дерево всегда единственно

(4) покрывающее дерево может не существовать для данного графа

Номер 3

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

Ответ:

(1) самое легкое ребро принадлежит минимальному покрывающему дереву

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

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

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

Номер 1

Что такое сжатие путей?

Ответ:

(1) метод, позволяющий хранить пути более эффективно по памяти

(2) метод, позволяющий при повторном хождении по пути, пройти путь за O(1)

(3) замена пути в графе на ребро, соединяющее начало и конец пути

Номер 2

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

Ответ:

(1) линейна по числу элементов в множестве

(2) сублагорифмична по числу элементов в множестве

(3) лагорифмична по числу элементов в множестве

Номер 3

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

Ответ:

(1) сжатие путей

(2) обход в ширину

(3) ранговая эвристика

(4) жадность

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

Номер 1

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

Ответ:

(1) на каждом шаге алгоритма Прима есть только одно нетривиальное дерево

(2) на каждом шаге алгоритма Крускала есть только одно нетривиальное дерево

(3) алгоритм Прима работает быстрее чем алгоритм Крускала

Номер 2

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

Ответ:

(1) O(V*logE)

(2) O(E+V)

(3) O(E*logV)

Номер 3

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

Ответ:

(1) O(V*logE)

(2) O(E+V)

(3) O(E*logV)

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

Номер 1

Применим монотонное преобразование к функции веса ребер. Какое утверждение верно?

Ответ:

(1) вес минимального покрывающего дерева не изменится

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

(3) может появиться новое минимальное покрывающее дерево

Номер 2

Применим монотонное преобразование к функции веса ребер. Какое утверждение верно?

Ответ:

(1) вес максимального покрывающего дерева не изменится

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

(3) может появиться новое максимальное покрывающее дерево

Номер 3

Применим монотонное преобразование к функции веса ребер. Какие утверждения верны?

Ответ:

(1) в каждом разрезе самое легкое ребро останится прежним

(2) в каждом разрезе самое тяжелое ребро останится прежним

(3) вес самого легкого ребра останется прежним

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

Номер 1

Пусть A и B два минимальных покрывающих дерева в графе G. Какое утверждение верно?

Ответ:

(1) веса ребер в A в точности совпадают с весами ребер в B

(2) сумма весов ребер в A в точности совпадают с суммой весов ребер в B, а значения весов могут не совпадать

(3) сумма весов ребер в A может не совпадать с суммой весов ребер в B

Номер 2

Пусть A и B два максимальных покрывающих дерева в графе G. Какое утверждение верно?

Ответ:

(1) веса ребер в A в точности совпадают с весами ребер в B

(2) сумма весов ребер в A в точности совпадают с суммой весов ребер в B, а значения весов могут не совпадать

(3) сумма весов ребер в A может не совпадать с суммой весов ребер в B

Номер 3

Пусть в графе G пять разных минимальных покрывающих деревьев. Вова загодал  K - одно из них. Пятя знает граф G но не знает какое минимальное покрывающее дерево, которое загадал Петя. Какие утверждения верны?

Ответ:

(1) Петя может назвать вес минимального ребра в K

(2) Петя может назвать веса всех ребер в K

(3) Петя может назвать все вершины K

(4) Петя может назвать все ребра K

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