МИНОБРНАУКИ РОССИИ
федеральное государственное бюджетное образовательное учреждение высшего образования
«Алтайский государственный университет»

Дискретная математика

рабочая программа дисциплины
Закреплена за кафедройКафедра экономики и эконометрики
Направление подготовки09.03.03. Прикладная информатика
ПрофильПрикладная информатика в экономике
Форма обученияОчная
Общая трудоемкость3 ЗЕТ
Учебный план09_03_03_ПИЭ-2-2020
Часов по учебному плану 108
в том числе:
аудиторные занятия 42
самостоятельная работа 39
контроль 27
Виды контроля по семестрам
экзамены: 2

Распределение часов по семестрам

Курс (семестр) 1 (2) Итого
Недель 20
Вид занятий УПРПДУПРПД
Лекции 16 16 16 16
Лабораторные 26 26 26 26
Сам. работа 39 39 39 39
Часы на контроль 27 27 27 27
Итого 108 108 108 108

Программу составил(и):
rанд. физ. - мат. наук, Доцент, Исаева О.В.

Рецензент(ы):
rанд. физ. - мат. наук, Доцент, Половникова Е.С.

Рабочая программа дисциплины
Дискретная математика

разработана в соответствии с ФГОС:
Федеральный государственный образовательный стандарт высшего образования по направлению подготовки 09.03.03 Прикладная информатика (уровень бакалавриата) (приказ Минобрнауки России от 19.09.2017 г. № 922)

составлена на основании учебного плана:
09.03.03 Прикладная информатика
утвержденного учёным советом вуза от 30.06.2020 протокол № 6.

Рабочая программа одобрена на заседании кафедры
Кафедра экономики и эконометрики

Протокол от 01.09.2020 г. № 1
Срок действия программы: 2020-2021 уч. г.

Заведующий кафедрой
профессор, д.э.н.Шваков Е.Е.


Визирование РПД для исполнения в очередном учебном году

Рабочая программа пересмотрена, обсуждена и одобрена для
исполнения в 2020-2021 учебном году на заседании кафедры

Кафедра экономики и эконометрики

Протокол от 01.09.2020 г. № 1
Заведующий кафедрой профессор, д.э.н.Шваков Е.Е.


1. Цели освоения дисциплины

1.1.усвоение студентами теоретических основ дискретной математики и математической логики, составляющих фундамент ряда математических дисциплин и дисциплин прикладного характера

2. Место дисциплины в структуре ООП

Цикл (раздел) ООП: Б1.О.04

3. Компетенции обучающегося, формируемые в результате освоения дисциплины

УК-1 Способен осуществлять поиск, критический анализ и синтез информации, применять системный подход для решения поставленных задач
ОПК-1 Способен применять естественнонаучные и общеинженерные знания, методы математического анализа и моделирования, теоретического и экспериментального исследования в профессиональной деятельности;
В результате освоения дисциплины обучающийся должен
3.1.Знать:
3.1.1.принципы использования языка, средств, методов и моделей дискретной математики в дисциплинах, которым ее изучение должно предшествовать, а также в проблемах прикладного характера;
методы теории множеств, математической логики, алгебры высказываний, теории автоматов и теории алгоритмов
3.2.Уметь:
3.2.1.использовать методы дискретной математики при изучении дисциплин математического и естественно - научного и профессионального цикла
3.3.Иметь навыки и (или) опыт деятельности (владеть):
3.3.1.использования методов дискретной математики, который необходим для формирования соответствующих компетенций;
моделирования прикладных задач

4. Структура и содержание дисциплины

