Обзор дисциплины «Дискретная математика»

Семестр: 3-ий,    Трудоёмкость: 144 часов,     Контроль: экзамен и коллоквиумы.


Цели дисциплины

Целью дисциплины «Дискретная математика» является изучение и освоение методов дискретной математики, наиболее применяемых при проектировании и эксплуатации вычислительных машин, комплексов, систем и сетей. Формирование практических навыков разработки и анализа алгоритмов над объектами дискретной математики. Дисциплина базируется на знаниях, полученных студентами в курсах «Высшая математика», «Математическая логика и теория алгоритмов», «Вычислительная математика».

Задачи дисциплины

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

Место дисциплины

Дисциплина является обязательной и относится к вариативной части цикла Б2 «Математический и естественнонаучный цикл». Дисциплина изучается в первом семестре второго курса и базируется на сведениях, полученных абитуриентами при выборе направления подготовки в высшем учебном заведении, а также на компетенциях, полученных студентом при освоении курсов: «Математика», «Информатика». К основным задачам изучаемой дисциплины следует отнести формирование умений и навыков по следующим направлениям: проецирование понятий множества и операций на множествах на предметную область автоматизированного проектирования сложных систем; построение структурных моделей с использованием теории графов; реализация операций алгебры логики при алгоритмизации процессов принятия решений. Дисциплина является предшествующей для следующих дисциплин «Теория вероятностей и математическая статистика», «Моделирование систем», «Программирование», «ЭВМ и периферийные устройства».


Результаты освоения дисциплины

В результате изучения данной учебной дисциплины студент:

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


Содержание основных разделов дисциплины

Цикл лекционных и практических занятий по учебной дисциплине включает следующий перечень тем и их краткое содержание:

Роль дискретной математики при разработке компьютерных систем

Роль дискретной математики при разработке процессоров вычислительных машин, а так же при передаче цифровой информации по компьютерным сетям.

Задание множеств и осуществление операций над ними

Способы задания. Операции объединения, пересечения, разности, дополнения и декартова произведения. Диаграммы Венна. Аксиоматика теории множеств. Алгебра Кантора. Минимизация представления множеств.

Отношения и их свойства

Бинарные отношения. Способы задания бинарных отношений. Свойства бинарных отношений. Разбиения. Отношения эквивалентности и порядка. Представление n-арных отношений бинарными. Алгебра отношений.

Отображения и их свойства

Понятие отображения. Отображения, заданные на одном множестве. Определение функции. Представление функции с помощью массива. Обратная функция. Функция времени. Понятие функционала. Понятие оператора.

Графовые структуры

Понятие графа. Способы задания графов. Основные свойства и характеристики. Виды графов. Подграфы. Матрицы, ассоциированные с графами. Степени вершин. Маршруты, цепи и циклы. Компоненты связности. Точки сочленения. Мосты. Вершинная и реберная связность. Связность ориентированных графов. Определения. Матрицы циклов и разрезов.

Операции на графах

Расстояние между вершинами. Диаметр и радиус графа. Унарные и бинарные операции над графами. Дополнение графа. Удаление и добавление вершин. Удаление и добавление ребер. Объединение графов. Пересечение графов. Вершинное число независимости. Реберное число независимости. Вершинное и реберное покрытие графа. Эйлеровы циклы. Ориентированные деревья. Упорядоченные деревья. Бинарные деревья.

Алгебра логики

Логика высказываний. Логические связки. Формулы логики высказываний. Булевы или двоичные функции. Способы задания. Булевы функции одной и двух переменных и их свойства. Формулы булевой алгебры. Основные законы булевой алгебры. Эквивалентность формул. Принцип двойственности. Определение функционально полной системы элементарных булевых функций. Примеры функционально полных базисов. Важнейшие замкнутые классы.

Минимизация формул алгебры логики

Разложение булевых функций по переменным. Совершенные дизъюнктивные (СДНФ) и совершенные конъюнктивные нормальные формы (СКНФ). Переход от СДНФ к СКНФ и наоборот. Геометрическое представление булевых функций. Минимизация булевых функций. Эквивалентные преобразования. Карты Карно.

Структурное представление переключательных функций

Алгебра переключательных функций. Реализация переключательных функций в различных базисах. Представление булевых функций в виде структурных элементов инвертора, конъюнктора, дизъюнктора. Схемы из функциональных элементов. Минимизация схем.

