47954 (Основы дискретной математики)

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

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

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

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

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 следовало (a_i, a_j) Є P. Выполнение этой задачи называется сортировкой массива данных [3].

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

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

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

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

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

Наиболее распространёнными видами сортировки данных являются упорядочение массива записей – расположение записей сортируемого массива данных в порядке монотонного изменения значения ключевого признака. Сортировка данных позволяет сократить в десятки раз продолжительность решения задач, связанных с обработкой больших массивов записей. Такое ускорение происходит за счёт сокращения времени поиска записей с определёнными значениями ключевых признаков. Упорядочение осуществляется в процессе многократного просмотра исходного массива.

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

Например, требуется решить задачу: даны целые числа x, a₁, a₂, …, a_n (n>0). Определить, каким по счёту идёт в последовательности a₁, a₂, …, a_n член, равный x. Если такого члена нет, то предусмотреть соответствующее сообщение.

В этом примере мы сталкиваемся с задачей поиска. «Одно из наиболее часто встречающихся в программировании действий – поиск. Он же представляет собой идеальную задачу, на которой можно испытывать различные структуры данных…» – пишет Н. Вирт [14]. Теория поиска – важный раздел теории информации.

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

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

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

Существуют различные алгоритмы сортировки данных. И понятно, что не существует универсального, наилучшего во всех отношениях алгоритма сортировки. Эффективность алгоритма зависит от множества факторов, среди которых можно выделить основные:

– числа сортируемых элементов;

– степени начальной отсортированности (диапазона и распределения значений сортируемых элементов);

– необходимости исключения или добавления элементов;

– доступа к сортируемым элементам (прямого или последовательного). Принципиальным для выбора метода сортировки является последний фактор [16].

Если данные могут быть расположены в оперативной памяти, то к любому элементу возможен прямой доступ. Удобной структурой данных в этом случае выступает массив сортируемых элементов. Если данные размещены на внешнем носителе в файле последовательного доступа, то к ним можно обращаться последовательно. В качестве структуры подобных данных можно взять файловый тип [9].

В этой связи выделяют сортировку двух классов объектов: массивов (внутренняя сортировка) и файлов (внешняя сортировка).

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

,

где знак неравенства понимается в смысле того порядка, который установлен в сортируемом множестве.

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

1.2.2 Поиск

Для определенности примем, что множество, в котором осуществляется поиск, задано как массив:

var a: array [0..N] of item;

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

Результатом поиска, как правило, служит элемент массива, равный эталону, или отсутствие такового.

Важно знать и про ассоциативную память. Это можно понимать как деление памяти на порции (называемые записями), и с каждой записью ассоциируется ключ. Ключ – это значение из некоторого вполне упорядоченного множества, а записи могут иметь произвольную природу и различные параметры. Доступ к данным осуществляется по значению ключа, которое обычно выбирается простым, компактным и удобным для работы.

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

Таблица расстановки.

Поиск, вставка и удаление, как известно, – основные операции при работе с данными [16]. Мы начнем с исследования того, как эти операции реализуются над самыми известными объектами – массивами и (связанными) списками.

Массивы

На рисунке 1.1 показан массив из семи элементов с числовыми значениями. Чтобы найти в нем нужное нам число, мы можем использовать линейный поиск (процедура представлена на псевдокоде, подобном языку Паскаль):

int function SequentialSearch (Array A, int Lb, int Ub, int Key);

begin

for i = Lb to Ub do

if A (i) = Key then

return i;

return –1;

end;

Максимальное число сравнений при таком поиске – 7; оно достигается в случае, когда нужное нам значение находится в элементе A[6]. Различают поиск в упорядоченном и неупорядоченном массивах. В неупорядоченном массиве, если нет никакой дополнительной информации об элементе поиска, его выполняют с помощью последовательного просмотра всего массива и называют линейным поиском. Рассмотрим программу, реализующую линейный поиск. Очевидно, что в любом случае существуют два условия окончания поиска: 1) элемент найден; 2) весь массив просмотрен, и элемент не найден. Приходим к программе:

