УЧЕБНАЯ ПРОГРАММА ПО ДИСЦИПЛИНЕ

ДИСКРЕТНАЯ МАТЕМАТИКА

Для очной формы обучения ВСЕГО 70

лекции 18

семинары 16

Всего аудиторных занятий 34

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

Требования ГОС к обязательному минимуму содержания основной

образовательной программы:

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

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

Перечень дисциплин, усвоение которых необходимо для изучения курса: «Математика»

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

-  иметь представление о:

·  Основных формулах теории графов.

-  знать:

·  Основные понятия теории графов;

-  уметь:

·  Строить матрицы для описания графов;

·  Определять изоморфность и гомеоморфность графов;

·  Находить различные типы маршрутов на ориентированных и неориентированных графах;

НЕ нашли? Не то? Что вы ищете?

·  Выполнять различные операции на эйлеровых и гамильтоновых графах;

·  Выполнять различные операции на графах транспортных сетей;

·  Выполнять различные операции с деревьями и циклами, строить цикломатическую матрицу графа;

·  Выполнять различные операции, связанные с определением внешней и внутренней устойчивости графов;

Основные виды занятий: лекции и практические занятия.

Основные виды текущего контроля занятий: контрольная работа, выполняемая самостоятельно (домашняя) в течение семестра.

Основной вид рубежного контроля знаний: экзамен.

СОДЕРЖАНИЕ КУРСА

Тема 1. Основные понятия теории графов.

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

Тема 2.Нахождение кратчайших и максимальных путей в графах.

Нахождение кратчайших путей. Алгоритм Дейкстры. Алгоритм Беллмана-Мура. Алгоритм нахождения максимального пути. Особенности алгоритмов теории графов.

Тема 3.Деревья и циклы

Деревья (основные определения). Задача об остове экстремального веса. Обходы графов, Фундаментальные циклы. Клини, независимые множества.

Тема 4.Планарность графов.

Планарность графов(основные понятия и определения). Алгоритм укладки графа на плоскость. Хроматические графы. Раскраска графов.

Тема 5.Транспортные сети.

Потоки в сетях. Теорема Форда-Фалкерсона. Поток минимальной стоимости. Элементы сетевого планирования. Критические пути, работы, резервы. Линейные графики.

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

·  Способы задания графов. Операции над графами. Метрические характеристики графов.

·  Нахождение минимальных и максимальных путей орграфа.

·  Остовы графов, фундаментальные циклы. Эйлеровы и гамильтоновы графы. Доминирующие множества и Клини.

·  Планарные и хроматические графы.

·  Потоки в сетях. Сетевые и линейные графики.

ЛИТЕРАТУРА

Основная:

, . «Дискретная математика.» Москва-Новосибирск 2007 г. , . «Дискретная математика и математическая логика» Москва, 2006г. . «дискретная математика» Санкт-Петербург 2007г.