Москва. — Московский государственный университет геодезии и
картографии, 2010. — 95 с.
Настоящее пособие включает материалы практических занятий по курсу
дискретной математики для специальностей «Информационные системы и
технологии» и «Организация и технологии защиты информации»
факультета прикладной космонавтики МГУиК. Цель изучения дисциплины
– ознакомление студентов с математическим аппаратом описания
моделей данных, логических взаимосвязей между ними и построения
алгоритмов обработки данных в тех прикладных направлениях
информатики, для которых производится подготовка специалистов на
факультете.
Ввиду ограниченности объема часов дискретной математики в МГУиК, при разработке программы курса максимально учитывалась специфика направлений подготовки специалистов. Для специалистов по геоинформационным системам и технологиям, работающих с пространственно-распределенными данными, и для специалистов по сетевым технологиям наиболее важно владение аппаратом теории графов и ее приложений. Поэтому большая часть курса посвящена изучению теории графов. При составлении программы курса учитывалось также, что некоторые элементы математической логики и теории множеств рассматриваются в курсах информатики и высшей математики. В связи с этим большее внимание уделено отношениям на множествах, составляющим основу конструирования различных моделей данных и их практической эксплуатации. Часть материала, обычно относящегося к курсу дискретной математики, вынесена в программы других специальных дисциплин. Практикум по дискретной математике состоит из трех разделов: элементы математической логики, множества и отношения на множествах, теория графов. В рамках практических занятий студентам предлагаются несложные задачи и упражнения на понимание и закрепление лекционного материала. Содержание.
Введение.
Элементы математической логики. Логика высказываний.
Основные определения.
Разложение логических (булевых) функций по переменным. Дизъюнктивная и конъюнктивная нормальные формы.
Логические законы.
Множества и отношения.
Множества и операции над ними. Связь с логикой высказываний.
Отношения на множествах. Бинарные отношения.
Однородные отношения.
Функции как специальный вид отношений.
Алгебраические системы. Алгебра множеств и булева алгебра.
Теория графов.
Основные понятия теории графов.
Представление графов в ЭВМ.
Изоморфизм графов.
Подграфы и части. Операции над графами.
Методы обхода (просмотра) вершин графов.
Маршруты, цепи, циклы. Связность и достижимость.
Вершинная и реберная связность графов. Мосты, блоки и точки сочленения.
Двудольные графы. Паросочетания.
Алгоритмы расчета кратчайших путей между вершинами графа.
Деревья и леса.
Специальные виды деревьев.
Сети. Потоки в сетях.
Элементы цикломатики. Циклы и коциклы. Фундаментальная система циклов и цикломатическое число.
Эйлеровы графы и эйлеровы циклы.
Гамильтоновы графы и гамильтоновы циклы.
Независимые и покрывающие множества. Задачи о раскраске.
Литература
Ввиду ограниченности объема часов дискретной математики в МГУиК, при разработке программы курса максимально учитывалась специфика направлений подготовки специалистов. Для специалистов по геоинформационным системам и технологиям, работающих с пространственно-распределенными данными, и для специалистов по сетевым технологиям наиболее важно владение аппаратом теории графов и ее приложений. Поэтому большая часть курса посвящена изучению теории графов. При составлении программы курса учитывалось также, что некоторые элементы математической логики и теории множеств рассматриваются в курсах информатики и высшей математики. В связи с этим большее внимание уделено отношениям на множествах, составляющим основу конструирования различных моделей данных и их практической эксплуатации. Часть материала, обычно относящегося к курсу дискретной математики, вынесена в программы других специальных дисциплин. Практикум по дискретной математике состоит из трех разделов: элементы математической логики, множества и отношения на множествах, теория графов. В рамках практических занятий студентам предлагаются несложные задачи и упражнения на понимание и закрепление лекционного материала. Содержание.
Введение.
Элементы математической логики. Логика высказываний.
Основные определения.
Разложение логических (булевых) функций по переменным. Дизъюнктивная и конъюнктивная нормальные формы.
Логические законы.
Множества и отношения.
Множества и операции над ними. Связь с логикой высказываний.
Отношения на множествах. Бинарные отношения.
Однородные отношения.
Функции как специальный вид отношений.
Алгебраические системы. Алгебра множеств и булева алгебра.
Теория графов.
Основные понятия теории графов.
Представление графов в ЭВМ.
Изоморфизм графов.
Подграфы и части. Операции над графами.
Методы обхода (просмотра) вершин графов.
Маршруты, цепи, циклы. Связность и достижимость.
Вершинная и реберная связность графов. Мосты, блоки и точки сочленения.
Двудольные графы. Паросочетания.
Алгоритмы расчета кратчайших путей между вершинами графа.
Деревья и леса.
Специальные виды деревьев.
Сети. Потоки в сетях.
Элементы цикломатики. Циклы и коциклы. Фундаментальная система циклов и цикломатическое число.
Эйлеровы графы и эйлеровы циклы.
Гамильтоновы графы и гамильтоновы циклы.
Независимые и покрывающие множества. Задачи о раскраске.
Литература