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

Количество вопросов - 179

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

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

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

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

Где использутся символ бесконечности?

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

Из какой вершины может идти суффиксная ссылка в неявную вершину?

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

Пусть два многочлена совпадают в n точках, при каком условии можно утверждать, что они равны друг другу?

Квадраты корней степени 10 из 1 это в точности ...

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

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

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

Вершина "dummy" добавляется для того чтобы ...

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

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

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

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

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

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

Сколько суффиксных ссылок в боре на n вершинах?

Какие утверждения верны для следующей матрицы $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}$ ?

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

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

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

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

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

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

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

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

Какое условие соответствует тому что точки $\left\{ a_i \right\}$ образуют систему точек общего положения?

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

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

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

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

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

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

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

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

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

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

Что такое величина потока $\left| f \right|$ ?

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

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

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

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

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

Пусть на начало пятого шага венгерского алгоритма мы работали со следующими строками $\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}$ . Как будут выглядеть эти строки к концу пятого шага?

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

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

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

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

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

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

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

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

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

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

Для образца "sissisippi" значение префикс функции $\pi (6) = ?$

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

Конечный автомат решающий задачу поиска образца в наборе строк длины которых работает за время

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

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

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

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

Какие утверждения верны для сжатого суффиксного бора?

По какой формуле можно посчитать количество неявных вершин в суффиксом дереве для слова s

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

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

Память необходимая для хранения суффиксного массива для входного слова длины n из алфавита мощности m равна

Нулевым позициям в графе игры Ним соответствуют

Игра называется нейтральной, если:

Чему равен нимбер игры ?(игра "ромашка" с начальной позицией 3 лепестка вряд)

Интерполяционный многочлен Лагранжа это

Чему равно $e^{i\pi}$ ?

Чему равны в дискретном преобразовании Фурье многочлена $p(x) = a_n\cdot x^n + \ldots + a_1 \cdot x + a_0$

Квадраты корней степени 9 из 1 это в точности ...

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

Сколько примитивных корней степени 5 из 1?

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

Квадраты корней степени 8 из 1 это в точности ...

Для того чтобы решать задачу поиска подстроки в тексте, нужно построить ...

Для образца "sissisippi" значение префикс функции $\pi (8) = ?$

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

Пусть двудольный граф задан следующей матрицей $\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}$ Чему равен размер максимального паросочетания?

Чему равно $\sqrt{i}$ ?

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

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

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

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

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

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

Проблема суффиксных ссылок из листьев в неявные вершины решается с помощью

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

Чему равна сумма всех примитивных корней степени 5 из 1?

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

Какими свойствами обладает функция потока $f:V\times V \rightarrow R_+$ ?

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

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

Что является аналогом нимберов для цветных игр?

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

Игра называется конечной, если:

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

В каком порядке идут вершины в "boundary-path"?

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

С помощью чего можно решать задачу поиска образца в наборе строк?

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть k точек в $R_{k-1}$ заданы векторами $\left\{ \vec{v_i} \right\}$ . Какое выражение соответствкет условию того что это система общего положения?

В скольких точках должны совпадать два многочлена степени n, чтобы можно было утверждать что они совпадают всюду?

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

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

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

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

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

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

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

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

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

Память необходимая для хранения суффиксного дерева для входного слова длины n из алфавита мощности m равна

Пусть на начало пятого шага венгерского алгоритма мы работали со следующим двумя строками $\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}$ как будут выглядеть эти строки к концу пятого шага?

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

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

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

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

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

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

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

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

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

Чему равен нимбер игры ? (игра "ромашка" с начальной позицией 4 липестка вряд)

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

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

Пусть (v, de) это reference pair для префикса abcde, тогда

Пусть k точек в $R_{k-1}$ заданы векторами $\left\{ \vec{v_i} \right\}$ . Какое выражение соответствует условию того что это система общего положения?

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

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

Какие утверждения верны для следующей матрицы $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}$ ?

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

Какими свойствами обладает функция потока $f:V\times V \rightarrow R_+$ ?

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

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

Для образца "sissisippi" значение префикс функции $\pi (3) = ?$

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

Как называется первая нелистовая вершина в "boundary-path"?

Пусть явная вершина v соответствует суффиксу abc, тогда reference pair для суффикса abcde это

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

Пусть у нас усть суффиксное дереводля слова s1 на очередном шаге мы добавляем один символ и строим суффиксное дерево для слова s2. Тогда вершине "end point" соответствеут ...

Какие вершины являются явными?

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

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

Какие утверждения верны для следующей матрицы $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}$ ?

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

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

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

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

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

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

Время работы алгоритма Укконена для входного слова длины n равно

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

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

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

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

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

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

Конечный автомат решающий задачу поиска образца в наборе строк не допускает слово если ...

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

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