Вопросы к экзамену
Описание файла
Документ из архива "Вопросы к экзамену", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 2 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Онлайн просмотр документа "Вопросы к экзамену"
Текст из документа "Вопросы к экзамену"
Вопросы к экзамену по курсу «Дискретная математика» (141 группа)
Лектор: доцент С.Н. Селезнева
Летняя сессия 2015-2016 учебного года
В билете два вопроса (один из части А и один из части В) и задача.
Часть А – ответ без подготовки по любым печатным материалам (конспектам, книгам, распечаткам лекций и т.д.); проверяется понимание доказательств; определения и теоремы формулируются без конспектов. Электронными средствами (компьютерами, телефонами и т.д.) на экзамене пользоваться не разрешается.
-
Сочетания с повторениями из n по k. Теорема о числе сочетаний с повторениями из n по k.
-
Формула включений-исключений для числа элементов, обладающих хотя бы одним из n свойств.
-
Линейные неоднородные рекуррентные уравнения (ЛНРУ) и соответствующие им ЛОРУ. Теорема об общем решении ЛНРУ. Теорема о частном решении ЛНРУ (только формулировка).
-
Умножитель. Леммы о сложности СФЭ для умножения на разряд и на степень двойки. Лемма о соотношении сложностей СФЭ для (n+1)-разрядного и n-разрядного умножителей. Теорема Карацубы о сложности СФЭ для n-разрядного умножителя.
-
Конечные автоматы (КА) без выхода (конечные автоматы-распознаватели). Диаграммы переходов. Автоматные множества (языки). Лемма о свойствах автоматных множеств. Пример неавтоматного множества.
-
Операции над конечно-автоматными множествами. Произведение и итерация автоматных множеств, их автоматность.
-
Регулярные выражения и регулярные множества. Теорема о совпадении классов регулярных множеств и автоматных множеств
-
Схемы из функциональных элементов с элементами единичной задержки (СФЭз). Теорема об автоматности осуществляемых ими отображений.
-
Схемы из функциональных элементов с элементами единичной задержки (СФЭз). Теорема о моделировании автоматной функции СФЭз.
-
Отличимые и неотличимые состояния КАВ, эксперимент, его длина. Лемма о двух отличимых состояниях КАВ.
-
Отличимые и неотличимые состояния КАВ, эксперимент, его длина. Теорема Мура о длине эксперимента, отличающего состояния КАВ.
Часть В – ответ без конспектов и почти без подготовки.
-
Размещения из n по k, их число и рекуррентная формула для них. Перестановки n элементов, их число. Размещения с повторениями из n по k и их число.
-
Сочетания из n по k, их число. Теорема о рекуррентной формуле числа сочетаний из n по k. Формула бинома Ньютона, следствия из нее. Биномиальные коэффициенты.
-
Теорема о возрастании и убывании последовательности биномиальных коэффициентов. Теорема о максимальном элементе этой последовательности.
-
Линейные однородные рекуррентные уравнения (ЛОРУ), частные и общие решения ЛОРУ. Лемма о линейной комбинации частных решений ЛОРУ.
-
Характеристический многочлен ЛОРУ. Лемма о простом корне характеристического многочлена ЛОРУ. Теорема об общем решении ЛОРУ с характеристическим многочленом, имеющим только простые корни. Теорема об общем решении произвольного ЛОРУ (только формулировка).
-
Схемы из функциональных элементов (СФЭ) в некотором базисе. Сложность СФЭ. Метод синтеза СФЭ по ДНФ, оценка сложности полученных по этому методу СФЭ.
-
Сумматор. Сложность одноразрядного сумматора. Теорема о верхней оценке сложности СФЭ n-разрядного сумматора в базисе из конъюнкции, дизъюнкции и отрицания.
-
Вычитатель. Теорема о верхней оценке сложности СФЭ n-разрядного вычитателя в базисе из конъюнкции, дизъюнкции и отрицания.
-
Недетерминированные конечные автоматы (НКА) без выхода. Теорема о совпадении классов множеств, принимаемых недетерминированными и детерминированными конечными автоматами. Процедура детерминизации НКА.
-
Операции над конечно-автоматными множествами. Дополнение, объединение, пересечение автоматных множеств, их автоматность.
-
Конечные автоматы с выходом (КАВ) (конечные автоматы-преобразователи). Диаграммы Мура, канонические уравнения. Автоматные функции. Функция единичной задержки, доказательство ее автоматности.
Литература
-
Слайды с лекциями http://mk.cs.msu.ru , страница «Дискретная математика 2».
-
Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001.
-
Алексеев В.Б. Лекции по дискретной математике. М.: МАКС Пресс, 2004.
-
Марченков С.С. Конечные автоматы. М.: Физматлит, 2008 (Часть 1).
-
Редькин Н.П. Дискретная математика. М.: Физматлит, 2008.
-
Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
-
Селезнева С.Н. Основы дискретной математики. М.: МАКС Пресс, 2010.