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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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