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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(→‎Литература)
(→‎Программа курса)
 
(не показаны 58 промежуточные версии 1 участника)
Строка 1: Строка 1:
−
Лектор - доц. [[Селезнева Светлана Николаевна]].
+
Лектор - профессор [[Вороненко Андрей Анатольевич]].
 +
 
 +
Курс читается для группы 141 во втором семестре. Лекции - 2 ч в неделю, семинары - 2 ч в неделю. Форма отчетности - экзамен.
  
 
[[Категория:Лекционные_курсы_кафедры_МК]]
 
[[Категория:Лекционные_курсы_кафедры_МК]]
  
−
==Программа курса==
+
==Объявления==
  
 +
Экзамен по курсу "Дискретная математика 2" проходит устно. В билете два вопроса, первый из части А, второй из части Б, а также задача. При ответе на первый вопрос билета можно пользоваться любыми печатными материалами (конспектами, книгами и т.д.). При ответе на второй вопрос билета никакими материалами пользоваться не разрешается.
  
−
*Лекция 1 (7.02.2014 г.). Комбинаторные объекты и комбинаторные числа. Правило суммы и правило произведения. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями. Их число и рекуррентные формулы для них. Теорема о числе сочетаний с повторениями.
+
[[Media:dm2-exam2016-v.doc|Вопросы к экзамену]]
 +
 +
По результатам контрольных работ, проведенных в семестре, каждый студент группы получил один из баллов (1, 0,5 или 0) по каждой из четырех тем задач ("Комбинаторика", "СФЭ", "Конечные автоматы без выхода", "Конечные автоматы с выходом").  
 +
Балл 1 означает, что студент освобожден от задачи по этой теме.  
 +
Балл 0,5 означает, что студент решает задачу по этой теме в том случае, если она у него в билете.
 +
Балл 0 означает дополнительную задачу по этой теме. Все дополнительные задачи решаются до того, как студент тянет билет. Отсутствие на контрольной означает балл 0 по соответствующей теме.
 +
 
 +
==Программа курса==
 +
 
 +
*Лекция 1. Комбинаторные объекты и комбинаторные числа. Правило суммы и правило произведения. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями. Их число и рекуррентные формулы для них. Теорема о числе сочетаний с повторениями. [1] стр. 171-174, 178-183, [5] стр. 253-255, [4] стр. 5-7. [[Media:dm2-lect1-selezn.pdf|Лекция 1]]
  
 
Задачи к лекции: найти число объектов определенного вида.
 
Задачи к лекции: найти число объектов определенного вида.
  
−
*Лекция 2 (14.02.2014 г.). Свойства биномиальных коэффициентов и их последовательностей. Формула бинома Ньютона. Производящие функции, вычисление сумм и доказательство комбинаторных тождеств. Формула включений-исключений и ее производные случаи.
+
*Лекция 2. Свойства биномиальных коэффициентов и их последовательностей. Формула бинома Ньютона. Производящие функции, вычисление сумм и доказательство комбинаторных тождеств. Формула включений-исключений и ее производные случаи. [1] стр. 177-178, 188-190, 197-200, [5] стр. 262-263, [4] стр. 7-10. [[Media:dm2-lect2-selezn.pdf|Лекция 2]]
  
 
Задачи к лекции: при помощи производящих функций вычислить комбинаторную сумму или доказать комбинаторное тождество; при помощи формулы включений-исключений найти число объектов определенного вида.
 
Задачи к лекции: при помощи производящих функций вычислить комбинаторную сумму или доказать комбинаторное тождество; при помощи формулы включений-исключений найти число объектов определенного вида.
  
