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

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

рабочая программа дисциплины
Закреплена за кафедройКафедра экономики и эконометрики
Направление подготовки09.03.03. Прикладная информатика
ПрофильУправление IT-проектами; ERP-системы и прикладное программирование
Форма обученияЗаочная
Общая трудоемкость3 ЗЕТ
Учебный планz09_03_03_Прикладная информатика_Профили-2023
Часов по учебному плану 108
в том числе:
аудиторные занятия 14
самостоятельная работа 90
контроль 4
Виды контроля по курсам
зачеты: 2

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

Курс 2 Итого
Вид занятий УПРПДУПРПД
Лекции 4 4 4 4
Лабораторные 10 10 10 10
Сам. работа 90 90 90 90
Часы на контроль 4 4 4 4
Итого 108 108 108 108

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

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

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

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

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

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

Протокол от 07.06.2023 г. № 9
Срок действия программы: 2023-2024 уч. г.

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


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

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

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

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


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

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

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

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

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

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

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

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

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

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

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
AcrobatReaderMicrosoft Office 2010 (Office 2010 Professional, № 4065231 от 08.12.2010), (бессрочно);
Microsoft Windows 7 (Windows 7 Professional, № 61834699 от 22.04.2013), (бессрочно);
Chrome (http://www.chromium.org/chromium-os/licenses), (бессрочно); 7-Zip (http://www.7-zip.org/license.txt), (бессрочно);
AcrobatReader (http://wwwimages.adobe.com/content/dam/Adobe/en/legal/servicetou/Acrobat_com_Additional_TOU-en_US-20140618_1200.pdf), (бессрочно);
ASTRA LINUX SPECIAL EDITION (https://astralinux.ru/products/astra-linux-special-edition/), (бессрочно);
LibreOffice (https://ru.libreoffice.org/), (бессрочно);
Веб-браузер Chromium (https://www.chromium.org/Home/), (бессрочно);
Антивирус Касперский (https://www.kaspersky.ru/), (до 23 июня 2024);
Архиватор Ark (https://apps.kde.org/ark/), (бессрочно);
Okular (https://okular.kde.org/ru/download/), (бессрочно);
Редактор изображений Gimp (https://www.gimp.org/), (бессрочно)
6.4. Перечень информационных справочных систем
Информационная справочная система:
СПС КонсультантПлюс (инсталлированный ресурс АлтГУ или http://www.consultant.ru/).
Профессиональные базы данных:
1. Электронная база данных «Scopus» (http://www.scopus.com);
2. Электронная библиотечная система Алтайского государственного университета (http://elibrary.asu.ru/);
3. Научная электронная библиотека elibrary (http://elibrary.ru)

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

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

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

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

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