Рабочая программа для студентов специальности 010300.62

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

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

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

.

ДИСКРЕТНАЯ МАТЕМАТИКА

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

Рабочая программа для студентов специальности 010300.62

«Математика. Компьютерные науки»

Тюмень 2008

1.  Пояснительная записка

1.1. Цели и задачи дисциплины

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

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

1.2. Требования к уровню освоения содержания дисциплины

В результате изучения дисциплины студенты должны

иметь представление:

·  о месте и роли дискретной математики в системе математических наук;

знать:

·  основные дискретные структуры: множества, отношения, графы; комбинаторные структуры,

·  методы перечисления для основных дискретных структур;

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

уметь:

·  употреблять специальную математическую символику для выражения количественных и качественных отношений между объектами;

·  выполнять операции над множествами, применять аппарат теории множеств для решения задач, исследовать бинарные отношения на заданные свойства,

·  применять аппарат производящих функций и рекуррентных соотношений для решения перечислительных задач;

·  решать оптимизационные задачи на графах.

иметь навыки:

·  применения языка и средств дискретной математики;

·  решения комбинаторных и теоретико-графовых задач.

2.  Объем дисциплины и виды учебной работы

Вид занятий	Всего часов	Семестры
3
Общая трудоемкость	150	150
Аудиторные занятия	90	90
Лекции	36	36
Лабор. занятия	54	54
Самостоятельная работа	60	60
Контрольные работы	+
Вид итогового контроля	экзамен

3.  Тематический план изучения дисциплины

Тема	Лекции	Лаборат.	Самост.	Контроль
1.  Введение	2
2.  Основные понятия   теории множеств. Отношения	8	9	10
3.  Комбинаторика	10	18	25	К. р.
4.  Теория графов	16	27	25	К. р.
Всего:	36	54	60

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

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

2. Основные понятия   теории множеств. Отношения. Определение множества. Способы задания множеств. Конечные и бесконечные множества. Пустое и универсальное множества. Мощность множества. Семейство множества. Операции над множествами. Диаграммы Эйлера-Венна. Декартово произведение множеств. Покрытие и разбиение множеств. Основные тождества алгебры множеств. Понятие отношения. Бинарные отношения и способы их задания. Операции над бинарными отношениями. Обратные отношения. Композиция бинарных отношений. Свойства бинарных отношений. Специальные бинарные отношения: порядок, эквивалентность.

3. Комбинаторика Классификация комбинаторных задач и характеристика их основных типов. Основные правила комбинаторики. Основные комбинаторные конфигурации: размещения, сочетания, перестановки. Разбиения. Бином Ньютона, биномиальные коэффициенты, треугольник Паскаля. Основные биномиальные тождества. Полиномиальная формула. Метод включений и исключений. Рекуррентные соотношения и производящие функции. Числа Стирлинга и их свойства.

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

5. *Булевы функции: табличный способ задания; существенные и несущественные переменные; формулы; эквивалентность формул; элементарные функции и их свойства; разложение функции по переменной; совершенная дизъюнктивная нормальная форма; полные системы функций; полиномы Жегалкина; представление булевых функций полиномами.

*Замыкание; свойства операции замыкания; замкнутые классы; Классы Т0 и Т1; линейные функции; лемма о нелинейной функции; самодвойственные функции; принцип двойственности; лемма о несамодвойственной функции; монотонные функции; лемма о немонотонной функции; теорема о неполноте систем функций алгебры логики; предполные классы; базисы; примеры базисов.

*Дизъюнктивные нормальные формы (ДНФ); тупиковая, минимальная и сокращенная ДНФ; геометрическая интерпретация; алгоритм нахождения всех минимальных ДНФ; свойство сокращенной ДНФ для монотонных булевых функций; методы построения сокращенной ДНФ; градиентный алгоритм; локальные алгоритмы.

*Функции k - значной логики; элементарные функции; полнота системы

{ О, 1, ..., k -1, J0(x), J1(x), ..., Jk -1(x), max (x, y), min (x, y)} ; полнота систем { max(x, y), х+1} , Vk(х, у)} ; алгоритм распознавания полноты конечных систем функций в Рk ; представление функций из Рk полиномами. Особенности функций k - значной логики; пример замкнутого класса в Рk, не имеющего базиса; пример замкнутого класса в Рk, имеющего счетный базис; пример континуального семейства замкнутых классов в Рk.

*Теорема Кузнецова о функциональной полноте в Рk ; существенные функции; теорема Слупецкого.

