Geum.ru

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

Вид материалаПрограмма

Содержание


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

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

ДИСКРЕТНАЯ МАТЕМАТИКА
Кузьмина И.П.


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

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

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

Цели преподавания дисциплины:

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

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

«Математика»

В результате изучения курса студент должен

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

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

иметь представление о:
  • основных формулах теории графов.

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

Основными видами промежуточного контроля знаний являются: выполнение промежуточных индивидуальных заданий и контрольное домашнее задание.

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

Часы, отведенные на изучение дисциплины, согласно учебному плану (156 ч):


Форма обучения
Всего ауд. занятий
Самостоятельная работа

очная
90ч
66ч

очно-заочная(вечерняя)
54ч
102ч

заочная
16ч
140ч




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




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

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

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

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

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

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

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

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

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

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




ЛИТЕРАТУРА




Основная:
  1. Судоплатов С.В., Овчинникова Е.В. Дискретная математика. Москва-Новосибирск: Инфра-М, 2007
  1. Шапорев С.Д.. Дискретная математика - СПб: БХВ-Петербург, 2007