Темы практических занятий

Минимизация представления множеств.

Разбиения. Отношения эквивалентности и порядка.

Определение функции. Представление функции с помощью массива. Обратная функция.

Матрицы, ассоциированные с графами.

Формулы булевой алгебры. Эквивалентность формул.

Переход от СДНФ к СКНФ и наоборот.

Темы лабораторного практикума

Представление и выполнение операций над множествами в виде диаграмм Эйлера-Венна;

Формы представления графовых структур;

Вершинная и реберная связность графов;

Внешняя устойчивость и покрытия в графах;

Приложения графов в вычислительных алгоритмах;

Транспортная задача в сетевой постановке;

Реализация алгебры логики на примере языка таблиц решений;

Минимизация формул алгебры логики;


Самостоятельная работа

Самостоятельная работа включает в себя:

Текущий контроль самостоятельной работы студентов осуществляется в форме коллоквиумов и консультаций. Итоговый контроль самостоятельной работы студентов осуществляется в форме экзамена.

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

Учебно-методическое обеспечение дисциплины включает печатную и электронную литературу, интегрированные справочные системы, авторские методические материалы, Интернет публикации и форумы.

    Основная литература:

  1. Халимон В.И. Дискретная математика. (Теория множеств, операции на графах, булевы функции): учеб. Пособие / В.И. Халимон, О. В. Проститенко, А. Ю. Рогов.- СПб., СПбГТИ(ТУ), 2009.-89 с.
  2. Халимон В.И. Применение методики сетевых графиков в автоматизированном проектировании: учеб. пособие / Т. Б. Чистякова, Л.Ф. Колесник, В. И. Халимон . -СПб., СПбГТИ(ТУ), 2009.-74 с.
  3. Дополнительная литература:

  4. Новиков, Ф.А. Дискретная математика для программистов / Ф. А. Новиков. – СПб: Питер, 2000.- 304 с.
  5. Белоусов, А.И., Ткачев С.В. Дискретная математика: Учеб. для вузов / В.С. Зарубина, А.П. Крищенко; под. ред. В.С. Зарубина.- М.: Изд-во МГТУ им. Н.Э.Баумана, 2001. – 744 с.
  6. Халимон, В. И. Использование программного комплекса «Комплекс ГРАФ» для исследования структур сложных систем.: Метод. Указания / Халимон В. И., Проститенко О. В., Рогов, А. Ю., Крюков А. В..- СПб., СПбГТИ(ТУ), 2001.-42 с.
  7. Халимон, В.И. Использование программного комплекса «GRAF TOOLBOX» для изучения операций на графах: Метод. Указания / Халимон В.И., Проститенко О.В. .- СПб.: СПбГТИ(ТУ), 2002.-56 с.
  8. Халимон, В.И. Дискретная математика. Учеб. Пособие / Халимон В.И., Проститенко О.В., Рогов, А.Ю.- СПб., СПбГТИ(ТУ), 2008.-105 с.
  9. программное обеспечение и Интернет-ресурсы:

  10. Халимон В.И.,Рогов А.Ю., Проститенко О.В. Программа «GRAF TOOLBOX» Свидетельство об официальной регистрации программ для ЭВМ №2002611910 от 12 ноября 2002г.
  11. Халимон В.И., Проститенко О.В. Программа «DECISION TABLE TOOLBOX» Свидетельство об официальной регистрации программ для ЭВМ №2003611869 от 12 августа 2003г.
  12. Халимон В.И., Рогов А.Ю. Проститенко О.В. Программа «GRAF. PETRINET. SMO.(3 Tools Solution)» Свидетельство о государственной регистрации программы для ЭВМ №2009612134 от 27 апреля 2009г.
  13. Халимон, В.И. Использование программного комплекса «GRAF TOOLBOX» для изучения операций на графах: Метод. Указания / Халимон В.И., Проститенко О.В. - СПб.: СПбГТИ(ТУ), 2002.-56 с.
  14. Халимон В. И., Колесник Л. Ф. Программа: "LingvoGraf, ASPR" Свидетельство о государственной регистрации программы для ЭВМ №2010614352 от 06 июля 2010г.

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

Классы 1, 4, 5, 6, 9 (кафедры системного анализа), Microsoft Windows 7, Internet Explorer, Microsoft Word 2010.


Вернуться к списку дисциплин бакалавриата

Страничка разработчика УМК/РПД дисциплин