Geum.ru

Учебно-методический комплекс для студентов заочного обучения специальности Прикладная информатика ( в экономике)

Вид материалаУчебно-методический комплекс

Содержание


Цели и задачи курса
Тематический план курса
Содержание программы курса по темам
Темы лабораторных работ, практических занятий, методические указания к их проведению
Подобный материал:
РоссийскАЯ ФедерациЯ

Министерство образования и науки

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

Государственное образовательное учреждение

высшего профессионального образования

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


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

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


« Дискретная математика»


Учебно-методический комплекс

для студентов заочного обучения

специальности Прикладная информатика ( в экономике).


Издательство

Тюменского государственного университета

Тюмень,2006


Рабочая программа разработана и утверждена:

29.03.2006

Рабочая учебная программа

Составлена старшим преподавателем Зайцевой С.С, утверждена на заседании кафедры программного обеспечения, 03.11.2006 г, протокол №2.
Вид занятий Всего часов Семестры
2
-------------------------------------
Общая трудоемкость 131 131
Аудиторные занятия 68 68
Лекции 34 34
Лабор. занятия 34 34
Индивидуальная работа 9 9
Самостоятельная работа 54 54
Контрольные работы +
Курсовая работа
Вид итогового контроля экзамен

Цели и задачи курса

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

Тематический план курса


  Тема  

 Лекции  

 Лаборат. 

   Самост.

 Контроль  

  ----------------------------------------  







   

   

  Введение  

1
1
15
   

  Основные понятия  

1
1
15



  теории множеств.  

2
2
15



  Отношения.  

2
2
15
   

  Комбинаторика  

1
1
16
  К.р.  

  Теория графов  

1
1
18
  К.р.  

  Всего:  

8
8
94
 

   












Содержание программы курса по темам

1. Место дискретной математики в системе математического образования. Использование элементов дискретной математики в решении прикладных задач. Связь данной дисциплины со специальными и общепрофессиональными дисциплинами. Организационно-методические указания по изучению дисциплины.
2. Определение множества. Способы задания множеств. Конечные и бесконечные множества. Пустое и универсальное множества. Мощность множества. Семейство множества. Операции над множествами. Диаграммы Эйлера-Венна. Декартово произведение множеств. Покрытие и разбиение множеств. Основные тождества алгебры множеств. Понятие отношения. Бинарные отношения и способы их задания. Операции над бинарными отношениями. Обратные отношения. Композиция бинарных отношений. Свойства бинарных отношений. Специальные бинарные отношения: порядок, эквивалентность. Функции и отображения; операции. Булевы алгебры.
3. Классификация комбинаторных задач и характеристика их основных типов. Основные правила комбинаторики. Основные комбинаторные конфигурации: размещения, сочетания, перестановки. Разбиения. Бином Ньютона, биномиальные коэффициенты, треугольник Паскаля. Основные биномиальные тождества. Полиномиальная формула. Метод включений и исключений. Рекуррентные соотношения и производящие функции. Числа Стирлинга и их свойства.
4. Графы и орграфы. Способы задания. Степени. Теорема Эйлера о сумме степеней. Изоморфизмы. Пути. Маршруты. Достижимость. Связность. Деревья. Теорема о характеризации деревьев. Остовы графа. Наименьший остов. Реберная и вершинная связность. Неравенство Уитни -Харари. Эйлеровы и гамильтоновы графы. Необходимые и достаточные условия. Планарные графы. Теорема о том, что К5 и К3,3 не планарны. Теорема Куратовского (без доказательства). Критерий планарности. Раскраска графа. Хроматическое число графа. Задачи поиска кратчайших путей в графах. Задача о максимальном потоке в сети. Задача поиска гамильтонова цикла в графе.
- Булевы функции и схемы из функциональных элементов; переключательные функции; теорема о функциональной полноте; примеры функционально полных базисов; целые числа и полиномы; рекуррентные уравнения; коды с обнаружением и исправлением ошибок.

Темы лабораторных работ, практических занятий, методические указания к их проведению

1-2. Операции над множествами. Диаграммы Эйлера-Венна. Упрощение выражений над множествами с использованием основных тождеств алгебры множеств.
3. Бинарные отношения. Запись бинарных отношений с помощью специальной математической символики. Определение свойств бинарных отношений и их принадлежности к специальным типам бинарных отношений. Матрицы бинарных отношений.
4-6. Решение задач на использование основных комбинаторных формул.
7-9. Решение задач на использование методов перечисления.
10. Основные понятия теории графов. Типы графов. Подграфы. Матричное представление графов. Операции над графами.
11. Достижимость и связность. Определение компонент связности неорграфов и сильных компонент орграфов.
12. Деревья: основные понятия. Алгоритмы Краскала и Прима построения кратчайшего остова взвешенного графа.
13. Определение кратчайших путей в графах. Решение задач на использование алгоритмов Дейкстры и Флойда.
14. Алгоритм Форда-Фалкерсона определения максимального потока в транспортной сети.
15. Решение транспортной задачи в сетевой постановке методом потенциалов.
16. Определение эйлеровых и гамильтоновых циклов графа и использование данных задач в приложениях. Решение задачи коммивояжера и его прикладное значение.
17. Алгоритмы раскраски графа. Решение прикладных задач, сводящихся к задаче о

