1 |
Название дисциплины |
Дискретная математика и математическая логика |
2 |
Курс обучения |
2, специальность «Математическое и программное обеспечение мобильных устройств» |
3 |
Семестр обучения |
4 |
4 |
Количество кредитов |
8 |
5 |
Ф.И.О. лектора |
Кандидат физико-математических наук, доцент Кузьмин Кирилл Геннадьевич |
6 |
Цели изучения дисциплины |
Данный курс предполагает ознакомление с основными идеями и методами дискретной математики. В результате изучения студент должен уметь: – формулировать и доказывать основные теоремы в перечислительной комбинаторике, алгебре логики и теории графов; – решать типовые комбинаторные задачи; – минимизировать булевы функции в классе ДНФ; – распознавать полноту и замкнутость систем булевых функций; – распознавать различные классы графов; – решать типовые задачи на графах; – составлять алгоритмы для нахождения решений для ряда задач теории графов. |
7 |
Пререквизиты |
Математический анализ, алгебра. |
8 |
Содержание дисциплины |
Математическая индукция; алгебра логики, логика первого порядка; перечислительная комбинаторика (включая комбинаторные конфигурации, метод включения и исключения, рекуррентные соотношения, производящие функции, числа Стирлинга и Каталана); булевы функции (включая нормальные формы, минимизацию в классе ДНФ, характеризацию замкнутых классов, теорему Поста); теория графов (включая изоморфизм графов, связность, деревья, эйлеровы и гамильтоновы циклы, раскраску графов, планарность и некоторые экстремальные задачи на графах). |
9 |
Рекомендуемая литература |
1. Селезнева С. Н. Основы дискретной математики – М.: МАКС Пресс, 2010. 2. Шень А. Математическая индукция – М.: МЦНМО, 2007. 3. Шень А., Вялый М., Подольский В., Рубцов А., Шварц Д. Лекции по дискретной математике – М.: МЦНМО, 2017. 4. Conradie W., Goranko V. Logic and discrete mathematics: a concise introduction – Chichester: Wiley, 2015. 5. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов – М.: Либкором, 2015. |
10 |
Методы преподавания |
Объяснительно-иллюстративный, репродуктивный, проблемного изложения, частично-поисковый, исследовательский. |
11 |
Язык обучения |
Русский язык |
12 |
Условия (требования), текущий контроль |
– контрольные работы, – коллоквиумы. Оценка на экзамене выставляется с учетом: 40% – работа на семинарах (включая контрольные работы и коллоквиумы), 60% – устный ответ. |
13 |
Форма текущей аттестации |
Экзамен |