*Теория кодирования: побуквенное кодирование; разделимые коды; префиксные коды; критерий однозначности декодирования; неравенство Крафта-Макмиллана для разделимых кодов; условие существования разделимого кода с заданными длинами кодовых слов; оптимальные коды; методы построения оптимальных кодов; метод Хафмана; самокорректирующиеся коды; коды Хэмминга, исправляющие единичную ошибку. Линейные коды и их простейшие свойства; коды Боуза-Чоудхури.

*Синтез и сложность управляющих систем: схемы из функциональных элементов; сложность схем; синтез схем из функциональных элементов для индивидуальных функций; схемы сложения и умножения n-разрядных чисел; простейшие универсальные методы синтеза; метод Шеннона; мощностный метод получения низких оценок сложности; функция Lсфэ(n); порядок роста функции Lсфэ(n).

*Асимптотически наилучший метод синтеза схем из функциональных элементов в базисе { v, &, -} ; асимптотика функции Lсфэ(n); контактные схемы; простейшие методы синтеза; контактное дерево; универсальный многополюсник; метод Шеннона для контактных схем; функция Lкс(n); порядок роста функции Lкс(n); метод каскадов. *Нижняя оценка сложности линейной функции в классе контактных схем (метод Кардо).

*Ограниченно-детерминированные функции: детерминированные функции; задание детерминированных функций при помощи деревьев; вес функций; ограниченно-детерминированные функции (ОДФ); задание ОДФ диаграммами переходов и каноническими уравнениями; конечные автоматы; автоматные функции; состояние автомата; эквивалентность состояний; теорема об эквивалентности состояний конечного автомата.

*Эквивалентность автоматов; построение автомата, эквивалентного данному, с минимальным числом состояний. *Преобразование автоматными функциями периодических последовательностей; операция суперпозиции; отсутствие полных относительно операции суперпозиции конечных систем автоматных функций; схемы из логических элементов и элементов задержки; реализация автоматных функций; события; операции над событиями; регулярные события и их представимость в автоматах; теорема Клини. *Регулярные выражения; представимость событий регулярными выражениями; пример нерегулярного события.

Примечание: разделы, помеченные звездочкой, при необходимости могут быть опущены.

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

1.  Основные понятия теории множеств. Отношения. Операции над множествами. Диаграммы Эйлера-Венна. Упрощение выражений над множествами с использованием основных тождеств алгебры множеств. Бинарные отношения. Запись бинарных отношений с помощью специальной математической символики. Определение свойств бинарных отношений и их принадлежности к специальным типам бинарных отношений. Матрицы бинарных отношений.

2.  Комбинаторика. Решение задач на использование основных комбинаторных формул. Задачи с ограничениями. Смешанные задачи. Основные правила комбинаторики. Решение задач на использование методов перечисления. Метод включения-исключения. Линейные однородные рекуррентные соотношения. Производящие функции.

3.  Теория графов. Основные понятия теории графов. Типы графов. Подграфы. Матричное представление графов. Операции над графами. Достижимость и связность. Определение компонент связности неорграфов и сильных компонент орграфов. Алгоритмы Краскала и Прима построения кратчайшего остова взвешенного графа. Определение кратчайших путей в графах. Решение задач на использование алгоритмов Дейкстры и Флойда. Алгоритм Форда-Фалкерсона определения максимального потока в транспортной сети. Определение эйлеровых и гамильтоновых циклов графа и использование данных задач в приложениях. Решение задачи коммивояжера и его прикладное значение. Алгоритмы раскраски графа. Решение прикладных задач, сводящихся к задаче о раскраске.

6.  Темы самостоятельных работ

1.  Пусть A, B,C – подмножества множества X. Доказать, что X\BÌX\A тогда и только тогда, когда AÌB.

2.  Показать, что для любых множеств A, B, C верно следующее соотношение если AÈB=C, BÈC=A, CÈA=B, то A=B=C.

3.  Пусть универсальное множество U состоит из 100 элементов, его подмножество A и B соответственно из 64 и 42 элементов. Определить минимально возможное число элементов следующих множеств:
а) AÈB, б) AÇB, в) AÈB, г) A\B, д) Ā\B.

4.  Какими свойствами обладает отношение на множестве целых чисел

5.  В шахматной олимпиаде участвуют представители n стран по 4 представителя от каждой страны. Сколькими способами можно они могут встать в ряд так, чтобы рядом с каждым был представитель той же страны?