раскраске.

Литература

1. Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986.
2. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики М., 1992.
3. Сачков В. Н. Введение в комбинаторные методы дискретной математики. М.: Наука, 1982.
4. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энегроатом издат, 1988.
5. Носов В. А. Специальные главы дискретной математики. Учебное пособие. М., Наука, 1990.
6. Брауэр В. Введение в теорию конечных автоматов, М., Наука, 1987 г.
7. Носов В.А. Основы комбинаторной теории для инженеров, М.: Мир, 1990.
8. Липский В. Комбинаторика для программистов, М.: Мир, 1988.

Контрольные вопросы к экзамену (зачету)

1. Множества. Способы задания множеств. Основные операции над множествами.
2. Доказательство основных законов алгебры множеств. Принцип двойственности.
3. Взаимно-однозначное соответствие. Эквивалентные множества. Мощность множеств.
4. Счётные множества. Мощность континуума. Теоремы о счётных множествах.
5. Доказать, что множество рациональных чисел счётно. Доказать, что множество действительных чисел несчётно.
6. Отображение. Виды отображений. Подстановки.
7. Теорема об отображениях. Правило равенства. Правило суммы. Правило произведения.
8. n-местное отношение. Бинарное отношение. Способы задания бинарного отношения на конечном множестве. Виды бинарных отношений.
9. Основные свойства матриц бинарных отношений.
10. Отношения эквивалентности. Основное свойство классов эквивалентности. Ранг отношения. Класс вычетов.
11. Отношения толерантности. Отношения частичного порядка. Линейный порядок.
12. Соединение. Соединение с повторением. Соединение без повторения. Перестановка. Количество перестановок. Размещение. Количество размещений. Сочетания. Количество сочетаний. Основные свойства сочетаний.
13. Метод включений и исключений. Формула включений-исключений. Задача о беспорядках.
14. Формальный степенной ряд. Производящая функция. Равенство формальных степенных рядов. Сложение и вычитание формальных степенных рядов. Умножение и деление формальных степенных рядов.
15. Рекуррентное соотношение. Возвратная последовательность. Характеристический многочлен. Общее решение рекуррентного соотношения. Теорема о рекуррентных соотношениях.
16. Граф. Ориентированный граф. Неориентированный граф. Смежность и инцидентность. Способы задания графа. Матрицы графа. Степени вершины.
17. Подграф. Часть графа. Виды графов. Изоморфизм графов. Теорема об изоморфизме графов.
18. Маршруты в ориентированных и неориентированных графах. Связность. Достижимость.
19. Дерево. Основные свойства деревьев. Ориентированное дерево. Бинарные деревья. Остов.
20. Задача о построении кратчайшего остовного дерева. Алгоритм Прима. Проблема Штейнера.
21. Задача о построении дерева кратчайших расстояний. Алгоритм Дейкстры.
22. Задача о построении матрицы кратчайших расстояний. Алгоритм Флойда.
23. Сеть. Поток в сети. Задача о максимальном потоке в сети. Разрез.
24. Доказать теорему Форда – Фалкерсона.
25. Остаточная пропускная способность. Остаточная сеть. Алгоритм Форда – Фалкерсона нахождения максимального потока.
26. Геометрическая реализация графа. Теорема о реализации конечного графа в трёхмерном евклидовом пространстве.
27. Планарный граф. Грань графа. Доказать формулу Эйлера для планарных графов.
28. Доказать, что граф К5 не планарен. Доказать, что граф К33 не планарен.
29. Независимое множество вершин графа. Вершинная раскраска. Правильная раскраска. Хроматическое число графа. Доказать теорему о 5 красках.
30. Эйлеров путь. Эйлеров граф. Алгоритм построения эйлерова пути в эйлеровом графе. Критерий эйлеровости графов.
31. Гамильтонов граф. Теорема Дирака.

32. Задача коммивояжёра. Метод ветвей и границ.
33. Бином Ньютона (теорема с доказательством).
34. Доказательство свойств биномиальных коэффициентов. Треугольник Паскаля.
35. Доказательство полиномиальной формулы.

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

>