Вопросы к экзамену по курсу «Дискретная математика»



Дата17.06.2015
Размер30,5 Kb.
ТипВопросы к экзамену

Вопросы к экзамену по курсу «Дискретная математика» (141 группа)
Лектор: доцент С.Н. Селезнева

Летняя сессия 2013-2014 учебного года
В билете два вопроса (один из части А и один из части В) и задача.
Часть А – ответ без подготовки по любым печатным материалам (конспектам, книгам, распечаткам лекций и т.д.); проверяется понимание доказательств; определения и теоремы формулируются без конспектов. Электронными средствами (компьютерами, телефонами и т.д.) на экзамене пользоваться нельзя.


  1. Сочетания с повторениями из n по k. Теорема о числе сочетаний с повторениями из n по k.

  2. Формула включений-исключений для числа элементов, обладающих хотя бы одним из n свойств.

  3. Линейные неоднородные рекуррентные уравнения (ЛНРУ) и соответствующие им ЛОРУ. Теорема об общем решении ЛНРУ. Теорема о частном решении ЛНРУ (только формулировка).

  4. Умножитель. Леммы о сложности СФЭ для умножения на разряд и на степень двойки. Лемма о соотношении сложностей СФЭ для (n+1)-разрядного и n-разрядного умножителей. Теорема Карацубы о сложности СФЭ для n-разрядного умножителя.

  5. Конечные автоматы (КА) без выхода (конечные автоматы-распознаватели). Диаграммы переходов. Автоматные множества (языки). Лемма о свойствах автоматных множеств.

  6. Операции над конечно-автоматными множествами. Произведение и итерация автоматных множеств, их автоматность.

  7. Регулярные выражения и регулярные множества. Теорема Клини о совпадении классов регулярных множеств и автоматных множеств

  8. Схемы из функциональных элементов с элементами единичной задержки (СФЭз). Теорема об автоматности осуществляемых ими отображений.

  9. Схемы из функциональных элементов с элементами единичной задержки (СФЭз). Теорема о моделировании автоматной функции СФЭз.

  10. Отличимые и неотличимые состояния КАВ, эксперимент, его длина. Лемма о двух отличимых состояниях КАВ.

  11. Отличимые и неотличимые состояния КАВ, эксперимент, его длина. Теорема Мура о длине эксперимента, отличающего состояния КАВ.



Часть В – ответ без конспектов и почти без подготовки.


  1. Размещения из n по k, их число и рекуррентная формула для них. Таблица размещений из n по k. Перестановки n элементов, их число. Размещения с повторениями из n по k и их число.

  2. Сочетания из n по k, их число. Теорема о рекуррентной формуле числа сочетаний из n по k. Таблица сочетаний из n по k. Формула бинома Ньютона, следствия из нее. Биномиальные коэффициенты.

  3. Теорема о возрастании и убывании последовательности биномиальных коэффициентов. Теорема о максимальном элементе этой последовательности.

  4. Линейные однородные рекуррентные уравнения (ЛОРУ), частные и общие решения ЛОРУ. Лемма о линейной комбинации частных решений ЛОРУ.

  5. Характеристический многочлен ЛОРУ. Лемма о простом корне характеристического многочлена ЛОРУ. Теорема об общем решении ЛОРУ с характеристическим многочленом, имеющим только простые корни. Теорема об общем решении произвольного ЛОРУ (только формулировка).

  6. Схемы из функциональных элементов (СФЭ) в некотором базисе. Сложность и глубина СФЭ. Метод синтеза СФЭ по ДНФ.

  7. Сумматор. Сложность одноразрядного сумматора. Теорема о верхней оценке сложности СФЭ n-разрядного сумматора в базисе из конъюнкции, дизъюнкции и отрицания.

  8. Вычитатель. Теорема о верхней оценке сложности СФЭ n-разрядного вычитателя в базисе из конъюнкции, дизъюнкции и отрицания.

  9. Недетерминированные конечные автоматы (НКА) без выхода. Теорема о совпадении классов множеств, принимаемых недетерминированными и детерминированными конечными автоматами. Процедура детерминизации НКА.

  10. Операции над конечно-автоматными множествами. Дополнение, объединение, пересечение автоматных множеств, их автоматность.

  11. Конечные автоматы с выходом (КАВ) (конечные автоматы-преобразователи). Диаграммы Мура, канонические уравнения. Автоматные функции. Функция единичной задержки, доказательство ее автоматности.


Литература


  1. Слайды с лекциями http://mk.cs.msu.ru , страница «Дискретная математика 2».

  2. Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001.

  3. Алексеев В.Б. Лекции по дискретной математике. М.: МАКС Пресс, 2004.

  4. Марченков С.С. Конечные автоматы. М.: Физматлит, 2008 (Часть 1).

  5. Редькин Н.П. Дискретная математика. М.: Физматлит, 2008.

  6. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.

  7. Селезнева С.Н. Основы дискретной математики. М.: МАКС Пресс, 2010.

Похожие:

Вопросы к экзамену по курсу «Дискретная математика» iconВопросы к экзамену по курсу «Дискретная математика»
Степень конечного расширения поля. Теорема о башне полей (без доказательства). Примеры
Вопросы к экзамену по курсу «Дискретная математика» iconВопросы к экзамену по курсу Дискретная математика, часть 3
Алгорифмическая неразрешимость задачи об остановке машины Тьюринга при произвольном входном слове и на пустой ленте
Вопросы к экзамену по курсу «Дискретная математика» iconВопросы к коллоквиуму №1 по курсу Дискретная математика
Элементы теории множеств. Задание множеств. Геометрическое моделирование множеств
Вопросы к экзамену по курсу «Дискретная математика» iconВопросы для подготовки к экзамену по математике для студентов ргуфксит вопросы для подготовки к экзамену по курсу «Математика»
«Туризм», по специальностям: 032101. 65 «Физическая культура и спорт», 032103. 65 «Рекреация и спортивно-оздоровительный туризм»,...
Вопросы к экзамену по курсу «Дискретная математика» iconВопросы к экзамену по курсу «Высшая математика»
Системы координат. Прямоугольная декартова система координат на плоскости и в пространстве
Вопросы к экзамену по курсу «Дискретная математика» iconВопросы к экзамену по курсу «Высшая математика часть 2»
Элементы теории соединений. Размещения без повторений. Две формулы для подсчёта числа размещений
Вопросы к экзамену по курсу «Дискретная математика» iconВопросы к зачету и экзамену по курсу «математика»
Векторы, координаты вектора, длина вектора, направляющие косинусы. Коллинеарные и компланарные векторы
Вопросы к экзамену по курсу «Дискретная математика» iconУчебная программа Дисциплины б4 «Дискретная математика» по специальности 090302 «Информационная безопасность телекоммуникационных систем»
Целью преподавания дисциплины «Дискретная математика» является подготовка специалистов к деятельности в сфере разработки, исследования...
Вопросы к экзамену по курсу «Дискретная математика» iconВопросы по общей истории и философия науки
Вопросы для подготовки к экзамену кандидатского минимума по курсу «Философия науки»
Вопросы к экзамену по курсу «Дискретная математика» iconВопросы к экзамену по курсу «теория вероятностей и математическая статистика»
Известные дискретные распределения: Бернулли, биномиальное, геометрическое и Пуассона
Разместите кнопку на своём сайте:
docs.likenul.com


База данных защищена авторским правом ©docs.likenul.com 2015
обратиться к администрации
docs.likenul.com