Дискретная математика

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к лабораторным работам по дисциплине

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

для студентов направления подготовки

0915 - “Компьютерная инженерия”

УТВЕРЖДЕНО

на заседании кафедры

информационных

и компьютерных систем

Протокол № 8 от 14 апреля 2010 г.

Чернигов ЧГТУ 2010

Дискретна математика. Методичні вказівки до лабораторних робіт з дисципліни “Дискретна математика” для студентів напрямку підготовки 0915 - “Комп’ютерна інженерія” / Укладачі Соломаха В.В., Павловський В.І., Верьовко О.В. – Чернігів: ЧДТУ, 2010. - 83 с. Рос. мовою.

Составители: Соломаха Валерий Владимирович, старший преподаватель

Павловский Владимир Ильич, кандидат технических наук, доцент

Верёвко Александр Валериевич, студент

Ответственный за выпуск:	Павловский В.И., зав. кафедрой информационных и компьютерных систем, кандидат технических наук, доцент
Рецензент:	Нестеренко С.О., кандидат технических наук, доцент

СОДЕРЖАНИЕ

ВВЕДЕНИЕ................................................................................................ 6

1 ЛАБОРАТОРНАЯ РАБОТА № 1........................................................ 9

1.1 Цель работы...................................................................................... 9

1.2 Темы лабораторной работы № 1..................................................... 9

1.3 Основные орпределения................................................................... 9

1.4 Теоретические сведения.................................................................. 10

1.4.1 Операция объединение множеств............................................ 10

1.4.2 Операция пересечение множеств............................................. 11

1.4.3 Операция разность множеств................................................... 11

1.4.4 Операция симметрическая разность множеств....................... 11

1.4.5 Универсум................................................................................. 12

1.4.6 Дополнение множества............................................................. 12

1.4.7 Множество всех подмножеств (булеан)................................... 13

1.5 Выполнение работы........................................................................ 13

1.6 Содержание отчета......................................................................... 13

1.7 Контрольные вопросы.................................................................... 14

2 ЛАБОРАТОРНАЯ РАБОТА № 2...................................................... 15

2.1 Цель работы.................................................................................... 15

2.2 Темы лабораторной работы № 2................................................... 15

2.3 Основные орпределения................................................................. 15

2.4 Теоретические сведения.................................................................. 16

2.4.1 Табличный способ задания логической функции................... 16

2.4.2 Матричный способ представления.......................................... 16

2.4.3 Графический способ представления........................................ 17

2.4.4 Аналитический способ представления..................................... 18

2.4.5 Переход от табличной формы к аналитической..................... 18

2.4.6 Минимизация функций методом Квайна – Мак-Класки......... 18

2.4.7 Минимизация логических функций методом Петрика........... 21

2.4.8 Переход от алгебры Буля к алгебре Жегалкина..................... 22

2.4.9 Реляционный оператор Select (выборка)................................. 23

2.4.10 Реляционный оператор Project (проекция).............................. 24

2.5 Выполнение работы........................................................................ 26

2.6 Содержание отчета......................................................................... 26

2.7 Контрольные вопросы.................................................................... 26

3 ЛАБОРАТОРНАЯ РАБОТА № 3...................................................... 27

3.1 Цель работы.................................................................................... 27

3.2 Темы лабораторной работы № 3................................................... 27

3.3 Основные определения................................................................... 27

3.4 Теоретические сведения.................................................................. 29

3.4.1 Задача о кратчайшем пути....................................................... 29

3.4.2 Алгоритм Дейкстры нахождения кратчайшего пути в графе 30

3.4.3 Пример решения задачи нахождения кратчайшего пути....... 31

3.4.4 Задача нахождения наибольшего потока................................ 32

3.4.5 Алгоритм Форда и Фалкерсона нахождения максимального потока транспортной сети................................................................................. 33

3.4.6 Пример нахождения максимального потока........................... 34

3.4.7 Транспортная задача по критерию стоимости........................ 37

3.4.8 Алгоритм метода частичных потоков..................................... 37

3.4.9 Пример решения транспортной задачи по критерию стоимости 38

3.4.10 Алгоритм Флёри нахождения эйлерова цикла....................... 42

3.4.11 Пример решения задачи о коммивояжёре.............................. 43

3.4.12 Алгоритм Краскала нахождения остова минимального веса 50