6.  На загородную прогулку поехало 92 человека. Бутерброды с колбасой взяли 47 человек, с сыром – 38 человек, с ветчиной – 42 человека, с сыром и с колбасой – 28 человек, с колбасой и с ветчиной – 31 человек, с сыром и с ветчиной – 26 человек. Все три вида бутербродов взяли с собой 25 человек, а несколько человек взяли с собой пирожки. Сколько человек взяли с собой пирожки?

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

8.  Найти an, зная рекуррентное соотношение и начальные члены:

9.  Для данного графа построить матрицы смежности, инцидентности.

10.  Используя алгоритм Прима, построить минимальный покрывающий остов и найти его длину.

11.  Для данного ориентированного графа построить дерево кратчайших расстояний из 1 вершины.

12.  Используя алгоритм Флойда, построить матрицу кратчайших расстояний и матрицу путей.

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

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

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. Доказательство полиномиальной формулы

8.  Литература

1.  Яблонский в дискретную математику. М.: Наука, 1986.

2.  , Сапоженко и упражнения по курсу дискретной математики М., 1992.

3.  Сачков в комбинаторные методы дискретной математики. М.: Наука, 1982.

4.  , Адельсон-Вельский математика для инженера. – М.: Энегроатом издат, 1988.

5.  Носов главы дискретной математики. Учебное пособие. М., Наука, 1990.

6.  Введение в теорию конечных автоматов, М., Наука, 1987 г.

7.  Носов комбинаторной теории для инженеров, М.: Мир, 1990.

8.  Комбинаторика для программистов, М.: Мир, 1988.

Приложение

Дополнения и изменения к программе на учебный год

В рабочую учебную программу по дисциплине «Дискретная математика» для направления «Математика. Компьютерные науки» вносятся следующие изменения:

1.  Добавлена балльно-рейтинговая система оценки успеваемости студентов;

2.  Внесены изменения в список литературы – основной и дополнительной.

Рабочая программа пересмотрена и одобрена на заседании кафедры от 01.01.2001 г., протокол №1.

Заведующий кафедрой

программного обеспечения

2. Тематический план изучения дисциплины

2.1. Распределение часов курса дисциплины по темам и видам работ

№	Тема	Лекции час.	Лабораторные занятия, час.	Самостоятельная и инд. работа, час	Итого часов по теме	Итого количество баллов
1	2	3	4	5	6	7
1.	Введение	2			2
2.	Основные понятия теории множеств. Отношения	8	9	10	27	20
3.	Комбинаторика	10	18	25	53	35
4.	Теория графов	16	27	25	68	45
	Итого по дисциплине за 3 семестр (часов, баллов)	36	54	60	150	100

2.2. ОЦЕНКА РАБОТЫ СТУДЕНТОВ В РЕЙТИНГОВЫХ БАЛЛАХ

Распределение рейтинговых баллов по видам работ и нормам контроля

Виды работ и контроля	Максимальное количество баллов
Тема 1	Тема 2	Тема 3	Тема 4	Итого
Лекции	-	-	-	-	-
Практические занятия	-	10	10	15	35
Контрольная работа	-	-	15	15	30
Самостоятельная работа	-	10	10	15	35
Итого по дисциплине	-	20	35	45	100

Виды контроля деятельности студентов, применяемые на аудиторных занятиях, их оценка в рейтинговых баллах

№ п/п	Вид контроля	Максимальное количество баллов
1.	Посещение лекционных занятий	В случае пропуска лекции без уважительной причины текущий рейтинг снижается на 1 балл
2.	Посещение практических занятий	В случае пропуска занятия без уважительной причины текущий рейтинг снижается на 1 балла
3.	Выполнение практических заданий	За защиту практического задания позже установленного срока количество баллов снижается на 2 балла.
4.	Выполнение индивидуальных заданий в процессе самостоятельной работы	0-5 баллов
5.	Выполнение факультативных творческих заданий	За выполнение по инициативе студента факультативных творческих заданий текущий рейтинг может быть повышен на величину баллов за задание
6.	Экзамен по дисциплине	0 - 5 баллов за ответ на вопрос экзаменационного билета

8.  Литература

Основная:

1.  Зайцева,  математика: учеб. пособие/ - Тюмень: Изд-во ТюмГУ, 20с..

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

1.  Плотников, А. Д.. Дискретная математика: учеб. пособие/ . - 2-е изд., испр. и доп. - Москва: Новое знание, 20с.

2.  Яблонский, С. В..  Введение в дискретную математику: учеб. пособие для студ. вузов, обуч. по спец. "Прикл. мат."/ ; Моск. гос. ун-т им. . - 4-е изд., стер.. - Москва: Высшая школа, 20с.: