Рабочая программа дисциплины «теория графов и прикладная комбинаторика»

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

Рабочая программа

Содержание 1. Цели и задачи дисциплины Целью изучения Задачи изучения дисциплины. 2. Место дисциплины в структуре ооп аспиранта 3. Требования к результатам освоения дисциплины 4. План изучения дисциплины Тема 2. Связность графов Тема 3. Расстояния и основные числа графов Тема 4. Деревья и сети. Тема 5. Операции над графами Тема 6. Элементы комбинаторики. Тема 7. Оптимизационные задачи на графах и задачи выбора 6. Итоговый контроль по дисциплине Дополнительная литература

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

• Программа вступительного экзамена в аспирантуру по специальностям 05. 13. 05 - "Элементы, 88.59kb.
• Рабочая программа учебной дисциплины «теория систем и системный анализ» Направление, 223.11kb.
• Рабочая программа учебной дисциплины «теория систем и системный анализ», 298.49kb.
• Ж. Д. Транспорта РФ петербургский государственный университет путей сообщения, 180.1kb.
• Рабочая программа учебной дисциплины дисциплина: Прикладная теория автоматизированного, 209.58kb.
• Рабочая программа дисциплины теория игр и исследование операций направления 010400, 185.05kb.
• Рабочая программа дисциплины прикладная математика (Наименование дисциплины), 188.06kb.
• Рабочая программа дисциплины, 270.7kb.
• Задача является np-полной для кубических планарных графов, реберных графов, ориентированных, 39.45kb.
• Рабочая программа дисциплины для магистрантов направления «Прикладная математика, 128.62kb.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ТАГАНРОГСКИЙ ИНСТИТУТ УПРАВЛЕНИЯ И ЭКОНОМИКИ

Экономический факультет

Кафедра математики и информатики


«УТВЕРЖДАЮ»

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

_____________/Н.Ф. Купчинов/

«____»___________2011 г.


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

«ТЕОРИЯ ГРАФОВ И ПРИКЛАДНАЯ КОМБИНАТОРИКА»


Программа разработана в соответствии с учебным планом по научной специальности 08.00.13 – Математические и инструментальные методы экономики


Квалификация (ученая степень)

Кандидат экономических наук


Общая трудоемкость 3 ЗЕ (108 часов), из них самостоятельная работа – 108 часов. Форма итогового контроля - зачет


Автор (составитель) программы Карелин Владимир Петрович, д.т.н., профессор

контактный электронный адрес - v.karelin@tmei.ru


Рекомендована кафедрой Математики и информатики

Дата_19.10.2011 г., протокол № __2____, ____________________

(_{подпись заведующего кафедрой)}


Утверждена Советом Экономического факультета

Дата_21.10.2011 г., протокол № __2____, _________________________

(_{подпись ученого секретаря)}


Таганрог – 2011

1. ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ


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

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

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


2. МЕСТО ДИСЦИПЛИНЫ В СТРУКТУРЕ ООП АСПИРАНТА


Дисциплина «Теория графов и прикладная комбинаторика» (ОД.А.07) относится к циклу дисциплин по выбору аспиранта по специальности 08.00.13 – Математические и инструментальные методы экономики.

3. ТРЕБОВАНИЯ К РЕЗУЛЬТАТАМ ОСВОЕНИЯ ДИСЦИПЛИНЫ


В процессе изучения дисциплины обучающиеся должны:

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

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

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


4. ПЛАН ИЗУЧЕНИЯ ДИСЦИПЛИНЫ


Общая трудоемкость 3 ЗЕ (108 часов), из них самостоятельная работа – 108 часов. Форма итогового контроля - зачет


5. Содержание курса


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

Способы задания графов: геометрический, алгебраический, матричный. Матрица смежности и матрица инцидентности. Степень вершины графа. Путь в графе. Подграф и часть графа. Однородные графы. Неориентированные и ориентированные графы. Изоморфизм графов. Изоморфное вложение и изоморфное пересечение графов. Плоские и планарные графы. Теорема Понтрягина-Куратовского. Двудольные графы. Мультиграфы. Взвешенные графы. Гиперграфы. Матрица инцидентности гиперграфа.

Тема 2. Связность графов

Понятие связности. Компоненты связности. Маршрут, длина маршрута. Цепи. Простые цепи. Контур. Цикл. Простые и элементарные циклы. Ациклический граф. Эйлеровы графы. Теорема Эйлера о существовании Эйлерова цикла. Гамильтоновы графы. Достаточные условия существования гамильтонова цикла в графе.

Тема 3. Расстояния и основные числа графов

