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

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

Курс посвящён теории алгоритмов и элементам дискретной математики. Основная цель курса - научиться эффективно решать алгоритмические задачи, вооружиться фундаментальными идеями и методами, выработать системный подход к решению алгоритмических задач.

Список вопросов:

# Какое утверждение верно для игры Ним с начальной позицией {2,1,1}?(каждая цифра означает число камней в соответствующей куче)
# Какое утверждение верно для игры Ним с начальной позицией {2,2,1}?(каждая цифра означает число камней в соответствующей куче)
# Какое утверждение верно для игры Ним с начальной позицией {2,2,3}?(каждая цифра означает число камней в соответствующей куче)
# Какая из следующих игр Ним является игрой с симетричной стратегией?
# Сколько вершин в графе иры Ним для начальной позиции {2,2}? (начальную {2,2} и конечную {0,0} тоже считать)
# Нулевым позициям в графе игры Ним соответствуют
# Игра называется конечной, если:
# Игра называется нейтральной, если:
# Какая из этих игр является конечной?
# Для игры Ним {7,2,1} нимбером является:
# Для игры Ним {3,3,2,1} нимбером является:
# Для игры Ним {3,3,2,7} нимбером является:
# Какое утвеждение верно?
# Какие утверждения верны?
# Как определяется нимбер произвольной игры A?
# Чему равен нимбер игры ? (игра "ромашка" с начальной позицией 4 липестка вряд)
# Чему равен нимбер игры ?(игра "ромашка" с начальной позицией 3 лепестка вряд)
# Что является аналогом нимберов для цветных игр?
# Пусть два многочлена совпадают в n точках, при каком условии можно утверждать, что они равны друг другу?
# В скольких точках должны совпадать два многочлена степени n, чтобы можно было утверждать что они совпадают всюду?
# Интерполяционный многочлен Лагранжа это
# Чему равно ?
# Чему равно ?
# Что такое примитивный корень степени n из 1?
# Чему равна сумма всех корней степени n из 1?
# Чему равны в дискретном преобразовании Фурье многочлена
# Как выражаются в обратном дискретном преобразовании Фурье?
# Квадраты корней степени 8 из 1 это в точности ...
# Квадраты корней степени 10 из 1 это в точности ...
# Квадраты корней степени 9 из 1 это в точности ...
# Чему равно время работы врямя работы алгоритма дискретного преобразования Фурье для многочлена степени n?
# Чему равно время работы алгоритма обратного дискретного преобразования Фурье для многочлена степени n?
# Какая абривеатура означает обратное дискретное преобразование Фурье?
# Какие утверждения верны для конечного поля?
# Сколько примитивных корней степени 5 из 1?
# Чему равна сумма всех примитивных корней степени 5 из 1?
# Какое условие соответствует тому что точки образуют систему точек общего положения?
# Пусть k точек в заданы векторами . Какое выражение соответствкет условию того что это система общего положения?
# Пусть k точек в заданы векторами . Какое выражение соответствует условию того что это система общего положения?
# Что такое симплекс?
# Какие утверждения верны?
# Какие из следующих множеств являются симплексами?
# Пусть веса ребер полного графа заданы матрицей A= \begin{pmatrix} - & 2 & 4 & 5 \\ 2 & - & 1 & 1 \\ 4 & 1 & - & 3 \\ 5 & 1 & 3 & - \\ \end{pmatrix}. В каком порядке жадный алгоритм будет выбирать ребра максимального покрывающего поддерева?
# Пусть веса ребер полного графа заданы матрицей A= \begin{pmatrix} - & 6 & 4 & 3 \\ 6 & - & 3 & 5 \\ 4 & 3 & - & 1 \\ 3 & 5 & 1 & - \\ \end{pmatrix}. В каком порядке жадный алгоритм будет выбирать ребра максимального покрывающего поддерева?
# Пусть веса ребер полного графа заданы матрицей A= \begin{pmatrix} - & 100 & -4 & -5 \\ 100 & - & -2 & -1 \\ -4 & -2 & - & -3 \\ -5 & -1 & -3 & - \\ \end{pmatrix}. В каком порядке жадный алгоритм будет выбирать ребра максимального покрывающего поддерева?
# Какие утверждения верны для следующей матрицы 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}?
# Какие утверждения верны для следующей матрицы 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= \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}?
# Какое условие соответствует тому, в наборе ребер есть цикл?
# Если набор строк в матрице инцедентности линейно независим над GF(2), то
# Если в графе степень всех вершин равна двум, то
# Какая операция отвечает за добавление нового одноэлементного множества в "структуру неперсекающихся множеств"?
# Какая операция отвечает за нахождение представителя множества в "структуре неперсекающихся множеств"?
# Какая операция отвечает за объединение двух множеств в "структуру неперсекающихся множеств"?
# Какие из следующих систем подмножеств являются матроидами?
# Что такое матроид?
# Как формулируется третья аксиома матроидов?
# Что такое покрывающее дерево?
# Какие утверждения верны?
# Какие утверждение верно?
# Что такое сжатие путей?
# При применении ранговой эвристики максимальная глубина дерева (отвечающего за одно из множеств в структуре непересекающихся подмножеств)
# Какие идеи используются в алгоритме Крускала?
# Какое утверждение верно?
# Чему равно время работы алгоритма Прима?
# Чему равно время работы алгоритма Крускала?
# Применим монотонное преобразование к функции веса ребер. Какое утверждение верно?
# Применим монотонное преобразование к функции веса ребер. Какое утверждение верно?
# Применим монотонное преобразование к функции веса ребер. Какие утверждения верны?
# Пусть A и B два минимальных покрывающих дерева в графе G. Какое утверждение верно?
# Пусть A и B два максимальных покрывающих дерева в графе G. Какое утверждение верно?
# Пусть в графе G пять разных минимальных покрывающих деревьев. Вова загодал K - одно из них. Пятя знает граф G но не знает какое минимальное покрывающее дерево, которое загадал Петя. Какие утверждения верны?
# Что такое сеть?
# Какими свойствами обладает функция потока ?
# Что такое величина потока ?
# Какие утверждения верны?
# Как определяется остаточная сеть ?
# Если в остаточной сети существует путь соединяющий s и t, то
# Как ищется путь в остаточной сети в алгоритме Энлмонса-Карпа
# Что такое паросочетание?
# Свободные вершины это...
# Что такое чередующаяся цепь?
# Что такое симметрическая разность множеств A и B?
# Будем искать максимальное паросочетание следующим способом: на каждом шаге ищем чередующийся путь с помощью поиска в глубину и увеличиваем имеющееся паросочетание с помощью этого пути. Пусть 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} Чему равен размер максимального паросочетания?
# Пусть двудольный граф задан следующей матрицей\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} 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} Чему равен размер максимального паросочетания?
# Какое множество вершин называется контролирующим?
# Что известно про минимальное контролирующее множество в двудольном графе?
# Какова сложность алгоритма нахождения минимального контролирующего множества в двудольном графе?
# Какие преобразования, приводящие задачу к эквивалентный, можно делать с матрицей цен в задаче о назначениях?
# Почему мы хотим иметь матрицу в которой нет отрицательных значений и моного нулей(настолько много, что оптимальное назначение имеет нулевую стоимость)?
# Пусть в задаче о назначениях N работ. Все элементы матрици цен неотрицательны. В матрице цен есть подматрица размера m*n без нулевых элементов и m+n>N. Какие утверждения тогда верны?
# Пусть на начало второго шага венгерского алгоритма мы работали со следующим двумя строками \begin{pmatrix} 3 & 0 & 3 & 5 & 4\\ 3 & 1 & 2 & 2 & 3\\ \end{pmatrix} как будут выглядеть эти строки к концу второго шага?
# Пусть на начало второго шага венгерского алгоритма мы работали со следующим двумя строками \begin{pmatrix} 3 & 0 & 1 & 5 & 4\\ 3 & 1 & 3 & 8 & 3\\ \end{pmatrix} как будут выглядеть эти строки к концу второго шага?
# Пусть на начало второго шага венгерского алгоритма мы работали со следующим двумя строками \begin{pmatrix} 3 & 0 & 1 & 5 & 4\\ 3 & 1 & 2 & 8 & 2\\ \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}. Как будут выглядеть эти строки к концу пятого шага?
# Пусть на начало пятого шага венгерского алгоритма мы работали со следующим двумя строками \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} как будут выглядеть эти строки к концу пятого шага?
# Вбирите верные утверждения
# Какие идеи могут улучшить алгоритм поиска лучшего хода в "middle game" позиции?
# В чем заключается эффект горизонта?
# Какой тег соответствует жадным алгоритмам?
# Какой тег соответствует сливанию групп городов в один в задаче коммивояжера?
# Какие теги соответствуют генетическим алгоритмам?
# Сколько различных позиций (реальных шахматных) в задаче "эндшпиль" из лекции?
# Какой тег соответствует динамическому программированию?
# Какова сложность по памяти задачи "эндшпиль"?
# Что такое сеть?
# Какими свойствами обладает функция потока ?
# Как определяется остаточная сеть ?
# Какое утверждение верно?
# Какое утверждение верно?
# Какое утверждение верно?
# Какими свойствами обладает фунция предпотока?
# Какие свойства общие для функций потока и предпотока?
# Какие утверждения верны, сли ?
# Какими свойствами обладает высотная фунция h?
# Какая формальная запись соответствут условию "если ребро идет круто вниз, то по нему течет максимальный поток"?
# Пусть h - правильная высотная функция, а ребро (u,v) круто идет вниз. Какие утверждения тогда верны?
# При выполнении каких условий можно делать операцию PUSH(u,v)?
# Чему равна величина проталкиваемого потока на шаге PUSH?
# Пусть величину d протолкнули на шаге PUSH по ребру (u,v). Какой код тогда отвечает за изменение потоков и излишков?
# При выполении каких условий можно делать операцию LIFT(v) ,?
# Какое утверждение верно, если на шаге LIFT подымается вершина v?
# Какой псевдокод отвечает операции LIFT?
# В чем заключается алгоритм проталкивания предпотока?
# Какие утверждения верны, если алгоритм проталкивания предпотока остановился?
# Какие утверждения верны?
# За какое время работает алгоритм проталкивания предпотока при оптимальной реализации?
# Что нужно для того чтобы алгоритм проталкивания предпотока работал за ?
# В алгоритме LIFT-TO-FRONT
# В строке "mississippi" строка "mi"
# В строке "abaaba" строка "aba"
# В строке "abacaba" строка "ca"
# Для образца "sissisippi" значение префикс функции
# Для образца "sissisippi" значение префикс функции
# Для образца "sissisippi" значение префикс функции
# Для строки "abcdabscabcdabia" префикс функция равна
# Для строки "abcdabscabcdabid" префикс функция равна
# Для строки "abcdabacabcdabid" префикс функция равна
# Чему равно время работы алгоритма Кнутта-Морриса-Пратта?
# Чему рано время построения префикс функции для строки длины m?
# Задача поиска наименьшего периода в периодической строке длины n решается за время
# С помощью чего можно решать задачу поиска образца в наборе строк?
# Конечный автомат решающий задачу поиска образца в наборе строк не допускает слово если ...
# Конечный автомат решающий задачу поиска образца в наборе строк длины которых работает за время
# Построим бор по словам "good","bad","bed","better". Какое утверждение верно?
# Построим бор по словам "good","bad","bed","better". Какое утверждение верно?
# Построим бор по словам "good","bad","bed","better". Какое утверждение верно?
# Для того чтобы решать задачу поиска подстроки в тексте, нужно построить ...
# Для того чтобы построить бор по слову длины n надо ...
# Для того чтобы хранить бор для слова длины n надо
# Какие утверждения верны?
# Какие утвеждения верны?
# Сколько суффиксных ссылок в боре на n вершинах?
# Пусть мы имеем бор для строки "abc", и хотим из него получить бор для строки "abca"
# Пусть мы имеем бор для строки "abca", и хотим из него получить бор для строки "abcad"
# Пусть мы имеем бор для строки "aba", и хотим из него получить бор для строки "abaa"
# Какие утверждения верны для сжатого суффиксного бора?
# Пусть у нас усть суффиксное дереводля слова s1 на очередном шаге мы добавляем один символ и строим суффиксное дерево для слова s2. Тогда вершине "end point" соответствеут ...
# Вершина "dummy" добавляется для того чтобы ...
# Что понимается под неявной вершиной?
# По какой формуле можно посчитать количество неявных вершин в суффиксом дереве для слова s
# Какие вершины являются явными?
# Из какой вершины может идти суффиксная ссылка в неявную вершину?
# Проблема суффиксных ссылок из листьев в неявные вершины решается с помощью
# В каком порядке идут вершины в "boundary-path"?
# Как называется первая нелистовая вершина в "boundary-path"?
# Где использутся символ бесконечности?
# Что позволяет символ бесконечности?
# Какое утверждение верно?
# Какое утверждение верно?
# В алгоритме Укконена при добавлении нового символа
# Пусть явная вершина v соответствует суффиксу abc, тогда reference pair для суффикса abcde это
# Пусть (v, de) это reference pair для префикса abcde, тогда
# Какие утверждения верны?
# Время работы алгоритма Укконена для входного слова длины n равно
# Память необходимая для хранения суффиксного дерева для входного слова длины n из алфавита мощности m равна
# Память необходимая для хранения суффиксного массива для входного слова длины n из алфавита мощности m равна