While (a[i]<>x) and (i

If a[i]<>x then Write (‘Заданного элемента нет’)

Если известно, что данные отсортированы, можно применить двоичный поиск:

int function BinarySearch (Array A, int Lb, int Ub, int Key);

begin

do forever

M = (Lb + Ub)/2;

if (Key < A[M]) then

Ub = M – 1;

else if (Key > A[M]) then

Lb = M + 1;

else

return M;

if (Lb > Ub) then

return –1;

end;

Переменные Lb и Ub содержат, соответственно, верхнюю и нижнюю границы отрезка массива, где находится нужный нам элемент. Мы начинаем всегда с исследования среднего элемента отрезка. Если искомое значение меньше среднего элемента, мы переходим к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. Другими словами, значением Ub становится равным (M – 1) и на следующей итерации мы работаем с половиной массива. Таким образом, в результате каждой проверки мы вдвое сужаем область поиска. Так, в нашем примере, после первой итерации область поиска – всего лишь три элемента, после второй остается всего лишь один элемент. Таким образом, если длина массива равна 6, нам достаточно трех итераций, чтобы найти нужное число.

Рисунок 1.1 – Массив

Двоичный поиск – очень мощный метод. Если, например, длина массива равна 1023, после первого сравнения область сужается до 511 элементов, а после второй – до 255. Легко посчитать, что для поиска в массиве из 1023 элементов достаточно 10 сравнений.

Кроме поиска нам необходимо бывает вставлять и удалять элементы. К сожалению, массив плохо приспособлен для выполнения этих операций. Например, чтобы вставить число 18 в массив на рисунке 1.1, нам понадобится сдвинуть элементы A[3]… A[6] вниз – лишь после этого мы сможем записать число 18 в элемент A[3]. Аналогичная проблема возникает при удалении элементов. Для повышения эффективности операций вставки / удаления предложены связанные списки.

Иначе двоичный поиск (бинарный поиск) называют поиском делением пополам. В большинстве случаев процедура поиска применяется к упорядоченным данным (телефонный справочник, библиотечные каталоги и пр.).

Односвязные списки

На рисунке 1.2 те же числа, что и раньше, хранятся в виде связанного списка; слово «связанный» часто опускают. Предполагая, что X и P являются указателями, число 18 можно вставить в такой список следующим образом:

X->Next = P->Next;

P->Next = X;

Списки позволяют осуществить вставку и удаление очень эффективно. Поинтересуемся, однако, как найти место, куда мы будем вставлять новый элемент, т. е. каким образом присвоить нужное значение указателю P. Увы, для поиска нужной точки придется пройтись по элементам списка. Таким образом, переход к спискам позволяет уменьшить время вставки / удаления элемента за счет увеличения времени поиска.

Рисунок 1. 2 – Односвязный список

Поиск в бинарных деревьях

Мы использовали двоичный поиск для поиска данных в массиве. Этот метод чрезвычайно эффективен, поскольку каждая итерация вдвое уменьшает число элементов, среди которых нам нужно продолжать поиск. Однако операции вставки и удаления элементов не столь эффективны. Двоичные деревья позволяют сохранить эффективность всех трех операций – если работа идет со «случайными» данными. В этом случае время поиска оценивается как O (lg n). Наихудший случай – когда вставляются упорядоченные данные. В этом случае оценка время поиска – O(n).

Двоичное дерево – это дерево, у которого каждый узел имеет не более двух наследников. Пример бинарного дерева приведен на рисунке 1.5. Предполагая, что Key содержит значение, хранимое в данном узле, мы можем сказать, что бинарное дерево обладает следующим свойством: у всех узлов, расположенных слева от данного узла, значение соответствующего поля меньше, чем Key, у всех узлов, расположенных справа от него, – больше. Вершину дерева называют его корнем. Узлы, у которых отсутствуют оба наследника, называются листьями. Корень дерева на рисунке 1.3 содержит число 20, а листья – 4, 16, 37 и 43. Высота дерева – это длина наидлиннейшего из путей от корня к листьям. В нашем примере высота дерева равна 2.