−
*Лекция 3 (21.02.2014 г.). Функции натурального аргумента (последовательности). Рекуррентные уравнения. Линейные однородные рекуррентные уравнения (ЛОРУ). Частное решение ЛОРУ, лемма о линейной комбинации частных решений ЛОРУ. Общее решение ЛОРУ. Характеристический многочлен ЛОРУ. Теоремы об общем решении ЛОРУ. Линейные неоднородные рекуррентные уравнения (ЛНРУ), их частные и общие решения. Теорема об общем решении ЛНРУ. Теорема о частном решении ЛНРУ.  
+
*Лекция 3. Функции натурального аргумента (последовательности). Рекуррентные уравнения. Линейные однородные рекуррентные уравнения (ЛОРУ). Частное решение ЛОРУ, лемма о линейной комбинации частных решений ЛОРУ. Общее решение ЛОРУ. Характеристический многочлен ЛОРУ. Теоремы об общем решении ЛОРУ. Линейные неоднородные рекуррентные уравнения (ЛНРУ), их частные и общие решения. Теорема об общем решении ЛНРУ. Теорема о частном решении ЛНРУ. [1] стр. 177-178, 188-190, [5] стр. 265-266, стр. 266 3.1, 3.4, [4] стр. 10-13. [[Media:dm2-lect3-selezn.pdf|Лекция 3]]
 
   
 
   
 
Задачи к лекции: решить заданное ЛОРУ или ЛНРУ.
 
Задачи к лекции: решить заданное ЛОРУ или ЛНРУ.
  
−
*Лекция 4 (28.02.2014 г.). Схемы из функциональных элементов (СФЭ) в некотором базисе. Сложность и глубина СФЭ. Линейные программы и их связь с СФЭ.
+
*Лекция 4. Схемы из функциональных элементов (СФЭ) в некотором базисе. Сложность и глубина СФЭ. Примеры. Метод синтеза СФЭ по ДНФ. [2] стр. 40-41.
 
   
 
   
−
Задачи к лекции: для заданной булевой функции или системы булевых функций построить СФЭ в заданном базисе с заданной сложностью или глубиной.
+
Задачи к лекции: для заданной функции алгебры логики или системы функций алгебры логики построить СФЭ в заданном базисе с заданной сложностью или глубиной.  
  
−
*Лекция 5 (7.03.2014 г.). Сумматор. Сложность одноразрядного сумматора. Теорема о верхней оценке сложности n-разрядного сумматора в базисе из конъюнкции, дизъюнкции и отрицания. Вычитатель. Теорема о верхней оценке сложности n-разрядного вычитателя в базисе из конъюнкции, дизъюнкции и отрицания.  
+
*Лекция 5. Сумматор. Сложность одноразрядного сумматора. Теорема о верхней оценке сложности n-разрядного сумматора в базисе из конъюнкции, дизъюнкции и отрицания. Вычитатель. Теорема о верхней оценке сложности n-разрядного вычитателя в базисе из конъюнкции, дизъюнкции и отрицания. [2] стр. 43-44.
 
   
 
   
 
Задачи к лекции: построить n-разрядный сумматор или вычитатель при заданном n.
 
Задачи к лекции: построить n-разрядный сумматор или вычитатель при заданном n.
  
−
*Лекция 6 (14.03.2014 г.). Умножитель. Леммы о сложности СФЭ для умножения на разряд и на степень двойки. Лемма о соотношении сложностей СФЭ для (n+1)-разрядного и n-разрядного умножителей. Теорема Карацубы о сложности СФЭ для n-разрядного умножителя.  
+
*Лекция 6. Умножитель. Леммы о сложности СФЭ для умножения на разряд и на степень двойки. Лемма о соотношении сложностей СФЭ для (n+1)-разрядного и n-разрядного умножителей. Теорема Карацубы о сложности СФЭ для n-разрядного умножителя. [2] стр. 45-48.
 
   
 
   
 
Задачи к лекции: построить n-разрядный умножитель при заданном n.
 
Задачи к лекции: построить n-разрядный умножитель при заданном n.
  
−
*Лекция 7 (21.03.2014 г.). Конечные автоматы (КА) без выхода (конечные автоматы-распознаватели). Диаграммы переходов. Автоматные множества (языки). Пример неавтоматного множества.  
+
*Лекция 7. Конечные автоматы (КА) без выхода (конечные автоматы-распознаватели). Диаграммы переходов. Автоматные множества (языки). Лемма о свойствах автоматных множеств. Пример неавтоматного множества. [[Media:dm2-lect7-selezn1.pdf|Лекция 7]]
 
   
 
   
 
Задачи к лекции: по заданной диаграмме переходов найти язык, принимаемый этим автоматом; доказать автоматность языка, построив диаграмму переходов автомата, принимающего этот язык.  
 
Задачи к лекции: по заданной диаграмме переходов найти язык, принимаемый этим автоматом; доказать автоматность языка, построив диаграмму переходов автомата, принимающего этот язык.  
  
