Дискретная математика 2 (группа 141)

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

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

О курсе

По курсу "Дискретная математика" во 2-м семестре форма отчетности - экзамен. Экзамен проходит письменно. При написании экзаменационной работы не разрешается пользоваться никакими материалами. За экзаменационную работу студент получает определенное количество баллов.

В течение семестра по курсу проходят две письменные контрольные работы по четырем разделам курса. При написании контрольных работ не разрешается пользоваться никакими материалами. За каждый раздел курса студент получает баллы: 1, 0 или -1.

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

Экзаменационная работа состоит из 10 заданий. Задания 1-4 - стандартные задачи (перечень типов предлагаемых задач перечисляется в программе курса). Проверяется, насколько студент усвоил методы решения задач по курсу. Каждая задача оценивается в 3 балла. Задания 5-8 - определения и формулировки теорем с дополнительным вопросом. Дополнительный вопрос проясняет, насколько студент понимает определение или формулировку теоремы, может ли привести их частный случай или пояснить на примере. Каждое из заданий 6-10 оценивается в 3 балла. Задания 9-10 - доказательства теорем курса, их частей и частных случаев или нестандартные задачи. Проверяется, как студент усвоил доказательства основных утверждений курса и насколько студент может применять полученные в курсе знания для решения новых задач. Задания 9-10 оцениваются в 4 балла. Продолжительность написания экзаменационной работы - 1,5 астрономических часа (90 минут).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Лекция 9 (10.04.2015 г.). Операции над конечно-автоматными множествами. Дополнение, объединение, пересечение, произведение и итерация автоматных множеств, их автоматность. Лекция 9

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

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

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

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

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

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

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

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

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

Литература

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

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

• Занятие 1. Подсчет числа комбинаторных объектов. Правила суммы и произведения.

[1] Гл. VIII 1.1(1, 2), 1.2(1-2), 1.4(1-3), 1.6, 1.8(1-3), 1.9(1, 2), 1.10(1, 2), 1.11(1-3).

На дом: [1] Гл. VIII 1.1(3), 1.5(1-2), 1.7, 1.8(4-7), 1.9(3), 1.10(3), 1.12(1-3).

• Занятие 2. Свойства биномиальных коэффициентов и их сумм.

[1] Гл. VIII 1.13(1-4), 1.14(1, 3, 5, 7), 1.18(1, 3, 5, 7, 9, 12), 1.21(1, 3), 1.22(1, 3), 1.25(1, 2).

На дом: [1] Гл. VIII 1.13(5-8), 1.14(2, 4, 6), 1.18(2, 4, 6, 8, 10), 1.21(2, 4), 1.22(2, 4), 1.25(3, 4).

• Занятие 3. Принцип включений-исключений.

[1] Гл. VIII 2.1(2-3), 2.4(1-2), 2.5(1, 3), 2.6(1, 3, 5), 2.2, 2.7(1, 3), 2.8.

На дом: [1] Гл. VIII 2.5(2), 2.6(2, 4, 6), 2.7(2, 4), 2.9.

• Занятие 4. Рекуррентные уравнения.

[1] Гл. VIII 3.2(1, 3, 5), 3.3(1, 3, 5), 3.5(1-3), 3.6(2), 3.7(5).

На дом: [1] Гл. VIII 3.2(2, 4, 6), 3.3(2, 4), 3.5(4-5), 3.6(3).

• Занятие 5. Понятие схемы в некотором базисе. Метод синтеза по ДНФ.

[1] Гл. X 1.4(р. 10.2 а)-в)), 1.1(1-2, 5), 1.18(1-3), 1.2(1-2), 1.5(1-2), 1.7(1-2, 5), 1.8.

На дом: [1] Гл. X 1.1(3-4, 6-7), 1.18(4-6), 1.2(3-4), 1.5(3-4), 1.7(3-4, 6).

• Занятие 6. Синтез некоторых систем функций алгебры логики.

[1] Гл. X 1.9(1-2), 1.10, 1.11(1-2), 1.12(1, 3), 1.13(1), 1.10, 2.8 (1-3, СФЭ с уменьшением сложности).

На дом: [1] Гл. X 1.9(3), 1.11(3), 1.12(2), 1.13(2), 1.17, 2.8 (4-6, СФЭ с уменьшением сложности).

• Занятие 7. Контрольная работа по темам "Комбинаторика" и "СФЭ" (2 ч).

• Занятие 8. Конечные автоматы без выхода (КА) и автоматные множества. Диаграмма переходов.

[2] 1(1-3, 7), 2(1, 3), 9.

На дом: [2] 1(4-6, 8), 2(2, 4), 10.

• Занятие 9. Недетерминированные конечные автоматы без выхода (НКА). Детерминизация НКА.

[2] 3(1, 3), 4(1, 3), 7(1), 8(1).

На дом: [2] 3(2, 4), 4(2, 4), 7(2), 8(2).

• Занятие 10. Регулярные выражения и регулярные множества. Упрощения КА.

[2] 5(1, 2), 6(1, 3, 5, 7).

На дом: [2] 5(3, 4), 6(2, 4, 6, 8).

• Занятие 11. Конечные автоматы с выходом (КАВ). Диаграмма Мура и канонические уравнения.

[1] Гл. IV 1.1(1-4), 1.2(1-2), 2.1(1, 3, 15, 24, 27).

На дом: [1] Гл. IV 1.1(8-12), 1.2(3-4), 2.1(4, 8, 16, 25, 28).

• Занятие 12. Реализация КАВ СФЭз. Упрощения КАВ.

[1] Гл. IV 2.13(1, 4, 7), 2.14(1, 3), 2.4(1-3).

На дом: [1] Гл. IV 2.13(2, 3, 10), 2.14(2, 4), 2.4(4-6).

• Занятие 13. Контрольная работа по темам «КА» и «КАВ» (2 ч).

Литература

1. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
2. Задачи для семинарских занятий по теме "Конечные автоматы без выхода"
3. Селезнева С.Н. Основы дискретной математики. М.: МАКС Пресс, 2010.