Код занятия Наименование разделов и тем Вид занятия Семестр Часов Компетенции Литература
Раздел 1. Элементы теории множеств
1.1. Множества. Подмножества и дополнения; объединения и перечисления Лекции 2 1 ОПК-1 Л2.2, Л1.2, Л2.3, Л3.1, Л2.1, Л1.1
1.2. Множества. Подмножества и дополнения; объединения и перечисления Лабораторные 2 2 ОПК-1 Л2.2, Л1.2, Л2.3, Л3.1, Л1.1
1.3. Множества. Подмножества и дополнения; объединения и перечисления Сам. работа 2 1 УК-1, ОПК-1 Л2.2, Л1.2, Л2.3, Л3.1, Л1.1
1.4. Отношения Лабораторные 2 2 УК-1, ОПК-1 Л2.2, Л1.2, Л2.3, Л3.1, Л1.1
1.5. Отношения Сам. работа 2 2 УК-1, ОПК-1 Л2.2, Л1.2, Л2.3, Л1.1
1.6. Счетные множества Лекции 2 2 УК-1, ОПК-1 Л2.2, Л1.2, Л2.3, Л3.1, Л1.1
1.7. Множества. Подмножества и дополнения; объединения и перечисления Лабораторные 2 2 УК-1, ОПК-1 Л2.2, Л1.2, Л2.3, Л3.1, Л1.1
1.8. Счетные множества Сам. работа 2 2 УК-1, ОПК-1 Л2.2, Л1.2, Л2.3, Л3.1, Л1.1
1.9. Кардинальные числа. Порядковые числа Сам. работа 2 2 УК-1, ОПК-1 Л2.2, Л1.2, Л2.3, Л1.3, Л1.1
Раздел 2. Математическая логика. Алгебра высказываний
2.1. Алгебра высказываний Лекции 2 1 УК-1, ОПК-1 Л2.2, Л1.2, Л2.3, Л1.3, Л1.1
2.2. Алгебра высказываний Лабораторные 2 2 УК-1, ОПК-1 Л2.2, Л1.2, Л2.3, Л1.3, Л1.1
2.3. Булевы функции Лекции 2 2 УК-1, ОПК-1 Л2.2, Л1.2, Л2.3, Л1.3, Л1.1
2.4. Булевы функции Лабораторные 2 2 ОПК-1 Л2.2, Л1.2, Л2.3, Л1.3, Л1.1
2.5. Теорема о полноте Лекции 2 2 УК-1, ОПК-1 Л2.2, Л1.2, Л2.3, Л1.3, Л1.1
2.6. Теорема о полноте Лабораторные 2 2 УК-1, ОПК-1 Л2.2, Л1.2, Л2.3, Л1.3, Л1.1
2.7. Приложения функций логики высказываний Сам. работа 2 2 УК-1 Л2.2, Л1.2, Л2.3, Л1.3, Л1.1
Раздел 3. Теория графов
3.1. Основные понятия теории графов и способы предстовления графов Лекции 2 2 ОПК-1 Л2.2, Л1.2, Л2.3, Л2.1, Л1.1
3.2. Теорема Л. Эйлера о плоских графах Лабораторные 2 4 ОПК-1 Л2.2, Л1.2, Л2.3, Л2.1, Л1.1
3.3. Основные понятия теории графов и способы предстовления графов Лабораторные 2 2 УК-1, ОПК-1 Л1.2, Л2.1, Л1.1
3.4. Оценка числа графов Сам. работа 2 2 УК-1, ОПК-1 Л2.2, Л1.2, Л2.3, Л2.1, Л1.1
3.5. Эйлеровы и гамельтоновы грифы Лекции 2 1 УК-1, ОПК-1 Л2.2, Л1.2, Л2.3, Л2.1, Л1.1
3.6. Деревья Лабораторные 2 4 УК-1 Л2.2, Л1.2, Л2.3, Л2.1, Л1.1
3.7. Экстремальные задачи: алгоритм Краскаля. Задача о четырех красках Сам. работа 2 2 ОПК-1 Л2.2, Л1.2, Л2.3, Л2.1, Л1.1
3.8. Теорема о целочисленности. Потоки в сетях. Теорема о максемальном потоке и минимальном размере Сам. работа 2 2 ОПК-1 Л2.2, Л1.2, Л2.3, Л2.1, Л1.1
Раздел 4. Элементы теории автоматов
4.1. Определение конечного автомата, способы изображения, примеры. Эквивалентность состояний. Основные понятия алгебры. Теорема о гомоморфизмах полугрупп. Лекции 2 1 УК-1, ОПК-1 Л2.2, Л1.2, Л2.3, Л1.3, Л1.1
4.2. Определение конечного автомата, способы изображения, примеры. Эквивалентность состояний. Основные понятия алгебры. Теорема о гомоморфизмах полугрупп. Сам. работа 2 2 УК-1, ОПК-1 Л2.2, Л1.2, Л2.3, Л1.3, Л1.1
4.3. Гомоморфизмы автоматов. Теорема о каноническом разложении гомоморфизма. Подавтомат, фактор-автомат, теорема о гомоморфизмах автоматов. Лекции 2 1 УК-1, ОПК-1 Л2.2, Л1.2, Л2.3, Л1.3, Л1.1
4.4. Гомоморфизмы автоматов. Теорема о каноническом разложении гомоморфизма. Подавтомат, фактор-автомат, теорема о гомоморфизмах автоматов. Сам. работа 2 2 УК-1, ОПК-1 Л2.2, Л1.2, Л2.3, Л1.3, Л1.1
4.5. Гомоморфизмы автоматов. Теорема о каноническом разложении гомоморфизма. Подавтомат, фактор-автомат, теорема о гомоморфизмах автоматов. Сам. работа 2 2 УК-1, ОПК-1 Л2.2, Л1.2, Л2.3, Л1.3, Л1.1
4.6. Автоматы Мура. Автоматы Мура и универсальные автоматы. Гомоморфизмы автоматов Мура. Теорема Крона-Кроуза (без доказательства). Лекции 2 1 УК-1, ОПК-1 Л2.2, Л1.2, Л2.3, Л1.3, Л1.1
4.7. Автоматы Мура. Автоматы Мура и универсальные автоматы. Гомоморфизмы автоматов Мура. Теорема Крона-Кроуза (без доказательства). Лабораторные 2 2 Л2.2, Л1.2, Л2.3, Л1.3, Л1.1
4.8. Автоматы Мура. Автоматы Мура и универсальные автоматы. Гомоморфизмы автоматов Мура. Теорема Крона-Кроуза (без доказательства). Сам. работа 2 4 УК-1, ОПК-1 Л2.2, Л1.2, Л2.3, Л1.3, Л1.1
Раздел 5. Элементы теории алгоритмов
5.1. Вычислимые функции, машины Тьюринга, тезис Черча. Примеры вычислимых функций. Рекурсивные и рекурсивно-перечислимые множества, их алгоритмическая характеристика. Теорема Поста. Лекции 2 1 УК-1 Л2.2, Л1.2, Л2.3, Л3.1, Л1.1
5.2. Вычислимые функции, машины Тьюринга, тезис Черча. Примеры вычислимых функций. Рекурсивные и рекурсивно-перечислимые множества, их алгоритмическая характеристика. Теорема Поста. Лабораторные 2 2 ОПК-1 Л2.2, Л1.2, Л2.3, Л3.1, Л1.1
5.3. Вычислимые функции, машины Тьюринга, тезис Черча. Примеры вычислимых функций. Рекурсивные и рекурсивно-перечислимые множества, их алгоритмическая характеристика. Теорема Поста. Сам. работа 2 6 ОПК-1 Л2.2, Л1.2, Л2.3, Л3.1, Л1.1
5.4. Примеры алгоритмически неразрешимых проблем, неразрешимость проблем самоприменимости и применимости. Теорема Поста-Маркова о существовании ассоциативного исчисления с алгоритмически неразрешимой проблемой равенства. Лекции 2 1 ОПК-1 Л2.2, Л1.2, Л2.3, Л3.1, Л1.1
5.5. Примеры алгоритмически неразрешимых проблем, неразрешимость проблем самоприменимости и применимости. Теорема Поста-Маркова о существовании ассоциативного исчисления с алгоритмически неразрешимой проблемой равенства. Сам. работа 2 2 ОПК-1 Л2.2, Л1.2, Л2.3, Л3.1, Л1.1
5.6. Примеры алгоритмически неразрешимых проблем, неразрешимость проблем самоприменимости и применимости. Теорема Поста-Маркова о существовании ассоциативного исчисления с алгоритмически неразрешимой проблемой равенства. Сам. работа 2 6 ОПК-1 Л2.2, Л1.2, Л2.3, Л3.1, Л1.1

