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

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

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

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

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

Пусть веса ребер полного графа заданы матрицей . В каком порядке жадный алгоритм будет выбирать ребра максимального покрывающего поддерева?

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

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

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

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

• (Правильный ответ)

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

• (Правильный ответ) лагорифмична по числу элементов в множестве
• линейна по числу элементов в множестве
• сублагорифмична по числу элементов в множестве

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

• O(E+V)
• O(V*logE)
• (Правильный ответ) O(E*logV)

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

• в соответствующем наборе ребер есть цикл
• число ребер в этом наборе нечетно
• (Правильный ответ) соответствующий набор ребер ацикличен

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

• алгоритм Прима работает быстрее чем алгоритм Крускала
• на каждом шаге алгоритма Крускала есть только одно нетривиальное дерево
• (Правильный ответ) на каждом шаге алгоритма Прима есть только одно нетривиальное дерево

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

• find_set
• make_set
• (Правильный ответ) unite

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

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

Пусть двудольный граф задан следующей матрицей Чему равен размер максимального паросочетания?

• 5
• (Правильный ответ) 4
• 3
• 6

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

• O(n)
• (Правильный ответ) O(n^3)
• O(n^2*log(n))
• O(n^2)

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

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

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

• (Правильный ответ)

В строке «abaaba» строка «aba»

• является префиксом
• является суффиксом
• (Правильный ответ) является и суффиксом, и префиксом

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

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

В строке «abacaba» строка «ca»

• является суффиксом
• является префиксом
• (Правильный ответ) не является ни суффиксом, ни префиксом

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

• (Правильный ответ) 1
• 2
• 3

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

• O(n2)
• O(n*log n)
• (Правильный ответ) O(n)

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

• 00120012345601
• (Правильный ответ) 000120012345600
• 000120012345601

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

• (Правильный ответ) вершина v переполнена
• нельзя протолкнуть предпоток в v
• вершина v пренадлежит нулевому уровню
• (Правильный ответ) ельзя протолкнуть предпоток из v ни в одну другую вершину

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

• (Правильный ответ) после применения DISCHARGE вершина может быть перенесена в начало списка обрабатываемых вершин
• (Правильный ответ) операции PUSH и LIFT используются апосредованно через DISCHARGE
• DISCHARGE для каждой вершины применяется только один раз

Для того чтобы хранить бор для слова длины n надо

• (Правильный ответ) O(n2) памяти
• O(n*log n ) памяти
• O(n3) памяти

Пусть мы имеем бор для строки «abc», и хотим из него получить бор для строки «abca»

• тогда нужно добавить 4 вершины и 4 суффиксных ссылки
• тогда нужно добавить 4 вершины и 5 суффиксных ссылок
• (Правильный ответ) тогда нужно добавить 3 вершины и 3 суффиксных ссылки

В алгоритме Укконена при добавлении нового символа

• просматривается только та часть boundary-path, которая идет после active point
• (Правильный ответ) просматривается только та часть boundary-path, которая идет между active point и end point
• просматривается весь новый boundary-path

Пусть мы имеем бор для строки «abca», и хотим из него получить бор для строки «abcad»

• (Правильный ответ) тогда нужно добавить 5 вершины и 5 суффиксных ссылки
• тогда нужно добавить 4 вершины и 4 суффиксных ссылки
• тогда нужно добавить 4 вершины и 5 суффиксных ссылок

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

• (Правильный ответ) суффиксная ссылка из вершины для строки s, ведет в вершину для строки соответствующей наиьольшему собственному суффиксу s
• (Правильный ответ) куффиксная ссылка из вершины для строки s, ведет в вершину для строки получающейся из s отрезанием первого символа
• суффиксная ссылка из вершины для строки s, ведет в вершину для строки получающейся из s отрезанием какого-то количества первых символов

Что позволяет символ бесконечности?

• непроизводить операций с листьями
• (Правильный ответ) не производить операций с листьями если структура дерева не меняется
• быстро просматривать листья

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

• end point k-го шага это родитель active point k-го шага
• active point k-го шага это родитель end point (k+1)-го шага
• (Правильный ответ) end point k-го шага это родитель active point (k+1)-го шага

Пусть мы имеем бор для строки «aba», и хотим из него получить бор для строки «abaa»

• (Правильный ответ) тогда нужно добавить 3 вершины и 3 суффиксных ссылки
• тогда нужно добавить 4 вершины и 4 суффиксных ссылки
• тогда нужно добавить 4 вершины и 5 суффиксных ссылок

Вершина «dummy» добавляется для того чтобы …

• увеличить высоту дерева
• (Правильный ответ) не писать лишние if в коде алгоритма
• усложнить алгоритм

Построим бор по словам «good»,»bad»,»bed»,»better». Какое утверждение верно?

• глубина бора равна 6
• (Правильный ответ) в боре 4 листовых вершин
• у корня 4 потомка

Сколько вершин в графе иры Ним для начальной позиции {2,2}? (начальную {2,2} и конечную {0,0} тоже считать)

• 5
• (Правильный ответ) 6
• 4

Для игры Ним {3,3,2,7} нимбером является:

• (Правильный ответ) 110
• 111
• 101

Какая из этих игр является конечной?

• шашки
• (Правильный ответ) крестики-нолики
• шахматы

Что такое примитивный корень степени n из 1?

• это такой корень, что среди его степеней есть все остальные корни степени n
• это такой корень, что среди его целых степеней есть все остальные корни
• (Правильный ответ) это такой корень, что среди его целых степеней есть все остальные корни степени n

Как выражаются в обратном дискретном преобразовании Фурье?

• (Правильный ответ)

Чему равно ?

• (Правильный ответ)

Что понимается под неявной вершиной?

• (Правильный ответ) вершина которая есть в боре, но которой не стало в суффиксном дереве из-за сжатия путей
• дополнительная листовая вершина
• дополнительная вершина над корнем

Как определяется нимбер произвольной игры A?

• (Правильный ответ)