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

Цели и задачи дисциплины
Целью дисциплины является овладение базовыми понятиями и теоретическими основами дискретной математики; формирование математической культуры студента; умение формулировать в комбинаторно-графовых терминах задачи, связанные с дискретными объектами; формирование у студентов способности к логическому мышлению, анализу и восприятию информации, изучению новых научных результатов, современной научной литературы в соответствии с профилем объекта профессиональной деятельности; овладение современным математическим аппаратом для дальнейшего использования при решении теоретических и прикладных задач. Задачи дисциплины: − изучение математического аппарата дискретной математики; − обучение методам решения прикладных задач с применением методов дискретной математики. В результате освоения дисциплины студент должен получить представление о решении следующей профессиональной задачи: применение методов математического и алгоритмического моделирования при анализе прикладных проблем; использование базовых математических задач и математических методов в научных исследованиях.
Краткое содержание дисциплины
Аксиоматический подход и его сущность. Прикладные области использования разделов дискретной математики. Понятие множества. Способы задания множеств. Подмножества. Операции над множествами. Соотношение между множествами. Отношения. Свойства отношений. Отношение порядка. Отношение эквивалентности. Основные положения теории доказательств и теории целых чисел. Делимость. Алгоритм деления. Общий делитель. Наибольший общий делитель. Свойства НОД. Алгоритм Евклида. Наименьшее общее кратное. Простые числа. Теорема Евклида. Основная теорема арифметики. Сравнения. Класс вычетов. Операции между классами вычетов. Полная система вычетов. Первичная система вычетов. Приведенная система вычетов. Способы воспроизведения других систем вычетов. Целочисленные решения линейных уравнений. Решения сравнений. Циклы и алгоритмы для матриц. Рекурсивные функции и алгоритмы. Сложность алгоритмов Основные принципы комбинаторики. Размещения, перестановки, сочетания. Комбинаторные тождества. Правило включения-исключения. Алгоритмы формирования перестановок и сочетаний. Основные понятия и определения теории графов. Способы представления графов и методы просмотра вершин. Поиск в ширину и глубину. Алгебраические свойства графов. Деревья и леса. Числовые параметры, характеризующие дерево. Бинарные деревья. Сортировка. Бинарные деревья поиска. Остовные деревья. Матричная формула Кирхгофа. Эйлеровы графы и задача о Кенигсбергских мостах. Гамильтоновы графы и задача коммивояжера. Алгоритмы построения эйлеровых и гамильтоновых циклов. Связь между эйлеровыми и гамильтоновыми циклами. Двудольные графы и задача о назначениях в графовой формулировке. Укладки графов. Свойства планарных графов. Формула Эйлера. Критерий планарности графа. Алгоритм укладки графа на плоскости. Нахождение кратчайших путей в графе. Задачи сетевого планирования: правила построения сетевых графиков; метод критического пути; управление проектом с неопределенным временем выполнения работ; оптимизация сетевого графика. Потоки в сетях: алгоритм Форда и Фалкерсона; метод блокирующих потоков. Раскраски графов: точный алгоритм раскрашивания; приближенный алгоритм последовательного раскрашивания; улучшенный алгоритм последовательного раскрашивания; клики и независимые множества. Алгоритмы поиска в лабиринте.
Компетенции обучающегося, формируемые в результате освоения дисциплины
Выпускник должен обладать:
  • ОПК-1 Способен применять фундаментальные знания, полученные в области математических и (или) естественных наук, и использовать их в профессиональной деятельности
You are reporting a typo in the following text:
Simply click the "Send typo report" button to complete the report. You can also include a comment.