Программа по дисциплине Экстремальные задачи на топологических структурах для специальности 511200 Математика. Прикладная математика (магистратура) дневной формы обучения




Скачать 104.06 Kb.
НазваниеПрограмма по дисциплине Экстремальные задачи на топологических структурах для специальности 511200 Математика. Прикладная математика (магистратура) дневной формы обучения
Дата16.02.2013
Размер104.06 Kb.
ТипПрограмма


ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

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


УДМУРТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ




Математический факультет


Кафедра алгебры и топологии


РАБОЧАЯ

ПРОГРАММА


по дисциплине


Экстремальные задачи на топологических структурах


для специальности 511200 Математика. Прикладная математика

(магистратура)


дневной формы обучения


Курс ………………………………………………______1

Семестр …………………………………………. ______1

Всего часов.……………. ……………….……. ______68

Всего аудиторных часов ……………….……… ______36

Лекции, час …………………………………….. ______18

Практические, час …………………………….. ______18

Самостоятельная работа, час ………………… ______32

Домашнее задание, семестр….……………….. ______1,1

Зачет (семестр) …………………….…………… ______1

Экзамен (семестр) ……………………………… ______1


Ижевск 2006

Рабочая программа составлена на основании ____________________________________________________

(название документа, дата утверждения)

Составители рабочей программы

_Доцент, к.ф.-м.н.__________ ______________ Мерзляков А.С.

(должность, ученое звание, степень) (подпись) (Ф.И.О.)


__________________________________ ______________ ___________________________

(должность, ученое звание, степень) (подпись) (Ф.И.О.)


Рабочая программа утверждена на заседании кафедры алгебры и топологии

«____» _______________________________ 200__ года


Заведующий кафедрой ________________ __Грызлов А.А.___________

(подпись) (Ф.И.О.)

«____» _______________200__года


Решение методической комиссии математического факультета

«____» _______________200__года


Председатель методической комиссии ________________ ____________________________

(подпись) (Ф.И.О.)


Согласовано с библиотекой УдГУ «___» ________________ 200__ года


Директор библиотеки УдГУ _____________ ________________________

(подпись) (Ф.И.О.)



  1. Организационно-методический раздел



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

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

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


II.ОБЪЕМ И РАСПРЕДЕЛЕНИЕ ЧАСОВ КУРСА ПО ТЕМАМ И ВИДАМ ЗАНЯТИЙ



Наименование разделов и тем

Всего

Лекции

Практические

Лабораторные

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



2

3

4

5

6

7

1

Краткий обзор экстремальных задач, связанных с использованием графов

4

2

2

-




2

Модели вычислений, алгоритмы и их сложности.

8

2

2

-

4

3

Экстремальные комбинаторные задачи на графах, связанные с подсчетами различных видов графов. Помеченных графы.

8

2

2

-

4

4

Точки сочленения и вершинные разрезы графов. Экстремальные задачи, связанные с разрезами и покрытиями.

12

3

3

-

6

5

Двудольные графы. Максимальные парасочетания.

8

2

2

-

4

6

Пути в сетях. Постановка задачи и различные алгоритмы ее решения

8

2

2

-

4

7

Задача о максимальном потоке. Алгоритмы ее решения.

12

3

3

-

6

8

Целочисленные задачи линейного программирования

8

2

2

-

4

Итого:

68

18

18

-

32

III. ФОРМЫ КОНТРОЛЯ



Текущий контроль- выполнение 2-х домашних работ. По окончании семестра предусматривается сдача зачета и экзамена.


IV. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

ТЕМЫ ЛЕКЦИЙ И ИХ КРАТКОЕ СОДЕРЖАНИЕ





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




  1. Модели вычислений. Алгоритмы и их сложность. Структуры данных: списки, очереди и стеки. Представление с их помощью множеств, графов. Рекурсия. Рассмотрение построения алгоритмов на конкретных задачах. Приемы построения алгоритмов: «Разделяй и властвуй»; балансировка.




  1. Экстремальные комбинаторные задачи: задача о покрытиях; задача о помеченных графах.




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




  1. Максимальные паросочетания в графе и алгоритм Куна для ее решения. Оценки сложности алгоритма Куна. Задача о назначениях. Венгерский алгоритм и его сложность.




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




  1. Целочисленные задачи линейного программирования. Метод ветвей и границ решения задач целочисленного программирования. Задача коммивояжера. Применение метода ветвей и границ для решения этой задачи, как альтернатива методу перебора.




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



ТЕМЫ ПРАКТИЧЕСКИХ ЗАНЯТИЙ


Комбинаторные задачи на графах.

Кратчайшие пути.

Оптимальные деревья.

