litceysel.ru
добавить свой файл
1





Программа по курсу

"Дискретная математика"


ЦЕЛИ И ЗАДАЧИ

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


Задачами данного курса являются:




    1. Содержание дисциплины






п/п

Раздел

Тема

Содержание

1.1

Введение в дискретную математику

Задачи комбинаторной оптимизации

Модели вычисления, вычислительная сложность.

1.2




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


Компоненты

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

1.3




Связь булевых матриц,

бинарных отношений и

графов. Операции над

бинарными отношениями.

Операции над бинарными отношениями и соответствующие им операции над графами.

1.4





Матрица смежности графа, алгоритм нахождения числа компонент связности

Матрица смежности графа, алгоритм нахождения числа компонент связности

1.5




Теорема Эйлера. Алгоритм нахождения

эйлерова цикла

Теорема Эйлера. Алгоритм нахождения эйлерова цикла

2.1

Задача нахождения кратчайшего пути

Алгоритм Форда

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

3.1

Транспортные сети

Потоки в сетях, алгоритм

Форда-Фолкерсона

Величина потока, разрез, пропускная способность разреза.

3.2




Критерии существования

потока, насыщающего

выходные дуги

Соотношение между поглощающей способностью и потребностью.

4.1

Задача о назначении

Двудольные графы, решение

задачи о назначении

Сведение задачи о назначении к задаче построения потока насыщающего выходные дуги.

5.1

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


Гамильтоновы контуры

Величина рассечения, дефицит графа. Необходимое условие существования гамильтонова контура.

5.2




Метод ветвей и границ.

Алгоритм Литтла.

Общая формулировка метода ветвей и границ. Применение метода для решения задачи коммивояжера.

6.1

Задача оптимального квардатичного назначения

Решение задачи методом

ветвей и границ.

Лемма Гилмора. Решение задачи методом

ветвей и границ.

7.1

Обобщенная задача кратчайшего пути

Обобщенный метод волны

Обобщенная задача кратчайшего пути на «взвешенном» графе. Обобщенный метод волны.

8.1

Обобщенный метод волны

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

Применение обобщенного метода волны к рещению многоитерационных задач оптимизации на графах. Обобщенная задача о назначении в двудольном графе.

9.1

Уравнение Беллмана-Маслова

Идемпотентные полукольца.

Уравнение Беллмана-Маслова в полумодуле функций С(А) и

его свойства.

Принцип суперпозиции, теорема об истокообразном представлении решения.

9.2





Функция Грина и принцип Дюамеля для нестационарного

уравнения Беллмана-Маслова.

Явные формулы для разрешающего оператора уравнения в однородной регулярной дискретной среде.

10.1

Комбинаторика разбиений

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

для системы тождественных

частиц

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

для системы тождественных

частиц



Контрольные вопросы к зачету:


1) Графы, связность, матрицы смежности.

2) Теорема Эйлера. Алгоритм нахождения эйлерова цикла.

3) Алгоритм Форда

4) Потоки в сетях, алгоритм Форда-Фолкерсона

5) Критерии существования потока, насыщающего выходные дуги

6) Двудольные графы, решение задачи о назначении

7) Гамильтоновы контуры

8) Метод ветвей и границ. Алгоритм Литтла.

9) Лемма Гилмора. Обобщенный метод волны

10) Многоитерационные задачи оптимизации на графах

11) Уравнение Беллмана-Маслова, его свойства.



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

    2. 1) В.В. Белов, Е.М. Воробьев, В.Е. Шаталов «Теория графов», "Высшая школа", 1976.

    3. 2) Зыков А. А. «Основы теории графов.» — М.: «Вузовская книга», 2004.

    4. 3) Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. «Лекции по теории графов.» Изд.2, испр. М.: УРСС, 2009.


    5. 4) Кирсанов М. Н. «Графы в Maple.», М.: Физматлит, 2007.

    6. 5) Харари Ф. «Теория графов.», Изд 3, М.: КомКнига, 2006.




    1. Пособия и методические указания.

    2. 1) Алексеев В. Б., Ложкин С. А., Элементы теории графов, схем, автоматов.Учебное пособие по курсам «Введение в дискретную математику» и «Основы кибернетики», Москва, МГУ, 2000. 

    3. 2) Рабкин Е.Л., Фарфоровская Ю.Б., Булевы функции и элементы теории графов, методические указания и контрольные задания.






    1. Электронные ресурсы:

1) http://ru.wikipedia.org/Теория_графов

2) http://math-portal.ru/teoriagrafov