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

14.10.2015 Вопросы Комментарии отключены

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть двудольный граф задан следующей матрицей $\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 & 0 & 4\ 3 & 1 & 0 & 2 & 3\\ 3 & 0 & 2 & 2 & 3\\ 0 & 1 & 2 & 2 & 3\\ 3 & 2 & 2 & 1 & 2\\ \end{pmatrix}$ как будут выглядеть эти строки к концу пятого шага?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В строке «mississippi» строка «mi»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Comments are closed.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Какие утверждения верны для следующей матрицы ?

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

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

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

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

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

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

Пусть на начало второго шага венгерского алгоритма мы работали со следующим двумя строками как будут выглядеть эти строки к концу второго шага?

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

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

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

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

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

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

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

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

Пусть на начало второго шага венгерского алгоритма мы работали со следующим двумя строками как будут выглядеть эти строки к концу второго шага?

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

Пусть на начало второго шага венгерского алгоритма мы работали со следующим двумя строками как будут выглядеть эти строки к концу второго шага?

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

Пусть на начало пятого шага венгерского алгоритма мы работали со следующим двумя строками как будут выглядеть эти строки к концу пятого шага?

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

Что такое величина потока ?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В строке «mississippi» строка «mi»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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