Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Дискретная_матем1.doc
Скачиваний:
115
Добавлен:
11.04.2015
Размер:
1.35 Mб
Скачать

Министерство Российской Федерации

по связи и информатизации

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

телекоммуникаций и информатики

М.Ю. Галкина

Дискретная математика Программа, методические указания и задания для контрольной работы

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

Удк 51(0.75)

Галкина М.Ю.

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

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

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

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

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

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

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

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

Оглавление

Программа курса………………………………...……….….….

4

Рекомендуемая литература………………………………….....

5

Правила выполнения и оформления контрольной работы......

5

Правила выбора варианта ..........................................................

6

Таблица выбора задач контрольной работы.............................

8

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

10

Методические указания для выполнения контрольной работы...........................................................................................

18

  1. Теория множеств……………………………...………...

18

    1. Способы задания множеств………………………….

18

    1. Отношения между множествами…………….……...

18

    1. Диаграммы Венна………………………………….…

19

    1. Операции над множествами.............................…..….

19

    1. Свойства операций над множествами..………….….

20

    1. Отношения на множествах....................…...........…...

21

  1. Комбинаторика………………………………………….

23

    1. Перестановки, размещения и сочетания без повторений…………….......……………………………...

23

    1. Выборки с повторениями…………..………………...

24

    1. Формулы включений и исключений………………...

27

    1. Рекуррентные соотношения. Возвратные последовательности…..………………..……….………..

29

  1. Алгебра логики……………..…………………..……….

31

    1. Булевы функции………………………………….…..

31

    1. Булева алгебра………………………………………..

32

    1. Нормальные формы…………………………………..

33

    1. Минимизация булевых функций в классе ДНФ……

37

    1. Метод Квайна получения минимальной ДНФ....…..

37

    1. Нахождение минимальной ДНФ с помощью карт Карно…………………………………………………..….

41

    1. Булева алгебра и переключательные схемы………..

43

  1. Теория графов……………………………….……....…..

45

    1. Способы задания графов……………………………..

47

    1. Маршруты, цепи, циклы……………………………..

49

    1. Эйлеровы графы……………………………………...

50

    1. Задача поиска минимального остова графа………...

51

    1. Задача поиска кратчайших расстояний между всеми парами вершин графа…………………………….

52

  1. Конечные автоматы……………….……………………

53

    1. Определение, способы представления конечного автомата………………………………………..…………

53

    1. Минимизация конечных автоматов…………………

55