Введение. Барбасова Т.А. Дискретная математика: Конспект лекций. – Челябинск: ЮУрГУ, 2010. – 78с

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

Конспект лекций

Челябинск

Издательство ЮУрГУ

Барбасова Т.А. Дискретная математика: Конспект лекций. – Челябинск: ЮУрГУ, 2010. – 78с.

Конспект лекций предназначен для студентов очной и заочной форм обучения специальности 220200 “Управление в технических системах”.

Рецензент: к.т.н., доц. Радкевич И.А.

Содержание

Введение. 4

1. Введение в теорию множеств. 5

1.1. Множества. 5

1.2. Отношения. 13

2. Теория графов. 18

2.1. Основные понятия. 18

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

2.4. Сети и их свойства. 25

3. Введение в математическую логику. 35

3.1. Логика высказываний. 36

3.2. Логика предикатов. 49

4. Прикладная теория алгоритмов. 54

4.1. Алгоритм: определение и основные свойства. 54

4.2. Реализация управляющих алгоритмов. 55

4.3. Формализация понятия алгоритма. 55

4.4. Машина Тьюринга. 58

4.5. Свойства машины Тьюринга. 61

4.6. Реализация машины Тьюринга. 62

4.7. Формальные системы и алгоритмы. 64

5. Комбинаторный анализ. 65

5.1. Основное правило комбинаторики. 65

5.2. Правило суммы.. 66

5.3. Правило прямого произведения. 67

5.4. Перестановки. 67

5.5. Число различных k-элементарных подмножеств n-элементарного множества. 68

5.6. Число подмножеств данного множества. 70

5.7. Размещение элементов множества. 71

5.7. Размещения с повторениями. 73

5.8. Размещения без повторений. 73

5.9. Комбинации элементов с повторениями. 74

6. Языки и грамматики. 78

6.1. Основные определения. 78

6.2. Формальные грамматики. 79

6.3. Грамматики с ограничениями на правила. 81

6.4. Способы записи синтаксиса языка. 83

Список рекомендуемой литературы.. 87

Дискретная математика – бурно развивающаяся в 21 веке ветвь математики. Ее роль и место определяются в основном тремя факторами:

- дискретную математику можно рассматривать как теоретические основы компьютерной математики,

- модели и методы дискретной математики являются хорошим средством и языком для построения и анализа моделей в различных науках, например, в химии, биологии, генетике, физике, психологии, экологии и др.

- язык дискретной математики чрезвычайно удобен и стал фактически языком всей современной математики.

Математика как наука, естественно, от рождения делится на дискретную и континуальную математику. Что мы относим к континуальной математике? Все, что явно или неявно содержит идеи теории пределов и непрерывности. Все остальное – дискретная математика (т.е. арифметика, алгебра. Теория множеств и общая теория отображений, математическая логика, комбинаторный анализ, теория алгоритмов и многое другое).

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

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

В учебный предмет «Дискретная математика» включает только тот круг вопросов, который можно озаглавить «Теоретические основы компьютерной математики».