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

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

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

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

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

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

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