3.5 Выполнение работы........................................................................ 51

3.6 Содержание отчета......................................................................... 51

3.7 Контрольные вопросы.................................................................... 52

4 ЛАБОРАТОРНАЯ РАБОТА № 4...................................................... 53

4.1 Цель работы.................................................................................... 53

4.2 Темы лабораторной работы № 4................................................... 53

4.3 Основные определения................................................................... 53

4.4 Теоретические сведения.................................................................. 56

4.4.1 Построение ОНК по методике Шеннона-Фано....................... 56

4.4.2 Построение ОНК по методике Хаффмена............................... 58

4.4.3 Построение линейного систематического кода....................... 60

4.4.4 Исправление ошибок в линейном систематическом коде....... 63

4.4.5 Построение кода Хємминга..................................................... 64

4.4.6 Исправление ошибок в коде Хэмминга................................... 65

4.4.7 Построение циклического кода................................................ 65

4.4.8 Исправление ошибок в циклическом коде.............................. 66

4.5 Выполнение работы........................................................................ 68

4.6 Содержание отчета......................................................................... 68

4.7 Контрольные вопросы.................................................................... 68

5 ЛАБОРАТОРНАЯ РАБОТА № 5...................................................... 69

5.1 Цель работы.................................................................................... 69

5.2 Темы лабораторной работы №5.................................................... 69

5.3 Основные определения................................................................... 69

5.4 Теоретические сведения.................................................................. 71

5.4.1 Вычисление степени числа а по модулю n.............................. 71

5.4.2 Алгоритм Евклида для нахождения наибольшего общего делителя 72

5.4.3 Вычисление обратных величин............................................... 73

5.4.4 Основные способы нахождения обратных величин............... 76

5.4.5 Расширенный алгоритм Евклида............................................. 78

5.4.6 Китайская теорема об остатках................................................ 80

5.5 Выполнение работы........................................................................ 81

5.6 Содержание отчета......................................................................... 82

5.7 Контрольные вопросы.................................................................... 82

ЛИТЕРАТУРА.......................................................................................... 83

ВВЕДЕНИЕ

Дискретная (конечная) математика – раздел математики, занимающийся изучением свойств объектов конечного характера: конечные группы, конечные графы, некоторые математические модели преобразователей информации. Т.е. это математика не связанная с понятиями бесконечности, предела и непрерывности. Дискретная математика имеет широкий спектр приложений, прежде всего в областях, связанных с информационными технологиями и компьютерами. В самом первоначальном названии компьютера – “электронная цифровая вычислительная машина” - слово “цифровая” указывает на принципиально дискретный характер работы данного устройства.

Лабораторный практикум состоит из 5 лабораторных на следующие темы:

· операции алгебры множеств;

· логические функции и реляционные операторы;

· алгоритмы на графах;

· кодирование информации;

· алгоритмы теории чисел.

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

Формальная логика – логика, где объектам, над которыми производятся логические рассуждения, приписываются формальные символы.

Когда к формальной логике применили математические методы - появилась математическая логика.

Математическая логика – наука о рассуждениях или доказательствах, проводимых в той или иной формальной теории.

Математическая или формальная логика делится на три подраздела: логику Буля, логику высказываний и логику предикатов.

В дискретной математике, теоретической информатике, программировании граф является важнейшим математическим понятием. На основе теории графов строятся модели разнообразных задач: маршрутизации, распределения ресурсов, дискретной оптимизации и управления, минимизации автоматов и алгоритмов. Стройная система специальных терминов и обозначений теории графов позволяют просто и доступно описывать сложные и тонкие вещи. Особенно важно наличие наглядной графической интерпретации. Картинки позволяют сразу “усмотреть” суть дела на интуитивном уровне, дополняя и украшая утомительные рациональные текстовые доказательства и сложные формулы.

Ранее средства кодирования играли вспомогательную роль и не рассматривались как отдельный предмет математического изучения. Но с появлением компьютеров ситуация радикально изменилась. Кодирование буквально пронизывает информационные технологии и является центральным вопросом при решении самых разных задач программирования:

¨ представление данных проищвольной формы в памяти компьютера;

¨ обеспечение помехоустойчивости при передаче информации по каналам связи;

¨ сжатие информации в базах данных;

¨ защита информации от несанкционированного доступа.

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

Дата добавления: 2015-08-31