- •Лесосибирск 2012
- •Лекция 1 Основные понятия теории множеств
- •1 Понятие множества
- •2 Способы задания множеств
- •3 Сравнение множеств
- •Лекция 2 Операции над множествами
- •1 Операции над множествами
- •2 Свойства операций над множествами
- •Лекция 3 Соответствия и функции
- •1 Соответствия
- •2 Функции
- •Лекция 4 Бинарные отношения и операции над ними
- •1 Понятие бинарного отношения
- •2 Операции над бинарными отношениями
- •Лекция 5 Свойства и виды бинарных отношений
- •1 Свойства бинарных отношений
- •2 Виды бинарных отношений
- •Модуль II Основы комбинаторики Лекция 6 Основные понятия комбинаторики
- •1 Правила суммы и произведения
- •2 Выборки
- •Лекция 7 Методы решения задач комбинаторики
- •1 Метод включений и исключений
- •2 Метод рекуррентных соотношений
- •Модуль II Элементы теории графов Лекция 6 основные понятия теории графов
- •1 Понятие графа
- •2 Виды графов
- •3 Матрица смежности, инцидентности
- •4 Изоморфизм графов
- •Лекция 9 Операции над графами
- •1 Подграфы
- •2 Операции над графами
- •Лекция 10 Пути и связность в неориентированных графах
- •1 Основные определения
- •2 Обходы в графе
- •Лекция 9 Пути и связность в ориентированных графах
- •1 Виды связности
- •2 Выделение компонент сильной связности
- •Алгоритм выделения компонент сильной связности
- •Лекция 10 Расстояния в графах
- •1 Основные определения
- •2 Нахождение расстояний в графе
- •Алгоритм Дейкстры
- •Алгоритм Форда-Беллмана нахождения минимального пути в нагруженном ориентированном графе d из vнач в vкон.( vнач ≠ vкон)
- •Лекция 11 Деревья
- •1 Основные свойства деревьев
- •2 Нахождение центров дерева
- •3 Покрывающие деревья (остовы)
- •Алгоритм построения покрывающего дерева для произвольного невзвешенного графа g
- •Алгоритм выделения минимального остовного дерева в неориентированном взвешенном графе g
- •Лекция 12 Двудольные и планарные графы
- •1 Двудольные графы
- •2 Планарные графы
- •Лекция 13 Раскраски графов
- •1 Раскраски
- •2 Внешняя и внутренняя устойчивость. Покрытия
- •Лекция 14 Потоки в сетях
- •1 Постановка задачи нахождения максимального потока
- •2 Решение задачи
- •Заключение
- •Библиографический список
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФГБОУ ВПО «Сибирский государственный технологический университет»
Лесосибирский филиал
Дискретная математика
Конспект лекций
для студентов направления подготовки 230100 Информатика и вычислительная техника,
профиль подготовкиПрограммное обеспечение вычислительной техники и автоматизированных систем очной, заочной и очно-заочной форм обучения
Лесосибирск 2012
Герасимова, М.М. Дискретная математика [Текст]: конспект лекций для студентов направления подготовки 230100 Информатика и вычислительная техника, профиль подготовки Программное обеспечение вычислительной техники и автоматизированных систем очной, заочной и очно-заочной форм обучения. / М.М. Герасимова. - Лесосибирск, 2012. - 55 с.
Рецензент доцент кафедры ФП Черепанова С.А.
Конспект лекций по дисциплине «Дискретная математика» разработан на основании рабочего учебного плана направления подготовки 230100 Информатика и вычислительная техника, профиль подготовки Программное обеспечение вычислительной техники и автоматизированных систем. В конспекте рассмотрены элементы теории множеств, основы комбинаторики, элементы теории графов.
ФГБОУ ВПО «Сибирский государственный технологический университет», Лесосибирский филиал
Содержание
Лекция 1 Основные понятия теории множеств 4
Лекция 2 Операции над множествами 8
Лекция 3 Соответствия и функции 10
Лекция 4 Бинарные отношения и операции над ними 13
Лекция 5 Свойства и виды бинарных отношений 15
Модуль II Основы комбинаторики 20
Лекция 6 Основные понятия комбинаторики 20
Лекция 7 Методы решения задач комбинаторики 23
Модуль II Элементы теории графов 25
Лекция 6 основные понятия теории графов 25
Лекция 9 Операции над графами 30
Лекция 10 Пути и связность в неориентированных графах 34
Лекция 9 Пути и связность в ориентированных графах 37
Лекция 10 Расстояния в графах 39
Лекция 11 Деревья 42
Лекция 12 Двудольные и планарные графы 45
Лекция 13 Раскраски графов 49
Лекция 14 Потоки в сетях 52
Заключение 57
Библиографический список 58
Для создания и эксплуатации комплексных интегрированных автоматизированных систем обработки информации и их компонент (математического обеспечения, пакетов прикладных программ, распределенных банков данных, встроенных микропроцессорных систем, сетей передачи данных, систем с разделением ресурсов и распределенной обработкой информации) необходимо знание дискретной математики, основной особенностью которой является отсутствие предельного перехода и непрерывности, характерных для классической математики.
Изучение данного курса тесно связано с такими дисциплинами, как «Математика», «Информатика». Знания, полученные при изучении курса, используются в дисциплинах: «Математическая логика и теория алгоритмов», «Исследование операций».
Целью настоящего курса является студентов к четкому, логически обоснованному математическому образу мышления, который позволит получить навыки формулировки прикладной задачи, ее корректного математического описания и правильного использования средств дискретной математики для ее решения.
В результате изучения курса «Дискретная математика» студент должен: знать основные положения, методы и алгоритмы дискретной математики и уметь их применять для решения практических задач.
Курс «Дискретная математика» включает следующие разделы: элементы теории множеств, основы комбинаторики, элементы теории графов.
Конспект лекций разработан на основе рабочего учебного плана направления подготовки 230100 Информатика и вычислительная техника, профиль подготовки Программное обеспечение вычислительной техники и автоматизированных систем.