Основы дискретной математики (стр. 1 из 23)

Федеральное агентство по образованию

Новомосковский институт (филиал)

Государственного образовательного учреждения высшего профессионального образования

«Российский химико-технологический университет имени Д.И. Менделеева»

T.П. Тюрина, В.И. Емельянов

Практикум по дискретной математике

(часть 1)

Учебно-методическое пособие

Новомосковск 2007

Оглавление

Введение....................................................................................................... 5

Практическая работа № 1 Изучение методов сортировки данных........... 6

1.1 Теоретическая часть............................................................................... 6

1.2 Методы, используемые при поиске и сортировке................................ 9

1.2.1 Основные понятия............................................................................... 9

1.2.2 Поиск................................................................................................. 10

1.2.3 Оценки времени исполнения............................................................. 18

1.2.4 Сортировки....................................................................................... 19

1.3 Практическая часть.............................................................................. 40

1.3.1 Содержание отчёта по практической работе................................... 40

1.3.2 Приложение на Delphi, в котором представлена работа некоторых методов сортировки и поиска.................................................................................. 40

1.3.3 Пример выполнения.......................................................................... 51

1.3.4 Варианты заданий............................................................................. 53

1.4 Вопросы для самопроверки................................................................ 62

Практическая работа № 2 Представление множеств в компьютере........ 64

2.1 Теоретическая часть............................................................................. 64

2.1.1 Множества и операции над ними..................................................... 64

2.1.2 Представление множеств и отношений в программах.................... 67

2.1.4 Представление множеств в приложениях на Delphi........................ 82

2.1.5 Характеристический вектор множества........................................... 83

2.2 Практическая часть.............................................................................. 85

2.2.1 Задание к работе............................................................................... 85

2.2.2 Примеры выполнения....................................................................... 86

2.2.3 Варианты заданий............................................................................. 90

2.3 Вопросы для самопроверки................................................................ 92

Практическая работа № 3 Элементы теории графов............................... 94

3.1 Теоретическая часть............................................................................. 94

3.2 Практическая часть............................................................................ 111

3.2.1 Задание к работе............................................................................. 111

3.2.2 Примеры выполнения..................................................................... 111

3.2.3 Вариантв заданий............................................................................ 117

Практическая работа № 4 Элементы теории множеств и алгебры логики 122

4.1 Указание к выполнению..................................................................... 122

4.2 Задание к работе................................................................................ 122

4.3 Практическая часть............................................................................ 122

4.4 Вопросы для самопроверки.............................................................. 133

Практическая работа № 5 Исследование логических функций............. 135

5.1 Задание к работе................................................................................ 135

5.2 Практическая часть............................................................................ 135

5.2.1 Пример выполнения........................................................................ 135

5.2.2 Варианты заданий........................................................................... 138

5.3 Вопросы для самопроверки.............................................................. 140

Практическая работа № 6 Изучение методов минимизации логических функций................................................................................................................... 142

6.1 Краткие теоретические сведения....................................................... 142

6.2 Практическая часть............................................................................ 144

6.2.1 Задание к работе............................................................................. 144

6.2.2 Примеры выполнения..................................................................... 144

6.3 Вопросы для самопроверки.............................................................. 147

Практическая работа № 7 Моделирование работы узлов компьютера с помощью Еxcel.......................................................................................................... 149

7.1 Теоретическая часть........................................................................... 149

7.2 Практическая часть............................................................................ 152

7.2.1 Схемы сравнения кодов.................................................................. 153

7.2.2 Дешифраторы.................................................................................. 158

7.3 Задания к работе................................................................................ 160

7.4 Вопросы для самопроверки.............................................................. 164

Список литературы.................................................................................. 165

Введение

В практикум включены необходимые теоретические сведения, содержание работ, примеры выполнения, варианты заданий, вопросы по самоконтролю знаний для 7 практических работ. Некоторые практические работы относятся к нескольким разделам дисциплины, поэтому для них можно, не «привязывая» к конкретному разделу, выполнять описание в виде отдельных приложений. Все практические работы выполняются с использованием компьютера.

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

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

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

Практическая работа № 1. Изучение методов сортировки данных

Цель работы: изучение наиболее известных методов сортировки данных и их использование на примерах конкретных задач.

1.1 Теоретическая часть

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

При рассмотрении данного круга задач необходимо предварительно изучить тему «Множества и отношения». Рефлексивное, транзитивное, но антисимметричное отношение R на множестве A называется частичным порядком. Частичный порядок важен в тех ситуациях, когда мы хотим как-то охарактеризовать старшинство. Иными словами, решить при каких условиях можно считать, что один элемент множества превосходит другой.

Примеры частичных порядков.

«£» на множестве вещественных чисел;

«Ì» на подмножествах универсального множества;

«…делит…» на множестве натуральных чисел.

Множества с частичным порядком принято называть частично упорядоченными множествами (ч. у. м.).

Если R – отношение частичного порядка на множестве A, то при х

y и xRy мы называем x предшествующим элементом или предшественником, а y – последующим. У произвольно взятого элемента y может быть много предшествующих элементов. Однако если x предшествует y, и не существует таких элементов z, для которых xRz и zRy, x называется непосредственным предшественником (иначе говорят, что y покрывает x) и обозначается x<y [3].

Линейным порядком на множестве A называется отношение частичного порядка, при котором из любой пары элементов можно выделить предшествующий и последующий.

Постановка задачи: пусть задано конечное множество А, состоящее из n элементов a_i, на нём задано отношение линейного порядка Р.

Требуется перенумеровать элементы А числами от 1 до n таким образом, чтобы из того, что i<j следовало (a_i, a_j) Є P. Выполнение этой задачи называется сортировкой массива данных [3].

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

Потребность в сортировке больших объёмов данных ощущалась очень давно, например, в комплекте счётно-аналитических машин Холлерита была специальная сортирующая машина.

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

Выдающийся специалист по программированию Д. Кнут посвятил сортировке и поиску данных почти весь второй том трудов «Искусство программирования для ЭВМ» [4].

Сортировка данных – обработка информации, в результате которой элементы её (записи) располагаются в определённой последовательности в зависимости от значения некоторых признаков элементов, называемых ключевыми.