Федеральное агентство связи
Федеральное государственное образовательное бюджетное
учреждение высшего профессионального образования
«Сибирский государственный университет телекоммуникаций и информатики»
(ФГОБУ ВПО «СибГУТИ»)
Форма утверждена научно-методическим советом
университета протокол от 18 декабря 2012 г.
УТВЕРЖДАЮ
Декан факультета
автоматической электросвязи,
д. т.н., профессор
_____________
«____» ___________ 2012 г.
РАБОЧАЯ ПРОГРАММА
по дисциплине «Дискретная математика»,
для специальности 090302 «Информационная безопасность телекоммуникационных систем»,
квалификация специалист,
специализация «Защита информации в системах связи и управления».
Факультет информатики и вычислительной техники (ИВТ)
Кафедра высшей математики (ВМ)
Программу разработала: доцент кафедры ВМ,
____________________
(ПОДПИСЬ)
Новосибирск – 2012
ОБЩЕЕ ОПИСАНИЕ ДИСЦИПЛИНЫ
Рабочая программа разработана согласно Федеральному государственному образовательному стандарту высшего профессионального образования по специальности 090302 «Информационная безопасность телекоммуникационных систем» (квалификация специалист) и рабочему учебному плану по специализации «Защита информации в системах связи и управления». Дисциплина относится к базовой части математического и естественнонаучного цикла (С2.Б). Шифр дисциплины в рабочем учебном плане – С2.Б.4.
Виды учебной работы
Виды учебной работы | Семестр 1 | Семестр 2 | Семестр 3 | Семестр 4 | Семестр 5 | Семестр 6 | Семестр 7 | Семестр 8 | Семестр 9 | Семестр 10 | Всего |
Лекции, часов | – | – | – | 50 | – | – | – | – | – | – | 50 |
Лабораторные работы, часов | – | – | – | – | – | – | – | – | – | – | – |
Практические занятия, часов | – | – | – | 52 | – | – | – | – | – | – | 52 |
Всего аудиторных занятий, часов | – | – | – | 102 | – | – | – | – | – | – | 102 |
- из них в интерактивной[1] форме, часов | – | – | – | 30 | – | – | – | – | – | – | 30 |
Самостоятельная работа студентов, часов | – | – | – | 78 | – | – | – | – | – | – | 78 |
Количество часов, отводимых на экзамен | – | – | – | 36 | – | – | – | – | – | – | 36 |
Общая трудоемкость дисциплины, часов | – | – | – | 216 | – | – | – | – | – | – | 216 |
Формы и сроки контроля: | |||||||||||
Курсовая работа / проект | – | – | – | – | – | – | – | – | – | – | – |
Расчетно-графическое задание | – | – | – | X | – | – | – | – | – | – | |
Коллоквиум | – | – | – | – | – | – | – | – | – | – | |
Контрольная работа | – | – | – | – | – | – | – | – | – | – | |
Зачет | – | – | – | – | – | – | – | – | – | – | |
Экзамен | – | – | – | X | – | – | – | – | – | – | |
Общая трудоемкость дисциплины, ЗЕ* | – | – | – | 6 | – | – | – | – | – | – | 6 |
*Одна зачетная единица (ЗЕ) эквивалентна 36часам.
1 ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ
Цель преподавания дисциплины «Дискретная математика» состоит в развитии логического и алгоритмического мышления; изучения основ математического аппарата, применяемого для решения задач управления и алгоритмизации процессов обработки информации; ознакомлении с элементами теории множеств, логическими функциями, графами и конечными автоматами; подготовке математических основ изучения специальных дисциплин в области телекоммуникаций.
2 МЕСТО ДИСЦИПЛИНЫ В СТРУКТУРЕ
ОСНОВНОЙ ОБРАЗОВАТЕЛЬНОЙ ПРОГРАММЫ
Дисциплина относится к базовой части математического и естественнонаучного цикла (С2.Б). Шифр дисциплины в рабочем учебном плане – С2.Б.2. Изучение данной дисциплины базируется на материале школьного курса «Математика». Дисциплина является предшествующей для большинства дисциплин, в том числе: «Моделирование систем и сетей телекоммуникаций», «Теория информации и кодирования».
3 ТРЕБОВАНИЯ К РЕЗУЛЬТАТАМ ОСВОЕНИЯ ДИСЦИПЛИНЫ
3.1 Процесс изучения дисциплины направлен на формирование следующих компетенций:
- ОК-1 способностью логически верно, аргументировано и ясно строить устную и письменную речь на русском языке, готовить и редактировать тексты профессионального назначения, публично представлять собственные и известные научные результаты, вести дискуссии;
- ОК-10 способностью самостоятельно применять методы и средства познания, обучения и самоконтроля для приобретения новых знаний и умений, в том числе в новых областях, непосредственно не связанных со сферой деятельности, развития социальных и профессиональных компетенций, изменения вида своей профессиональной деятельности;
- ПК-1 способностью выявлять естественнонаучную сущность проблем, возникающих в ходе профессиональной деятельности, и применять соответствующий физико-математический аппарат для их формализации, анализа и выработки решения.
3.2 В результате освоения дисциплины студент должен:
знать:
- основные операции над множествами, определения и свойства соответствий, функций и отношений;
- определения и свойства функций алгебры логики;
- простейшие алгоритмические модели (машины Тьюринга);
- основные понятия теории графов;
уметь:
- формулировать простые и составные высказывания на языке формул алгебры логики;
- решать простейшие задачи на графах (о минимальном соединении);
- строить простейшие конечные автоматы и функциональные схемы.
- находить характеристики простейших алгоритмических моделей (машины Тьюринга);
4 СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
№ учеб. недели | Наименование лекционных тем (разделов) дисциплины | Часов |
1, 2 | Тема1. ВВЕДЕНИЕ. 1. Разделы «дискретной математики». 2. Классические задачи «дискретной математики». Тема 2. ТЕОРИЯ МНОЖЕСТВ. 2.1 Алгебра множеств. 1. Понятия множества, равенство множеств. 2. Понятие подмножества, отношение включения. 3. Алгебра множеств. 4. Индикаторы множеств. | 4 |
2 | Тема 2. ТЕОРИЯ МНОЖЕСТВ. 2.2 Отношения. 1. Декартово произведение множеств. 2. Отношения. Специальные бинарные отношения. Классы эквивалентности. | 2 |
3, 4 | Тема 2. ТЕОРИЯ МНОЖЕСТВ. 2.2 Отношения. 3. Функции. Взаимно-обратные функции. 2.3. Комбинаторика. 1. Основные понятия и правила. 2. Сочетания, размещения, перестановки. | 4 |
4 | Тема 3. МАТЕМАТИЧЕСКАЯ ЛОГИКА. 3.1 Алгебра высказываний. 1. Высказывания. Логические операции над высказываниями. | 2 |
5, 6 | Тема 3. МАТЕМАТИЧЕСКАЯ ЛОГИКА. 3.1 Алгебра высказываний. 2. Пропозициональные формулы и истинностные таблицы. 3. Выполнимые и опровержимые формулы. Тавтологии и противоречия. | 4 |
6 | Тема 3. МАТЕМАТИЧЕСКАЯ ЛОГИКА. 3.1 Алгебра высказываний. | 2 |
7, 8 | Тема 3. МАТЕМАТИЧЕСКАЯ ЛОГИКА. 3.1 Алгебра высказываний. 4. Равносильные формулы. Основные равносильности. Правила равносильных преобразований. 3.2 Булевы функции. 1. Булевы функции. Теоремы о представлении булевой функции. 2. Булевы функции одной и двух переменных. Существенные и несущественные переменные. | 4 |
8 | Тема 3. МАТЕМАТИЧЕСКАЯ ЛОГИКА. 3.2 Булевы функции. 3. Двойственные функции. Принцип двойственности. 4. Нормальные формы формул. Теоремы о приведении формулы к нормальным формам. 5. Совершенные нормальные формы. Теоремы о приведении формулы к совершенным нормальным формам. | 2 |
9, 10 | Тема 3. МАТЕМАТИЧЕСКАЯ ЛОГИКА. 3.2 Булевы функции. 6. Полные системы функций. Многочлен Жегалкина. 7. Функционально замкнутые классы функций. Базис функционально замкнутого класса. Теорема Поста. 8. Минимизация ДНФ. 9. Релейно-контактные схемы. Задачи теории релейно-контактных схем. 3.3 Алгебра предикатов. 1. Предикаты, кванторы. Формулы логики предикатов. | 4 |
10 | Тема 3. МАТЕМАТИЧЕСКАЯ ЛОГИКА. 3.3 Алгебра предикатов. 2. Операции над предикатами. | 2 |
11, 12 | Тема 3. МАТЕМАТИЧЕСКАЯ ЛОГИКА. 3.3 Алгебра предикатов. 3. Основные равносильности алгебры предикатов. Приведенные и нормальные формулы. 3.4 Элементы теории алгоритмов. 1. Понятие алгоритма. Описание машины Тьюринга. 2. Правильно вычислимые функции по Тьюрингу. | 4 |
12 | Тема 3. МАТЕМАТИЧЕСКАЯ ЛОГИКА. 3.4 Элементы теории алгоритмов. 3. Композиция машин Тьюринга. Примеры машин Тьюринга. 4. Алгоритмически разрешимые и неразрешимые задачи. | 2 |
13, 14 | Тема 4. ТЕОРИЯ ГРАФОВ. 4.1. Основные понятия теории графов. 1. Основные определения, понятия и теоремы теории графов. 4.2. Специальные графы. 1. Основные виды и назначение специальных графов. 4.3. Задачи на графах. 1. Отношения смежности, инцидентности. Теорема «о рукопожатиях». 2. Матричное задание графов. 3. Изоморфизм графов. Подграфы. Операции на графах. | 4 |
14 | Тема 4. ТЕОРИЯ ГРАФОВ. 4.3. Задачи на графах. 4. Связность графов и орграфов. Компоненты связности. 5. Матрицы достижимости, связанности, сильной связанности. Выделение компонент связности. 6. Эйлеровы и гамильтоновы графы. | 2 |
15, 16 | Тема 4. ТЕОРИЯ ГРАФОВ. 4.3. Задачи на графах. 7. Расстояния и минимальные пути. Алгоритм Дейкстры. 8. Деревья и лес. 9. Построение остовного и минимального остовного деревьев. 10. Применение графов при решении задач теории связи. | 4 |
16 | Тема 5. ТЕОРИЯ КОНЕЧНЫХ АВТОМАТОВ И ФУНКЦИОНАЛЬНЫХ СИСТЕМ. 5.1. Конечные детерминированные автоматы. 1. Понятие конечного детерминированного автомата. Автоматы Мура и Мили. 2. Таблицы переходов-выходов. 3. Диаграммы Мура. | 2 |
17 | Тема 5. ТЕОРИЯ КОНЕЧНЫХ АВТОМАТОВ И ФУНКЦИРНАЛЬНЫХ СИСТЕМ. 5.2. Проектирование конечных автоматов. 1. Эквивалентные состояния. Минимизация конечных автоматов. 2. Построение канонических уравнений. Минимизация уравнений. 5.3. Проектирование дискретных устройств. 1. Функциональные и логические элементы. 2. Проектирование комбинационных логических автоматов. | 2 |
ВСЕГО | 50 |
5 СОДЕРЖАНИЕ ПРАКТИЧЕСКИХ (СЕМИНАРСКИХ) ЗАНЯТИЙ
№ учеб. недели | Наименование лабораторных работ, практических занятий | Часов |
1 | Тема 1. ТЕОРИЯ МНОЖЕСТВ. 1.1 Алгебра множеств. 1. Понятия множества, равенство множеств. 2. Понятие подмножества, отношение включения. 3. Алгебра множеств. 4. Индикаторы множеств. | 4 |
2 | Тема 1. ТЕОРИЯ МНОЖЕСТВ. 1.2 Отношения. 1. Декартово произведение множеств. 2. Отношения. Специальные бинарные отношения. Классы эквивалентности. | 2 |
3 | Тема 1. ТЕОРИЯ МНОЖЕСТВ. 1.2 Отношения. 3. Функции. Взаимно-обратные функции. 1.3. Комбинаторика. 1. Основные понятия и правила. 2. Сочетания, размещения, перестановки. | 4 |
4 | Тема 2. МАТЕМАТИЧЕСКАЯ ЛОГИКА. 2.1 Алгебра высказываний. 1. Высказывания. Логические операции над высказываниями. | 2 |
5 | Тема 2. МАТЕМАТИЧЕСКАЯ ЛОГИКА. 2.1 Алгебра высказываний. 2. Пропозициональные формулы и истинностные таблицы. 3. Выполнимые и опровержимые формулы. Тавтологии и противоречия. 4. Равносильные формулы. Основные равносильности. Равносильные преобразования. | 4 |
6 | Тема 2. МАТЕМАТИЧЕСКАЯ ЛОГИКА. 2.2 Булевы функции. 1. Булевы функции одной и двух переменных. Существенные и несущественные переменные. | 2 |
7 | Тема 2. МАТЕМАТИЧЕСКАЯ ЛОГИКА. 2.2 Булевы функции. 2. Двойственные функции. 3. Нормальные формы формул. 4. Совершенные нормальные формы. 6. Полные системы функций. Многочлен Жегалкина. 7. Функционально замкнутые классы функций. 8. Минимизация ДНФ. 9. Релейно-контактные схемы. | 4 |
8 | Тема 2. МАТЕМАТИЧЕСКАЯ ЛОГИКА. 2.3 Алгебра предикатов. 1. Предикаты, кванторы. Формулы логики предикатов. | 2 |
9 | Тема 2. МАТЕМАТИЧЕСКАЯ ЛОГИКА. 2.3 Алгебра предикатов. 2. Операции над предикатами. 3. Основные равносильности алгебры предикатов. Приведенные и нормальные формулы. | 4 |
10 | Тема 2. МАТЕМАТИЧЕСКАЯ ЛОГИКА. 2.4 Элементы теории алгоритмов. 1. Машины Тьюринга. 2. Правильно вычислимые функции по Тьюрингу. | 2 |
11 | Тема 2. МАТЕМАТИЧЕСКАЯ ЛОГИКА. 2.4 Элементы теории алгоритмов. 3. Композиция машин Тьюринга. Примеры машин Тьюринга. 4. Алгоритмически разрешимые и неразрешимые задачи. | 4 |
12 | Тема 3. ТЕОРИЯ ГРАФОВ. 3.1. Основные понятия теории графов. 1. Основные определения, понятия теории графов. | 2 |
13 | Тема 3. ТЕОРИЯ ГРАФОВ. 3.2. Задачи на графах. 1. Отношения смежности, инцидентности. 2. Матричное задание графов. 3. Изоморфизм графов. Подграфы. Операции на графах. 4. Связность графов и орграфов. Компоненты связности. 5. Матрицы достижимости, связанности, сильной связанности. Выделение компонент связности. | 4 |
14 | Тема 3. ТЕОРИЯ ГРАФОВ. 3.2. Задачи на графах. 6. Эйлеровы и гамильтоновы графы. | 2 |
15 | Тема 3. ТЕОРИЯ ГРАФОВ. 3.2. Задачи на графах. 7. Расстояния и минимальные пути. Алгоритм Дейкстры. 8. Деревья и лес. 9. Построение остовного и минимального остовного деревьев. 10. Применение графов при решении задач теории связи. | 4 |
16 | Тема 4. ТЕОРИЯ КОНЕЧНЫХ АВТОМАТОВ И ФУНКЦИОНАЛЬНЫХ СИСТЕМ. 4.1. Конечные детерминированные автоматы. 1. Автоматы Мура и Мили. 2. Таблицы переходов-выходов. 3. Диаграммы Мура. | 2 |
17 | Тема 4. ТЕОРИЯ КОНЕЧНЫХ АВТОМАТОВ И ФУНКЦИРНАЛЬНЫХ СИСТЕМ. 4.2. Проектирование конечных автоматов. 1. Эквивалентные состояния. Минимизация конечных автоматов. 2. Построение канонических уравнений. Минимизация уравнений. 4.3. Проектирование дискретных устройств. 1. Функциональные и логические элементы. 2. Проектирование комбинационных логических автоматов. | 4 |
ВСЕГО | 52 |
6 СОДЕРЖАНИЕ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ
Виды и содержание самостоятельной работы | Кол-во ЗЕ /часов | Формы и контроль | Литература и дидактические материалы |
1. Подготовка к практическим занятиям | 0,7/26 | выполнение заданий на занятиях | Лекционный материал, литература по дисциплине |
2. Выполнение домашних заданий | 0,7/25 | проверка наличия д/з | |
3. Выполнение РГЗ | 0,7/25 | защита РГЗ | |
4. Подготовка к экзамену | 1/36 | экзамен | |
ВСЕГО | 3,1/114 |
7 ИСПОЛЬЗУЕМЫЕ ИНТЕРАКТИВНЫЕ ФОРМЫ
И МЕТОДЫ ОБУЧЕНИЯ ПО ДИСЦИПЛИНЕ
Виды учебных занятий: лекции (Л), практические (семинарские) занятия (ПЗ), индивидуальные (групповые) консультации (К), самостоятельная работа студентов (СРС) по выполнению различных видов заданий.
Интерактивные образовательные методы и технологии: деловые игры, дискуссии, дидактические игры, анализ конкретных ситуаций, мозговой штурм, предметная олимпиада, проблемная лекция, пресс-конференция и другие методы, применяемые при реализации ООП.
№ п/п | Тема | Объем в часах* | Вид учебных занятий | Используемые интерактивные методы и технологии | Формируемые компетенции (ОК, ПК) |
1 | Теория множеств | 6 | ПЗ | Дискуссия, Мозговой штурм | ОК-7, ОК-10, ПК-1 |
2 | Математическая логика | 8 | ПЗ | Дискуссия, Мозговой штурм | ОК-7, ОК-10, ПК-1 |
3 | Теория графов | 8 | ПЗ | Дискуссия, Мозговой штурм | ОК-7, ОК-10, ПК-1 |
4 | Теория конечных автоматов | 4 | ПЗ | Дискуссия, Мозговой штурм | ОК-7, ОК-10, ПК-1 |
5 | Теория множеств | 1 | К | Мозговой штурм | ОК-7, ОК-10, ПК-1 |
6 | Математическая логика | 1 | К | Мозговой штурм | ОК-7, ОК-10, ПК-1 |
7 | Теория графов | 1 | К | Олимпиада | ОК-7, ОК-10, ПК-1 |
8 | Теория конечных автоматов | 1 | К | Мозговой штурм | ОК-7, ОК-10, ПК-1 |
ВСЕГО | 30 |
*Доля занятий, проводимых в интерактивной форме, в соответствии с ФГОС для данного профиля (направления) подготовки.
8 УЧЕБНО-МЕТОДИЧЕСКОЕ
И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ПО ДИСЦИПЛИНЕ
8.1 Список основной литературы
1. Бернштейн, по дискретной математике [Текст] : учеб. пособие / , ; Сиб. гос. ун-т телекоммуникаций и информатики. - Новосибирск : [б. и.], 20с. (78 экз)
2. Храмова, по теории графов [Текст] : учеб. пособие / ; Сиб. гос. ун-т телекоммуникаций и информатики. - Новосибирск : [б. и.], 20с. (75экз., электронный ресурс: http://ellib. *****/ellib/2011/375_Hramova_LEKCII_teor_graf. rar)
8.2 Список дополнительной литературы
3. Новиков, математика для программистов [Текст] : учеб. пособие / . - СПб. : ПИТЕР, 20с. (35 экз.)
4. Пономарев, математика для инженеров [Текст] : учеб. пособие / . - М. : Горячая линия-Телеком, 20с. (1 экз)
5. Мальцев, математика [Текст] : учеб. пособие / . - 2-е изд., испр. - СПб. : Лань, 20с. (30 экз)
6. Бернштейн, математика [Текст] : учеб. пособие / , Р.Н. Марков, Т.В. Храмова; Сиб. гос. ун-т телекоммуникаций и информатики. - Новосибирск : [б. и.], 20с. (386 экз.)
7. Бернштейн, математика [Текст] : сборник задач / , ; Сиб. гос. ун-т телекоммуникаций и информатики. - Новосибирск : [б. и.], 20с. (845 экз.)
8. Яблонский, в дискретную математику [Текст] : учеб. пособие / . - 4-е изд., стереотип. - М. : Высш. шк, 20с. (1 экз.)
9. Оре, О. Графы и их применение [Текст] : монография / пер. с англ. ; под ред. и с предисл. . - 3-е изд., стереотип. - М. : КомКнига, 20с. (1 экз.)
10. Иванов, математика. Алгоритмы и программы [Текст] : учеб. пособие / . - М. : Лаборатория Базовых Знаний, 20с. (1 экз.)
11. Галкина, математика [Текст] : учеб. пособие / ; Сиб. гос. ун-т телекоммуникаций и информатики. - Новосибирск : [б. и.], 20с. (364 экз.)
12. Судоплатов, математика [Текст] : учебник / , . - 2-е изд., перераб. - М. : ИНФРА-М, 20с. (1 экз.)
13. Кузнецов, математика для инженера [Текст] : [учебник] / . - 4-е изд., стереотип. - СПб. : Лань, 20с. (1 экз.)
14. Иванов, математика. Алгоритмы и программы. Полный курс [Текст] : [учеб. пособие] / . - М. : Физматлит, 20с. (5 экз.)
15. Судоплатов, дискретной математики [Текст] : учебник / , . - М. : ИНФРА-М ; Новосибирск : НГТУ, 20с. (1 экз.)
9 СОГЛАСОВАНИЕ РАБОЧЕЙ ПРОГРАММЫ
Кафедра, Ф. И.О., должность | Дисциплина (ы) кафедры | Замечания и предложения | Подпись, дата. |
10 ПЕРЕЧЕНЬИЗМЕНЕНИЙ И ДОПОЛНЕНИЙ К РАБОЧЕЙ ПРОГРАММЕ
Дата | Содержание изменений и дополнений (по темам и разделам) | Примечание |
Рабочая программа обсуждена на заседании Кафедры ВМ
Протокол № от "____" __________20__ г.
Заведующий кафедрой ВМ _____________________
Рабочая программа обсуждена на заседании кафедры
Протокол № от "____" __________20__ г.
Заведующий кафедрой ВМ _____________________
Рабочая программа обсуждена на заседании кафедры
Протокол № от "____" __________20__ г.
Заведующий кафедрой ВМ _____________________
Рабочая программа обсуждена на заседании кафедры
Протокол № от "____" __________20__ г.
Заведующий кафедрой ВМ _____________________
Рабочая программа обсуждена на заседании кафедры
Протокол № от "____" __________20__ г.
Заведующий кафедрой ВМ _____________________
[1] Доля занятий в интерактивной форме не менее 20% от общего количества аудиторных занятий, в соответствии с ФГОС для данного направления подготовки.