−
*Лекция 8 (28.03.2014 г.). Недетерминированные конечные автоматы (НКА) без выхода. Теорема о совпадении классов множеств, принимаемых недетерминированными и детерминированными конечными автоматами. Процедура детерминизации НКА.  
+
*Лекция 8. Недетерминированные конечные автоматы (НКА) без выхода. Теорема о совпадении классов множеств, принимаемых недетерминированными и детерминированными конечными автоматами. Процедура детерминизации НКА. [[Media:dm2-lect8-selezn.pdf|Лекция 8]]
 
   
 
   
 
Задачи к лекции: детерминизировать заданный НКА.  
 
Задачи к лекции: детерминизировать заданный НКА.  
  
−
*Лекция 9 (4.04.2014 г.). Регулярные выражения и регулярные множества. Теорема о совпадении классов регулярных и автоматных множеств.
+
*Лекция 9. Операции над конечно-автоматными множествами. Дополнение, объединение, пересечение, произведение и итерация автоматных множеств, их автоматность. [[Media:dm2-lect9-selezn.pdf|Лекция 9]]
 +
 
 +
Задачи к лекции: по заданным ДКА без выхода построить НКА, принимающие множества, являющиеся дополнением, объединением, произведением или итерацией множеств, принимаемых исходными ДКА; провести детерминизацию полученных НКА.
 +
 
 +
*Лекция 10. Регулярные выражения и регулярные множества. Теорема о совпадении классов регулярных множеств и автоматных множеств. [[Media:dm2-lect10-selezn.pdf|Лекция 10]]
 
   
 
   
 
Задачи к лекции: по заданному регулярному выражению построить КА, принимающий регулярное множество, соответствующее этому регулярному выражению; по заданному автоматному множеству построить регулярное выражение, определяющее это автоматное множество.  
 
Задачи к лекции: по заданному регулярному выражению построить КА, принимающий регулярное множество, соответствующее этому регулярному выражению; по заданному автоматному множеству построить регулярное выражение, определяющее это автоматное множество.  
  
−
*Лекция 10 (11.04.2014 г.). Упрощение КА. Теорема о длине эксперимента, отличающего два отличимые состояния КА.  
+
*Лекция 11. Конечные автоматы с выходом (КАВ) (конечные автоматы-преобразователи). Диаграммы переходов, канонические уравнения. Автоматные функции. Функция единичной задержки, доказательство ее автоматности. Пример неавтоматной функции. [[Media:dm2-lect11-selezn.pdf|Лекция 11]]
 
   
 
   
−
Задачи к лекции: упростить заданный КА, представленный диаграммой переходов.  
+
Задачи к лекции: по описанию функции доказать ее неавтоматность или доказать ее автоматность, построив диаграмму переходов автомата для этой функции.
  
−
*Лекция 11 (18.04.2014 г.). Конечные автоматы с выходом (КАВ)(конечные автоматы-преобразователи). Диаграммы переходов, канонические уравнения. Автоматные функции. Функция единичной задержки, доказательство ее автоматности. Пример неавтоматной функции.
+
*Лекция 12. Схемы из функциональных элементов с элементами задержки (СФЭз), автоматность осуществляемых ими отображений. Реализация КАВ СФЭз. [[Media:dm2-lect12-selezn.pdf|Лекции 12-13]]
−
+
−
Задачи к лекции: по описанию функции доказать ее неавтоматность или доказать ее автоматность, построив диаграмму переходов автомата, осуществляющего эту функцию.
+
  
−
*Лекция 12 (25.04.2014 г.). Схемы из функциональных элементов с элементами задержки (СФЭз), автоматность осуществляемых ими отображений. Реализация КАВ СФЭз. Реализация сумматора СФЭз.
 
−
 
 
Задачи к лекции: по заданной СФЭз построить КАВ, реализуемый этой схемой; построить СФЭз, реализующий заданный КАВ.
 
Задачи к лекции: по заданной СФЭз построить КАВ, реализуемый этой схемой; построить СФЭз, реализующий заданный КАВ.
  
