Галкина М.Ю. Дискретная математика - файл n1.doc

приобрести
Галкина М.Ю. Дискретная математика
скачать (1162 kb.)
Доступные файлы (1):
n1.doc1162kb.14.09.2012 19:58скачать

n1.doc

  1   2   3   4   5   6   7   8


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

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

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

телекоммуникаций и информатики
М.Ю. Галкина

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


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

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

Новосибирск 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

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

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


Множества, способы задания множеств. Диаграммы Венна. Операции над множествами. Бинарное отношение между элементами множества, виды бинарных отношений. Свойства операций над множествами.

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


Перестановки, размещения, сочетания без повторений. Выборки из множества с повторением элементов. Правило суммы, правило произведения. Формула включений и исключений.

Последовательности, рекуррентные соотношения. Возвратные последовательности. Характеристический многочлен возвратной последовательности. Общее и частное решение рекуррентного соотношения.

Алгебра логики


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

Импликанта, простая импликанта. Сокращенная дизъюнктивная нормальная форма, тупиковая дизъюнктивная нормальная форма, минимальная ДНФ. Метод Квайна, операции склеивания и поглощения, импликантная таблица, процедура ветвления. Нахождение минимальной ДНФ с помощью карт Карно, покрытие.

Булева алгебра в применении к переключательным схемам.
  1   2   3   4   5   6   7   8


Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации