Комбинаторные алгоритмы для программистов - ответы
Количество вопросов - 152
Линейное рекуррентное соотношение с постоянными коэффициентами имеет вид f(n+k)=a1f(n+k-1)+...+anf(n). Какое уравнение будет для него характеристическим?
Что мы понимаем под алгоритмом замещения страниц?
По какому направлению развиваются комбинаторные вычисления?
Сколько разрядов требуется для задания графа матрицей смежностей?
Что называется путем в графе?
Что понимают под сбором мусора?
Чем отличается симметричный порядок для бинарных деревьев от лексикографического порядка?
Что называют k-сочетаниями из n-элементов?
Какие операции определены над множествами?
Какой коэффициент является наибольшим в разложении (a+b+c)10
Что понимают под нулевым указателем?
Какая сортировка называется вставкой?
Какой граф называется полным?
Какая последовательность называется последовательностью Фибоначчи?
Что называют листьями дерева?
Что такое сортирующая последовательность?
Каковы основные базисные операции для работы с однонаправленным связанным списком?
Что понимают под сортировкой по возрастанию?
Что называют кратностью элементов мультимножества?
Какая таблица называется статической таблицей?
Может ли функция f(x) иметь два различных разложения в степенные ряды?
Сколькими способами можно расставить 20 книг в книжном шкафу с 5 полками, если каждая полка может вместить все 20 книг?
Какую функцию называют производящей для последовательности чисел a0,a1,...,an?
Что используется в качестве основных объектов в вычислительной комбинаторике?
Из состава конференции, на которой присутствует 52 человека, надо избрать делегацию, состоящую из 5 человек. Сколькими способами это можно сделать?
Что понимают под обходом дерева?
Какие сортировки относятся к обменной сортировке?
Какая разница между двумя вопросами: "Какими свойствами обладает данный алгоритм?" и "Какие свойства должен иметь любой алгоритм, решающий данную проблему?"
Какие существуют основные базисные операции для работы со стеком?
Когда имеет практическое значение техника исчерпывающего поиска?
Что является предметом теории комбинаторных алгоритмов?
Каким образом можно найти оптимальные деревья решений?
Какие фундаментальные проблемы существуют в анализе алгоритмов?
Как можно найти оптимальные деревья решений?
Что понимают под указателем?
Что понимают под очередью?
Что называют конечным корневым деревом Т?
Сколькими способами можно выбрать три различные краски из имеющихся пяти?
Сколько различных перестановок можно получить, переставляя буквы в слове "ингредиент"?
Сколькими способами можно расставить белые фигуры (2 коня, 2 слона, 2 ладьи, ферзя и короля) на первой линии шахматной доски?
Что называют мультимножеством?
Что называют именем подмножества?
Какие числа называют составными числами?
Что называется поиском по числам Фибоначчи?
Какие соотношения называют линейными рекуррентными соотношениями с постоянными коэффициентами?
Какое уравнение является характеристическим для данного соотношения f(n+2)=a1f(n+1)+a2f(n)?
Что означает название "формальный ряд последовательности"?
Что называют суммой бесконечного ряда?
Пусть имеется два разложения функции: f(x)=a0+a1x+...+anxn+... f(x)=b0+b1x+...+bnxn+...
Какое отношение между ai,bi верно?
Какая последовательность удовлетворяет равенству an+2+2an+1-8an=2n
Какой коэффициент является наибольшим в разложении (a+b+c+d)14
Какие существуют основные базисные операции для работы с очередью?
Что такое двоичное дерево?
Какой граф называется взвешенным графом?
Что является остовными деревьями графа G?
Что называют именами?
Что подразумевается под последовательным поиском?
Можно ли обобщить деревья бинарного поиска до m-арных деревьев поиска?
Какая задача решается при внутренней сортировке?
Что означает "сливать"?
Что понимают в комбинаторике под пирамидой?
Что понимают под сортировкой?
Какая сортировка называется сортировкой слиянием?
Что называется меткой в графе G?
Что называется потомком определенной вершины в дереве <V,T>, где Т⊆E?
Если последовательность вершин v0,v1,...,vp определяет путь в G(V,E) графе, то как определяется его длина?
Что понимают под решением лабиринта?
Что понимают под оптимизацией?
Сколькими способами можно выбрать из 15 человек группу людей для работы (в группу могут входить 1, 2, 3,…, 15 человек)? Та же задача для случая выбора из n человек
Что такое ключ сортировки?
Что понимают под методом рекуррентных соотношений (от латинского "recurrere" – "возвращаться")?
Какой ряд называют расходящимся?
Какое решение лабиринта называют единственным?
Что понимают под связанным распределением последовательности?
Какие числа называются простыми?
Ряд c0+c1x+...+cnxn+... при достаточно малых значениях x сходится к f(x)/ϕ(x). От чего зависит размер области сходимости?
Что называется формальным рядом для последовательности a0,a1,a2,...,?
Что называют корнем дерева?
Что называют частным от деления многочлена на многочлен?
Какая память называется оперативной?
Что понимают под представителем подмножества?
Какие действия возможны над степенными рядами?
На какие классы алгоритмов можно разбить внутреннюю сортировку?
Какая разница между двумя вопросами: "Какими свойствами обладает данный алгоритм?" и "Какие свойства должен иметь любой алгоритм, решающий данную проблему?"
Что такое адрес?
Что называют мостом графа G(V,E)?
Когда дерево пусто?
Что понимают под носителем данных?
Рациональнее исследовать классы алгоритмов или изучать отдельные алгоритмы?
В селении проживает 2000 жителей. Могут ли все из них иметь разные инициалы?
Являются ли классы алгоритмов сортировки взаимоисключающими?
Что называется деревом G(V,E)?
Какую задачу решает внешняя сортировка?
Что понимают в комбинаторике под внешней сортировкой?
Что называется связанным списком?
Что понимают под стеком?
Что является решением данного рекуррентного соотношения?
Чем отличается процедура прохождения в глубину от процедуры прохождения в прямом порядке?
Что используют большинство вычислительных устройств в качестве основных объектов?
Что называют лесом?
Что называют высотой дерева?
Что мы понимаем под информацией?
Сколько различных перестановок можно получить, переставляя буквы в слове "математика"?
Какие числа называется числами Фибоначчи?
Какие расстановки называют n - перестановками?
Что называется общим решением рекуррентного соотношения k-го порядка?
Имеется pq+r разных предметов, где 0≤r<p. Они делятся между p людьми возможно ровнее (все получают либо q, либо q+1 предметов). Сколько существует способов такого раздела?
Что называется стеком?
Что называется очередью?
Каковы основные базисные операции для работы с двунаправленным связанным списком?
Каким способом нужно задать граф, если в алгоритмах граф модифицируется таким образом, что в нем добавляются или удаляются вершины?
Что называется длиной пути?
Что понимают под пространством имен?
Может ли корень иметь сыновей меньше m в сбалансированном сильно ветвящемся дереве порядка m?
В чем состоит идея сортировки посредством выбора?
Какая память называется внешней?
Чем отличается стягивающие дерево от каркаса и остова дерева?
Что такое страница памяти?
Что такое сходимость бесконечного числового ряда?
Являются ли классы алгоритмов сортировки исчерпывающими?
Какие алгоритмы используются для быстрой сортировки?
Обозначим число перестановок последовательности α1,...,αn-1,αn через Pn. Какая формула подсчета перестановок верна?
Какова одна из важных проблем в комбинаторных вычислениях?
Что понимают под носителями данных?
Можно ли тестированием определить существование лучшего алгоритма для решения той же самой задачи?
Что содержится в указателе стека sp (steck pointer)?
Какие условия являются необходимыми для использования алгоритма Дейкстры?
Какие расстановки считаются различными?
Какое характеристическое уравнение соответствует рекуррентному соотношению f(n)=f(n-1)+f(n-2)?
В некотором государстве не было двух жителей с одинаковым набором зубов. Какова может быть наибольшая численность населения государства (наибольшее число зубов равно 32)?
Что называется производящей функцией для последовательности a0,a1,a2,...,?
При каких условиях метод поиска в глубину в графе "хорош"?
Какая функция является производящей функцией для чисел Сnk,k=0,1,...,?
Какая таблица называется динамической таблицей?
В каком интервале имеют сыновей внутренние узлы m-арного дерева?
Каким способом эффективнее представлять разреженный граф?
Что называют частным при делении рядов?
Теория информации - это...
Какие разновидности связанных списков вы знаете?
Когда имеет практическое значение техника исчерпывающего поиска?
В каком режиме оперирует очередь?
Сколько различных перестановок можно получить, переставляя буквы в слове "парабола"?
Что называют точкой сочленения в графе?
Что делает сортировка?
Можно ли тестированием определить существование лучшего алгоритма для решения той же самой задачи?
Какое дерево называют бинарным Т?
Что понимают под множеством?
Какие расстановки называют перестановками из n элементов?
Рациональнее исследовать классы алгоритмов или изучать отдельные алгоритмы?
Что называется основанием системы счисления?
Для чего используют формулу включения и исключения?
Как обычно задается простой взвешенный граф?