Дискретная математика 2 (группа 141) — различия между версиями

Версия 10:14, 3 февраля 2014

Лектор - доцент Селезнева Светлана Николаевна.

Курс читается для группы 141 во втором семестре. Лекции - 36 ч, семинары - 36 ч. Форма отчетности - экзамен.

Программа курса

• Лекция 1 (7.02.2014 г.). Комбинаторные объекты и комбинаторные числа. Правило суммы и правило произведения. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями. Их число и рекуррентные формулы для них. Теорема о числе сочетаний с повторениями.

Задачи к лекции: найти число объектов определенного вида.

• Лекция 2 (14.02.2014 г.). Свойства биномиальных коэффициентов и их последовательностей. Формула бинома Ньютона. Производящие функции, вычисление сумм и доказательство комбинаторных тождеств. Формула включений-исключений и ее производные случаи.

Задачи к лекции: при помощи производящих функций вычислить комбинаторную сумму или доказать комбинаторное тождество; при помощи формулы включений-исключений найти число объектов определенного вида.

• Лекция 3 (21.02.2014 г.). Функции натурального аргумента (последовательности). Рекуррентные уравнения. Линейные однородные рекуррентные уравнения (ЛОРУ). Частное решение ЛОРУ, лемма о линейной комбинации частных решений ЛОРУ. Общее решение ЛОРУ. Характеристический многочлен ЛОРУ. Теоремы об общем решении ЛОРУ. Линейные неоднородные рекуррентные уравнения (ЛНРУ), их частные и общие решения. Теорема об общем решении ЛНРУ. Теорема о частном решении ЛНРУ.

Задачи к лекции: решить заданное ЛОРУ или ЛНРУ.

• Лекция 4 (28.02.2014 г.). Схемы из функциональных элементов (СФЭ) в некотором базисе. Сложность и глубина СФЭ. Линейные программы и их связь с СФЭ.

Задачи к лекции: для заданной булевой функции или системы булевых функций построить СФЭ в заданном базисе с заданной сложностью или глубиной.

• Лекция 5 (7.03.2014 г.). Сумматор. Сложность одноразрядного сумматора. Теорема о верхней оценке сложности n-разрядного сумматора в базисе из конъюнкции, дизъюнкции и отрицания. Вычитатель. Теорема о верхней оценке сложности n-разрядного вычитателя в базисе из конъюнкции, дизъюнкции и отрицания.

Задачи к лекции: построить n-разрядный сумматор или вычитатель при заданном n.

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

Задачи к лекции: построить n-разрядный умножитель при заданном n.

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

Задачи к лекции: по заданной диаграмме переходов найти язык, принимаемый этим автоматом; доказать автоматность языка, построив диаграмму переходов автомата, принимающего этот язык.

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

Задачи к лекции: детерминизировать заданный НКА.

• Лекция 9 (4.04.2014 г.). Регулярные выражения и регулярные множества. Теорема о совпадении классов регулярных и автоматных множеств.

Задачи к лекции: по заданному регулярному выражению построить КА, принимающий регулярное множество, соответствующее этому регулярному выражению; по заданному автоматному множеству построить регулярное выражение, определяющее это автоматное множество.

• Лекция 10 (11.04.2014 г.). Упрощение КА. Теорема о длине эксперимента, отличающего два отличимые состояния КА.

Задачи к лекции: упростить заданный КА, представленный диаграммой переходов.

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

Задачи к лекции: по описанию функции доказать ее неавтоматность или доказать ее автоматность, построив диаграмму переходов автомата, осуществляющего эту функцию.

• Лекция 12 (25.04.2014 г.). Схемы из функциональных элементов с элементами задержки (СФЭз), автоматность осуществляемых ими отображений. Реализация КАВ СФЭз. Реализация сумматора СФЭз.

Задачи к лекции: по заданной СФЭз построить КАВ, реализуемый этой схемой; построить СФЭз, реализующий заданный КАВ.

• Лекция 13 (16.05.2014 г.). Упрощение конечных автоматов с выходом. Лемма о двух отличимых состояниях КАВ. Теорема Мура о длине эксперимента, отличающего два отличимые состояния КАВ.

Задачи к лекции: упростить заданный КАВ, представленный диаграммой переходов.

Литература

1. Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001.
2. Алексеев В.Б. Лекции по дискретной математике. М.: МАКС Пресс, 2004.
3. Марченков С.С. Конечные автоматы. М.: Физматлит, 2008.
4. Редькин Н.П. Дискретная математика. М.: Физматлит, 2008.
5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.

Программа семинарских занятий