Республики Беларусь Белорусский государственный университет Механико-математический факультет Кафедра уравнений математической физики


Скачать 91.83 Kb.
НазваниеРеспублики Беларусь Белорусский государственный университет Механико-математический факультет Кафедра уравнений математической физики
Дата публикации10.05.2013
Размер91.83 Kb.
ТипТематический план
referatdb.ru > Математика > Тематический план
Министерство образования Республики Беларусь

Белорусский государственный университет

Механико-математический факультет

Кафедра уравнений математической физики


УТВЕРЖДАЮ

Проректор по учебной работе

профессор В.В. Самохвал

________________________

Рег.№ __________________

«____» ____________ 2007 г.
Базовая учебная программа дисциплины

«ТЕОРИЯ ГРАФОВ И АЛГОРИТМОВ»


для студентов специальности 1-31 03 01 «Математика»

Минск

2007

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

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

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

Программа предназначена для студентов-математиков специальности механика механико-математического факультета.

Цель курса – познакомить студентов с основными понятиями теории графов, с наиболее распространенными графовыми моделями и методами их исследования, обучить студентам приемам построения эффективных алгоритмов, алгоритмами решения универсальных задач и методами их оценивания.

^ Тематический план курса «Основы математической кибернетики»


темы

Количество часов

^ Содержание курса:


Лекции

Семинарские

занятия

Введение..

Построение математических моделей.

1

2

^ Раздел 1. Элементы теории графов.







1.1 Определение графа. Примеры графов, Простейшие свойства.

1

1

1.2. Маршруты, цепи, циклы. Теорема Кенига о двудольных графах.

1

1

1.3. Деревья.

2

1

1.4. Обходы в графах.

2

2

1.5 Плоские и планарные графы (КСР).

2




Раздел 2. Экстремальные задачи на графах.







2.1. Определение кратчайших цепей в сетях..

2

2

2.2. Основная теорема о потоке. .Алгоритм построения максимального потока. Обобщение потоковых задач.

2

2

2.3 Потоки минимальной стоимости.

1

2

2.4.Решение задачи о назначении..

2

2

Раздел 3. Универсальные алгоритмы решения комбинаторных задачю.







3.1. Метод ветвей и границ и решение задачи коммивояжера.

2

2

3.2. Динамическое программирование и решение задач о траектории, о ранце, задачи коммивояжера.

2

2

3.3. Метод минорантной функции.

1




3.4. Перестановочный прием, решение задач теории расписаний.

2




3.5. Понятие о многокритериальных задачах (КСР)..

2




Раздел 4. Эффективные методы построения и оценивания комбинаторных алгоритмов.







4.1. Принципы оценки комбинаторных алгоритмов.

1




4.2. Простейшие структуры данных.

1




4.3..Сортировка. Теоремы о трудоемкости сортировки.

1

1

4.4. Сортировка цепочек. Определение изоморфизма корневых деревьев.

2

1

4.5. 2-3-деревья.

2

1

4.6. Понятие поиска с возвращением.

1




4.7. Поиск в глубину в графе. Определение с помощью поиска в глубину блоков графа.

2

2

4.8 Определение планарности графа и построение его плоской укладки (КСР).

2

2

4.9.. Определение изоморфизма графов.

1

1

4.10. Построение циклов в графе (КСР).

1

1

4. 11. Построение транзитивного замыкания орграфа..

1

1

4.12. Принцип разделяй и властвуй. Алгоритм Штрассена умножения матриц.

1




4.13. Понятие о классах Р и NР.

2




Итого

42

30



Введение. Цели и задачи курса. Принципы построения математических моделей.

^ Раздел 1. Элементы теории графов. Определение графа. Примеры графов. Способы задания графов. Лемма о рукопожатии и следствия из нее. Проблемы изоморфизма и реконструируемости графов.

Маршруты, цепи, циклы, простые цепи и циклы. Связные графы, компоненты графа. Расстояние в графе. Теорема Кенига о двудольности графа.

Эквивалентные определения дерева. Теорема о центре дерева. Алгоритм построения минимального остовного дерева.

Обходы в графах. Эйлеровы графы. Необходимые и достаточные условия эйлеровости. Разбиение ребер на наибольшее число цепей. Гамильтоновы графы. Достаточное условие гамильтоновости.

Плоские и планарные графы. Укладка графа на плоскости и пространстве. Грани плоского графа. Теорема Эйлера для плоского графа. Теорема Понтрягина-Куратовского (без доказательства).

^ Раздел 2. Экстремальные задачи на графах. Определение кратчайшего расстояния между двумя вершинами графа. Определение кратчайших расстояний между всеми парами вершин.

