ПРОГРАММА КУРСА

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

Программа, методические указания и

Задания для контрольной работы

Новосибирск 2002

УДК 51(0.75)

Галкина М.Ю.

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

Кафедра прикладной математики и кибернетики.

Список лит. – 8.

Рецензент: Бернштейн Т.В.

Для направления 550400 – Телекоммуникации (бакалавры)

Рекомендовано редакционно-издательским советом СибГУТИ в качестве методических указаний.

Ó Сибирский государственный университет

телекоммуникаций и информатики, 2002 г.

Оглавление

Программа курса………………………………...……….….….
Рекомендуемая литература………………………………….....
Правила выполнения и оформления контрольной работы......
Правила выбора варианта ..........................................................
Таблица выбора задач контрольной работы.............................
Задачи для контрольной работы................................................
Методические указания для выполнения контрольной работы...........................................................................................
1 Теория множеств……………………………...………...
1.1Способы задания множеств………………………….
1.2Отношения между множествами…………….……...
1.3Диаграммы Венна………………………………….…
1.4Операции над множествами.............................…..….
1.5Свойства операций над множествами..………….….
1.6Отношения на множествах....................…...........…...
2 Комбинаторика………………………………………….
2.1Перестановки, размещения и сочетания без повторений…………….......……………………………...
2.2Выборки с повторениями…………..………………...
2.3Формулы включений и исключений………………...
2.4Рекуррентные соотношения. Возвратные последовательности…..………………..……….………..
3 Алгебра логики……………..…………………..……….
3.1Булевы функции………………………………….…..
3.2Булева алгебра………………………………………..
3.3Нормальные формы…………………………………..
3.4Минимизация булевых функций в классе ДНФ……
3.5Метод Квайна получения минимальной ДНФ....…..
3.6Нахождение минимальной ДНФ с помощью карт Карно…………………………………………………..….
3.7Булева алгебра и переключательные схемы………..
4 Теория графов……………………………….……....…..
4.1Способы задания графов……………………………..
4.2Маршруты, цепи, циклы……………………………..
4.3Эйлеровы графы……………………………………...
4.4Задача поиска минимального остова графа………...
4.5Задача поиска кратчайших расстояний между всеми парами вершин графа…………………………….
5 Конечные автоматы……………….……………………
5.1Определение, способы представления конечного автомата………………………………………..…………
5.2Минимизация конечных автоматов…………………

ПРОГРАММА КУРСА