Расстояние между вершинами графа. Удаленность вершины. Центр неориентированного графа. Радиус и диаметр графа. Матрица расстояний и алгоритм её нахождения. Цикломатическое число. Независимые циклы. Теорема о связи числа вершин и ребер графа с числом независимых циклов. Хроматическое число графа. Свойства хроматического числа. Теорема о минимальной раскраске плоского графа. Число внутренней устойчивости графа. Максимальное внутренне устойчивое подмножество графа. Число внешней устойчивости графа. Ядро графа.

Тема 4. Деревья и сети.

Определение дерева. Характерные свойства деревьев. Сеть. Транспортная сеть. Поток транспортной сети. Разрез сети. Пропускная способность разреза. Задача о наибольшем потоке.

Тема 5. Операции над графами

Сумма, пересечение, композиция графов. Декартово произведение графов. Операция суммирования графов. Операция суммирования в матричной форме. Транзитивное замыкание графов.

Тема 6. Элементы комбинаторики.

Основные комбинаторные конфигурации. Разбиения, перестановки, выборки. Формулы числа конфигураций: перестановок, сочетаний, выборок, разбиений. Латинские квадраты. Коды Хемминга. Прикладная комбинаторика. Комбинаторные задачи на графах. Задача о минимальной раскраске вершин графа. Задача о нахождении максимального внутренне устойчивого подмножества графа, минимального внешне устойчивого подмножества графа. Сложность решения комбинаторных задач. Класс P задач, решаемых за полиномиальное время. Класс NP и NP- полных задач. Примеры прикладных задач из класса NP- полных.

Тема 7. Оптимизационные задачи на графах и задачи выбора

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


6. ИТОГОВЫЙ КОНТРОЛЬ ПО ДИСЦИПЛИНЕ


 Проводится в форме зачета (собеседование по темам).


7. ЛИТЕРАТУРА

Основная литература:

1. Алгоритмы и программы решения задач на графах и сетях / Не­чепуренко М.И., Попков В.К., Майнагашев С.М. и др. - Новоси­бирск: Наука.Сиб.отд., 1990.
   
2. Басакер Р., Саати Т. Конечные графы и сети. М.: Гл. ред. Физ-мат. лит. Изд-ва "Наука", 1973.
   
3. Емеличев В.А. и др. Лекции по теории графов. М.: Наука,1990.
   
4. Илюхин А.А., Скобелев В.Г., Дискретная математика: Учебное пособие. Таганрог: Изд-во ТИУиЭ, 2005.
   
5. Кристофидес Н. Теория графов. Алгоритмический подход.- М.: Мир, 1978.- 432с.
   
6. Компьютер и задачи выбора / Автор предисл. Ю.И. Журавлёв. М.: Наука, 1989.
   
7. Кофман А. Введение в прикладную комбинаторику. М.: Гл. ред. Физ-мат. лит. Изд-ва "Наука", 1975.
   

Дополнительная литература

1. Авондо-Бодино Дж. Применение в экономике теории графов. М.: Изд-во "Прогресс", 1976.
   
2. Берж К. Теория графов и её применение. М. : ИЛ, 1962.
   
3. Зыков А.А. Основы теории графов.- М.: Наука, 1987.- 384с.
   
4. Курейчик В.М., Чернышев Ю.О. Методы оптимизации задач на графах: конспект лекций. – Ростов н/Д: Изд-во Инст. Сельхоз машиностр., 1982.
   
5. Мелихов А.Н., Карелин В.П. Методы распознавания изоморфизма и изоморфного вложения чётких и нечётких графов: Учебное посо­бие.- Таганрог: Изд.ТРТУ, 1995.- 112 с.
   
6. Робертс Ф.С. Дискретные математические модели с приложением к социальным, биологическим и экономическим задачам.- М.: Нау­ка, 1986.- 360 с.
   
7. Оре О. Графы и их приложения. М.: Мир, 1965.
   
8. Уилсон Р. Введение в теорию графов. М.: Мир, 1977.
   
9. Холл М. Комбинаторика. М.: Мир, 1970.
   
10. Горелова Г.В., Карелин В.П. Методы теории графов в когнитивном анализе и моделировании социально-экономических систем. // Вестник ТИУиЭ. Вып.1, 2005.
    
11. Карелин В.П., Лозовский А.В. Методы понижения сложности и сокращения перебора при решении комбинаторных задач. // Вестник ТИУиЭ. Вып.1, 2005.
    

8. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

Соответствует требованиям «Положения об организации учебного процесса в ТИУиЭ» и включает компьютерные классы с выходом в интернет и электронно-образовательную среду MOODLE (раздел обеспечение учебного процесса) и библиотечный фонд института.