Задача о максимальном потоке. Понятие потока и разреза. Основная теорема о потоке. Следствия из теоремы. Алгоритм построения максимального потока. Обобщение задачи о потоке. Алгоритм построения потока минимальной стоимости.

Алгоритм решения задачи о назначении. Задачи о назначении на узкие места.

^ Раздел 3. Универсальные алгоритмы решения комбинаторных задач. Метод ветвей и границ. Решение с его помощью задачи коммивояжера. Динамическое программирование. Решение с его помощью задачи о траектории, задачи о ранце, задачи коммивояжера. Метод минорантной функции. Перестановочный прием. Решение задачи одного станка и задачи Беллмана-Джонсона для двух станков.

Понятие о многокритериальных задачах. Решение оптимальное по Парето. Приемы решения многокритериальных задач.

^ Раздел 4. Эффективные методы построения и оценивания комбинаторных алгоритмов. Принципы оценки комбинаторных алгоритмов. Простейшие структуры данных. Сортировка с помощью сравнений. Алгоритмы о трудоемкости алгоритмов сортировки с помощью сравнений. Черпаковая сортировка. Сортировка цепочек. Корневые деревья. Алгоритм определения изоморфизма корневых деревьев.

2.3-деревья. Построение с их помощью словарей и очередей с приоритетом. Реализация с помощью корневых деревьев алгоритма построения минимального остовного дерева.

Поиск с возвращением. Принцип поиска. Поиск в глубину в графе. Нахождение с его помощью двусвязных компонент. Реализация с помощью поиска с возвращение алгоритма построения плоской укладки графа. Алгоритм определения изоморфизма графов. Построение множества фундаментальных циклов и множества всех циклов. Построение транзитивного замыкания графа.

Принцип «разделяй и властвуй». Алгоритм Штрассена эффективного умножения матриц.

Понятие о классах Р и NР. Списки распространенных NР-полных задач.

Литература

по курсу «Теория графов и алгоритмов»
Основная:

1. Лекции по теории графов / В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. – М.: Наука, 1990.

2. Ахо А., .Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1978.

3. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. Минск: Вышэйшая школа, 1984.
Дополнительная:

1. Вагнер Г. Основы исследования операций: В 3 т. – М.: Мир, 1972.

2. Костевич Л.С., Лапко А.А. Теория игр и исследование операций. Минск: Вышэйшая школа, 1989.

Автор:
Профессор кафедры уравнений математической физики, доктор пед. наук

О. И. Мельников


Рецензент:

Зав. кафедрой дискретной математики и алгоритмики факультета прикладной математики

профессор, доктор физ.-мат.наук В. М. Котов
Одобрена на заседании кафедры

уравнений математической физики

протокол № 7 от 06 июня 2007 г.

Одобрена на заседании Ученого совета механико-математического факультета

протокол № 7 от 20 июня 2007 г.

Ответственный за выпуск

вед. лаборант кафедры уравнений математической физики Л.Н. Кулибаба

Похожие рефераты:

Республики Беларусь Белорусский государственный университет Механико-математический...
Внесена кафедрой уравнений математической физики и Главным управлением учебной и научно-методической работы Белорусского государственного...
Республики Беларусь Белорусский государственный университет Механико-математический...
Программа предназначена для студентов-математиков специальности математическая электроника механико-математического факультета
Республики Беларусь Белорусский государственный университет Механико-математический...
Программа предназначена для студентов-математиков специальности математическая электроника механико-математического факультета
Республики Беларусь Белорусский государственный университет Механико-математический...
...
Республики Беларусь Белорусский Государственный Университет Механико-математический...
Одобрена на заседании кафедры теории функций бгу протокол №8 от 14 декабря 2007 г
Республики Беларусь Белорусский Государственный Университет Механико-математический...
Одобрена на заседании кафедры теории функций бгу протокол №6 от 17 декабря 2007 г
Республики Беларусь Белорусский Государственный Университет Механико-математический...
Одобрена на заседании кафедры теории функций бгу протокол №6 от 17 декабря 2007 г
Республики Беларусь Белорусский Государственный Университет Механико-математический...
Одобрена на заседании кафедры теории функций бгу протокол №6 от 17 декабря 2007 г
Республики Беларусь Белорусский Государственный Университет Механико-математический...
Целью курса является ознакомление студентов с основными свойствами дробных интегралов и производных и показать непосредственную взаимосвязь...
Республики Беларусь Белорусский Государственный Университет Механико-математический...
Целью курса является ознакомление студентов с основными свойствами дробных интегралов и производных и показать непосредственную взаимосвязь...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
referatdb.ru
referatdb.ru
Рефераты ДатаБаза