База ответов ИНТУИТ

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

Количество вопросов - 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 ?

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

Что нужно для того чтобы алгоритм проталкивания предпотока работал за O(V^3)?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Чему равны b_j в дискретном преобразовании Фурье многочлена 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) круто идет вниз. Какие утверждения тогда верны?

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

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

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

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

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

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

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

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

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

Какие утверждения верны, сли e(u) > 0 ?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть (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

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

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

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

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