−
*Лекция 13 (16.05.2014 г.). Упрощение конечных автоматов с выходом. Лемма о двух отличимых состояниях. Теорема Мура о длине эксперимента, отличающего два отличимые состояния.   
+
*Лекция 13. Упрощение конечных автоматов с выходом. Лемма о двух отличимых состояниях КАВ. Теорема Мура о длине эксперимента, отличающего два отличимые состояния КАВ.   
 
   
 
   
 
Задачи к лекции: упростить заданный КАВ, представленный диаграммой переходов.
 
Задачи к лекции: упростить заданный КАВ, представленный диаграммой переходов.
  
−
==Литература==
+
'''Литература'''
  
 
# Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001.
 
# Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001.
−
# Алексеев В.Б. Лекции по дискретной математике. М.: МАКС Пресс, 2004.
+
# [[Media:dm-alekseev.pdf|Алексеев В.Б. Лекции по дискретной математике]]. М.: МАКС Пресс, 2004.
−
# Марченков С.С. Конечные автоматы. М.: Физматлит, 2008.
+
# Марченков С.С. Конечные автоматы. М.: Физматлит, 2008 ([[Media:ka-march-part1.pdf|Часть 1]]).
 
# Редькин Н.П. Дискретная математика. М.: Физматлит, 2008.
 
# Редькин Н.П. Дискретная математика. М.: Физматлит, 2008.
 
# Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
 
# Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
 +
# [[Media:odm-selezn.pdf|Селезнева С.Н. Основы дискретной математики]]. М.: МАКС Пресс, 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 ч).
 +
 +
'''Литература'''
 +
 +
# Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
 +
# [[Media:finaut.pdf|Задачи для семинарских занятий по теме "Конечные автоматы без выхода"]]
 +
# [[Media:odm-selezn.pdf|Селезнева С.Н. Основы дискретной математики]]. М.: МАКС Пресс, 2010.

Текущая версия на 04:43, 13 февраля 2023

Лектор - профессор Вороненко Андрей Анатольевич.

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

Объявления

Экзамен по курсу "Дискретная математика 2" проходит устно. В билете два вопроса, первый из части А, второй из части Б, а также задача. При ответе на первый вопрос билета можно пользоваться любыми печатными материалами (конспектами, книгами и т.д.). При ответе на второй вопрос билета никакими материалами пользоваться не разрешается.

Вопросы к экзамену

По результатам контрольных работ, проведенных в семестре, каждый студент группы получил один из баллов (1, 0,5 или 0) по каждой из четырех тем задач ("Комбинаторика", "СФЭ", "Конечные автоматы без выхода", "Конечные автоматы с выходом"). Балл 1 означает, что студент освобожден от задачи по этой теме. Балл 0,5 означает, что студент решает задачу по этой теме в том случае, если она у него в билете. Балл 0 означает дополнительную задачу по этой теме. Все дополнительные задачи решаются до того, как студент тянет билет. Отсутствие на контрольной означает балл 0 по соответствующей теме.

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

  • Лекция 1. Комбинаторные объекты и комбинаторные числа. Правило суммы и правило произведения. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями. Их число и рекуррентные формулы для них. Теорема о числе сочетаний с повторениями. [1] стр. 171-174, 178-183, [5] стр. 253-255, [4] стр. 5-7. Лекция 1

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

  • Лекция 2. Свойства биномиальных коэффициентов и их последовательностей. Формула бинома Ньютона. Производящие функции, вычисление сумм и доказательство комбинаторных тождеств. Формула включений-исключений и ее производные случаи. [1] стр. 177-178, 188-190, 197-200, [5] стр. 262-263, [4] стр. 7-10. Лекция 2

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

  • Лекция 3. Функции натурального аргумента (последовательности). Рекуррентные уравнения. Линейные однородные рекуррентные уравнения (ЛОРУ). Частное решение ЛОРУ, лемма о линейной комбинации частных решений ЛОРУ. Общее решение ЛОРУ. Характеристический многочлен ЛОРУ. Теоремы об общем решении ЛОРУ. Линейные неоднородные рекуррентные уравнения (ЛНРУ), их частные и общие решения. Теорема об общем решении ЛНРУ. Теорема о частном решении ЛНРУ. [1] стр. 177-178, 188-190, [5] стр. 265-266, стр. 266 3.1, 3.4, [4] стр. 10-13. Лекция 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

  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.
Источник — «https://mk.cs.msu.ru/index.php?title=Дискретная_математика_2_(группа_141)&oldid=9924»