Программа по дисциплине дискретная математика

Вид материала

Программа

Содержание Перечень дисциплин, усвоение которых необходимо для изучения курса Содержание курса Тема 2.Нахождение кратчайших и максимальных путей в графах. Тема 3.Деревья и циклы Тема 5.Транспортные сети.

Подобный материал:

• Темы курсовой работы по дисциплине "дискретная математика" (Приложение к рабочей программе, 128.96kb.
• Джеймс А. Дискретная математика и комбинаторика [Текст] / Джеймс А. Андерсон, 42.79kb.
• Учебная программа для специальности: (рабочий вариант) 1-310301-02 Математика (научно-педагогическая, 120.64kb.
• Рабочая программа дисциплины (модуля) Дискретная математика, 101.32kb.
• Рабочая программа учебной дисциплины «Дискретная математика» Направление подготовки, 139.29kb.
• Примерная программа наименование дисциплины «Дискретная математика» Рекомендуется для, 135.29kb.
• Методические указания к выполнению курсовой работы по дисциплине " Дискретная математика", 254.75kb.
• Календарный план учебных занятий по обязательной дисциплине «Дискретная математика, 109.62kb.
• Программа по дисциплине дискретная математика, 32.4kb.
• Примерная рабочая программа по дисциплине: «Дискретная математика» Факультет экономический, 134.71kb.

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

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

Кузьмина И.П.

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

лекции 18

семинары 16

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

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


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

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

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


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

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

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

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

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

• знать:
  

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

• уметь:
  

• Строить матрицы для описания графов;
  
• Определять изоморфность и гомеоморфность графов;
  
• Находить различные типы маршрутов на ориентированных и неориентированных графах;
  
• Выполнять различные операции на эйлеровых и гамильтоновых графах;
  
• Выполнять различные операции на графах транспортных сетей;
  
• Выполнять различные операции с деревьями и циклами, строить цикломатическую матрицу графа;
  
• Выполнять различные операции, связанные с определением внешней и внутренней устойчивости графов;
  

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

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

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


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

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

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

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

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

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

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

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

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

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

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


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

• Способы задания графов. Операции над графами. Метрические характеристики графов.
  
• Нахождение минимальных и максимальных путей орграфа.
  
• Остовы графов, фундаментальные циклы. Эйлеровы и гамильтоновы графы. Доминирующие множества и Клини.
  
• Планарные и хроматические графы.
  
• Потоки в сетях. Сетевые и линейные графики.
  

ЛИТЕРАТУРА

Основная:

1. С.В. Судоплатов, Е.В. Овчинникова. «Дискретная математика.» Москва-Новосибирск 2007 г.
   
2. Ю.А.Алеев, С.Ф. Тюрин. «Дискретная математика и математическая логика» Москва, 2006г.
   
3. С.Д. Шапорев. «дискретная математика» Санкт-Петербург 2007г.