Главная / Алгоритмы и дискретные структуры / Алгоритмы: построение и анализ

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

Правильные ответы выделены зелёным цветом.
Все ответы: Курс посвящён теории алгоритмов и элементам дискретной математики. Основная цель курса - научиться эффективно решать алгоритмические задачи, вооружиться фундаментальными идеями и методами, выработать системный подход к решению алгоритмических задач.
Смотрите также:
Программирование
Какое утверждение верно для игры Ним с начальной позицией {2,1,1}?(каждая цифра означает число камней в соответствующей куче)
(1) первый игрок может гарантировать себе выйгрыш
(2) второй игрок может гарантировать себе выйгрыш
(3) может случиться ничья
Какое условие соответствует тому что точки math образуют систему точек общего положения?
(1) никакие k из них не лежат ни в одном k-2 мерном подпространстве
(2) точки не лежат нив одном n-2 мерном подпространстве, где n это число точек
(3) никакие 4 из них не лежат ни в одном 2 мерном подпространстве
(4) никакие 2 точки не лежат на одной прямой
Что такое сеть?
(1) множество вершин V c выделенными вершинами S T и функция math
(2) ориентированный граф у которого на ребрах написаны положительные числа
(3) это ориентированный граф у которого на ребрах написаны положительные числа и выделены две вершины: сток и исток
(4) множество вершин V c выделенными вершинами S T и функция math
Что такое сеть?
(1) это ориентированный граф у которого на ребрах написаны положительные числа и выделены две вершины: сток и исток
(2) множество вершин V c выделенными вершинами S T и функция math
(3) множество вершин V c выделенными вершинами S T и функция math
(4) ориентированный граф у которого на ребрах написаны положительные числа
С помощью чего можно решать задачу поиска образца в наборе строк?
(1) хеш таблиц
(2) суффиксных деревьев
(3) венгерского алгоритма
(4) жадного алгоритма
(5) конечных автоматов
Какая из следующих игр Ним является игрой с симетричной стратегией?
(1) {1,2,3,2,1}
(2) {4,2,1,4,1,2}
(3) {4,3,4,2}
Что такое симплекс?
(1) это набор точек общего положения
(2) это многогранник, вершины которого являются точками общего положения
(3) это тетраэдр или треугольник
Какие утверждения верны?
(1) максимальный поток ограничен суммарной пропускной способностью ребер исходящих из истока
(2) максимальный поток ограничен суммарной пропускной способностью ребер приходящих в сток
(3) максимальный поток не ограничен
(4) максимальная пропускная способность ребра в сети не превосходит максимальный поток
Какое утверждение верно?
(1) в остаточной сети пропускная способность ребер не больше чем в исходной
(2) в остаточной сети пропускная способность ребер не меньше чем в исходной
(3) в остаточной сети пропускная способность ребер может быть больше чем в исходной
Построим бор по словам "good","bad","bed","better". Какое утверждение верно?
(1) в боре 5 листовых вершин
(2) глубина бора равна 6
(3) у корня 2 потомка
Игра называется конечной, если:
(1) из любой позиции можно сделать не более чем конечное число ходов
(2) первый игрок может гарантировать конечность игры
(3) в любой момент один из игроков может сдаться и тем самым закончить игру
Пусть веса ребер полного графа заданы матрицей 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)
Как ищется путь в остаточной сети в алгоритме Энлмонса-Карпа
(1) методом поиска в ширину
(2) методом поиска в глубину
(3) с помощью ранговой эвристики
Какими свойствами обладает фунция предпотока?
(1) math
(2) math
(3) math
(4) math
(5) math
Для того чтобы решать задачу поиска подстроки в тексте, нужно построить ...
(1) бор всех суффиксов
(2) бор всех подслов
(3) бор всех префиксов
Для игры Ним {7,2,1} нимбером является:
(1) 110
(2) 100
(3) 111
(4) 1010
Какие утверждения верны для следующей матрицы 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)
Что такое чередующаяся цепь?
(1) это цепь из ребер графа, в которой нечетные ребра - это ребра из паросочетания
(2) это цепь из ребер графа, в которой четные ребра - это ребра из паросочетания
(3) это цепь нечетной длины из ребер графа в, которой четные ребра - это ребра из паросочетания
(4) это цепь нечетной длины из ребер графа, в которой четные ребра - это ребра из паросочетания
Какими свойствами обладает высотная фунция h?
(1) она равна расстоянию от вершины до стока
(2) math
(3) если math, то math
(4) если math, то math
Какие утверждения верны?
(1) каждому суффиксу исходного слова соответствует листовая вершина в боре
(2) каждой листовой вершине в боре соответствует суффикс в исходном слове
(3) каждой вершине в боре соответствует суффикс в исходном слове
(4) число вершин в боре не меньше числа суффиксов в исходном слове
Какое утвеждение верно?
(1) в игре Ним при правильной игре обоих игроков выигрывает второй игрок тогда и только тогда, когда ее нимбер оканчивается на ноль
(2) в игре Ним при правильной игре обоих игроков проигрывает второй игрок тогда и только тогда, когда ее нимбер равен нулю
(3) в игре Ним при правильной игре обоих игроков выигрывает второй игрок тогда и только тогда, когда ее нимбер равен нулю
Какое условие соответствует тому, в наборе ребер есть цикл?
(1) строки соответствующие этим ребрам в матрице инцедентности линейно зависимы
(2) строки соответствующие этим ребрам в матрице инцедентности линейно зависимы над GF(2)
(3) строки в матрице инцедентности для графа содержащего эти ребра линейно зависимы над GF(2)
Пусть двудольный граф задан следующей матрицей\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)
При выполнении каких условий можно делать операцию PUSH(u,v)?
(1) вершина uпереполнена
(2) ребро (u,v) принадлежит остаточной сети
(3) вершина v принадлежит нулевому уровню
(4) вершина u выше чем вершина v
Пусть мы имеем бор для строки "abc", и хотим из него получить бор для строки "abca"
(1) тогда нужно добавить 4 вершины и 4 суффиксных ссылки
(2) тогда нужно добавить 4 вершины и 5 суффиксных ссылок
(3) тогда нужно добавить 3 вершины и 3 суффиксных ссылки
Чему равен нимбер игры math ? (игра "ромашка" с начальной позицией 4 липестка вряд)
(1) 1
(2) 2
(3) 3
(4) 0
Какая операция отвечает за добавление нового одноэлементного множества в "структуру неперсекающихся множеств"?
(1) make_set
(2) find_set
(3) unite
Какое множество вершин называется контролирующим?
(1) такое, что любая вершина в графе соединена ребром с какой-то контролирующей
(2) такое, что любая вершина в графе соединена ребром с какой-то контролирующей или сама является контролирующей
(3) такое, что из любой вершины графа можно дойти до контролирующей по ребрам
При выполении каких условий можно делать операцию LIFT(v) ,math?
(1) вершина v переполнена
(2) ельзя протолкнуть предпоток из v ни в одну другую вершину
(3) вершина v пренадлежит нулевому уровню
(4) нельзя протолкнуть предпоток в v
Какие утверждения верны для сжатого суффиксного бора?
(1) если вершина не листовая и не корень, то у нее как минимум два потомка
(2) если вершина не листовая и не корень, то у нее может быть один потомок
(3) на ребрах записаны подслова исходного слова
(4) на ребрах записаны два числа - начало и конец подслова в исходном слове
Пусть два многочлена совпадают в n точках, при каком условии можно утверждать, что они равны друг другу?
(1) их степени не превосходят n
(2) их степени не превосходят n+1
(3) их степени не превосходят n-1
Какие из следующих систем подмножеств являются матроидами?
(1) всевозможные ациклические наборы ребер в графе G
(2) всевозможные циклические наборы ребер в графе G
(3) всевозможные наборы ребер в графе G, такие что удаление всех ребер в наборе оставляет граф связным
Какие преобразования, приводящие задачу к эквивалентный, можно делать с матрицей цен в задаче о назначениях?
(1) вычесть из всех чисел в строке константу
(2) вычесть из всех чисел в столбце константу
(3) вычесть из всех чисел на главной диагонали константу
(4) поменять местами значения в двух соседних клетках
В чем заключается алгоритм проталкивания предпотока?
(1) делать по очереди LIFT и PUSH пока это возможно
(2) делать операции LIFT и PUSH пока это возможно
(3) применять операцию LIFT пока это возможно, а потом применять операцию PUSH пока это возможно
(4) применять операцию PUSH пока это возможно, а потом применять операцию LIFT пока это возможно
Что понимается под неявной вершиной?
(1) вершина которая есть в боре, но которой не стало в суффиксном дереве из-за сжатия путей
(2) дополнительная вершина над корнем
(3) дополнительная листовая вершина
Чему равно math?
(1) 0
(2) -1
(3) 1
(4) это выражание неопредлено
Что такое покрывающее дерево?
(1) это дерево, которое содержит все вершины
(2) это дерево, которое является подграфом и содержит все вершины
(3) это дерево, которое содержит все ребра
Пусть на начало второго шага венгерского алгоритма мы работали со следующим двумя строками \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}
За какое время работает алгоритм проталкивания предпотока при оптимальной реализации?
(1) math
(2) math
(3) math
Из какой вершины может идти суффиксная ссылка в неявную вершину?
(1) из вершины у которой два сына
(2) из неявной вершины
(3) из листовой вершины
Чему равна сумма всех корней степени n из 1?
(1) n
(2) 0
(3) 1
Что такое сжатие путей?
(1) метод, позволяющий хранить пути более эффективно по памяти
(2) метод, позволяющий при повторном хождении по пути, пройти путь за O(1)
(3) замена пути в графе на ребро, соединяющее начало и конец пути
Пусть на начало пятого шага венгерского алгоритма мы работали со следующими строками \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}
В строке "mississippi" строка "mi"
(1) является суффиксом
(2) является префиксом
(3) не является ни суффиксом, ни префиксом
Как называется первая нелистовая вершина в "boundary-path"?
(1) end point
(2) active point
(3) root
Квадраты корней степени 8 из 1 это в точности ...
(1) все корни степни 4 из 1
(2) все корни степни 8 из 1
(3) первые 4 корня степени 8 из 1
Какое утверждение верно?
(1) на каждом шаге алгоритма Прима есть только одно нетривиальное дерево
(2) на каждом шаге алгоритма Крускала есть только одно нетривиальное дерево
(3) алгоритм Прима работает быстрее чем алгоритм Крускала
Вбирите верные утверждения
(1) альфа-бета отсечения это эвристика
(2) альфа-бета отсечения это точный алгоритм
(3) применение альфа-бета отсечений гарантированно увеличивает глубину продумывания в 2 раза
(4) применение альфа-бета отсечений в среднем увеличивает глубину продумывания в 2 раза
Для образца "sissisippi" значение префикс функции math
(1) 6
(2) 3
(3) 2
Какое утверждение верно?
(1) end point k-го шага это родитель active point (k+1)-го шага
(2) active point k-го шага это родитель end point (k+1)-го шага
(3) end point k-го шага это родитель active point k-го шага
Чему равно время работы врямя работы алгоритма дискретного преобразования Фурье для многочлена степени n?
(1) O(n^2)
(2) O(n*log n)
(3) O(n)
Применим монотонное преобразование к функции веса ребер. Какое утверждение верно?
(1) вес минимального покрывающего дерева не изменится
(2) минимальное покрывающее дерево не изменится
(3) может появиться новое минимальное покрывающее дерево
Какой тег соответствует жадным алгоритмам?
(1) macro
(2) scale
(3) local
(4) meta
Для строки "abcdabscabcdabia" префикс функция равна
(1) 000120012345001
(2) 000120012345601
(3) 00120012345601
Пусть явная вершина v соответствует суффиксу abc, тогда reference pair для суффикса abcde это
(1) (v, abcde)
(2) (v, de)
(3) (abc, de)
Какие утверждения верны для конечного поля?
(1) для любого элемента есть обратный
(2) любой элемент в какой-то степени равен любому другому элементу поля
(3) любой элемент является корнем из единицы
Пусть A и B два минимальных покрывающих дерева в графе G. Какое утверждение верно?
(1) веса ребер в A в точности совпадают с весами ребер в B
(2) сумма весов ребер в A в точности совпадают с суммой весов ребер в B, а значения весов могут не совпадать
(3) сумма весов ребер в A может не совпадать с суммой весов ребер в B
Сколько различных позиций (реальных шахматных) в задаче "эндшпиль" из лекции?
(1) 64*64
(2) 63*62
(3) 63*62*2
(4) 64*63*2
Чему равно время работы алгоритма Кнутта-Морриса-Пратта?
(1) O(n)
(2) O(n+m)
(3) O(nm)
Время работы алгоритма Укконена для входного слова длины n равно
(1) O(n)
(2) O(n2)
(3) O(n * log n)
Какое утверждение верно для игры Ним с начальной позицией {2,2,1}?(каждая цифра означает число камней в соответствующей куче)
(1) первый игрок может гарантировать себе выйгрыш
(2) второй игрок может гарантировать себе выйгрыш
(3) может случиться ничья
Пусть k точек в math заданы векторами math. Какое выражение соответствкет условию того что это система общего положения?
(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
Какими свойствами обладает функция потока math ?
(1) math
(2) math
(3) math
(4) math
(5) math
Какими свойствами обладает функция потока math?
(1) math
(2) math
(3) math
(4) math
(5) math
Конечный автомат решающий задачу поиска образца в наборе строк не допускает слово если ...
(1) он не может сделать очередной переход по дереву своих состояний
(2) он спустился до листовой вершины в дереве своих состояний, и при этом просмотрел все слово
(3) он просмотрел все слово, но еще не спустился до листовой вершины в дереве своих состояний
(4) он спустился до листовой вершины в дереве своих состояний, но еще не просмотрел все слово
Сколько вершин в графе иры Ним для начальной позиции {2,2}? (начальную {2,2} и конечную {0,0} тоже считать)
(1) 6
(2) 4
(3) 5
Какие утверждения верны?
(1) любое подмножество вершин симплекса задает симплекс меньшей размерности
(2) грани симплекса являются симлексами
(3) любое множество точек может быть вершинами симплекса
Как определяется остаточная сеть math ?
(1) math
(2) math
(3) math
(4) math
Какое утверждение верно?
(1) в остаточной сети могут быть только те ребра, которые были в исходной сети
(2) в остаточной сети могут появиться новые ребра
(3) в остаточной сети могут появиться новые вершины и ребра соединяющие их со старыми вершинами
Построим бор по словам "good","bad","bed","better". Какое утверждение верно?
(1) в боре 4 листовых вершин
(2) глубина бора равна 6
(3) у корня 4 потомка
Игра называется нейтральной, если:
(1) в ней возможна ничья
(2) из любой позиции множество ходов первого и второго игроков совпадают
(3) в ее графе нет циклов
Пусть веса ребер полного графа заданы матрицей 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)
Что такое паросочетание?
(1) это разбиение вершин графа на пары
(2) это подмножество ребер двудольного графа, такое что в нем нет ребер с общими вершинами
(3) это пары вершин и инцидентных им ребер
Какие свойства общие для функций потока и предпотока?
(1) math
(2) math
(3) math
Для того чтобы построить бор по слову длины n надо ...
(1) O(n3) операций
(2) O(n2) операций
(3) O(n*log n ) операций
Для игры Ним {3,3,2,1} нимбером является:
(1) 10
(2) 110
(3) 101
Какие утверждения верны для следующей матрицы 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)
Что такое симметрическая разность множеств A и B?
(1) это элементы которые принадлежат A или B, но не принадлежат их пересечению
(2) это элементы которые принадлежат A или B
(3) это элементы которые принадлежат пересечению A и B
(4) это элементы которые не принадлежат ни A ,ни B
Какая формальная запись соответствут условию "если ребро идет круто вниз, то по нему течет максимальный поток"?
(1) math
(2) math
(3) math
Какие утвеждения верны?
(1) куффиксная ссылка из вершины для строки s, ведет в вершину для строки получающейся из s отрезанием первого символа
(2) суффиксная ссылка из вершины для строки s, ведет в вершину для строки получающейся из s отрезанием какого-то количества первых символов
(3) суффиксная ссылка из вершины для строки s, ведет в вершину для строки соответствующей наиьольшему собственному суффиксу s
Какие утверждения верны?
(1) если нимбер игры нулевой, то на следующий ход он обязательно станет ненулевым
(2) если нимбер игры не нулевой, то сделав один ход его всегда можно сделать нулевым
(3) если нимбер игры не нулевой, то на следующий ход он обязательно станет нулевым
(4) если нимбер нулевой, то при правильной игре выигрывает второй игрок
Если набор строк в матрице инцедентности линейно независим над GF(2), то
(1) в соответствующем наборе ребер есть цикл
(2) число ребер в этом наборе нечетно
(3) соответствующий набор ребер ацикличен
Пусть двудольный граф задан следующей матрицей\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)
Чему равна величина проталкиваемого потока на шаге PUSH?
(1) math
(2) math
(3) math
Пусть мы имеем бор для строки "abca", и хотим из него получить бор для строки "abcad"
(1) тогда нужно добавить 4 вершины и 4 суффиксных ссылки
(2) тогда нужно добавить 4 вершины и 5 суффиксных ссылок
(3) тогда нужно добавить 5 вершины и 5 суффиксных ссылки
Чему равен нимбер игры math ?(игра "ромашка" с начальной позицией 3 лепестка вряд)
(1) 0
(2) 1
(3) 2
(4) 3
Какая операция отвечает за нахождение представителя множества в "структуре неперсекающихся множеств"?
(1) make_set
(2) find_set
(3) unite
Что известно про минимальное контролирующее множество в двудольном графе?
(1) его мощность не больше мощность максимального паросочетания
(2) его мощность не меньше мощность максимального паросочетания
(3) его мощность может быть больше мощности максимального паросочетания
(4) его мощность может быть меньше мощности максимального паросочетания
Какое утверждение верно, если на шаге LIFT подымается вершина v?
(1) в остаточной сети math
(2) math только для вершин u, которые выше v
(3) math только для вершин u, которые выше v
Пусть у нас усть суффиксное дереводля слова s1 на очередном шаге мы добавляем один символ и строим суффиксное дерево для слова s2. Тогда вершине "end point" соответствеут ...
(1) наибольший суффикс слова s2, являющийся суффиксом s1
(2) наибольший суффикс слова s2 являющийся подсловом s1
(3) наибольший суффикс слова s2, являющийся префиксом s1
В скольких точках должны совпадать два многочлена степени n, чтобы можно было утверждать что они совпадают всюду?
(1) в n+1 точке
(2) в n точках
(3) в n-1 точке
Что такое матроид?
(1) пара из множества math и системы подмножеств в math, удовлетворяющая трем аксиомам матроидов
(2) набор линейнонезависимых подстрок в матрице
(3) многомерная матрица
Почему мы хотим иметь матрицу в которой нет отрицательных значений и моного нулей(настолько много, что оптимальное назначение имеет нулевую стоимость)?
(1) в такой задаче будет меньше суммарная стоимость работ
(2) в такой постанове задача принадлежит NP
(3) потому что такая задача сводится к задаче о поиске максимального паросочетания
Какие утверждения верны, если алгоритм проталкивания предпотока остановился?
(1) переполненных вершин нет
(2) получившийся поток является максимальным потоком
(3) величина получившегося предпотока равна величине максимального сечения
По какой формуле можно посчитать количество неявных вершин в суффиксом дереве для слова s
(1) (количество символов в s) - (количество вершин в дереве) + (+2 из-за dummy и корня)
(2) (количество символов в s) - (количество ребер в дереве) + (+2 из-за dummy и корня)
(3) (количество символов в s) - (количество ребер в дереве)
(4) (количество символов в s) - (количество вершин в дереве)
Чему равно math?
(1) math
(2) math
(3) math
Какие утверждения верны?
(1) покрывающее дерево единственно
(2) если граф связен, то покрывающеее дерево существует
(3) покрывающее дерево всегда единственно
(4) покрывающее дерево может не существовать для данного графа
Пусть на начало второго шага венгерского алгоритма мы работали со следующим двумя строками \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}
Что нужно для того чтобы алгоритм проталкивания предпотока работал за math?
(1) из пары возможных действий LIFT и PUSH всегда выбирать LIFT
(2) надо обрабатывать вершины последовательно с помощью операции DISCHARGE
(3) из пары возможных действий LIFT и PUSH всегда выбирать PUSH
Проблема суффиксных ссылок из листьев в неявные вершины решается с помощью
(1) добавления этих неявных вершин в дерево
(2) отказа от суффиксных ссылок в листьях
(3) добавления ссылок на фиктивные вершины
Чему равны math в дискретном преобразовании Фурье многочлена math
(1) math
(2) math
(3) math
При применении ранговой эвристики максимальная глубина дерева (отвечающего за одно из множеств в структуре непересекающихся подмножеств)
(1) линейна по числу элементов в множестве
(2) сублагорифмична по числу элементов в множестве
(3) лагорифмична по числу элементов в множестве
В строке "abaaba" строка "aba"
(1) является суффиксом
(2) является префиксом
(3) является и суффиксом, и префиксом
Где использутся символ бесконечности?
(1) может использоваться в любой вершине
(2) в неявных вершинах
(3) в листьях
Квадраты корней степени 10 из 1 это в точности ...
(1) все корни степни 5 из 1
(2) все корни степни 10 из 1
(3) первые 5 корней степени 10 из 1
Чему равно время работы алгоритма Прима?
(1) O(V*logE)
(2) O(E+V)
(3) O(E*logV)
Какие идеи могут улучшить алгоритм поиска лучшего хода в "middle game" позиции?
(1) альфа-бета отсечения
(2) упорядочивание просматриваемых ходов по эвристическому признаку
(3) эвристическое отсечение
(4) кэширование
(5) пристрелка в узком окне
Для образца "sissisippi" значение префикс функции math
(1) 2
(2) 1
(3) 3
Какое утверждение верно?
(1) active point и end point это два названия одного и того же объекта
(2) active point и end point никогда не совпадают
(3) active point и end point могут совпадать
Чему равно время работы алгоритма обратного дискретного преобразования Фурье для многочлена степени n?
(1) O(n^2)
(2) O(n)
(3) O(n*log n)
Применим монотонное преобразование к функции веса ребер. Какое утверждение верно?
(1) вес максимального покрывающего дерева не изменится
(2) максимальное покрывающее дерево не изменится
(3) может появиться новое максимальное покрывающее дерево
Какой тег соответствует сливанию групп городов в один в задаче коммивояжера?
(1) macro
(2) scale
(3) local
(4) meta
Для строки "abcdabscabcdabid" префикс функция равна
(1) 000120012345601
(2) 000120012345600
(3) 00120012345601
Пусть (v, de) это reference pair для префикса abcde, тогда
(1) v - это явная вершина
(2) префиксу abcde соответствует явная вершина
(3) v соответствует префиксу abc
(4) v соответствует префиксу abcde
Сколько примитивных корней степени 5 из 1?
(1) 4
(2) 5
(3) 1
Пусть A и B два максимальных покрывающих дерева в графе G. Какое утверждение верно?
(1) веса ребер в A в точности совпадают с весами ребер в B
(2) сумма весов ребер в A в точности совпадают с суммой весов ребер в B, а значения весов могут не совпадать
(3) сумма весов ребер в A может не совпадать с суммой весов ребер в B
Какой тег соответствует динамическому программированию?
(1) macro
(2) scale
(3) local
(4) meta
(5) cache
Чему рано время построения префикс функции для строки длины m?
(1) O(m)
(2) O(m^2)
(3) O(m^3)
Память необходимая для хранения суффиксного дерева для входного слова длины n из алфавита мощности m равна
(1) O(n*m)
(2) O(n2)
(3) O(n)
Какое утверждение верно для игры Ним с начальной позицией {2,2,3}?(каждая цифра означает число камней в соответствующей куче)
(1) первый игрок может гарантировать себе выйгрыш
(2) второй игрок может гарантировать себе выйгрыш
(3) может случиться ничья
Пусть k точек в math заданы векторами math. Какое выражение соответствует условию того что это система общего положения?
(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
Что такое величина потока math?
(1) math
(2) math
(3) math
(4) math
Как определяется остаточная сеть math?
(1) math
(2) math
(3) math
(4) math
Конечный автомат решающий задачу поиска образца в наборе строк длины которых math работает за время
(1) math
(2) math
(3) math
Нулевым позициям в графе игры Ним соответствуют
(1) позичии в которых первый игрок может гарантировать себе выйгрыш
(2) позичии в которых второй игрок может гарантировать себе выйгрыш
(3) позиции в которых в одной из куч 0 камней
Какие из следующих множеств являются симплексами?
(1) октайдер
(2) отрезок
(3) прямая
(4) триугольник
(5) тетрайдер
(6) куб
Если в остаточной сети существует путь соединяющий s и t, то
(1) он единственен
(2) добавив поток по нему мы получим максимальный поток
(3) поток не максимален
Какое утверждение верно?
(1) math
(2) math
(3) math
(4) math
Построим бор по словам "good","bad","bed","better". Какое утверждение верно?
(1) в боре 5 листовых вершин
(2) глубина бора равна 7
(3) у корня 4 потомка
Какая из этих игр является конечной?
(1) шахматы
(2) крестики-нолики
(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)
Свободные вершины это...
(1) вершины двудольного графа, не являющиеся вершинами ребер из паросочетания
(2) вершины из которых не идет ребер
(3) вершины степени один в графе
Какие утверждения верны, сли math?
(1) u это переполненная вершина
(2) поток приходящий в вершину u больше уходящего потока
(3) поток уходящий из вершины u больше приходящего потока
(4) math и math
Для того чтобы хранить бор для слова длины n надо
(1) O(n3) памяти
(2) O(n2) памяти
(3) O(n*log n ) памяти
Для игры Ним {3,3,2,7} нимбером является:
(1) 101
(2) 111
(3) 110
Какие утверждения верны для следующей матрицы 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)
Будем искать максимальное паросочетание следующим способом: на каждом шаге ищем чередующийся путь с помощью поиска в глубину и увеличиваем имеющееся паросочетание с помощью этого пути. Пусть m и n размеры долей. Чему равно время работы алгоритма?
(1) min( O(n2*m), O(n*m2))
(2) O(n2*m2)
(3) max( O(n2*m), O(n*m2))
(4) O(n*m)
Пусть h - правильная высотная функция, а ребро (u,v) круто идет вниз. Какие утверждения тогда верны?
(1) math
(2) math
(3) math
(4) math
(5) math
Сколько суффиксных ссылок в боре на n вершинах?
(1) n
(2) 2*n
(3) n-1
Как определяется нимбер произвольной игры A?
(1) math
(2) math
(3) math
Если в графе степень всех вершин равна двум, то
(1) в графе нет циклов
(2) в графе обязательно найдется цикл
(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
Пусть величину 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;
Пусть мы имеем бор для строки "aba", и хотим из него получить бор для строки "abaa"
(1) тогда нужно добавить 4 вершины и 4 суффиксных ссылки
(2) тогда нужно добавить 4 вершины и 5 суффиксных ссылок
(3) тогда нужно добавить 3 вершины и 3 суффиксных ссылки
Что является аналогом нимберов для цветных игр?
(1) числа Конвея
(2) цветные нимберы
(3) числа Хакенбуша
Какая операция отвечает за объединение двух множеств в "структуру неперсекающихся множеств"?
(1) make_set
(2) find_set
(3) unite
Какова сложность алгоритма нахождения минимального контролирующего множества в двудольном графе?
(1) O(n)
(2) O(n^2)
(3) O(n^3)
(4) O(n^2*log(n))
Какой псевдокод отвечает операции LIFT?
(1) LIFT(v) { h(v):= 1 + math }
(2) LIFT(v) { h(v)+= 1; }
(3) LIFT(v) { h(v):= 1 + math }
Вершина "dummy" добавляется для того чтобы ...
(1) не писать лишние if в коде алгоритма
(2) усложнить алгоритм
(3) увеличить высоту дерева
Интерполяционный многочлен Лагранжа это
(1) многочлен принимающий заданные значения в заданных точках
(2) многочлен принимающий нулевые значения в заданных точках
(3) многочлен который принимающий нулевые значения во всех кроме одной заданной точки, а в этой точке равен единице
Как формулируется третья аксиома матроидов?
(1) Если math и мощность math больше мощности math, то существует math такой, что math
(2) Если math и мощность math больше мощности math, то существует math такой, что math
(3) Если math , то существует math такой, что math
Пусть в задаче о назначениях N работ. Все элементы матрици цен неотрицательны. В матрице цен есть подматрица размера m*n без нулевых элементов и m+n>N. Какие утверждения тогда верны?
(1) можно расставить N ладей на нулевых значениях в матрице, так чтоб они не били друг друга
(2) стоимость оптимального назначения работ больше нуля
(3) вычитая и добавляя к строкам и столбцам константы можно уменьшить сумму элементов матрицы, оставив при этом все элементы неотрицательными
(4) оптимального назначения не существует
Какие утверждения верны?
(1) пусть math остаточная сеть на произвольном шаге алгоритма проталкивания предпотока, тогда из истока сток не достижим
(2) любой путь соединяющий исток со стоком всегда содержит круто идущее вниз ребро
(3) алгоритм может неостановиться при иррациональных пропускных способностях дуг
Какие вершины являются явными?
(1) корень
(2) dummy
(3) вершины дерева степени два и более
(4) листовые вершины
(5) вершины дерева у которых два и более ребенка
Что такое примитивный корень степени n из 1?
(1) это такой корень, что среди его целых степеней есть все остальные корни степени n
(2) это такой корень, что среди его степеней есть все остальные корни степени n
(3) это такой корень, что среди его целых степеней есть все остальные корни
Какие утверждение верно?
(1) самое легкое ребро принадлежит минимальному покрывающему дереву
(2) самое легкое ребро может не пренадлежать минимальному покрывающему дереву
(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}
В алгоритме LIFT-TO-FRONT
(1) операции PUSH и LIFT используются апосредованно через DISCHARGE
(2) DISCHARGE для каждой вершины применяется только один раз
(3) после применения DISCHARGE вершина может быть перенесена в начало списка обрабатываемых вершин
В каком порядке идут вершины в "boundary-path"?
(1) сперва листовые, потом неявные, потом не листовые явные
(2) сперва листовые, потом не листовые явные
(3) сперва листовые, потом неявные и не листовые явные вперемешку
Как выражаются math в обратном дискретном преобразовании Фурье?
(1) math
(2) math
(3) math
Какие идеи используются в алгоритме Крускала?
(1) сжатие путей
(2) обход в ширину
(3) ранговая эвристика
(4) жадность
Пусть на начало пятого шага венгерского алгоритма мы работали со следующим двумя строками \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}
В строке "abacaba" строка "ca"
(1) является суффиксом
(2) является префиксом
(3) не является ни суффиксом, ни префиксом
Что позволяет символ бесконечности?
(1) непроизводить операций с листьями
(2) быстро просматривать листья
(3) не производить операций с листьями если структура дерева не меняется
Квадраты корней степени 9 из 1 это в точности ...
(1) все корни степни 9 из 1
(2) все корни степни 5 из 1
(3) все корни степни 3 из 1
Чему равно время работы алгоритма Крускала?
(1) O(V*logE)
(2) O(E+V)
(3) O(E*logV)
В чем заключается эффект горизонта?
(1) программа не замечает вилки
(2) атаки соперника могут идти дальше чем глубина продумывания, и поэтому программы может не заметить улучшение своей позиции
(3) глубина продумывания ограничена
Для образца "sissisippi" значение префикс функции math
(1) 3
(2) 5
(3) 0
В алгоритме Укконена при добавлении нового символа
(1) просматривается весь новый boundary-path
(2) просматривается только та часть boundary-path, которая идет после active point
(3) просматривается только та часть boundary-path, которая идет между active point и end point
Какая абривеатура означает обратное дискретное преобразование Фурье?
(1) math
(2) math
(3) math
(4) math
Применим монотонное преобразование к функции веса ребер. Какие утверждения верны?
(1) в каждом разрезе самое легкое ребро останится прежним
(2) в каждом разрезе самое тяжелое ребро останится прежним
(3) вес самого легкого ребра останется прежним
Какие теги соответствуют генетическим алгоритмам?
(1) macro
(2) scale
(3) local
(4) meta
(5) competition
(6) gready
Для строки "abcdabacabcdabid" префикс функция равна
(1) 00121012345601
(2) 000120012345601
(3) 000121012345601
Какие утверждения верны?
(1) для каждого суффикса существует единственная reference pair
(2) для каждого суффикса существует единственная каноническая reference pair
(3) reference pair существует только для неявных вершин
(4) reference pair существует для всех вершин
Чему равна сумма всех примитивных корней степени 5 из 1?
(1) 0
(2) 1
(3) -1
Пусть в графе G пять разных минимальных покрывающих деревьев. Вова загодал K - одно из них. Пятя знает граф G но не знает какое минимальное покрывающее дерево, которое загадал Петя. Какие утверждения верны?
(1) Петя может назвать вес минимального ребра в K
(2) Петя может назвать веса всех ребер в K
(3) Петя может назвать все вершины K
(4) Петя может назвать все ребра K
Какова сложность по памяти задачи "эндшпиль"?
(1) O(64)
(2) O(642)
(3) O(643)
Задача поиска наименьшего периода в периодической строке длины n решается за время
(1) O(n2)
(2) O(n*log n)
(3) O(n)
Память необходимая для хранения суффиксного массива для входного слова длины n из алфавита мощности m равна
(1) O(n*m)
(2) O(n2)
(3) O(n)