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

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

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

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

Курс 3 Итого
Вид занятий УПРПДУПРПД
Лекции 4 4 4 4
Лабораторные 6 6 6 6
Сам. работа 94 94 94 94
Часы на контроль 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
Срок действия программы: 2021-2024 уч. г.

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


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

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

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

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

6.1. Рекомендуемая литература
6.1.1. Основная литература
Авторы Заглавие Издательство, год Эл. адрес
Л1.1 Шевелев Ю.П. Дискретная математика: учеб. пособие для вузов СПб.: Лань // ЭБС "Лань", 2008 e.lanbook.com
Л1.2 Редькин Н.П. Дискретная математика: Учебник "Физматлит" // ЭБС "Лань", 2009
Л1.3 Гашков С.Б., Фролов А.Б. ДИСКРЕТНАЯ МАТЕМАТИКА 2-е изд., испр. и доп. Учебник и практикум для академического бакалавриата: Гриф УМО ВО М.:Издательство Юрайт, 2018 biblio-online.ru
6.1.2. Дополнительная литература
Авторы Заглавие Издательство, год Эл. адрес
Л2.1 Соболева Т.С., Чечкин А.В. Дискретная математика: учеб. для вузов М.: Академия, 2006
Л2.2 Микони С.В. Дискретная математика для бакалавра: множества, отношения, функции, графы: СПб.: Лань // ЭБС "Лань", 2012 e.lanbook.com
Л2.3 Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы: Учебник СПб.: Лань // ЭБС "Лань", 2010// ЭБС "Лань"
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. Методические указания для обучающихся по освоению дисциплины

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

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