Алгоритмы поиска паросочетаний в графе.

Алгоритмы поиска покрытий в графе.

Потоки в сетях. Построение соответствующих алгоритмов.

Задача почтальона.

Задача коммивояжера.

Оптимальные ветвления.

ПРИМЕРНЫЕ ВАРИАНТЫ ДОМАШНИХ ЗАДАНИЙ

ДОМАШНЕЕ ЗАДАНИЕ № 1





  1. Возможно ли, чтобы разрез и цикл содержали в точности одну общую дугу? Если невозможно, то почему?




  1. Требуется построить систему дорог, связывающих между собой N городов, так, чтобы общая стоимость прокладки дорог была минимальной. Стоимость прокладки дорог между каждой парой городов (i,j) известна.




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




  1. Предположим, что алгоритм Флойда был использован для получения длин трех наилучших путей между всеми парами вершин в задаче поиска узких мест. Как полученные результаты могут быть использованы для поиска самих путей?



ДОМАШНЕЕ ЗАДАНИЕ № 2


1. Составьте список всех увеличивающих поток цепей из вершины s в вершину t, в графе, показанном на рисунке.


  1. Городские власти объявили, что с данного момента на определенной улице с двусторонним движением будет введено одностороннее движение. Обязательно ли это приведет к возрастанию протяженности оптимального маршрута почтальона, обслуживающего эту улицу?




  1. Для данного сетевого графика, заданного рисунком вычислить,

А) наиболее ранние сроки событий;

Б) наиболее поздние сроки событий;

В) найти критический путь;

Г) полный резерв времени для каждой операции;

Д) вычислить свободный резерв времени для каждой операции;

Е) вычислить независимый резерв времени для каждой операции.

НАБОР ЗАДАНИЙ НА ЗАЧЕТ




ВАРИАНТ ЗАДАНИЙ





  1. Покажите, что на шести вершинах существует точно шесть неизоморфных графов деревьев.

  2. Покажите, что дерево является двудольным графом.

  3. Найдите минимальное дерево бинарного поиска для весов {1,2,3,3,4,4}.

  4. Максимизировать , при условии, что



  1. Постройте минимальное покрывающее дерево для конкретного графа.



ВОПРОСЫ НА ЭКЗАМЕН





  1. Оптимизационные задачи на графах.

  2. Основные понятия линейного (дискретного) программирования. Постановка и алгоритм решения задач. Различные методы решения задач линейного программирования: метод отсекающих плоскостей; алгоритм Гомори.

  3. Алгоритм построения покрывающего дерева.

  4. Алгоритм построения максимального ориентированного леса.

  5. Алгоритм поиска кратчайшего пути.

  6. Алгоритмы поиска максимального потока

  7. Алгоритмы поиска поток минимальной стоимости.

  8. Алгоритм решения задачи о паросочетании максимальной мощности.

  9. Алгоритм выбора паросочетания с максимальным весом.

  10. Алгоритм выбора покрытия с минимальным весом.

  11. Решение задачи почтальона для неориентрованного графа.

  12. Решение задачи почтальона для ориентрованного графа.

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

  14. Метод критического пути.



V. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ КУРСА