5. Фонд оценочных средств

5.1. Контрольные вопросы и задания для проведения текущего контроля и промежуточной аттестации по итогам освоения дисциплины
см. Приложения
5.2. Темы письменных работ для проведения текущего контроля (эссе, рефераты, курсовые работы и др.)
см. Приложения
5.3. Фонд оценочных средств для проведения промежуточной аттестации
представлен отдельным документом

6. Учебно-методическое и информационное обеспечение дисциплины

6.1. Рекомендуемая литература
6.1.1. Основная литература
Авторы Заглавие Издательство, год Эл. адрес
Л1.1 Гашков С.Б., Фролов А.Б. ДИСКРЕТНАЯ МАТЕМАТИКА 2-е изд., испр. и доп. Учебник и практикум для академического бакалавриата: Гриф УМО ВО М.:Издательство Юрайт, 2018 biblio-online.ru
Л1.2 Шевелев Ю.П. Дискретная математика: учеб. пособие для вузов СПб.: Лань // ЭБС "Лань", 2008 e.lanbook.com
Л1.3 Редькин Н.П. Дискретная математика: Учебник "Физматлит" // ЭБС "Лань", 2009
6.1.2. Дополнительная литература
Авторы Заглавие Издательство, год Эл. адрес
Л2.1 Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы: Учебник СПб.: Лань // ЭБС "Лань", 2010// ЭБС "Лань"
Л2.2 Соболева Т.С., Чечкин А.В. Дискретная математика: учеб. для вузов М.: Академия, 2006
Л2.3 Микони С.В. Дискретная математика для бакалавра: множества, отношения, функции, графы: СПб.: Лань // ЭБС "Лань", 2012 e.lanbook.com
6.1.3. Дополнительные источники
Авторы Заглавие Издательство, год Эл. адрес
Л3.1 Гаврилов Г. П. , Сапоженко А. А. Задачи и упражнения по дискретной математике: усеб. пособие М.: Физматлит, 2005
6.2. Перечень ресурсов информационно-телекоммуникационной сети "Интернет"
Название Эл. адрес
Э1 Сайт библиотеки АлтГУ: www.lib.asu.ru;
Э2 электронно-библиотечная система издательства «Лань»: www.e.lanbook.com;
Э3 электронно-библиотечная система "Университетская библиотека online": www.biblioclub.ru;
Э4 свободная энциклопедия «Википедия»: http://ru.wikipedia.org
Э5 дискретная математика portal.edu.asu.ru
6.3. Перечень программного обеспечения
Microsoft Windows
Microsoft Office
7-Zip
AcrobatReader
6.4. Перечень информационных справочных систем
Информационная справочная система:
СПС КонсультантПлюс (инсталлированный ресурс АлтГУ или http://www.consultant.ru/).
Профессиональные базы данных:
1. Электронная база данных «Scopus» (http://www.scopus.com);
2. Электронная библиотечная система Алтайского государственного университета (http://elibrary.asu.ru/);
3. Научная электронная библиотека elibrary (http://elibrary.ru)

7. Материально-техническое обеспечение дисциплины

Аудитория Назначение Оборудование
Помещение для самостоятельной работы помещение для самостоятельной работы обучающихся Компьютеры, ноутбуки с подключением к информационно-телекоммуникационной сети «Интернет», доступом в электронную информационно-образовательную среду АлтГУ
Учебная аудитория для проведения занятий лекционного типа, занятий семинарского типа (лабораторных и(или) практических), групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации, курсового проектирования (выполнения курсовых работ), проведения практик Стандартное оборудование (учебная мебель для обучающихся, рабочее место преподавателя, доска)

8. Методические указания для обучающихся по освоению дисциплины

Основными формами аудиторных занятий являются лекции, органично сочетающиеся с практическими занятиями в рамках всего изучаемого курса.
На лекционных занятиях закладываются базовые теоретические знания по всем разделам изучаемой дисциплины. Они направлены на овладение общекультурными и профессиональными компетенциями. На основе полученных знаний формируется фундамент, необходимый для последующего глубокого изучения и освоения материала в рамках данной дисциплины.
На практических занятиях теоретические знания, полученные на лекциях, применяются для решения прикладных задач. Практические занятия направлены на овладение профессиональными компетенциями по применению математических методов и системного подхода в решении прикладных практических задач.
Самостоятельная работа студента включает в себя подготовку к аудиторным занятиям, самостоятельную работу по каждому разделу дисциплины, подготовку ко всем видам контрольных испытаний, в том числе экзамену.

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