ОСНОВНАЯ ЛИТЕРАТУРА





  1. АХО А, Дж. ХОПКРОФТ, Дж.УЛЬМАН Построение и анализ вычислительных алгоритмов. М: Мир,1979,536с.

  2. АДЕЛЬСОН-ВЕЛЬСКИЙ Г.М.,Е.А. ДИНИЦ, А.В.КАРЗАНОВ Потоковые алгоритмы. М.: Наука.1975.

  3. АСАНОВ М.О. Дискретная оптимизация.-Екатеринбург:УралНаука,1998.

  4. АСАНОВ М.О.,В.А.БАРАНСКИЙ, В.В.РАСИН Дискретная математика: графы, матроиды, алгоритмы. Ижевск,2001.288с.

  5. ЕВСТИГНЕЕВ В.А.,В.Н.КАСЬЯНОВ Теория графов: алгоритмы обработки деревьев. Новосибирск: Наука,1994.

  6. ЕВСТИГНЕЕВ В.А., В.Н.КАСЬЯНОВ Теория графов: алгоритмы обработки бесконтурных графов. Новосибирск: Наука. Сиб. предприятие РАН,1998.

  7. ЗАМЯТИН А.П. Графы и сети. Учебное пособие. Екатеринбург: Изд.УрУ.2004.160с.

  8. КРИСТОФИДЕС Н. Теория графов. Алгоритмический подход. М.: Мир,1978.

  9. ЛОВАС Л., М.ПЛАММЕР Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии. М.: Мир, 1998.

  10. МАЙНИКА Э. Алгоритмы оптимизации на сетях и графах. М.: Мир,1981,324с.

  11. СВАМИ М.,К.ТХУЛАСИРАМАН Графы, сети и алгоритмы. М.: Мир,1984,454с.

  12. ТАХА Х. Введение в исследование операций.М.:Мир,1985.

  13. ФЕРГЮСОН Р.О.,Л.Ф.САРЖЕНТ Линейное программирование. М.: Госстат.издат. 1962.
  14. ЮДИН Д.Б., Гольдштейн Б.Г. Задачи и методы линейного программирования. М. Советское радио.1961.

ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА





  1. КАМЕРОН П. Дж,ван ЛИНТ Дж.Х. Теория графов, теория кодирования и блок-схемы. М.: Наука,1980.

  2. КОРМЕН Т., ЛЕЙЗЕРСОН Ч., РИВЕСТ Р. Алгоритмы: построение и анализ. М: МЦНМО,1999.

  3. НОВИКОВ Ф.А. Дискретная математика для программистов. СПб.: Питер,2000.

  4. ОРЕ О. Графы и их применение (популярная серия. "Современная математика". М.Мир.1965.176с.



Похожие:

Программа по дисциплине Экстремальные задачи на топологических структурах для специальности 511200 Математика. Прикладная математика (магистратура) дневной формы обучения iconПрограмма по дисциплине «Вычислительные задачи геометрии» для специальности: 511200 Математика. Прикладная математика (магистратура) очная форма обучения
Эвм, вычислительной геометрии. Основным содержанием дисциплины является исследования и оценка сложности геометрических построений,...
Программа по дисциплине Экстремальные задачи на топологических структурах для специальности 511200 Математика. Прикладная математика (магистратура) дневной формы обучения iconПрограмма по дисциплине «Теоретико-числовые основы защиты информации» для специальности 511200 Математика, прикладная математика (магистратура) (код, название) форма обучения очная
Программа дисциплины «Теоретико-числовые основы защиты информации» составлена в соответствии с требованиями вузовского компонента...
Программа по дисциплине Экстремальные задачи на топологических структурах для специальности 511200 Математика. Прикладная математика (магистратура) дневной формы обучения iconРабочая программа по дисциплине «синтез программ» для специальности 010200 Прикладная математика и информатика Форма обучения: очная
Рабочая программа составлена на основании гос впо специальности 010200 «Прикладная математика и информатика» (квалификация – математик,...
Программа по дисциплине Экстремальные задачи на топологических структурах для специальности 511200 Математика. Прикладная математика (магистратура) дневной формы обучения iconРабочая программа дисциплины алгебра и аналитическая геометрия Рекомендовано Методическим советом угту-упи для направления 230400 «Прикладная математика»
Программа составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования по направлению...
Программа по дисциплине Экстремальные задачи на топологических структурах для специальности 511200 Математика. Прикладная математика (магистратура) дневной формы обучения iconПрограмма дисциплины Прикладные задачи тв и мс  для направления 230. 401. 65 «Прикладная математика»
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки по...
Программа по дисциплине Экстремальные задачи на топологических структурах для специальности 511200 Математика. Прикладная математика (магистратура) дневной формы обучения iconРабочая программа дисциплины "математическое моделирование" Для
Для подготовки дипломированных специалистов по направлению 657100–”Прикладная математика по специальности 073000–“Прикладная математика...
Программа по дисциплине Экстремальные задачи на топологических структурах для специальности 511200 Математика. Прикладная математика (магистратура) дневной формы обучения iconРабочая программа по дисциплине «Дискретная математика» для специальности 080801 «Прикладная информатика (в экономике)» Набор 2005 года и последующих лет
«Дискретная математика» составлена на основании требований Государственного образовательного стандарта по специальности 080801 —...
Программа по дисциплине Экстремальные задачи на топологических структурах для специальности 511200 Математика. Прикладная математика (магистратура) дневной формы обучения iconРабочая программа дисциплины Системное и прикладное программное обеспечение Для подготовки дипломированных специалистов по направлению 657100 -“Прикладная математика” по специальности 073000
...
Программа по дисциплине Экстремальные задачи на топологических структурах для специальности 511200 Математика. Прикладная математика (магистратура) дневной формы обучения iconМетоды оптимизации
...
Программа по дисциплине Экстремальные задачи на топологических структурах для специальности 511200 Математика. Прикладная математика (магистратура) дневной формы обучения iconРабочая программа дисциплины Оптимальное и адаптивное управление Для подготовки дипломированный специалистов по направлению 657100 «Прикладная математика» по специальности 073000
...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница