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

Федеральное агентство пообразованию
Новомосковский институт(филиал)
Государственногообразовательного учреждения высшего профессионального образования
«Российский химико-технологический университет имени Д.И. Менделеева»
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) иобозначается xy [3].
Линейнымпорядком на множестве A называется отношение частичного порядка, прикотором из любой пары элементов можно выделить предшествующий и последующий.
Постановказадачи:пусть задано конечное множество А, состоящее из n элементов ai,на нём задано отношение линейного порядка Р.
Требуетсяперенумеровать элементы А числами от 1 до n таким образом, чтобыиз того, что i следовало (ai, aj)Є P. Выполнение этой задачи называется сортировкой массива данных [3].
Способысравнения могут быть очень разнообразными, но в большинстве случаев они исходятиз двух базовых элементарных упорядочений: упорядочение чисел по значению иупорядочение слов по алфавиту.
Потребность всортировке больших объёмов данных ощущалась очень давно, например, в комплектесчётно-аналитических машин Холлерита была специальная сортирующая машина.
Во многихзадачах требуется иметь данные, расположенные в порядке возрастания или впорядке убывания. Такое упорядочение в программировании называется сортировкой.Сортировка применяется во многих задачах. Существуют различные методысортировки: одни из них просты, но более медленные, другие быстрые, но болеесложные. Одни сортируют каждый массив заново, другие распознают ужеупорядоченные части массива и поэтому работают быстрее.
Выдающийсяспециалист по программированию Д. Кнут посвятил сортировке и поиску данныхпочти весь второй том трудов «Искусство программирования для ЭВМ» [4].
Сортировкаданных – обработка информации, в результате которой элементы её (записи) располагаютсяв определённой последовательности в зависимости от значения некоторых признаковэлементов, называемых ключевыми.
Наиболеераспространёнными видами сортировки данных являются упорядочение массива записей– расположение записей сортируемого массива данных в порядке монотонногоизменения значения ключевого признака. Сортировка данных позволяет сократить вдесятки раз продолжительность решения задач, связанных с обработкой большихмассивов записей. Такое ускорение происходит за счёт сокращения времени поисказаписей с определёнными значениями ключевых признаков. Упорядочениеосуществляется в процессе многократного просмотра исходного массива.
Одними изважнейших процедур обработки структурированной информации являются сортировка ипоиск. Сортировкой также называют процесс перегруппировки заданнойпоследовательности (кортежа) объектов в некотором определенном порядке.Определенный порядок (например, упорядочение в алфавитном порядке, по возрастаниюили убыванию количественных характеристик, по классам, типам и т. п.)в последовательности объектов необходим для удобства работы с этими объектами.В частности, одной из целей сортировки является облегчение последующего поискаэлементов в отсортированном множестве. Под поиском подразумевается процесснахождения в заданном множестве объекта, обладающего свойствами или качествамизадаваемого априори эталона (или шаблона).
Например,требуется решить задачу: даны целые числа x, a1, a2,…, an (n>0). Определить, каким по счёту идёт впоследовательности a1, a2, …, anчлен, равный 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
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.

/>
Рисунок 1.3 – Двоичное дерево
Чтобы найти вдереве какое-то значение, мы стартуем из корня и движемся вниз. Например, дляпоиска числа 16, мы замечаем, что 16 7, так что мы движемся вправо. Третья попыткауспешна – мы находим элемент с ключом, равным 16.
Каждоесравнение вдвое уменьшает количество оставшихся элементов. В этом отношенииалгоритм похож на двоичный поиск в массиве. Однако, все это верно только вслучаях, когда наше дерево сбалансировано. На рисунке 1.4 показано другоедерево, содержащее те же элементы. Несмотря на то, что это дерево тожебинарное, поиск в нем похож, скорее, на поиск в односвязном списке, времяпоиска увеличивается пропорционально числу запоминаемых элементов.
/>/>
Рисунок 1.4 – Несбалансированноебинарное дерево
Вставка иудаление
Чтобы лучшепонять, как дерево становится несбалансированным, посмотрим на процесс вставкипристальнее. Чтобы вставить 18 в дерево на рисунке 1.3 мы ищем это число. Поискприводит нас в узел 16, где благополучно завершается. Поскольку 18 > 16, мы попростудобавляет узел 18 в качестве правого потомка узла 16 (рисунок 1.5).
Теперь мывидим, как возникает несбалансированность дерева. Если данные поступают ввозрастающем порядке, каждый новый узел добавляется справа от последнеговставленного. Это приводит к одному длинному списку. Обратите внимание: чемболее «случайны» поступающие данные, тем более сбалансированным получается дерево.
Удаленияпроизводятся примерно так же – необходимо только позаботиться о сохраненииструктуры дерева. Например, если из дерева на рисунке 1.5 удаляется узел 20,его сначала нужно заменить на узел 37. Это даст дерево, изображенное на рисунок1.6. Рассуждения здесь примерно следующие. Нам нужно найти потомка узла 20,справа от которого расположены узлы с большими значениями. Таким образом, намнужно выбрать узел с наименьшим значением, расположенный справа от узла 20.Чтобы найти его, нам и нужно сначала спуститься на шаг вправо (попадаем в узел38), а затем на шаг влево (узел 37); эти двухшаговые спуски продолжаются, покамы не придем в концевой узел, лист дерева.
/>
Рисунок 1.5 – Бинарное дерево после добавления узла 18
/>
Рисунок 1.6 – Бинарное дерево после удаления узла 20
 
Разделенныесписки
Разделенныесписки – это связные списки, которые позволяют вам прыгнуть (skip) кнужному элементу. Это позволяет преодолеть ограничения последовательногопоиска, являющегося основным источником неэффективного поиска в списках. В тоже время вставка и удаление остаются сравнительно эффективными. Оценка среднеговремени поиска в таких списках есть O (lg n). Для наихудшего случаяоценкой является O(n), но худший случай крайне маловероятен.
Идея, лежащаяв основе разделенных списков, очень напоминает метод, используемый при поискеимен в адресной книжке. Чтобы найти имя, вы помечаете буквой страницу, откуданачинаются имена, начинающиеся с этой буквы. На рисунке 1.6, например, самыйверхний список представляет обычный односвязный список. Добавив один «уровень»ссылок, мы ускорим поиск. Сначала мы пойдем по ссылкам уровня 1, затем, когдадойдем до нужного отрезка списка, пойдем по ссылкам нулевого уровня.
Эта простаяидея может быть расширена – мы можем добавить нужное число уровней. Внизу нарисунке 1.6 мы видим второй уровень, который позволяет двигаться еще быстреепервого. При поиске элемента мы двигаемся по этому уровню, пока не дойдем донужного отрезка списка. Затем мы еще уменьшаем интервал неопределенности,двигаясь по ссылкам 1‑го уровня. Лишь после этого мы проходим по ссылкам0‑го уровня.
Вставляяузел, нам понадобится определить количество исходящих от него ссылок. Эта проблемалегче всего решается с использованием случайного механизма: при добавлениинового узла мы «бросаем монету», чтобы определить, нужно ли добавлять еще слой.Например, мы можем добавлять очередные слои до тех пор, пока выпадает «решка».Если реализован только один уровень, мы имеем дело фактически с обычным спискоми время поиска есть O(n). Однако если имеется достаточное числоуровней, разделенный список можно считать деревом с корнем на высшем уровне, адля дерева время поиска есть O (lg n).
Посколькуреализация разделенных списков включает в себя случайный процесс, для временипоиска в них устанавливаются вероятностные границы. При обычных условиях этиграницы довольно узки. Например, когда мы ищем элемент в списке из 1000 узлов,вероятность того, что время поиска окажется в 5 раз больше среднего, можно оценитькак 1/ 1,000,000,000,000,000,000 (рисунок 1.7).
/>
Рисунок 1.7 – Устройство разделенного списка
 
1.2.3Оценки времени исполнения
Для оценки эффективностиалгоритмов можно использовать разные подходы. Самый бесхитростный – простозапустить каждый алгоритм на нескольких задачах и сравнить время исполнения.Другой способ – оценить время исполнения. Например, мы можем утверждать, чтовремя поиска есть O(n) (читается так: о большое от n).Это означает, что при больших n время поиска не сильно больше, чем количествоэлементов. Когда используют обозначение O(), имеют в виду не точноевремя исполнения, а только его предел сверху, причем с точностью до постоянногомножителя. Когда говорят, например, что алгоритму требуется время порядка O(n2),имеют в виду, что время исполнения задачи растет не быстрее, чем квадратколичества элементов. Чтобы почувствовать, что это такое, посмотрите таблицу 1.1,где приведены числа, иллюстрирующие скорость роста для нескольких разныхфункций. Скорость роста O(log2n) характеризует алгоритмытипа двоичного поиска.

Таблица 1.1 – Скорость роста нескольких функций O()
n
log2n
n log2n
n1.25
n2 1 1 1 16 4 64 32 256 256 8 2,048 1,024 65,536 4,096 12 49,152 32,768 16,777,216 65,536 16 1,048,565 1,048,476 4,294,967,296 1,048,476 20 20,969,520 33,554,432 1,099,301,922,576 16,775,616 24 402,614,784 1,073,613,825 281,421,292,179,456
Если считать,что числа в таблице 1.1 соответствуют микросекундам, то для задачи с 1048476элементами алгоритму со временем работы O(log2n) потребуется 20 микросекунд,алгоритму со временем работы O(n1.25) – порядка 33секунд, алгоритму со временем работы O(n2) – более 12дней. В нижеследующем тексте для каждого алгоритма приведены соответствующие O‑оценки.Более точные формулировки и доказательства можно найти в [12], [15].
Как мывидели, если массив отсортирован, то искать его элементы необходимо с помощьюдвоичного поиска. Однако не забудем, что массив должен быть отсортированным! Вследующем разделе мы исследует разные способы сортировки массива. Оказывается,эта задача встречается достаточно часто и требует заметных вычислительныхресурсов, поэтому сортирующие алгоритмы исследованы вдоль и поперек, известныалгоритмы, эффективность которых достигла теоретического предела.
/>/>/>/>/>/>/>/>/>/>Связанные спискипозволяют эффективно вставлять и удалять элементы, но поиск в нихпоследователен и потому отнимает много времени. Имеются алгоритмы, позволяющиеэффективно выполнять все три операции.
 
1.2.4Сортировки
Сортировкавставками
Один изпростейших способов отсортировать массив – сортировка вставками. В обычнойжизни мы сталкиваемся с этим методом при игре в карты. Чтобы отсортироватьимеющиеся у вас карты, вы вынимаете карту, сдвигаете оставшиеся карты, а затемвставляете карту на нужное место. Процесс повторяется до тех пор, пока хотьодна карта находится не на месте. Как среднее, так и худшее время для этогоалгоритма – O(n2). Дальнейшую информацию можно получитьв книге Кнута [4].
На рисунке 1.8(a) мы вынимаем элемент 3. Затем элементы, расположенные выше, сдвигаемвниз – до тех пор, пока не найдем место, куда нужно вставить 3. Это процесспродолжается на рисунке 1.8 (b) для числа 1. Наконец, на рисунке 1.8 (c)мы завершаем сортировку, поместив 2 на нужное место.
/>
Рисунок 1.8 – Сортировка вставками
Если длинанашего массива равна n, нам нужно пройтись по n – 1 элементам.Каждый раз нам может понадобиться сдвинуть n – 1 других элементов. Вотпочему этот метод требует довольно-таки много времени.
Сортировкавставками относится к числу методов сортировки по месту. Другими словами, ей нетребуется вспомогательная память, мы сортируем элементы массива, используятолько память, занимаемую самим массивом. Кроме того, она является устойчивой –если среди сортируемых ключей имеются одинаковые, после сортировки они остаютсяв исходном порядке.
Сортировкас помощью включения
Кто играл вкарты, процедуру сортировки включениями осуществлял многократно. Как правило,после раздачи карт игрок, держа карты веером в руке, переставляет карты с местана место, стремясь их расположить по мастям и рангам, например, сначала всетузы, затем короли, дамы и т. д. Элементы (карты) мысленно делятся науже «готовую последовательность» и неправильно расположенную последовательность.Теперь на каждом шаге, начиная с i = 2, из неправильно расположеннойпоследовательности извлекается очередной элемент и перекладывается в готовуюпоследовательность на нужное место.
for i:=2 to N do
begin
x:=a[i];

End
Поискподходящего места можно осуществить одним из методов поиска в массиве,описанным выше. Затем х либо вставляется на свободное место, либо сдвигаетвправо на один индекс всю левую сторону. Схематично представим алгоритм дляконкретного примера:
Исходныеэлементы     23     34     12     13     9
i=2                       23     34     12     13     9
i=3                       12     23     34     13     9
i=4                       12     13     23     34     9
i=5                       9       12     13     23     34
В алгоритмепоиск подходящего места осуществляется как бы просеиванием x: придвижении по последовательности и сравнении с очередным a[j]. Затем хлибо вставляется на свободное место, либо а[j] сдвигается вправо ипроцесс как бы «уходит» влево.
Сортировкас помощью прямого включения
Элементы массива,начиная со второго, последовательно берутся по одному и включаются на нужноеместо в уже упорядоченную часть массива, расположенную слева от текущегоэлемента а[i]. В отличие от стандартной ситуации включения элемента в заданнуюпозицию массива, позиция включаемого элемента при этом неизвестна. Определимеё, сравнивая в цикле поочерёдно a[i] с a [i‑1],а [i‑2],… до тех пор, пока не будет найден первый изэлементов меньший или равный а[i], либо не будет достигнут левыйконец массива. Поскольку операции сравнения и перемещения чередуются друг сдругом, то этот способ часто называют просеиванием или погружением. Очевидно,что программа, реализующая описанный алгоритм, должна содержать цикл в цикле.
program sortirovka_l;
(*сортировка включением по линейному поиску*)
const N=5;
type item= integer;
var a: array [0..n] of item; i, j: integer; x: item;
begin (*задание искомого массива*)
for i:=1 to N do begin write ('введите элемент a [', i, ']=');
readln (a[i])
end;
for i:=1 to N do begin write (a[i], ' ');
end;
writeln;
(*алгоритм сортировки включением*)
for i:=2 to n do
begin
x:=a[i]; j:=i; a[0]:=x; (*барьер*)
while x
begin
a[j]:=a [j‑1]; j:=j‑1;
end;
a[j]:=x;
{for k:=1 to n do write (a[k], ' ') end;writeln;} end;
(*вывод отсортированного массива*)
for i:=1 to N do
begin
write (a[i], ' '); end;
readln; end.
Врассмотренном примере программы для анализа процедуры пошаговой сортировки можнорекомендовать использовать трассировку каждого прохода по массиву с цельювизуализации его текущего состояния. В тексте программы в блоке непосредственногоалгоритма сортировки в фигурных скобках находится строка, которая при удалениискобок выполнит требуемое (параметр k необходимо описать вразделе переменных – var k:integer).
Вернемся канализу метода прямого включения. Поскольку готовая последовательность ужеупорядочена, то алгоритм улучшается при использовании алгоритма поиска делениемпополам. Такой способ сортировки называют методом двоичного включения.
programsortirovka_2;
(*сортировкадвоичным включением*)
constN=5;
typeitem= integer;
vara: array [0..n] of item; i, j, m, L, R: integer; x: item;
begin(*задание элементов массива*)
fori: – l to N do begin write ('введите элемент a [', i, ']= ');
readln(a[i]);
end;
fori:=1 to N do begin write (a[i], ' ');
end;
writeln;
(*алгоритмсортировки двоичным включением*)
fori:=2 to n do
begin
x:=a[i];L:=l; R:^i;
whileL
begin
m:=(L+R)div 2; if a [m]
end;
forj:=i downto R+l do a[j]:=a [j‑1];
a[R]:=x; end;
(* выводотсортированного массива*)
fori: – l to N do
beginwrite (a[i], ' ');
end;
readln;
end.
СортировкаШелла
Метод,предложенный Дональдом Л. Шеллом, является неустойчивой сортировкой по месту.Эффективность метода Шелла объясняется тем, что сдвигаемые элементы быстропопадают на нужные места. Среднее время для сортировки Шелла равняется O(n1.25),для худшего случая оценкой является O(n1.5). Дальнейшиессылки см. в книге Кнута [4].
На рисунке 1.8приведен пример сортировки вставками. Мы сначала вынимали 1, затем сдвигали 3 и5 на одну позицию вниз, после чего вставляли 1. Таким образом, нам требовалисьдва сдвига. В следующий раз нам требовалось два сдвига, чтобы вставить нанужное место 2. На весь процесс нам требовалось 2+2+1=5 сдвигов.
На рисунке 1.9иллюстрируется сортировка Шелла. Мы начинаем, производя сортировку вставками сшагом 2. Сначала мы рассматриваем числа 3 и 1: извлекаем 2, сдвигаем 3 на 1позицию с шагом 2, вставляем 2. Затем повторяем то же для чисел 5 и 2: извлекаем2, сдвигаем вниз 5, вставляем 2 и т. д. Закончив сортировку с шагом2, производим ее с шагом 1, т. е. выполняем обычную сортировку вставками.Всего при этом нам понадобится 1 + 1+ 1 = 3 сдвига. Таким образом, использоваввначале шаг, больший 1, мы добились меньшего числа сдвигов.
/>
Рисунок 1.9 – Сортировка Шелла
Можноиспользовать самые разные схемы выбора шагов. Как правило, сначала мы сортируеммассив с большим шагом, затем уменьшаем шаг и повторяем сортировку. В самомконце сортируем с шагом 1. Хотя этот метод легко объяснить, его формальныйанализ довольно труден. В частности, теоретикам не удалось найти оптимальнуюсхему выбора шагов. Кнут провел множество экспериментов и следующую формулувыбора шагов (h) для массива длины N.
Вот несколькопервых значений h:
/>.
Чтобыотсортировать массив длиной 100, прежде всего, найдем номер s, длякоторого hs ³ 100. Согласно приведенным цифрам, s = 5.Нужное нам значение находится двумя строчками выше. Таким образом,последовательность шагов при сортировке будет такой: 13–4–1. Ну, конечно, намне нужно хранить эту последовательность: очередное значение h находитсяиз предыдущего.
Сортировкас помощью дерева
Улучшенныйметод сортировки выбором с помощью дерева. Метод сортировки прямым выборомоснован на поисках наименьшего элемента среди неготовой последовательности.Усилить метод можно запоминанием информации при сравнении пар элементов. Этогодобиваются определением в каждой паре меньшего элемента за n/2 сравнений.Далее n/4 сравнений позволит выбрать меньший из пары уже выбранныхменьших и т. д. Получается двоичное дерево сравнений после n‑1сравнений, у которого в корневой вершине находится наименьший элемент, а любаявершина содержит меньший элемент из двух приходящих к ней вершин. Одним изалгоритмов, использующих структуру дерева, является сортировка с помощьюпирамиды (Дж. Вильямс) [3]. Пирамида определяется как последовательностьключей hL…hR, такая, что
 
hi2i и hih2i+l, для i=L,…,R/2.
Другимисловами, пирамиду можно определить как двоичное дерево заданной высоты h,обладающее тремя свойствами:
• каждаяконечная вершина имеет высоту h или h‑1;
• каждаяконечная вершина высоты h находится слева от любой конечной вершинывысоты h‑1;
• значениелюбой вершины больше значения любой следующей за ней вершины.
Рассмотримпример пирамиды, составленной по массиву 27 9 14 8 5 11 7 2 3.
У пирамиды n=9вершин, их значения можно разместить в массиве а, но таким образом, чтоследующие за вершиной из a[i] помещаются в a[2i] и a [2i+l].Заметим, что а[6]=11, а[7]=7, а они следуют за элементом а[3]=14(рисунок 1.10).
/>
Рисунок 1.10 –Пирамида
Очевидно, чтоесли 2i > n, тогда за вершиной a[i] не следуютдругие вершины, и она является конечной вершиной пирамиды.
Процесспостроения пирамиды для заданного массива можно разбить на четыре этапа:
1) меняяместами а[1] и а[n], получаем 3 9 14 8 5 11 7 2 27;
2) уменьшаем nна 1, т. е. n=n‑1, что эквивалентно удалению вершины 27 издерева;
3)преобразуем дерево в другую пирамиду перестановкой
нового корняс большей из двух новых, непосредственно следующих за ним вершин, до тех пор,пока он не станет больше, чем обе вершины, непосредственно за ним следующие;
4) повторяемшаги 1, 2, 3 до тех пор, пока не получим n=1.
Для алгоритмасортировки нужна процедура преобразования произвольного массива в пирамиду (шаг3). В ней необходимо предусмотреть последовательный просмотр массива справаналево с проверкой одновременно двух условий: больше ли а[n], чем a[2i]и a [2i+l].
Полный текстпрограммы приведен ниже.
programsortirovka_5;
(*улучшеннаясортировка выбором – сортировка с помощью дерева*)
constN=8;
typeitem= integer;
vara: array [1..n] of item; k, L, R: integer; x: item;
proceduresift (L, R:integer);
vari, j: integer; x, y: item;
begini:=L; j:=2*L; x:=a[L]; if (j
while(j
a[j]:=y;a[i]:=a[j]; i:=j; j:=2*j;
if(j
end;
end;
begin
(*заданиеискомого массива*)
fork:=1 to N do beginwrite ('Bведите элемент a [', k,']=');
readln(a[k]);
end;
fork:=1 to N do beginwrite (a[k], ' ');
end;
writeln;
(*алгоритмсортировки с помощью дерева*)
(*построение пирамиды*)
L:=(ndiv 2) +1; R:=n; while L>1 do begin L:=L‑1; SIFT (L, R);
end;
(*сортировка*)
whileR>1 do begin x:=a[l]; a[l]:=a[R]; a[R]:=x; R:=R‑1; SIET (1, R);
end;
(*вывод отсортированного массива*) for k:=1 toN do begin write (a[k], ' ');
end;
readln;
end.
Сортировкас помощью обменов
1‑ыйвариант.Соседние элементы массива сравниваются и при необходимости меняются местами дотех пор, пока массив не будет полностью упорядочен. Повторные проходы массивасдвигают каждый раз наименьший элемент оставшейся части массива к левому егоконцу. Метод широко известен под названием «пузырьковая сортировка» потому, чтобольшие элементы массива, подобно пузырькам, «всплывают» на соответствующуюпозицию. Основной фрагмент программы содержит два вложенных цикла, причёмвнутренний цикл удобнее выбрать с шагом, равным -1 [8]:
fori: =2 to n do
forj:=n downto i do
ifa [j‑1]>a[j] then
begin{обмен}x:=a [j‑1]; a [j‑1]:=a[j];a[j]:=xend;
2‑ойвариант.Пузырьковая сортировка является не самой эффективной, особенно дляпоследовательностей, у которых «всплывающие» элементы находятся в крайнейправой стороне. В улучшенной (быстрой) пузырьковой сортировке предлагаетсяпроизводить перестановки на большие расстояния, причем двигаться с двух сторон.Идея алгоритма заключается в сравнении элементов, из которых один берется слева(i = 1), другой – справа (j = n). Если a[i] j], то устанавливают j = j – 1 и проводят следующеесравнение. Далее уменьшают j до тех пор, пока a[i] > a[j].В противном случае меняем их местами и устанавливаем i = i + 1.Увеличение i продолжаем до тех пор, пока не получим a[i]> a[j]. После следующего обмена опять уменьшаем j.Чередуя уменьшение j и увеличение i, продолжаем этот процесс собоих концов до тех пор, пока не станет i = j. После этого этапа возникаетситуация, когда первый элемент занимает ему предназначенное место, слева отнего младшие элементы, а справа – старшие [8].
Далееподобную процедуру можно применить к левой и правой частям массива и т. д.Очевидно, что характер алгоритма рекурсивный. Для запоминания ведущих левого иправого элементов в программе необходимо использовать стек.
Характернойчертой алгоритмов сортировки с помощью обмена является обмен местами двухэлементов массива после их сравнения друг с другом. В так называемой«пузырьковой сортировке» проводят несколько проходов по массиву, в каждом изкоторых повторяется одна и та же процедура: сравнение двух последовательностоящих элементов и их обмен местами в порядке меньшинства (старшинства).Подобная процедура сдвигает наименьшие элементы к левому концу массива.
programsortirovka_6;
(*сортировкапрямым обменом – пузырьковая сортировка*)
constN=5;
typeitem= integer;
vara: array [1..n] of item; i, j: integer; x: item;
begin(*задание искомого массива*)
fori:=1 to N do beginwrite ('введи элемент a [', i,']= ');
readln(a[i]);
end;
fori:=1 to N do beginwrite (a[i], ' ');
end;
writeln;
(*алгоритмпузырьковой сортировки*)
fori:=2 to n do for j:=n downto i do begin
ifa [j‑1]>a[j] then begin x:=a [j‑1]; a [j‑1]:=a[j]; a[j]:=x;
end;
end;
(*выводотсортированного массива*)
fori:=1 to N do beginwrite (a[i], ' ');
end;
readln;
end.
Представленнуюпрограмму можно легко улучшить, если учесть, что если после очередного проходаперестановок не было, то последовательность элементов уже упорядочена, т. е.продолжать проходы не имеет смысла. Если чередовать направление последовательныхпросмотров, алгоритм улучшается. Такой алгоритм называют «шейкерной» сортировкой.
programsortirovka_7;
(*сортировкапрямым обменом – шейкерная сортировка*)
constN=5;
typeitem= integer;
vara: array [1..n] of item; i, j, k, L, R: integer; x: item;
begin(*задание искомого массива*)
fori: =1 to N do begin write ('введи элемент а [', i, '] =');
readln(a[i]);
end;
fori:=1 to N do begin write (a[i], ' ');
end;
writeln;
(*алгоритмшейкерной сортировки*)
L:=2; R:=n; k:=n;
repeat
forj:=R downto L do begin
ifa [j-l]>a[j] then begin x:=a [j‑1]; a [j‑1]:=a[j];
a[j]:=x;k:=-j
end;
end;
L:=k+1;
forj:=L to R do begin
ifa [j-l]>a[j] then begin x:=a [j-l]
a [j-l]:=a[j];a[j]:=x; k:=j
end;
end;
R:=k‑1;until L>R;
(*выводотсортированного массива*)
for i:=l to Ndo
beginwrite (a[i], ' ');
end;
readln;
end.
Быстраясортировка
Хотя идеяШелла значительно улучшает сортировку вставками, резервы еще остаются. Один изнаиболее известных алгоритмов сортировки – быстрая сортировка, предложенная Ч. Хоаром.Метод и в самом деле очень быстр, недаром по-английски его так и величают QuickSort[6].
Этому методутребуется O (n log2n) в среднем и O(n2)в худшем случае. К счастью, если принять адекватные предосторожности, наихудшийслучай крайне маловероятен. Быстрый поиск не является устойчивым. Кроме того,ему требуется стек, т. е. он не является и методом сортировки на месте.
Алгоритмразбивает сортируемый массив на разделы, затем рекурсивно сортирует каждыйраздел. В функции Partition один из элементов массива выбирается вкачестве центрального. Ключи, меньшие центрального, следует расположить слеваот него, те, которые больше – справа.
intfunction Partition (Array A, int Lb, int Ub);
begin
selecta pivot from A[Lb]… A[Ub];
reorderA[Lb]… A[Ub] such that:
allvalues to the left of the pivot are £ pivot
allvalues to the right of the pivot are ³ pivot
returnpivot position;
end;
procedureQuickSort (Array A, int Lb, int Ub);
begin
ifLb
M= Partition (A, Lb, Ub);
QuickSort(A, Lb, M – 1);
QuickSort(A, M + 1, Ub);
end;
На рисунке 1.11(а) в качестве центрального выбран элемент 3. Индексы начинают изменяться сконцов массива. Индекс i начинается слева и используется для выбораэлементов, которые больше центрального, индекс j начинается справа ииспользуется для выбора элементов, которые меньше центрального. Эти элементыменяются местами – см. рисунок 1.11 (b). Процедура QuickSort рекурсивносортирует два подмассива, в результате получается массив, представленный нарисунке 1.11 (c).
В процессесортировки может потребоваться передвинуть центральный элемент. Если намповезет, выбранный элемент окажется медианой значений массива, т. е.разделит его пополам. Предположим на минутку, что это и в самом деле так.Поскольку на каждом шаге мы делим массив пополам, а функция Partition, в концеконцов, просмотрит все n элементов, время работы алгоритма есть O (nlog2n).
В качествецентрального функция Partition может попросту брать первый элемент (A[Lb]).Все остальные элементы массива мы сравниваем с центральным и передвигаем либовлево от него, либо вправо. Есть, однако, один случай, который безжалостноразрушает эту прекрасную простоту. Предположим, что наш массив с самого началаотсортирован. Функция Partition всегда будет получать в качествецентрального минимальный элемент и потому разделит массив наихудшим способом: влевом разделе окажется один элемент, соответственно, в правом останется Ub –Lb элементов.
/>
Рисунок 1.11 – Пример работы алгоритма Quicksort
Такимобразом, каждый рекурсивный вызов процедуры quicksort всего лишьуменьшит длину сортируемого массива на 1. В результате для выполнениясортировки понадобится n рекурсивных вызовов, что приводит к времениработы алгоритма порядка O(n2). Один из способовпобороть эту проблему – случайно выбирать центральный элемент. Это сделаетнаихудший случай чрезвычайно маловероятным.
Сортировкас помощью прямого выбора
Присортировке этим методом выбирается наименьший элемент массива и меняетсяместами с первым. Затем выбирается наименьший среди оставшихся n – 1элементов и меняется местами со вторым и т. д. до тех пор, пока неостанется один самый больший элемент. Основной фрагмент программы можетвыглядеть так [11]:
for i:=l to n‑1do
begin
k:=i;
x:=a[i];
forj:=i+1 to n do
ifa[j]
k – величина, хранящаяиндекс элемента, участвующего в операции обмена.
Сортировкафайлов
Главнаяособенность методов сортировки последовательных файлов в том, что при ихобработке в каждый момент непосредственно доступна одна компонента (на которуюуказывает указатель). Чаще процесс сортировки протекает не в оперативнойпамяти, как в случае с массивами, а с элементами на внешних носителях («винчестере»,дискете и т. п.).
Понятьособенности сортировки последовательных файлов на внешних носителях позволитследующий пример [9].
Предположим,что нам необходимо упорядочить содержимое файла с последовательным доступом покакому-либо ключу. Для простоты изучения и анализа сортировки условимся, чтофайл формируем мы сами, используя, как и в предыдущем разделе, некоторый массивданных. Его же будем использовать и для просмотра содержимого файла послесортировки. В предлагаемом ниже алгоритме необходимо сформировать вспомогательныйфайл, который позволит осуществить следующую процедуру сортировки. Сначалавыбираем из исходного файла первый элемент в качестве ведущего, затем извлекаемвторой и сравниваем с ведущим. Если он оказался меньше, чем ведущий, топомещаем его во вспомогательный файл, в противном случае во вспомогательныйфайл помещается ведущий элемент, а его замещает второй элемент исходного файла.Первый проход заканчивается, когда аналогичная процедура коснется всех последовательныхэлементов исходного файла. Ведущий элемент заносится во вспомогательный файлпоследним. Теперь необходимо поменять местами исходный и вспомогательный файлы.После nil проходов в исходном файле данные будут размещены в упорядоченномвиде.
programsortirovka_faila_1;
{сортировкапоследовательного файла}
constn=8; type item= integer;
vara: array [1..n] of item;
i,k: integer; x, y: item;
fl,f2: text; {file of item};
begin
{задание искомого массива}
fori:=1 to N do begin write ('введи элемент а ['i, '] = ');
readln(a[i]);
end;
writeln;assign (fl, 'datl.dat'); rewrite(fl);
assign(f2, 'dat2.dat'); rewrite(f2);
{формирование последовательного файла}
fori:=1 to N do begin writeln (fl, a[i]);
end;
{алгоритмсортировки с использованием вспомогательного файла}
fork:=1 to (n div 2) do
begin {извлечениеиз исходного файла и запись во вспомогательный}
reset(fl);readln (fl, x);
fori:=2 to n do begin readln (fl, y);
ifx>y then writeln (f2, y) else begin writeln (f2, x); x:=y;
end;
end;
writeln(f2, x);
{извлечениеиз вспомогательного файла и запись в исходный}
rewrite(fl);reset(f2); readln (f2, x);
fori:=2 to n do begin readln (f2, y);
ifx>y then writeln (fl, y) else begin writeln (fl, x); x:=y;
end;
end;
writeln(fl, x); rewrite(f2); end;
(вывод результата)
reset(fl);
fori:=1 to N do readln (fl, a[i]);
fori:=1 to N do begin write (a[i], ' ');
end;
close(fl);close(f2); readln;
end.
По сути можнов программе обойтись без массива а [1..n]. В качестве упражненияпопытайтесь создать программу, в которой не используются массивы.
Многие методысортировки последовательных файлов основаны на процедуре слияния, означающейобъединение двух (или более) последовательностей в одну, упорядоченную спомощью повторяющегося выбора элементов (доступных в данный момент). Вдальнейшем (чтобы не осуществлять многократного обращения к внешней памяти),будем рассматривать вместо файла массив данных, обращение к которому можноосуществлять строго последовательно. В этом смысле массив представляется какпоследовательность элементов, имеющая два конца, с которых можно считывать данные.При слиянии можно брать элементы с двух концов массива, что эквивалентносчитыванию элементов из двух входных файлов.
Идея слияниязаключается в том, что исходная последовательность разбивается на две половины,которые сливаются вновь в одну упорядоченными парами, образованными двумя элементами,последовательно извлекаемыми из этих двух подпоследовательностей. Вновь повторяемделение и слияние, но упорядочивая пары, затем четверки и т. д. Дляреализации подобного алгоритма необходимы два массива, которые поочередно (каки в предыдущем примере) меняются ролями в качестве исходного и вспомогательного.
Если объединитьэти два массива в один, разумеется, двойного размера, то программа упрощается.Пусть индексы i и j фиксируют два входных элемента с концовисходного массива, k и L – два выходных, соответствующихконцам вспомогательного массива. Направлением пересылки (сменой ролей массивов)удобно управлять с помощью булевской переменной, которая меняет свое значениепосле каждого прохода, когда элементы a1…, anдвижутся на место ani….a2n инаоборот. Необходимо еще учесть изменяющийся на каждом проходе размер объединяемыхупорядоченных групп элементов. Перед каждым последующим проходом размерудваивается. Если считать, что количество элементов в исходной последовательностине является степенью двойки (для процедуры разделения это существенно), то необходимопридумать стратегию разбиения на группы, размеры которых q и r могут не совпадать сведущим размером очередного прохода. В окончательном виде алгоритм сортировкислиянием представлен ниже.
programsortirovka__faila_2;
{сортировкапоследовательного файла слиянием}
const N=8;
typeitem= integer;
vara: array [1..2*n] of item;
i,j, k, L, t, h, m, p, q, r: integer; f: boolean;
begin
{задание искомого массива}
fori:=1 to N do beginwrite ('введи элемент а [', i, '] = ');
readln(a[i]);
end;
writeln;
{сортировка слиянием}
f:=true;p:=1;
repeat
h:=1; m:=n; if fthen begin
i:=1;j:=n; k:=n+1; L:=2*n
end
elsebegin k:=1; L:=n; i:=n+1; j:=2*n
end;
repeat
ifm>=p then q:=p else q:=m; m:=m-q;
ifm>=p then r:=p else r:=m; m:=m-r;
while(q0) and (r0) do
begin
ifa[i}
begina[k]:=a[i]; k:=k+h; i:=i+1; q:=q‑1
end
else
begina[k]:=a[j]; k:=k+h; j:=j‑1; r:=r‑1
end;
end;
whiler>0 do
begina[k]:=a[j]; k:=k+h; j:=j‑1; r:=r‑1;
end;
whileq>0 do begin
a[k]:=a[i];k: – k+h; i:=i+1; q:=q‑1;
end;
h:=-h;t:=k; k:=L; L:=t;
untilm=0;
f:=not(f);p:=2*p;
untilp>=n;
ifnot(f) then for i:=1 to n do a[i]:=a [i+n];
{вывод результата}
fori:=1 to N do beginwrite (a[i], ' ');
end;
readln;
end.
Рассмотренныедва предыдущих примера иллюстрируют большие проблемы сортировки внешних файлов,если в них часты изменения элементов, например, удаления, добавления,корректировки существующих.
В подобныхситуациях эффективными становятся алгоритмы, в которых обрабатываемые элементыпредставляются в виде структур данных, удобных для поиска и сортировки. Вкачестве структур данных можно отметить, в частности, линейные списки, очереди,стеки, деревья и т. п. О них было рассказано в предыдущем разделе.
/>1.3 Практическая часть
 
1.3.1 Содержаниеотчёта по практической работе
1         Заданиепо варианту.
2         Теоретическаячасть (краткое описание используемого метода и необходимые пояснения дляпонимания функционирования приложения на Delphi).
3         Блок-схемадля процедуры, реализующей основной алгоритм.
4         Кодпрограммы.
5         Результатырасчёта.
Примечание: а) подбор исходныхданных выполнить самостоятельно; б) если в варианте не указан метод, то выбратьнаиболее подходящий для решения поставленной задачи (предварительно согласоватьс преподавателем).
 
1.3.2Приложение на Delphi, в котором представлена работа некоторых методовсортировки и поиска
Графическийинтерфейс представлен на рисунке 1.14.

/>
Рисунок 1.14 – Форма
useswseme1;
procedureTForm1. Button16Click (Sender: TObject);
begin
close;
end;
procedureTForm1. Button1Click (Sender: TObject);
var i:integer;
begin
 //генерируем множество, состоящее из случайных чисел
Randomize;
fori:=0 to StringGrid1. RowCount do
StringGrid1.Cells [0, i]:=IntToStr (Random(10000)+1);
end;
procedureTForm1. FormCreate (Sender: TObject);
begin
Button1.Click();
end;
procedureTForm1. Edit1Exit (Sender: TObject);
begin
 //проверяем заполнено ли поле
ifedit1. Text='' then begin
MessageDlg('Введите число не больше 15', mtError,[mbOk, mbCancel], 0);
exit;end else
StringGrid1.RowCount:=strtoint (edit1. Text);
StringGrid2.RowCount:=strtoint (edit1. Text);
end;
procedureTForm1. Button3Click (Sender: TObject);
var
n,minimum, j, i, obmen:integer;
a:array[1..15] of integer;
begin
n:=strtoint(edit1. Text);
 //задание массива
forj:=1 to n do
a[j]:=StrToInt(StringGrid1. Cells [0, j‑1]);
forj:=1 to n do begin
 // номер минимальногоэлемента
minimum:=j;
fori:=j+1 to n do if a[i]
 // запоминаниеминимального элемента
obmen:=a[j];
a[j]:=a[minimum];
a[minimum]:=obmen;
 // вывод отсортированногомассива
for i:=0 to ndo
stringgrid2.Cells [0, j‑1]:=inttostr (a[j]);
end;
end;
procedureTForm1. Button4Click (Sender: TObject);
var
n,obmen, i, j:integer;
a:array[1..15] of integer;
colicobmen:boolean;
begin
n:=strtoint(edit1. Text);
 //задание массива
fori:=1 to n do
a[i]:=StrToInt (StringGrid1. Cells [0, i‑1]);
 //сортировка массива
repeat
colicobmen:=FALSE;
forj:=1 to n‑1 do
ifa[j] > a [j+1] then
begin
obmen:=a[j];
a[j]:=a[j+1];
a [j+1]:=obmen;
colicobmen:=TRUE;
end;
 //вывод массива
fori:=1 to n do
stringgrid2.Cells [0, i‑1]:=inttostr (a[i]);
untilnot colicobmen;
stringgrid2.Cells [0, i‑1]:=inttostr (a[i]);
end;
procedureTForm1. Button5Click (Sender: TObject);
var
a:array[1..15] of integer;
i,j, m, L, R, n, x:integer;
begin
n:=strtoint(edit1. Text);
 //задание массива
fori:=1 to n do
a[i]:=StrToInt(StringGrid1. Cells [0, i‑1]);
 // алгоритм сортировкидвоичным включением
for i:=2 to ndo
begin
x:=a[i];
L:=1;
R:=i;
whileL
m:=(L+R)div 2;
ifa[m]
end;
forj:=i downto R+1 do a[j]:=a [j‑1];
a[R]:=x;
end;
 //вывод отсортированного массива
fori:=1 to n do
stringgrid2.Cells [0, i‑1]:=inttostr (a[i]);
end;
procedureTForm1. Button6Click (Sender: TObject);
constt=15;
var
n:integer;
a:array[1..15] of integer;
i,j, k, s:integer;
x:integer;
m:1..t;
h:array[1..t] of integer;
begin
n:=strtoint(edit1. Text);
 //задание массива
fori:=1 to n do
a[i]:=StrToInt(StringGrid1. Cells [0, i‑1]);
 // алгоритм Шелла
h[1]:=9;
h[2]:=5;
h[3]:=3;
h[4]:=1;
form:=1 to t do
begink:=h[m];
s:=-k;
 //барьеры для каждого шага
fori:=k+1 to n do
beginx:=a[i];
j:=i-k;
ifs=0 then s:=-k;
s:=s+1;
a[s]:=x;
whilex
j:=j-k;
end;
a [j+k]:=x;
end;
end;
 //вывод отсортированного массива
fori:=1 to n do
stringgrid2.Cells [0, i‑1]:=inttostr (a[i]);
end;
procedureTForm1. Button7Click (Sender: TObject);
var
n:integer;
a:array[1..15] of integer;
L,R, x, k:integer;
proceduresift (L, R:integer);
var
i,j:integer;
x,y:integer;
begin
i:=L;
j:=2*L;
x:=a[L];
if(j
while(j
a[i]:=a[j];
a[j]:=y;
a[i]:=a[j];
i:=j;
j:=2*j;
if(j
end;
end;
begin
n:=strtoint(edit1. Text);
 // задание искомогомассива
for k:=1 to ndo
a[k]:=StrToInt(StringGrid1. Cells [0, k‑1]);
 // алгоритм сортировки спомощью дерева
 //построение пирамиды
L:=(ndiv 2)+1;
R:=n;
whileL>1 do begin L:=L‑1;
SIFT(L, R);
end;
 //сортировка
whileR>1 do begin x:=a[l];
a[l]:=a[R];
a[R]:=x;
R:=R‑1;
SIFT(1, R);
end;
 // выводотсортированного массива
for k:=1 to ndo
stringgrid2.Cells [0, k‑1]:=inttostr (a[k]);
end;
procedureTForm1. Button8Click (Sender: TObject);
var
n:integer;
a:array[1..15] of integer;
i,j, x:integer;
begin
n:=strtoint(edit1. Text);
 //задание искомого массива
fori:=1 to n do
a[i]:=StrToInt(StringGrid1. Cells [0, i‑1]);
 //алгоритм пузырьковой сортировки
fori:=2 to n do for j:=n downto i do begin
ifa [j‑1]>a[j] then begin x:=a [j‑1];
a [j‑1]:=a[j];
a[j]:=x;
end;
end;
 //вывод отсортированного массива
for i:=1 to ndo
stringgrid2.Cells [0, i‑1]:=inttostr (a[i]);
end;
procedureTForm1. Button9Click (Sender: TObject);
var
n:integer;
a:array[1..15] of integer;
i,j, k, L, R, x: integer;
begin
n:=strtoint(edit1. Text);
 // задание искомогомассива
for i:=1 to ndo
a[i]:=StrToInt(StringGrid1. Cells [0, i‑1]);
 // алгоритм шейкернойсортировки
L:=2;
R:=-n;
k:=n;
repeat
fori:=2 to n do
forj:=-R downto L do begin
ifa [j‑1]>a[j] then begin x:=a [j‑1];
a [j‑1]:=a[j];
a[j]:=x;
k:=j;
end;
end;
L:=k+1;
fori:=2 to n do
forj:=L to R do begin
ifa [j‑1]>a[j] then begin x:=a [j‑1] end else
a [j‑1]:=a[j];
a[j]:=x;
k:=-j;
end;
R:=k‑1;
until L>R;
 //вывод отсортированного массива
fori:=1 to n do
stringgrid2.Cells [0, i‑1]:=inttostr (a[i]);
end;
procedureTForm1. Button10Click (Sender: TObject);
var
n:integer;
a:array[1..15] of integer;
i:integer;
proceduresort (L, R: integer);
var
i,j:integer;
x,y:integer;
begin
i:=L;
j:=R;
x:=a[(L+R)div 2];
repeat
whilea[i]
whilex
ifi
a[i]:=a[j];
a[j]:=y;
i:=i+l;
j:=j-l;
end;
untili>j;
ifL
ifi
end;
begin
n:=strtoint(edit1. Text);
 //задание искомого массива
fori:=1 to n do
a[i]:=StrToInt(StringGrid1. Cells [0, i‑1]);
 // алгоритм быстройсортировки
 //рекурсивная процедура
SORT (1, n);
 //вывод отсортированного массива
for i:=1 to ndo
stringgrid2.Cells [0, i‑1]:=inttostr (a[i]);
end;
procedureTForm1. Button17Click (Sender: TObject);
begin
AboutBox.showmodal;
end;
end.

1.3.3 Пример выполнения
Задание: заданы два одномерныхмассива А и В, содержащие по n элементов каждый.Объединить эти два массива в один, исключив повторяющиеся элементы. Считать,что массивы А и В отсортированы по убыванию.
Теоретическоеописание метода
Методпузырька, как таковой, не требует глубокого рассмотрения. Смысл методазаключается в том, что мы находим в определённой области максимальный (илиминимальный элемент) и помещаем его в начало исследуемой области, далееуменьшаем область поиска на 1 и повторяем те же действия, не имеет худшегослучая, всегда O(n2).
/>
Рисунок 1.15– Форма с результатами расчета
Кодпрограммы на Delphi:
constn=5;
var
a:array[1..n] of Byte;
b:array[1..n] of Byte;
c:array of Byte;
i:byte;
implementation
procedureTForm1. Button1Click (Sender: TObject);
varm, x:byte;
begin
randomize;
fori:=1 to n do begin
a[i]:=random(200);
b[i]:=random(200);
end;
form:=n downto 2 do begin
fori:=1 to m‑1 do begin
ifa[i]
x:=a[i];
a[i]:=a[i+1];
a [i+1]:=x;
end;
ifb[i]
x:=b[i];
b[i]:=b[i+1];
b [i+1]:=x;
end;
end;
end;
fori:=1 to n do begin
StringGrid1.Cells [i – 1,0]:=IntToStr (a[i]);
StringGrid2.Cells [i – 1,0]:=IntToStr (b[i]);
end;
end;
procedureTForm1. Button2Click (Sender: TObject);
labelm1;
vark, l, x:byte;
begin
k:=1;
l:=1;
x:=0;
SetLength(c, 1);
while(k
m1:if a[k]>b[l] then begin
x:=x+1;
SetLength(c, x);
c [x‑1]:=a[k];
k:=k+1;
gotom1;
end;
ifa[k]
x:=x+1;
SetLength(c, x);
c [x‑1]:=b[l];
end;
l:=l+1;
end;
Fori:=0 to high(c) do ListBox1. Items. Add (IntToStr(c[i]));
end;
end.
 
1.3.4 Вариантызаданий
Варианты 1 –27 имеют пояснения к выполнению решений в [7].
1) Длязаданного массива A размером n требуется выполнить проверку наупорядоченность. Результат присвоить переменной строкового типа (сделать вывод,каким именно образом упорядочен массив, если он окажется упорядоченным: повозрастанию, по убыванию, по неубыванию, по невозрастанию). Пояснения в [7],стр. 245.
2) Выполнитьпоиск заданного элемента в упорядоченном массиве. Пояснения в [7], стр. 246.
3) Требуетсяобъединить два упорядоченных по возрастанию массива A и B одногоразмера N (N – заданное натуральное число) в один массив размером2N также упорядоченный по возрастанию. Пояснения в [7], стр. 247.
4) Требуетсяобъединить два упорядоченных по убыванию массива A и B одного размераN (N – заданное натуральное число) в один массив размером 2Nтакже упорядоченный по убыванию. Пояснения в [7], стр. 247.
5) Требуетсяобъединить два массива A и B одного размера N (N –заданное натуральное число) в один массив размером 2N, упорядоченный повозрастанию. [7], стр. 247.
6) Требуетсяобъединить два массива A и B одного размера N (N –заданное натуральное число) в один массив размером 2N, упорядоченный поубыванию. Пояснения в [7], стр. 247.
7) Требуетсяобъединить два упорядоченных массива A и B одного размера N(N – заданное натуральное число) по возрастанию в один массив размером 2N,упорядоченный по неубыванию. [7], стр. 247; [9], стр. 75.
8) Требуетсяобъединить два упорядоченных массива A и B одного размера N(N – заданное натуральное число) по убыванию в один массив размером 2N,упорядоченный по невозрастанию. Пояснения в [7], стр. 247.
9) Требуетсяопределить количество совпадающих элементов двух упорядоченных по убываниюмассивов A и B. Размеры массивов не обязательно одинаковые.Пояснения в [7], стр. 248.
10) Требуетсяопределить количество совпадающих элементов двух неупорядоченных массивов Aи B. Размеры массивов не обязательно одинаковые. Пояснения в [7], стр. 248.
11) Требуетсяопределить количество совпадающих элементов двух упорядоченных по убываниюмассивов A и B. Размеры массивов одинаковые. Пояснения в [7],стр. 248.
12) Требуетсяопределить количество совпадающих элементов двух неупорядоченных массивов Aи B. Размеры массивов одинаковые. Пояснения в [7], стр. 248.
13) Требуетсяопределить количество совпадающих элементов двух упорядоченных по возрастаниюмассивов A и B. Размеры массивов не обязательно одинаковые.Пояснения в [7], стр. 248.
14) Фамилииучастников соревнований по фигурному катанию после короткой программырасположены в порядке, соответствующем занятому месту. Составить списокучастников в порядке их стартовых номеров для произвольной программы (участникивыступают в порядке, обратном занятым местам). Пояснения в [7], стр. 255.
15) Японскаярадиокомпания провела опрос 250 радиослушателей по трём вопросам:
1) Какоеживотное Вы связываете с Японией и японцами?
2) Какаячерта характера присуща японцам больше всего?
3) Какойнеодушевлённый предмет или понятие Вы связываете с Японией?
Большинствоопрошенных прислали ответы на все или на часть вопросов. Составить программуполучения первых пяти наиболее часто встречающихся ответов по каждому вопросу идоли (в%) каждого такого ответа. Предусмотреть необходимость сжатия столбцаответов в случае отсутствия ответов на некоторые вопросы. Пояснения в [7], стр. 264.
16) В памятикомпьютера хранится список фамилий абонентов в алфавитном порядке их номеровтелефонов. Составить программу, обеспечивающую быстрый поиск фамилии абонентапо номеру телефона. Пояснения в [7], стр. 266.
17) В памятиЭВМ хранятся списки номеров телефонов и фамилий абонентов, упорядоченные пономерам телефонов, для каждого из пяти телефонных узлов города. Один телефонныйузел включает несколько АТС (не более 10). Номера АТС (первые две цифры номерателефона), относящихся к каждому телефонному узлу, также хранятся в памяти ЭВМ.Составить программу, обеспечивающую быстрый поиск фамилии абонента по заданномуномеру телефона (количественные данные по телефонной сети не относятся к г. Москва).Пояснения в [7], стр. 266
18) Требуетсяупорядочить заданный одномерный массив A размером N (N –заданное натуральное число) по возрастанию методом пузырька.
19) Требуетсяупорядочить заданный одномерный массив A размером N (N –заданное натуральное число) по убыванию методом пузырька.
20) Требуетсяупорядочить заданный одномерный массив A размером N (N –заданное натуральное число) по возрастанию методом Шелла.
21) Требуетсяупорядочить заданный одномерный массив A размером N (N –заданное натуральное число) по убыванию методом Шелла.
22) Требуетсяупорядочить заданный одномерный массив A размером N (N –заданное натуральное число) по возрастанию методом прямого включения. Поясненияв [9], стр. 78 – стр. 80.
23) Требуетсяупорядочить заданный одномерный массив A размером N (N –заданное натуральное число) по возрастанию методом прямого выбора. Пояснения в[9], стр. 79 – стр. 80.
24) Требуетсяупорядочить заданный одномерный массив A размером N (N –заданное натуральное число) по убыванию методом прямого включения. Пояснения в[9], стр. 78.
25) Требуетсяупорядочить заданный одномерный массив A размером N (N –заданное натуральное число) по убыванию методом прямого выбора. Пояснения в[9], стр. 79 – стр. 80.
26) Требуетсяупорядочить заданный одномерный массив A размером N (N –заданное натуральное число) по убыванию методом сортировки прямым обменом(шейкерная сортировка).
27) Требуетсяупорядочить заданный одномерный массив A размером N (N –заданное натуральное число) по убыванию методом улучшенной сортировкиразделением (быстрая сортировка с рекурсией).
28) Составитьпрограмму сортировки, используя деревья сортировки (улучшенная сортировкавыбором – сортировка с помощью дерева).
29) Составитьпрограмму сортировки в файле (сортировка последовательного файла).
30) Составитьпрограмму сортировки в файле (сортировка последовательного файла слиянием).
31) Данодномерный массив А, состоящий из N элементов (N – заданноенатуральное число). Если элементы массива А составляют строго монотоннуюпоследовательность, то все положительные элементы массива заменить единицей,иначе отсортировать массив по возрастанию.
32) Данодномерный массив А, состоящий из N элементов (N – заданноенатуральное число). Если имеется хотя бы одна пара совпадающих элементов, тоупорядочить элементы этого массива по неубыванию, иначе записать элементы этогомассива в обратном порядке.
33) Заданыдва одномерных целочисленных массива А и В, состоящие из Nэлементов каждый (N – заданное натуральное число). Объединить элементыэтих двух массивов в один и упорядочить их по неубыванию, удалив из негоэлементы, являющиеся четными положительными числами.
34) Данодномерный целочисленный массив А, состоящий из N элементов (N– заданное натуральное число). Присвоить переменной F значение 1, еслиэлементы массива составляют строго возрастающую последовательность, F=-1,если строго убывающую, F=2, если элементы массива составляютзнакочередующуюся последовательность, F=0, если она не является строгомонотонной или знакочередующейся.
35) Данодномерный массив А, состоящий из N элементов (N – заданноенатуральное число). Упорядочить массив А по неубыванию, воспользовавшисьследующим алгоритмом сортировки. Отыскивается максимальный элемент ипереносится в конец. Затем этот алгоритм применяется ко всем элементам кроме последнегои т. д.
36) Даны дваодномерных целочисленных массива А и В, состоящих из Nэлементов каждый (N – заданное натуральное число). Сформировать массив,элементы которого являются пересечением указанных массивов, и расположить егоэлементы по неубыванию. Одинаковые значения заносить только один раз. Еслипресечение массивов есть пустое множество, то выдать соответствующее текстовоесообщение.
37) Даны дваодномерных целочисленных массива А и В, состоящих из Nэлементов каждый, N – заданное натуральное число. Сформировать массив С,элементы которого являются объединением указанных массивов, и расположить егоэлементы по неубыванию. Одинаковые значение заносить только один раз.
38) Данодномерный массив А, состоящий из N элементов (N – заданноенатуральное число). Присвоить переменной F=1, если элементы массива составляютстрогую возрастающую арифметическую прогрессию, и F=-1, если строгоубывающую арифметическую прогрессию.
39) Данодномерный целочисленный массив А, состоящий из N элементов, N– заданное натуральное число. Пусть МАХ – наибольшее, а MIN –наименьшее значения среди элементов массива. Составить одномерный массив Виз простых чисел из сегмента [MIN, МАХ], которые не являются элементамимассива А, записав его элементы в порядке неубывания. Если такихэлементов нет, то выдать соответствующее текстовое сообщение.
40) Каждый из12 магазинов имеет свой список товаров с известными ценами и в известномколичестве. Число товаров в каждом списке различно и заранее не определено.Подсчитать, на какую сумму денег имеет товаров каждый магазин, расположивсписок в порядке убывания этой суммы.
41) Каждая из30 групп студентов имеет свой процент успеваемости (от 0 % до 100 %).Составить список номеров групп, которым необходимо повысить успеваемость досреднего уровня. Список расположить в порядке убывания процента успеваемостиэтих групп.
42) Вмагазине имеются товары различных наименований. В течение дня каждый из Мпокупателей (М – заданное число) сообщил о своем намерении приобрестиопределенное количество товара одного из наименований. Требуется определитьсуммарный спрос на товары каждого наименования, расположив товары в порядкеубывания дневного спроса на них.
43) Опросили200 подписчиков. Каждый из них назвал три любимые газеты. Напечататьпронумерованный список первых 10 наиболее популярных газет, расположив названиягазет в списке в порядке уменьшения числа поданных за них голосов.Предусмотреть, что каждый из опрошенных должен назвать три разные газеты, аобщее число названных газет может быть как больше, так и меньше 10.
44) Каждый изX магазинов в течениемесяца работал Di дней (N и Di – заданные числа, где i=l,2,…, X). Известна прибыль каждого магазина в каждый день его работы.Необходимо напечатать упорядоченный по месячным доходам список названиймагазинов, имеющих прибыль в пересчете на один день работы выше средней дневнойприбыли по всем магазинам.
45) Вгостинице N этажей по M номеров на этаже (N и М заданы, анумерация гостиничных номеров сплошная). Требуется для каждого номера ввестиего стоимость и информацию о том, свободен он, занят или забронирован, а затемполучить ведомости всех свободных, занятых и забронированных номеров в порядкевозрастания их стоимости с указанием стоимости проживания, этажа и номера гостиницы.
46) Витоговой таблице первого круга футбольного чемпионата, каждая из Nкоманд (N и названия команд заданы) представлена количеством забитых ипропущенных голов в каждой из встреч с противниками. Перечислить команды,которые в сумме забили в чужие ворота голов больше, чем пропустили в свои, впорядке убывания разности забитых и пропущенных голов.
47) Порезультатам опроса прошлого года известен список 10 политических деятелей впорядке убывания их популярности. Проведен новый опрос. Каждый из Nжурналистов (N – заданное число) назвал три различные фамилии из этогосписка. Требуется получить новый список в порядке убывания популярностиполитических деятелей и показать место, которое занимал каждый деятель впредыдущем опросе. Предусмотреть проверку: каждый из опрошенных журналистовназывал разные фамилии и только из имеющихся в старом списке.
48) Опросили30 кинологов, каждый из которых 3 раза назвал одну породу собак или разныепороды собак в любом сочетании, как самую популярную (популярные) по егомнению. Вывести на экран список пород, попавших в первую десятку в порядкеубывания популярности, с указанием числа полученных ими голосов опрошенных.
49) Каждая изМ библиотек района (М – задано) составляет заявку на приобретениекниг. Заявка содержит перечень книг, состоящий из не более 20 наименований.Каждая библиотека в каждой строке заявки указывает название книги, фамилиюавтора, а также количество экземпляров. Определить суммарный спрос на каждую изуказанных книг, и напечатать общий список книг в порядке убывания спроса.
50) 200учеников шести школ города (номера школ заданы) принимают участие втестировании по математике. Правильные численные ответы к пяти предложеннымзадачам даны. О каждом ученике известно: фамилия, номер школы и пять ответов назадачи. Сведения об учениках не имеют определенной упорядоченности. Составитьсписки учеников по школам, расположив в каждом списке фамилии в порядкеубывания количества решенных задач. Предусмотреть возможный ответ «не решил».
51) Каждое изМ садоводческих товариществ (М – заданное число) направляет набазу свой список-заявку с указанием наименований требуемых и семян и ихколичества в кг. Число наименований семян в заявке для каждого товарищества непревышает 20‑ти. Составить суммарный запрос на базу, указав общеенеобходимое количество семян каждого вида, расположив наименования в списке впорядке убывания спроса.
52) В массивразмерности N (N – заданное натуральное число) ввести словадлиной не более 15 символов каждое. Вывести на экран эти слова в порядкеувеличения их длины с указанием количества букв «i» в каждом из них.Выполнить проверку вводимой информации.
53) Имеютсясведения о каждом рейсе Аэрофлота с номерами от 1 до 100: пункт назначения иколичество перевезенных пассажиров. Определить количество пунктов назначения ипостроить списки номеров рейсов для каждого из них в порядке уменьшения числапассажиров, перевезенных этими рейсами.
54) Ввести вмассив N произвольных чисел (N – заданное натуральное число).Отсортировать отрицательные числа по убыванию, положительные – по возрастанию,оставив отрицательные на местах, принадлежащих отрицательным, а положительныена местах, принадлежащих положительным. Постараться дополнительных массивов неиспользовать. Вывести на экран исходный и полученный массивы.
55) Ввестипроизвольные числа в два одномерных массива одинакового размера N (N– заданное натуральное число). Переставить элементы первого массива так, чтобыего максимальный элемент находился на месте, расположения максимальногоэлемента из второго массива, а каждый очередной по убыванию элемент из первогомассива располагался на месте, соответствующем расположению очередного поубыванию элемента второго массива. Напечатать модифицированный массив.
56) В массивзаданного размера N (от 3 до 10) ввести произвольные числа. Изменитьпорядок следования элементов в нем на обратный отдельно до и отдельно после К-гоэлемента массива (К задано). Напечатать модифицированный массив. Привводе данных осуществить проверку.
57) В массивзаданного размера N (от 3 до 10) ввести произвольные числа. Не изменяясостояния этого массива и используя лишь один дополнительный массив, напечататьномера элементов исходного массива, соответствующие порядку убывания значенийэлементов. При вводе данных осуществить проверку.
58) В дваодномерных массива одинакового размера N (N – заданноенатуральное число) ввести произвольные числа. Не изменяя исходных массивов,сформировать из элементов первого массива третий массив так, чтобы максимальныйэлемент первого массива в третьем находился на месте, соответствующемрасположению максимального во втором, а каждый очередной по убыванию элемент изпервого массива располагался в третьем на месте, соответствующем расположениюочередного по убыванию элемента второго массива. Напечатать все три массива.
59)Напечатать в возрастающем порядке все четырехзначные натуральные числа, всецифры которых являются соседями в натуральном ряду. Примерами таких чиселявляются 4756 и 7645. Найти количество и среднее арифметическое этих чисел.
60) Ввестичисловую матрицу размером NxM (N, M заданы). Найтимаксимальный элемент среди расположенных в тех строках матрицы, которыеявляются упорядоченными (либо по возрастанию, либо по убыванию), или сообщить,что такого элемента нет.
/> 
1.4 Вопросыдля самопроверки
1) Какимисвойствами обладает отношение частичного порядка? Приведите примеры этогоотношения.
2) Дайтеопределение отношения линейного порядка.
3) Сформулируйтепостановку задачи сортировки.
4) В чёмзаключается преимущество отсортированных (упорядоченных) данных?
5) Какрассматривается задача сортировки с точки зрения программирования?
6) От какихфакторов зависит эффективность алгоритма сортировки?
7) Перечислитенаиболее часто используемые на практике методы поиска и сортировки.
8) Какимобразом могут быть представлены данные при поиске и сортировке?
9) Перечислитеосновные операции при работе с данными.
10) В чёмзаключается алгоритм линейного поиска?
11) В чёмзаключается алгоритм бинарного поиска?
12) Опишитекратко поиск в бинарных деревьях.
13) Какиефункции используются при оценке времени исполнения алгоритма?
14) В чёмзаключается метод сортировки вставками?
15) В чёмзаключается метод сортировки с помощью включения, прямого включения?
16) В чёмзаключается метод Шелла?
17) Опишитесортировку с помощью обменов.
18) Опишитеалгоритм быстрой сортировки, предложенный Ч. Хоаром (QuickSort).
/> 
 

Практическая работа № 2. Представление множеств вкомпьютере
Цель работы:изучение представлений множеств и отношений в программах, алгоритмов сиспользованием множеств; представление множеств характеристическими векторами иих практическая реализация.
/> 
2.1Теоретическая часть
 
2.1.1 Множестваи операции над ними
Множество – этосовокупность объектов, называемых элементами множества. Например:
• {Эссекс,Йоркшир, Девон};
• {2, 3, 5,7, 11}.
В этомпримере элементы каждого множества заключены в фигурные скобки. Чтобыобеспечить возможность ссылок, мы будем обозначать множества прописнымилатинскими буквами. Например,
S = {3, 2, 11, 5, 7} – множество,содержащее целые числа. Заметим, что множество S совпадает с одним измножеств, выписанных выше, поскольку порядок, в котором записываются элементымножества, значения не имеет.
В общемслучае запись а/>Sозначает, что объект а – элемент множества S. Часто говорят, что апринадлежит множеству S. Если объект а не принадлежит S,то пишут: а/> S.
В современныхязыках программирования требуется, чтобы переменные объявлялись какпринадлежащие к определенному типу данных. Тип данных представляет собоймножество объектов со списком стандартных операций над ними. Определение типапеременных равносильно указанию множества, из которого переменным присваиваютсязначения [22].
Существуетнесколько способов конструирования нового множества из двух данных. Опишемкоротко эти операции на множествах. Прежде всего, отметим, что все элементынекоторых множеств принадлежали другим большим множествам. Например, всеэлементы множества С = {0, 1, 4, 9, 16,…} содержатся в множестве
Z = {0, ±1, ±2, ±3,…}.
/>
Рисунок 2.1 –Диаграмма Венна подмножества А />S
 
Объединениемдвух множеств А и В называется множество
А/>В = {х:х /> А или х /> В}.
Оно состоитиз тех элементов, которые принадлежат либо множеству A, либо множеству В,а возможно и обоим сразу. Диаграмма Венна объединения показана на рисунке 2.2.
Пересечениемдвух множеств А и В называется множество
А /> В = {х: х/> А и х />В}.
Оно состоитиз элементов, которые принадлежат как множеству А, так и множеству B.Диаграмма Венна пересечения приведена на рисунке 2.3.
/> />
Рисунок 2.2 –Диаграмма Венна Рисунок 2.3 – Диаграмма Венна для объединения множеств дляпересечения множеств
Дополнениеммножества В до множества А называется
 
A\В = {х: х/> А и x />В}.
Дополнение А\ В состоит из всех элементов множества А, которые не принадлежатВ (см. рисунок 2.4). Если мы оперируем подмножествами некоего большогомножества U, мы называем U универсальным множеством для даннойзадачи. На наших диаграммах Венна прямоугольник как раз и символизирует этоуниверсальное множество. Для подмножества А универсального множества Uможно рассматривать дополнение А до U, т. е. U \ А.Поскольку в каждой конкретной задаче универсальное множество фиксировано,множество U \ А обычно обозначают /> иназывают просто дополнением множества А. Таким образом, понимая, что мыработаем с подмножествами универсального множества U можно записать
/> = {х: не(х/> А)} ó /> = {х: х /> A}.
ДиаграммаВенна дополнения изображена на рисунке 2.5.
/>
Рисунок 2.4 – Диаграмма Венна разности А \ В
/>
Рисунок 2.5 – Диаграмма Венна дополнения />
Симметрическойразностью двух множеств А и В называют множество А Δ В= {х: (х /> А и х/> В) или (х /> В и х /> А)}.
Оно состоитиз всех тех и только тех элементов универсального множества, которые либопринадлежат А и не принадлежат В, либо наоборот, принадлежат В,но не А. Грубо говоря, симметрическая разность состоит из элементов,лежащих либо в А, либо в В, но не одновременно. Диаграмма Венна,иллюстрирующая симметрическую разность, начерчена на рисунке 2.6.

/>
Рисунок 2.6 –Диаграмма Венна симметрической разности А Δ В
 
2.1.2Представление множеств и отношений в программах
В этомпараграфе рассматривается представление множеств в программах. Термин«представление» (еще употребляют термин «реализация») применительно кпрограммированию означает следующее. Задать представление какого-либо объекта(в данном случае множества) – значит, описать в терминах используемой системыпрограммирования структуру данных, используемую для хранения информации опредставляемом объекте, и алгоритмы над выбранными структурами данных, которыереализуют присущие данному объекту операции. Предполагается, что в используемойсистеме программирования доступны такие общеупотребительные структуры данных,как массивы, структуры (или записи) и указатели. Таким образом, применительно кмножествам определение представления подразумевает описание способа храненияинформации о принадлежности элементов множеству и описание алгоритмов длявычисления объединения, пересечения и других введенных операций [5].
Следуетподчеркнуть, что, как правило, один и тот же объект может быть представленмногими разными способами, причем нельзя указать способ, который являетсянаилучшим для всех возможных случаев. В одних случаях выгодно использовать однопредставление, а в других – другое. Выбор представления зависит от целого рядафакторов: особенностей представляемого объекта, состава и относительной частотыиспользования операций в конкретной задаче и т. д. Умение выбратьнаиболее подходящее для данного случая представление является основой искусствапрактического программирования. Хороший программист отличается тем, что онзнает много разных способов представления и умело выбирает наиболее подходящий.
Множестваи задачи информационного поиска
Наиболеепродуктивный подход к разработке эффективного алгоритма для решения любойзадачи – изучить ее сущность. Довольно часто задачу можно сформулировать наязыке теории множеств, относящейся к фундаментальным разделам математики. Вэтом случае алгоритм ее решения можно изложить в терминах основных операций надмножествами. К таким задачам относятся и задачи информационного поиска, в которыхрешаются проблемы, связанные с линейно упорядоченными множествами [1].
Многиезадачи, встречающиеся на практике, сводятся к одной или нескольким подзадачам,которые можно абстрактно сформулировать как последовательность основных команд,выполняемых на некоторой базе данных (универсальном множестве элементов). Например,выполнение последовательности команд, состоящих из операций поиск, вставка,удаление и минимум, составляет существенную часть задач поиска. Об этих идругих подобных командах и пойдет речь ниже [12].
Рассмотримнесколько основных операций над множествами, типичных для задач информационногопоиска.
• Поиск (а;S) определяет, принадлежит ли элемент а множеству S;
если а/>S, результатоперации – ответ «да»; в противном случае –
ответ «нет».
• Вставка (а,S) добавляет элемент а в множество S, то есть заменяет Sна S U {а}.
• Алгоритмправильного обхода(S) печатает элементы множества S с
соблюдениемпорядка.
• Удаление (a,S) удаляет элемент а из множества S, то есть заменяет Sна S \ {а}.
• Объединение(S1, S2, S3) объединяет множества S1 и S2, т. е.строит
множество S3 = S1 U S2.
• Минимум (S)выдает наименьший элемент множества S.
Следующаяоперация – операция минимум(S). Для нахождения наименьшего элемента вдвоичном дереве поиска Т строится путь v0, vi,…, vp, где v0-корень дерева Т, vi– левый сын вершины vi-1 (i= 1,2,…, р),а у вершины vp левый сын отсутствует. Ключ вершины vp, и является наименьшимэлементом в дереве Т. В некоторых задачах полезно иметь указатель навершину vy, чтобы обеспечить доступ к наименьшему элементу запостоянное время.
Алгоритмвыполнения операции минимум(S) использует рекурсивную процедуру левыйсын(v), определяющую левого сына вершины v. Алгоритм и процедуравыглядят следующим образом.
Input
двоичноедерево поиска Т для множества S
begin
ifT = 0 then output «дерево пусто»;
else
вызватьпроцедуру левый сын(r)
(здесь r – кореньдерева Т);
минимум:=1(v), где v – возврат процедуры левый сын;
end
Output ответ«дерево пусто», если Т не содержит вершин;
минимум – наименьшийэлемент дерева Т в противном случае.
Procedureлевый сын (v).
begin
ifv имеет левого сына w then returnлевый сын (w)
else return v
end
Пример 2.1 Проследите работуалгоритма минимум на дереве поиска, изображенном на рисунке 2.7.
Решение.Дерево Т не пусто, следовательно, вызывается процедура левый сын (1).
Вершина 1имеет левого сына – вершину 2, значит, вызывается процедура левый сын (2).
Вершина 2имеет левого сына вершину 4, значит, вызывается процедура левый сын (4).
Вершина 4 неимеет левого сына, поэтому вершина 4 и будет возвратом процедуры левый сын.
Ключомвершины 4 является слово begin, следовательно, наименьшим элементомдерева Т является значение минимум= begin.
/>
Рисунок 2.7 –Дерево поиска минимума S
Реализоватьоперацию удаление (a, S) на основе бинарных поисковых деревьев тожепросто. Допустим, что элемент а, подлежащий удалению, расположен ввершине v. Возможны три случая:
• вершина vявляется листом; в этом случае v просто удаляется
из дерева;
• у вершины vв точности один сын; в этом случае объявляем отца вершины v отцом сынавершины v, удаляя тем самым v из дерева (если v – корень,то его сына делаем новым корнем);
• у вершины vдва сына; в этом случае находим в левом поддереве вершины v наибольшийэлемент b, рекурсивно удаляем из этого поддерева вершину, содержащую b,и присваиваем вершине v ключ b. (Заметим, что среди элементов,меньших а, элемент b будет наибольшим элементом дерева. Крометого, вершина, содержащая b, может быть или листом, являющимся чьим-топравым сыном, или иметь только левое поддерево.)
Ясно, что довыполнения операции удаление (а, S) необходимо проверить, не является лидерево пустым и содержится ли элемент а в множестве S. Для этогопридется выполнить операцию поиск (а, S), причем, и в случаеположительного ответа необходимо выдать кроме ответа «да» и номер вершины, ключкоторой совпадает с a (далее ключ вершины v будем обозначатьчерез l(v)). Кроме этого, для реализации операции удаление (a,S) требуется знать и номер вершины w, являющейся отцом вершины v.Саму же рекурсивную процедуру удаление (а, S) можно реализовать так, какпоказано ниже.
Procedureудаление (а, S)
begin
if v – листthen удалить v из Т
else
(2) if vимеет только левого или только
правого сынаu then
(3) if vимеет отца w then
назначить и сыномw
else
сделать uкорнем дерева,
присвоив емуномер v
else
найти в левомподдереве v наибольший элемент b, содержащийся в вершине у;
(6)return удаление (b, S);
(7)l(v):=b;
end
Пример 2.2 Проследите за работойалгоритма удаление (а, S) для двоичного дерева поиска S,изображенного на рисунке 2.7, если a – это слово «if».
Решение.Слово «if» расположено в корне с номером 1, у которого два сына (вершины2 и 3), поэтому выполняем строку (5) алгоритма. Наибольшее слово, меньшее «if»(лексикографически), расположенное в левом поддереве корня и находящееся ввершине 2, – это end. Вызываем процедуру удаление (end, S).
Условиестроки (2) алгоритма выполняется, так как вершина 2 с ключом end имееттолько левого сына. Условие строки (3) не выполняется, так как удаляемаявершина является корнем. Поэтому переходим к строке (4): делаем вершину 2корнем, сыновьями которого становятся вершины 4 (левым) и 3 (правым). Работапроцедуры удаление (end, S) закончена.
Продолжаемвыполнение алгоритма (выполняем строку (7)): полагаем ключ вершины 1 равным «end»(l (I):=end).
Полученное врезультате дерево изображено на рисунке 2.8.
Заметим, чтопри работе рассмотренных алгоритмов необходимо находить сыновей, отца и ключзаданной вершины двоичного дерева поиска. Это можно сделать довольно просто,если дерево в памяти компьютера хранится в виде трех массивов: LEFTSON,RIGHTSON и KEY. Эти массивы устроены следующим образом:
LEFTSON (i) =
/>v, если v – левый сын вершины i
*, если у вершины i левого сына нет
RIGHTSONM (i) =
/>v, если v – правый сын вершины i
*, если у вершины i правого сына нет
key(i) = l(i)– ключ вершины i.
/>
Рисунок 2.8 –Результат работы алгоритма удаление (а, S) для двоичного дерева поиска S
Например,бинарное поисковое дерево, изображенное на рисунке 2.7, может быть представленов виде таблицы 2.1.
Таблица 2.1 –Представление бинарного поискового дерева в виде таблицы
I LEFTSON RIGHTSON KEY 1 2 3
if 2 4 *
end 3 * 6
then 4 * 5
begin 5 * *
else 6 * *
while
Правилапоиска сыновей и ключа заданной вершины следуют из определения массивов.Определение отца заданной вершины состоит в нахождении строки массивов LEFTSONили RIGHTSON, в которой находится номер заданной вершины. Например,отцом вершины 4 является вершина 2, так как число 4 находится во второй строкемассива LEFTSON.
Объединениемножеств
Обратимсятеперь к объединению множеств, то есть к операции объединение (S1, S2,S3).
Еслимножества S1 и S2 линейно упорядочены, то естественно требоватьтакого порядка и от их объединения. Один из возможных способов объединениясостоит в последовательном выполнении описанной выше операции вставка длядобавления каждого элемента одного множества в другое. При этом, очевидно,операцию вставка предпочтительнее выполнять над элементами меньшего множества сцелью сокращения времени на объединение. Отметим, что такой способ работы подходиткак для непересекающихся, так и для пересекающихся множеств.
Во многихзадачах объединяются непересекающиеся множества. Это упрощает процесс, так какисчезает необходимость каждый раз проверять, содержится ли добавляемый элементв множестве, либо удалять повторяющиеся экземпляры одного и того же элемента изS3.
Процедураобъединения непересекающихся множеств применяется, например, при построенииминимального остовного дерева в данном нагруженном графе.
Рассмотрималгоритм объединения непересекающихся множеств на основе списков. Будемсчитать, что элементы объединяемых множеств пронумерованы натуральными числами1,2,…. n. Кроме того, предположим, что имена множеств – такженатуральные числа. Это не ограничивает общности, поскольку имена множеств можнопросто пронумеровать натуральными числами.
Представимрассматриваемые множества в виде совокупности линейных связанных списков. Такуюструктуру данных можно организовать следующим образом.
Сформируемдва массива R и next размерности n, в которых R(i)– имя множества, содержащего элемент i, a next(i) указывает номерследующего элемента массива R, принадлежащего тому же множеству, что иэлемент i. Если i – последний элемент какого-то множества, то положимnext(i) = 0. Для указателей на первые элементы каждого множествабудем использовать массив list, число элементов которого равно числурассматриваемых в задаче множеств, и элемент которого list(j)содержит номер первого элемента множества с именем j в массиве R.
Кроме того,сформируем массив size, каждый элемент которого size(j) содержит количествоэлементов множества с именем j.
Будемразличать внутренние имена множеств, содержащиеся в массиве к, и внешниеимена, получаемые множествами в результате выполнения операции объединение.Соответствие между внутренними и внешними именами множеств можно установить спомощью массивов Ехт-NAME и INT-NAME. Элемент массива EXT-NAME(j)содержит внешнее имя множества, внутреннее имя которого есть j, аINT-NAME(k) – внутреннее имя множества, внешнее имя которого есть к.
Пример 2.3 Используя только чтоопределенные массивы, опишите множества {1,3,5,7}, {2,4.8}, {6} с внешнимиименами 1, 2, 3 и внутренними именами 2, 3, 1 соответственно.
Решение.Прежде всего, отметим, что общее количество элементов всех множеств равновосьми. Поэтому размерность массивов R и next будет n = 8.Кроме того, напомним, что номера элементов массивов list, SIZE, Ехт-NAMEи значения элементов массива R – это внутренние имена множеств, амассива INT-NAME внешние.
Алгоритмвыполнения операции объединение (S1, S2, S3) состоит в добавлении к спискуэлементов большего из множеств S1 и S2 элементов меньшего множества иприсвоение полученному множеству внешнего имени S3. При этом вычисляется такжеразмер построенного множества S3.
Объединение (i,j, к)
Input
i, j – внешниеимена объединяемых множеств
(пусть размерi меньше размера j);
массивы R, NEXT,LIST, SIZE, ЕХТ-NAME,INT-NAME;
begin
A:=INT-NAME(i);
B:=INT-NAME(j);
element:=LIST(A);
whileelement 0 do
begin
R(element):=B;
last:=element;
element:=NEXT(element)
end
NEXT(last):=LIST(B);
LIST(B):=LIST(A);
SIZE(B):=SIZE(B)+ SIZE(A);
INT-NAME(K):=B;
EXT-NAME(B):=k
End
Объединениемножеств i, j с внешним именем k.
В процессеработы алгоритм совершает следующие действия:
1) определяетвнутренние имена множеств i и j;
2) определяетначало списка элементов меньшего множества;
3) просматриваетсписок элементов меньшего множества и изменяет соответствующие элементы массиваR на внутреннее имя большего множества;
4) объединяетмножества путем подстановки меньшего множества перед большим;
5) присваиваетновому множеству внешнее имя k.
Заметим, чтовремя выполнения операции объединения двух множеств с помощью рассмотренногоалгоритма пропорционально мощности меньшего множества.
2.1.3 Алгоритмыгенерации множеств
Реализацияопераций над подмножествами заданного универсума U
Пустьуниверсум U – конечный, и число элементов в нем не превосходитразрядности ЭВМ: мощность |U| n. Элементы универсуманумеруются: U = {u1,…, un}.Подмножество А универсума U представляется кодом (машинным словомили битовой шкалой) С, в котором:
/>
где С(i)– это i‑й разряд кода С.
Кодпересечения множеств А и В есть поразрядное логическоепроизведение кода множества А и кода множества В. Код объединениямножеств А и В есть поразрядная логическая сумма кода множества Аи кода множества В. Код дополнения множества А есть инверсия кодамножества А. В большинстве ЭВМ для этих операций есть соответствующиемашинные команды. Таким образом, операции над небольшими множествами выполняютсявесьма эффективно.
Если мощностьуниверсума превосходит размер машинного слова, но не очень велика, то дляпредставления множеств используются массивы битовых шкал. В этом случаеоперации над множествами реализуются с помощью циклов по элементам массива [23].
Генерациявсех подмножеств универсума
Во многихпереборных алгоритмах требуется последовательно рассмотреть все подмножествазаданного множества. В большинстве компьютеров целые числа представляютсякодами в двоичной системе счисления, причем число 2k – 1 представляется кодом,содержащим k единиц. Таким образом, число 0 является представлением пустогомножества 0, число 1 является представлением подмножества, состоящего изпервого элемента, и т. д. Следующий тривиальный алгоритм перечисляетвсе подмножества n‑элементного множества (представлен впаскале-подобном коде, описание в [23]).
Алгоритм 1.1:Алгоритм генерации всех подмножеств n‑элементного множества
Вход: n/>0 – мощностьмножества
Выход:последовательность кодов подмножеств i
fori from 0 to 2n – 1 do
yield i
end for
Обоснование: Алгоритмвыдает 2n различных целых чисел, следовательно, 2n различныхкодов.
С увеличениемчисла n увеличивается количество двоичных разрядов, необходимых для егопредставления. Самое большое (из генерируемых) число 2n‑1 требуетдля своего представления ровно n разрядов. Таким образом, всеподмножества генерируются, причем ровно по одному разу.
Во многихпереборных задачах требуется рассмотреть все подмножества некоторого множестваи найти среди них то, которое удовлетворяет заданному условию. При этомпроверка условия часто может быть весьма трудоемкой и зависеть от составаэлементов очередного рассматриваемого подмножества. В частности, если очередноерассматриваемое подмножество незначительно отличается по набору элементов отпредыдущего, то иногда можно воспользоваться результатами оценки элементов,которые рассматривались на предыдущем шаге перебора. В таком случае, еслиперебирать множества в определенном порядке, можно значительно ускорить работупереборного алгоритма. [5]
Алгоритмпостроения бинарного кода Грея
Данныйалгоритм генерирует последовательность всех подмножеств n‑элементногомножества, причем каждое следующее подмножество получается из предыдущегоудалением или добавлением одного элемента.
Алгоритм 1.2:Алгоритм построения бинарного кода Грея Вход: n/>0 – мощность множества
Выход:последовательность кодов подмножеств В
В: array[l..n] of 0..1 {битовая шкала для представления подмножеств}
fori from 1 to n do
B[i]: = 0 {инициализация}end for
yield В {пустоемножество}
fori from I to 2n – 1 do
p: = Q(i) {определениеэлемента, подлежащего добавлению или удалению}
B[р]: = 1 – В[р]{добавление или удаление элемента}
yield В {очередноеподмножество} end for
proc Q(i) {количество2 в разложении i на множители + 1} q: = l; j: = i while j четно do
j:=j/2;q: = q + l end while return q end proc
Обоснование
Для n= 1 искомая последовательность кодов суть 0,1. Пусть есть искомаяпоследовательность кодов В1,…, /> дляn = к. Тогда последовательность кодов B10,…, /> 0, />1, …. B11будет искомой последовательностью для n = к + 1. Действительно, впоследовательности B10,…, />0,/>1,…, В11имеется 2k+1 кодов, они все различны и соседние различаются ровно водном разряде по строению. Именно такое построение и осуществляет данный алгоритм.На нулевом шаге алгоритм выдает правильное подмножество В (пустое).Пусть за первые 2k – 1 шагов алгоритм выдал последовательность значений В.При этом В [k + 1] = В [k + 2] = • • • = В[n] = 0. На 2k‑ом шаге разряд В[k + 1] изменяет свое значение с 0 на 1. После этого будет повторенапоследовательность изменений значений В [1.k] в обратном порядке, посколькуQ (2k + m) = Q (2k – m) для />
Пример 2.4
 
Таблица 2.5 –Протокол выполнения алгоритма 1.2 для п = 3i Р В 1 1 1 2 2 1 1 3 1 1 4 3 1 1 5 1 1 1 1 6 2 1 1 7 1 1
 
Представлениемножеств упорядоченными списками
Если универсумочень велик (или бесконечен), а рассматриваемые подмножества универсума неочень велики, то представление с помощью битовых шкал не является эффективным сточки зрения экономии памяти. В этом случае множества обычно представляютсясписками элементов. Элемент списка при этом представляется записью с двумяполями: информационным и указателем на следующий элемент. Весь список представляетсяуказателем на первый элемент.
elem = record
i: info; {информационноеполе}
n: elem {указательна следующий элемент} end record
При такомпредставлении трудоемкость операции /> составитO(n), а трудоемкость операций />составитО(nm), где n и m – мощности участвующих в операциимножеств.
Если элементыв списках упорядочить, например, по возрастанию значения поля i, тотрудоемкость всех операций составит О(n). Эффективная реализацияопераций над множествами, представленными в виде упорядоченных списков,основана на весьма общем алгоритме, известном как алгоритм типа слияния.
1
1       1
1       2       1
13     3       1
14     6 4    1
Рисунок 2.9 –Иллюстрация к алгоритму слияния
В этомравнобедренном треугольнике каждое число (кроме единиц на боковых сторонах)является суммой двух чисел, стоящих над ним. Число сочетаний С (m, n) находится в (m +1) – м ряду на (n + 1) – м месте.
Генерацияподмножеств
Элементымножества {1,…, m} упорядочены. Поэтому каждое n‑элементноеподмножество также можно рассматривать как упорядоченную последовательность. Намножестве таких последовательностей естественным образом определяетсялексикографический порядок. Следующий простой алгоритм генерирует все n‑элементныеподмножества m‑элементного множества в лексикографическом порядке.
Алгоритм 1.3.Генерация n‑элементных подмножеств m‑элементногомножества
Вход: n – мощность подмножества, m – мощность множества, m/>n > 0.
Выход:последовательность всех n‑элементных подмножеств m‑элементногомножества в лексикографическом порядке.
fori from 1 to m do
A[i]: = i {инициализацияисходного множества} end for
ifm = n then
yieldA [1..n] {единственное подмножество} exit end if
p: = n {p – номерпервого изменяемого элемента} while p /> 1 do
yield A [1..n]{очередное подмножество в первых n элементах массива А} if А[i] = m then
р: = р – 1 {нельзяувеличить последний элемент} else
р:=n {можно увеличитьпоследний элемент} end if if p/>1 then
fori from n downto p do
А[i]: = А[р]+i‑р+1 {увеличение элементов} end for endif end while
Заметим, чтов искомой последовательности n‑элементиых подмножеств (каждое изкоторых является возрастающей последовательностью n чисел из диапазонаl..m) вслед за последовательностью (ai,…, an)следует последовательность
(b1,…,bn) = (а1…, ap-1,ар + 1, ар+ 2,…, ар+ n-р +1), где р – максимальный индекс, для которого bn= ар+ n — р + 1/>m. Другимисловами, следующая последовательность получается из предыдущей заменой некоторогоколичества элементов в хвосте последовательности на идущие подряд целые числа,но так, чтобы последний элемент не превосходил n, а первый изменяемыйэлемент был на 1 больше, чем соответствующий элемент в предыдущейпоследовательности. Таким образом, индекс р, начиная с которого следуетизменить «хвост последовательности», определяется по значению элемента А[n].Если А[n] m, то следует изменять только А[n],и при этом р: = n. Если же уже А(n) = m, тонужно уменьшать индекс р: =р – 1, увеличивая длину изменяемогохвоста.
/> 
2.1.4Представление множеств в приложениях на Delphi
Тип множествозадает неупорядоченную совокупность неповторяющихся объектов. Переменная типамножество – это совокупность объектов из исходного заданного множества – можетиметь значение «пусто» (пустое множество). Число элементов исходного множестваограничено – оно не может быть более 256. Для задания элементов множества можетиспользоваться любой порядковый тип, однако порядковые номера элементовмножества, т. е. значения функции ord, должны находиться в пределахот 0 до 255. Для задания типа множества используется следующее объявление [22]:
Type = set of ;
При заданиитипа элементов необходимо соблюдать ограничения, указанные выше.
TypeA = set of Char; A1 = set of ‘A’.’Z’;
Oper= set of (Plus, Minus, Mult, Divide);
Number= set of Byte; D = set of 1..20;
Дляпеременных типа множество можно задавать типизированные константы. При этомзначения задаются в виде конструктора множества.
Const K:D =[5,9,11,17]; R:D = [1… 9,13,20];
Для заданиязначений переменным типа множество также можно использовать конструкторы. Пустьобъявлено
Var AA:A;,тогда возможна запись (тип A объявлен выше)
AA:=[Char(13),Char(7), ‘0’, ‘Q’];
Еслитребуется присвоить этой переменной значение «пусто», то используется такойконструктор: AA:= [];
Операциинад множествами
Как и длядругих типов, имеется ряд встроенных операций для типа множество. Пусть заданыследующие типы и переменные: Type Mn = set of 1..50; Var A, B, C: Mn;
Пустьпеременным присвоены значения:
A:= [3,5,9,10];B:= [1,7,9,10];
Объединениемножеств
C:=A+B;              {1,3,5,7,9,10}
Разность (A-B B-A)
C:=A-B;              {3,5}
C:=B-A;                        {1,7}
Пересечение(умножение)
C:=A*B;              {9,10}
Проверкаэквивалентности, например в операторе IF
(A = B)                {False}
Проверканеэквивалентности
(A B)              {True}
Проверка,является ли одно множество подмножеством другого
(A>=B)               {False}
(A
Проверка,входит ли заданный элемент в заданное множество
(3 in A)                {True}
(3 in B)                {False}
Стандартныеподпрограммы для выполнения некоторых действий над множествами
Exclude (A, 3);удалить из множества A элемент 3}
Include (A, 3);{вставить элемент 3 в множество A}.
 
2.1.5Характеристический вектор множества
Характеристическимвектором Vx множества X, заданного на универсальном множестве I, является вектор,содержащий 0 и 1. Количество элементов в векторе Vx равно количествуэлементов в универсальном множестве, причём, 1 записывается в случае, еслиэлемент присутствует и в универсальном множестве I, и в множестве X,в противном случае записывается 0. Некоторые задачи с множествами, особенно накомпьютере, удобно решать, используя характеристические векторы [1].
Действия надвекторами похожи на логические операции.
Надхарактеристическими векторами выполняются поразрядно логические операции:
припересечении – логическое умножение;
приобъединении – логическое сложение;
принахождении дополнения – значения в исходном векторе изменяются на противоположные.
При объединениимножеств /> элементы характеристическоговектора считают по правилу:
/>
2) Припересечении множеств /> элементыхарактеристического вектора считают по правилу:
/>
3) Принахождении дополнения /> нули меняют наединицы, единицы – на нули;
4) Принахождении симметричной разности />,используют формулу:
/>
Пример 2.5 Пусть I = {1, 2,3, 4, 5, 6}, А={1, 2, 4, 5} и В={3, 5} Характеристическим вектором множества Аявляется вектор а = (1, 1, 0, 1, 1, 0). Характеристический вектор множества Вравен b = (0, 0, 1, 0, 1, 0).
Вычислимхарактеристический вектор множества A U />.Он равен
а или (не b) = (1,1, 0, 1, 1, 0) или (1, 1, 0 1, 0, 1) = (1,1,0,1,1,1).
Следовательно,A U />= {1, 2, 4, 5, 6}.
Характеристическийвектор множества А Δ В равен
(а и(не b)) или (b и (не а)) = ((1, 1, 0, 1, 1, 0) и (1, 1, 0,1, 0, 1)) или
или ((0, 0,1, 0, 1, 0) и (0, 0, 1, 0, 0, 1)) = (1, 1, 0, 1, 0, 0) или (0, 0, 1, 0, 0, 0) =(1, 1, 1, 1, 0, 0).
Такимобразом, А Δ В = {1, 2, 3, 4}.
/> 
2.2Практическая часть
 
2.2.1 Заданиек работе
1. Изучитьтеоретический материал, включая и дополнительные сведения, представленные в теоретическойчасти.
2. Задатьсамостоятельно универсальное множество X, множества A, B, C (илинекоторые из них, т. к. в некоторых вариантах используются только двамножества).
3. Cформироватьхарактеристические векторы для исходных множеств и получить результирующеемножество (по варианту), используя характеристические вектора.
4. Вычислитьэлементы результирующего множества (по варианту), используя операции надмножествами.
5. Вывестирезультаты, полученные в пункте 3 и пункте 4.
6. Сравнитьэти результаты и сделать выводы.
7. Пункты 3 и4 выполнить двумя способами: аналитически и реализовать в виде приложения наDelphi.
Примечание:
1. Если ввыражении используется операция разности или симметрической разности, то привыполнении действий с характеристическими векторами (пункт 3) заменить ихдругими операциями на множествах (использовать формулы из лекций и [23]).
2. Привыполнении пункта 4 операцию симметрической разности заменить другимиоперациями, которые используются в Object Pascal.
3. В качестведополнительного задания предлагается реализовать любой описанный втеоретической части алгоритм в виде приложения на Delphi.
 
2.2.2Примеры выполнения
Пример 1.
1) Задание поварианту
I:={1,2,3,4,5,6,7}
Значениявекторов A, B, C берутся произвольно, но с учетом, что количествоэлементов не должно быть больше 7.
Найти:характеристический вектор множеств A, B и C, характеристическийвектор множества D – Vd, перейти от Vd к D.
2) Создатьприложение в среде Delphi, которое решит данную задачу.
3) Решитьзадачу аналитически.
4) К защитеданной работы необходимо знать теоретический материал по данной теме из лекцийи методички, а также ответить на «Вопросы для самопроверки».
D=/>
Аналитическоерешение:
/>
/>
/>
/>
/>
Характеристическиевекторы
 
A:={1,0,1,0,1,0,1}
B:={1,1,1,1,0,0,0}
C:={1,0,1,1,1,0,1}
/>
Переходим от /> к D
D:= />={1,3}
Форма
/>
Рисунок 2.10– Формы с результатами
Код программы
implementation
procedureTForm1. Button1Click (Sender: TObject);
var
n,A, B, C: set of char;
s,s1, s2, s3, s11, s22, s33, s4, s44, s5, s55:string;
i:integer;
begin
s:='1234567';
n:=['1'..'7'];
A:=['1','3', '5', '7'];
B:=['1','2', '3', '4'];
C:=['1','3', '4', '5', '7'];
begin
fori:=1 to 7 do
begin
if(s[i] in A) then
s1:=s1+'1'
else
s1:=s1+'0';
end;
s11:='{'+s1+'}';
label7.Caption:=s11;
end;
begin
fori:=1 to 7 do
begin
if(s[i] in B) then
s2:=s2+'1'
else
s2:=s2+'0';
end;
s22:='{'+s2+'}';
label12.Caption:=s22;
end;
begin
fori:=1 to 7 do
begin
if(s[i] in C) then
s3:=s3+'1'
else
s3:=s3+'0';
end;
s33:='{'+s3+'}';
label13.Caption:=s33;
{Задаемхарактеристические векторы}
end;
begin
fori:=1 to 7 do
if((s1[i])=(s2 [i])) and ((s3 [i])=(s2 [i])) and ((s3 [i])='1') then
s4:=s4+'1'else
s4:=s4+'0';
s44:='{'+s4+'}';
label17.Caption:=s44;
{НаходимХарактеристический вектор
множества Vd}
end;
begin
fori:=1 to 7 do
ifs4 [i]='1' then
s5:=s5+inttostr(i);
s55:='{'+s5+'}';
label21.Caption:=s55;
{Переходим отVd к D}
end;
end;
procedureTForm1. Button2Click
(Sender:TObject);
begin
close;
end;
end.
2.2.3 Вариантызаданий
1) />
2) />
3) />
4) />
5) />
6) />
7) />
8) />
9) />
10) />
11) />
12) />
13) />
14) />
15) />
16) />
17) />
18) />
19) />
20) />
21) />
22) />
23) />
24) />
25) />
26) />
27) />
28) />
29) />
30) />
31) />
32) />
33) />
34) />
35) />
36) />
37) />
38) />
39) />
40) />
41) />
42) />
43) />
44) />
45) />
46) />
47) />
47) />
49) />
50) />
/> 
2.3 Вопросыдля самопроверки
1) Какиеосновные символы, используемые в теории множеств, вы знаете?
2) Перечислитеосновные операции над множествами и функции, применимые к множествам, которыеиспользуются в Delphi.
3) Что такоемножество? Как его обозначить? Как можно задать множество?
4) Какоемножество называют счетным? Какое – пустым?
5) Что такоеподмножество?
6)Сформулируйте основные свойства счетных множеств.
7) Определитепонятие вектора, булеана.
8)Сформулируйте основные аксиомы теории множеств.
9) Какиесоотношения (действия) между множествами вы знаете, как они обозначаются?
10) Какое множествоможно назвать универсальным?
11) Какиеоперации (из аналогичных арифметическим) нельзя производить с множествами?
12) Что такоедиаграмма Эйлера-Венна? Проиллюстрируйте с помощью диаграмм Эйлера-Веннаобъединение и пересечение трех множеств.
13) Дайтеопределение декартова произведения множеств; какие теоремы о декартовомпроизведении Вы знаете?
14) Пояснитетермин «мощность множества».
15)Сформулируйте (и докажите) основные тождества алгебры множеств.
16) Дайтеопределение проекции вектора.
17) Чтопонимается под соответствием между множествами?
18) Дайтеопределение функции с точки зрения теории множеств. Приведите пример.
19) Дайтеопределение бинарного отношения, перечислите свойства.
20) Какиеотношения называют рефлексивными, транзитивными?
21) Что такое«класс эквивалентности»?
22) Для чегонужна диаграмма Хассе?
23) Дайтеопределение нечёткого множества.
24) Какиеоперации допустимы над нечёткими множествами?
25) Дайтеопределение расстояний Хемминга и его основных свойств.
26)Перечислите основные алгоритмы генерации множеств.

/>/>Практическая работа № 3. Элементытеории графов
Цель работы:изучение математических структур для представления графов, изучение наиболееизвестных алгоритмов на графах и построение приложений на Delphi для описанияграфов в виде математических структур, реализации некоторых алгоритмов награфах.
/> 
3.1 Теоретическаячасть
В данномпараграфе многие определения и рисунки взяты из [17] и [19], являютсядополнительными сведениями для материала, рассматриваемого в [24].
Пусть V– конечное множество (множество вершин), А – множество упорядоченных парвершин, элементы которого называются ребрами.
Тогда графом G(V, A) называется совокупность множества вершин и множества ребер.Вершины а и с соединяются ребром, если (а, с)ÌА.
Пусть даномножество вершин V и декартово произведение VхV –множество всевозможных пар вершин. Тогда графом G является подмножестводекартового произведения.
Ребро графа Gориентировано, если порядок пары (a, b) существенен.
Ребро графа Gне ориентировано, если порядок пары (a, b) несущественен.
/>
Рисунок 3.1 –Ориентированный граф
Графназывается ориентированным, если все его ребра ориентированы.
Граф Gназывается неориентированным, если все его ребра неориентированы.
Смешаннымграфом называется граф, у которого есть как ориентированные, так инеориентированные ребра.
Каждому ребруE=ía, bý можно поставить в соответствие некотороечисло.
Граф G,каждому ребру которого присвоено число (например, расстояние) называется сетью.
Пусть даны a,b – вершины графа. Ребро E их соединяет. Тогда говорят, что ребро Eинцидентно вершинам a и b. И обратно – вершины a и bинцидентны ребру E.
Приизображении графа имеется большая свобода в размещении вершин и дуг.
/>
Рисунок 3.2 –Три изображения одного и того же графа
 
Пусть Gи G1 графы, V и V1 – множества их вершин соответственно.Графы G и G1 изоморфны, если существует взаимнооднозначное соответствиемежду множествами их вершин V и V1 и вершины в графе Gсоединены ребром в том и только том случае, если соответствующие вершины соединеныребром в графе G1.
Если графы Gи G1 ориентированы, то направления ребер должны соответствовать другдругу. Изоморфные графы имеют одинаковые свойства.
Вершина, неинцидентная никакому ребру, называется изолированной. Граф, состоящий изизолированных вершин, называется нуль граф. Обозначается через О.
Граф, любые двевершины которого соединены ребром, называется полным графом U=U(V).
Петлейназывается ребро L=(a, a). Петля считается неориентированнымребром.
/> 
Рисунок 3.3 –Петля
Пара вершинможет соединяться несколькими различными ребрами.
Пара ребер EiEj, ориентированная в противоположном направлении, эквивалентна одномунеориентированному ребру.
Такимобразом, мы можем любой неориентированный граф превратить в ориентированный.При этом количество ребер увеличивается в 2 раза.
Графназывается плоским, если может быть изображен на плоскости так, чтобы его ребрапересекались только в вершинах.
Граф назовемоднородным степени k, если локальные степени во всех его вершинах равны k,т. е. />
/>
Рисунок 3.4 – Бесконечный однородный граф
/>
Рисунок 3.5 – Конечный однородный граф
Граф Hназывается частью графа G, если подмножество вершин его V(H)содержится во множестве вершин V(G) и все ребра части графа Hявляются ребрами G и обозначается HÌG.
Для любойчасти H графа G существует дополнение />, которое состоит из всех реберграфа G, не принадлежащих H.

/>
V2   />
V3  
Рисунок 3.6 –Граф G                    Рисунок3.7 – Часть графа G
Пусть H1и H2 – две части графа G. Сумма этих частей H1UH2есть часть, состоящая из ребер, принадлежащих H1 или H2. ПересечениеD=H1/>H2 – есть часть, состоящаяиз ребер, принадлежащих H1 и H2 одновременно. Две части непересекаются по вершинам, если они не имеют общих вершин, и, следовательно,ребер. Части H1 и H2 не пересекаются по ребрам, если они не имеютобщих ребер H1/>H2=0. Если H1 и H2непересекающиеся части графа G, то их сумма называется прямой и H1UH2=G.
Бинарныеотношения и графы
Бинарныеотношения можно изобразить графом: вершины графа – элементы множества V,ребра графа соединяют вершины, которые находятся в отношении друг к другу.
Любой графопределяет бинарное отношение R на множестве вершин V, если длякаждого ребра (a, b) выполняется aRb. Нельзя говорить овзаимнооднозначном соответствии между графами и бинарными отношениями. Пустомубинарному отношению соответствует нуль-граф О. Универсальному бинарномуотношению отвечает полный граф U. Бинарному отношению aRb,где R – отрицание R (дополнительное бинарное отношение) отвечаетграф G(R)=U(V) – G(R). Обратномубинарному отношению bR*a отвечает обратный граф G (R*),т. е. граф с измененной ориентацией ребер. Операции, которые вводятся длябинарных отношений, могут быть перенесены на графы.
Симметричноебинарное отношение: если aRb, то bRa.
Рефлексивность:бинарное отношение aRa соответствует графу с петлей в каждой вершине.
Транзитивность:если aRb и bRc, то aRc. Для графа это означает, что еслисуществует ребро (a, b) и ребро (b, c), то существует ребро (a,c). Такой граф называется связным.
Свойствосвязности можно рассмотреть как бинарное отношение, которое:
а)рефлексивно: вершина а связана сама с собой;
б)симметрично: если вершина а связана с вершиной b, то и вершина bсвязана с вершиной a;
в)транзитивно: если вершина a связана с вершиной b, и bсвязана с вершиной с, то вершина a связана с вершиной c.
Отношениесвязности есть отношение эквивалентности, т. е. оно разбивает множествовершин на попарно непересекающиеся классы.
Так каккаждое множество Vi – множество связанных вершин, а вершины из разныхмножеств Vi не связаны, то имеем разложение графа G на части,которые не пересекаются и каждая часть – связная.
Подграфы G(Vi)называются связными компонентами графа G.
Каждыйнеориентированный граф распадается единственным образом в прямую сумму всехсвоих связных компонент.
Покрывающиедеревья
Граф, несодержащий циклов, называется ациклическим. Деревом называется связный граф, несодержащий циклов. Пусть VG – число элементов в множестве вершин, VL– число элементов множества ребер дерева.
/> 
Рисунок 3.8 –Дерево
 
VG =VL‑1
Добавим ребро– появляется цикл, удалим ребро – теряется связность. Лесом называетсянесвязный граф, компонентами которого являются деревья.
Пусть VLl – число элементов вмножестве ребер леса, VGl – число элементов вмножестве вершин леса, k – число деревьев в лесе.
VLl = VGl — k
Если дерево Тимеет корень, то дерево называется деревом с корнем. Выделим в дереве Тнекоторую цепь.
/>
Рисунок 3.9 –Дерево
Задача.
Как узнать,существуют ли циклы в графе?
Для деревасвязь между числом ребер и числом вершин такова
Vl=VG‑1. Рассмотримs=Vl-VG+1, s называется цикломатическим числом. Если граф G –дерево, то s=0, если s не равно нулю, то в графе G есть циклы.
Алгоритмпостроения произвольного покрывающего дерева [20]
Ограничения:в графе не должно быть петель. Букетом называется произвольное дерево в графе.
Шаг 1.Выбираем произвольное ребро и помечаем его х (красим в голубой цвет).
Шаг 2.Выбираем другое произвольное непомеченное ребро. Если оба конца ребра лежат водном букете, красим ребро в красный цвет. В противном случае – в голубой.
Шаг 3. Есливсе вершины графа вошли в один букет, то процедура заканчивается, т. к.помеченные голубым ребра образуют покрывающее дерево. В противном случае – перейтик шагу 2.
/>
Рисунок 3.10 –Граф
1 шаг: (a,d) – помечаем голубым
2 шаг: (b,e) – помечаем голубым
3 шаг: (d,e) – помечаем голубым
4 шаг: (a,b) – помечаем красным
5 шаг: (a,c) – получаем голубым
/> 
Рисунок 3.11 –Дерево
 
Алгоритмпостроения минимального и максимального покрывающего дерева [21]
Пусть каждомуребру графа G присвоена длина (вес) l (x, y) (таблица 3.1).Весом дерева называется сумма весов ребер, входящих в дерево. Минимальнымдеревом называется дерево с минимальным весом.
Алгоритмформируется так же, как и алгоритм построения произвольного покрывающегодерева. Но ребра просматриваются в порядке возрастания их веса.

Таблица 3.1 –Веса ребер графа
 
A
b
c
d
e
a 5 50 85 90
b 5 70 60 50
c 50 70 8 20
d 85 60 8 10
e 90 50 20 10
Порядокпросмотра
(a, b) –5    (b, e) – 50            упорядочим ребра по возрастанию
(c,d) – 8     (b, d) – 60
(d,e) – 10   (b, c) – 70
(c,e) – 20   (a, d) – 85
(a, c) –50   (a, b) – 90
1 шаг: (a,b) – помечаем голубым
2 шаг: (c,d) – помечаем голубым
3 шаг: (d,e) – помечаем голубым
4 шаг: (c,e) – помечаем красным
5 шаг: (a,c) – помечаем голубым
Деревопостроено!
/> 
Рисунок 3.12 –Дерево
 
Алгоритмпостроения максимального ориентированного дерева(алгоритм Эдмонса) [15]:
Шаг 1.Последовательно в произвольном порядке просматриваем вершины графа G0.Просмотр вершины заключается в том, чтобы из дуг, заходящих в эту вершину,выбрать дугу с максимальным весом. При просмотре следующих вершин к ужеотобранным ранее дугам добавляются новые дуги. Если добавление ребра ненарушает свойства букета, то добавление ребер продолжается. Если новое реброобразует контур, перейти к шагу 2.
Шаг 2. Вслучае формирования контура строится уменьшенный граф путем стягивания дуг ивершин выявленного контура исходного графа Go в одну вершину V.
В новом графевеса ребер (xi, vi) полагаются равными
 
l(x, vi)=l (x, y)+l (r, s) –l (t, y),
где К– контур, а у – вершина, принадлежащая контуру.
l (x, vi) – ребро,переходящее в ребро l (x, vi)
l (r, s) – ребро,имеющее в контуре минимальный вес
l (t, y) – ребро,заходящее в вершину у и имеющее максимальный вес
Шаг 3.Выполняется тогда, когда вершины нового графа попадают в букет, а дуги образуютдерево.
Возможны 2случая:
вершина Voявляется корнем дерева, тогда необходимо рассмотреть ребра букета в новом графесовместно с ребрами контура. Удалить из рассматриваемого множества ребер реброс минимальным весом;
если Voне является корнем дерева – в букете нового графа имеется лишь одно ребро,заходящее в некоторую вершину Z и одно ребро контура, заходящее в ту жевершину. Удаляем ребро контура, заходящее в вершину Z.
Пример.

/>
Рисунок 3.13 –Граф
 
Просмотрвершин:      Букет получаемых ребер
a                                    (da)
b                                    (da)(cb)
c                                    (da)(cb) (ac)
d                                   (da)(cb) (ac) (bd)
Ребра (ac) (cb)(bd) (da) образуют контур. Минимальный вес ребра вконтуре 2.
Стягиваемконтур в одну вершину и рассматриваем граф:
/>
Рисунок 3.14 –Граф
 
l(fe)=1
l(e, Vo)=l(ea)+2–3=3+2–3=2
l(f, Vo)=l (f, a)+2–3=-1
l(f, Vo) 1=l(fd)+2‑l (b, d)=1+2–2=1
Просмотрвершин       Букет ребер
e                                    (fe)
f                                     (fe)
Vo                        (fe)(eVo)
Получили множестворебер исходного графа Go такое:
(fe) (ea)– образуют букет
(ac) (cb)(bd) (da) – образуют контур
Vo не является контуромдерева, удаляем (da), поскольку (da) – ребро из контура. Получилидерево:
(fe) (ea)(ac) (cb) (bd) с весом l=1+2+3+2+2=10
Задача ократчайших путях
Пусть G– ориентированный граф, Е – ребра графа. Каждому ребру соответствуетчисло.
/>
Рисунок 3.15– Эйлеров цикл
 
ЗадачаЭйлера о Кенигсбергских мостах [19]: необходимо выйти из любой точки города ивернуться в нее, при этом пройдя по каждому мосту только один раз. Эйлер свелэту задачу к графу: существует ли в конечном графе такой цикл, в котором каждоеребро участвует только один раз? Цикл, в котором каждое ребро графа Gучаствует всего один раз, называется эйлеровым циклом. Граф, содержащий эйлеровцикл, называется эйлеровым.
Дальнейшееразвитие задачи об Эйлеровом цикле
Припишемребрам графа длину μ (ai, aj). Требуется найти путь в графе,который проходит через все ребра и имеет наименьшую длину.
Пример.

/>
Рисунок 3.16– Граф
 
S – стартовая вершина. Извершины S надо пройти по всем ребрам так, чтобы маршрут имел минимальнуюдлину. Очевидно, что длина маршрута будет минимальной, если каждое ребро будетпройдено всего один раз – т. е. маршрут будет эйлеровым циклом.
Все локальныестепени – четные, значит граф эйлеров.
Вариантыпрохождения по циклу:
1)(sa) (ab) (bc) (cd) (db) (ds)
2)(sa)(ab) (bd) (dc) (cb) (bs)
3)(sb)(bc) (cd) (db) (ba) (as)
4)(sb)(bd) (dc) (cb) (ba) (as)
Длинаэйлерова цикла – 22. Любой из вариантов 1–4 содержит каждое ребро графа, следовательно,длина одинакова для всех циклов 1–4. Длина эйлерова цикла не зависит от того,какая вершина будет выбрана за исходную.
Задача поискаэйлерова цикла – это задача о: – поиске наилучшего способа прохождения бригадыпо дорогам; – прохождении с/х техники по полям.
Впервые этазадача рассматривалась в связи с нахождением оптимального маршрута следованияпочтальона, который доставляет письма своим адресатам и должен при этом пройтиминимальный путь.
Алгоритмнахождения эйлерова цикла для неориентированного графа [19]:
Дан эйлеровграф – т. е. граф с четными локальными степенями.
Найдем первоеребро х, инцидентное вершине S. Затем найдем ребро, смежное сребром х, которое не образует цикл и еще не было использовано. Продолжимэтот процесс до тех пор, пока не вернемся в вершину S. Если впостроенный цикл С1 вошли все ребра графа – задача решена.
Если впостроенный цикл С1 вошли не все ребра – строим цикл С2,состоящий из неиспользованных ребер и начинающийся с произвольногонеиспользованного ребра.
Такимобразом, строим циклы С2, С3,….Образование циклов продолжается дотех пор, пока не будут использованы все ребра.
Все циклы Сiнеобходимо объединить в один цикл. Условие объединения циклов С1 и С2– наличие у них общей вершины х. Начинаем движение с любой вершины идвигаемся по циклу С1 до тех пор, пока не дойдем до х. Затемпроходим ребро. С» и возвращаемся в х. Продолжаем обход по оставшимсяребрам до возвращения к исходной точке. Эта процедура легко обобщается наслучай любого числа объединяемых циклов.
ЦиклыЭйлера для ориентированного графа
Алгоритмпостроения эйлерова цикла в эйлеровом ориентированном графе является аналогомалгоритма построения эйлерова цикла для неориентированного графа.
Строятсяциклы Сi с учетом ориентации ребер, и затем все циклы объединяются водин.
Гамильтоновцикл (задача о коммивояжере)
Простой цикл,проходящий через каждую вершину графа только один раз, называется гамильтоновымциклом.
Если ребрамприписана длина, то различные варианты циклов отличаются друг от друга. Поэтомуставится задача нахождения гамильтонова цикла, имеющего минимальную длину.
Гамильтоновцикл наименьшей длины называется оптимальным гамильтоновым циклом (ОГЦ)
Поископтимального гамильтонова цикла – задача о коммивояжере, который долженпосетить множество пунктов и вернуться домой, пройдя наименьший путь.
Решениемзадачи о коммивояжере не всегда является ОГЦ.
Гамильтоновыграфы применяются для моделирования многих практических задач. Графическаямодель задачи коммивояжера состоит из гамильтонова графа, вершины которогоизображают города, а ребра – связывающие их дороги. Кроме того, каждое реброоснащено весом, обозначающим транспортные затраты, необходимые для путешествияпо соответствующей дороге, например, расстояние между городами или времядвижения по дороге. Для решения задачи нам необходимо найти гамильтонов циклминимального общего веса.
/>
Рисунок 3.17 –Ребра, входящие в гамильтонов цикл С
К сожалению,алгоритм решения данной задачи, дающий оптимальное решение, пока не известен. Длясложных сетей число гамильтоновых циклов, которые необходимо просмотреть длявыделения минимального, непомерно огромно. Однако существуют алгоритмы поискасубоптимального решения [1]. Субоптимальное решение необязательно даст циклминимального общего веса, но найденный цикл будет, как правило, значительноменьшего веса, чем большинство произвольных гамильтоновых циклов! Один из такихалгоритмов – алгоритм ближайшего соседа.
Этот алгоритмвыдает субоптимальное решение задачи коммивояжера, генерируя гамильтоновы циклыв нагруженном графе с множеством вершин V. Цикл, полученный в результатеработы алгоритма, будет совпадать с конечным значением переменной маршрут,а его общая длина – конечное значение переменной w.
begin
Выбрать v €V;
маршрут:=v;      
w:=0;
v':=v;
Отметить v';       
whileостаются неотмеченные вершины do begin
Выбратьнеотмеченную вершину и,
ближайшую кv';
маршрут:=маршрут u;       
w:= w + весребра v'u;
v':=u;
Отметить v';
end
маршрут:=маршрут v;
w:= w + весребра v'v;
end
Пример.Примените алгоритм ближайшего соседа к графу, изображенному на рисунке 3.18. Заисходную вершину возьмите вершину D.
/>
Рисунок 3.18 –Граф

Таблица 3.2 –Алгоритм ближайшего соседа и маршрут
w
v'
  Исходные значения
–
D
D
С
dc 3
С
А
DCA 9
A
В
DCAB 14
В Последний проход
В
DCABD 24
В
В результатеработы алгоритма был найден гамильтонов цикл DCABD общего веса 24. Делаяполный перебор всех циклов в этом маленьком графе, можно обнаружить еще двадругих гамильтоновых цикла: ABCDA общего веса 23 и ACBDA общеговеса 31. В полном графе с двадцатью вершинами существует приблизительно 6,1 *10^16 гамильтоновых циклов, перечисление которых требует чрезвычайно многомашинной памяти и времени.
Реализация примераданного алгоритма в Delphi:
procedureTForm1. Button1Click (Sender: TObject);
constmat:array [1… 4,1..4] of byte=((0,5,6,8), (5,0,7,10), (6,7,0,3), (8,10,3,0));
Versh:array[1..4] of char=('a', 'b', 'c', 'd');
buk:char='d';
Typet=set of 'a'..'d';
Vardlina, i, j, min, n, k, s:byte;
put:string;
z:t;
begin
dlina:=0;
Memo1.Lines. Clear;
fori:=1 to 4 do if versh[i]=buk then begin n:=i; s:=i;
include(z, buk);
put:=put+buk;
end;
forj:=1 to 3 do begin
ifmat [n, 1]0 then begin min:=mat [n, 1]; k:=1; end
elsebegin min:=mat [n, 2]; k:=2; end;
fori:=1 to 4 do
if(mat [n, i]0) and (not (versh[i] in z)) then begin
min:=mat[n, i];
k:=i;
end;
dlina:=dlina+min;
put:=put+versh[k];
include(z, versh[k]);
n:=k;
end;
put:=put+'d';
dlina:=dlina+mat[k, s];
Memo1.Lines. Add ('маршрут:'+' '+put);
Memo1.Lines. Add ('длина маршрута='+IntToStr(dlina));
end;
end.
/> 
Рисунок 3.19– Форма с результатом
 

3.2 Практическая часть
 
3.2.1 Заданиек работе
1 изучитьтеоретический материал по методическому пособию [24], лекциям и записям напрактических занятиях;
2 получитьзадание по индивидуальному варианту в виде графа или матрицы смежности, впервом случае построить матрицу смежности, во втором – нарисовать граф;
3 составитьподробное описание графа: ориентированный или неориентированный, количествовершин, дуг (рёбер), содержит ли циклы и какие, найти степени вершин,количество компонент связности и т. д.;
4 создатьприложение на Delphi для расчёта матрицы инцидентности по известной матрицесмежности (если граф достаточно сложный, то можно взять подграф этого графа);
5 в качестведополнительного творческого задания создать приложение на Delphi для реализацииалгоритма ближайшего соседа, алгоритма Прима, алгоритма Уоршелла, алгоритмаДейкстры, алгоритма определения количества компонент связности графа и другихизвестных алгоритмов на графах. [13], [17], [18], [19], [20], [21].
3.2.2 Примеры выполнения
Пример 1: Позаданной матрице смежности построить матрицу инцидентности.
implementation
procedureTForm1. UpDown1Click (Sender: TObject; Button: TUDBtnType);
begin
withUpDown1 do begin
withStringGrid1 do begin
RowCount:=Position;
ColCount:=Position;
end;
StringGrid2.RowCount:=Position;
end;
end;
procedureTForm1. BitBtn1Click (Sender: TObject);
vari, j, CD, P, n:byte;
MS:arrayof array of byte;
MI:arrayof array of ShortInt;
begin
P:=StrToInt(Edit1. Text);
SetLength(MS, P, P);
CD:=0;
fori:=0 to P‑1 do for j:=0 to P‑1 do begin
MS[i, j]:=StrToInt (StringGrid1. Cells [j, i]);
ifMS [i, j]=1 then inc(CD);
end;
SetLength(MI, P, CD);
fori:=0 to High(MS) do for j:=0 to CD‑1 do MI [i, j]:=0;
n:=0;
fori:=0 to High(MS) do for j:=0 to High(MS) do
ifMS [i, j]=1 then begin
MI[i, n]:=1;
MI[j, n]:=-1;
inc(n);
end;
StringGrid2.ColCount:=CD;
fori:=0 to High(MS) do for j:=0 to CD‑1 do
StringGrid2.Cells [j, i]:=IntToStr (MI[i, j]);
end;
end.
/>
Рисунок 3.20– Форма  с результатом
Пример 2: Позаданной матрице смежности построить матрицу инцидентности.
var
Form1:TForm1;
constmaxv=4;
typecanh=record dinh1, dinh2:byte;
dodai:real;end;
dothi=recordn:byte;
l:array[1..maxv, 1..maxv] of real;
x,y:set of 1..maxv;
t:array[1..maxv] of canh;
nt:byte;
it:real;end;
implementation
{$R*.dfm}
procedureTForm1. Button1Click (Sender: TObject);
varg:dothi;
min:real;
x, y,x0, y0:1..maxv;
i, j:byte;
beginmemo1. Clear;
g.n:=maxv;
edit1.Text:=inttostr(maxv);
stringgrid1.cells[0,0]:=' Номер';
fori:=1 to maxv do begin
stringgrid1.cells[0, i]:=inttostr(i);
stringgrid1.cells[i, 0]:=inttostr(i); end;
g.nt:=0;g.it:=0; g.x:=[1..g.n]; g.y:=[1];
fori:=1 to maxv do
forj:=1 to maxv do g.l [i, j]:=strtofloat (stringgrid1. Cells [j, i]);
whileg.nt
min:=-1;
forx:=1 to g.n do
fory:=1 to g.n do
if(x in g.y) and (y in (g.x-g.y)) and (g.l [x, y]>0) then
begin
if(min=-1) or (min>g.l [x, y]) then begin
min:=g.l[x, y];
x0:=x;y0:=y; end;
end;
g.y:=g.y+[y0];
g.nt:=g.nt+1;
g.it:=g.it+min;
withg.t [g.nt] do begin
dinh1:=x0;
dinh2:=y0;
dodai:=min;end; end;
fori:=1 to (maxv‑1) do
withg.t[i] do
memo1.Lines.add ('Ребро:'+inttostr(dinh1)+inttostr(dinh2)+' '+
'Весом:'+floattostr(dodai));
end;
end.
/> 
Рисунок 3.21– Форма с результатом
Пример 3:Составить приложение на Delphi, реалилующее алгоритм Уоршелла.
var
Form1:TForm1;
constmaxv=4;
typecanh=record dinh1, dinh2:byte;
dodai:real;end;
dothi=recordn:byte;
l:array[1..maxv, 1..maxv] of real;
x,y:set of 1..maxv;
t:array[1..maxv] of canh;
nt:byte;
it:real;end;
implementation
{$R*.dfm}
procedureTForm1. Button1Click (Sender: TObject);
varg:dothi;
min:real;
x, y,x0, y0:1..maxv;
i, j:byte;
beginmemo1. Clear;
g.n:=maxv;
stringgrid1.cells[0,0]:=' Номер';
fori:=1 to maxv do begin
stringgrid1.cells[0, i]:=inttostr(i);
stringgrid1.cells[i, 0]:=inttostr(i); end;
g.nt:=0;g.it:=0; g.x:=[1..g.n]; g.y:=[1];
fori:=1 to maxv do
forj:=1 to maxv do g.l [i, j]:=strtofloat (stringgrid1. Cells [j, i]);
whileg.nt
min:=-1;
forx:=1 to g.n do
fory:=1 to g.n do
if(x in g.y) and (y in (g.x-g.y)) and (g.l [x, y]>0) then
begin
if(min=-1) or (min>g.l [x, y]) then begin
min:=g.l[x, y];
x0:=x;y0:=y; end;
end;
g.y:=g.y+[y0];
g.nt:=g.nt+1;
g.it:=g.it+min;
withg.t [g.nt] do begin
dinh1:=x0;
dinh2:=y0;
dodai:=min;end; end;
fori:=1 to (maxv‑1) do
withg.t[i] do
memo1.Lines.add ('Ребро:'+inttostr(dinh1)+inttostr(dinh2)+' '+
'Весом: '+floattostr(dodai));
end;
end.
/>
Рисунок 3.23– Форма с результатом
 
3.2.3 Вариантв заданий
 
/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>/>

3.3 Вопросы для самопроверки
1) Какие операциинад графами Вы знаете?
2) Какформируется матрица смежности?
3) Какформируется матрица весов?
4) Какформируется матрица достижимости?
5) Какформируется матрица инцидентности?
6) Перечислитеосновные понятия, относящиеся к графам-деревьям.
7) Приведитепример сортировки и поиска в деревьях.
8) Длячего применяется алгоритм, подобный алгоритму Дейкстры, в коммуникационных сетях?
9)Перечислите известные Вам алгоритмы обхода графов.
10) Что такоетранспортная сеть? Приведите пример.
11) Какойграф называется эйлеровым? Приведите пример эйлерова графа.
12) Какойграф называется гамильтоновым? Приведите пример гамильтонова графа.
13) Какой видотношений на графах представляет изоморфизм графов?
14) Приведитепример отношения порядка и отношения эквивалентности на графе.
15) Какие алгоритмыобхода графов Вам известны?
16) Какие видыграфов Вы знаете?
17) Чтопонимается под степенью вершины?
18) Какопределяются числа внутренней и внешней устойчивости графа?
19) Какопределяются хроматическое и цикломатическое числа графа?
20) Сформулируйтетранспортную задачу и связанные с ней понятия?
21) Опишитекратко алгоритм управления проектами.
22) Приведитепример построения разреза графа.
23) Приведитепример дерева с корнем.

/>Практическая работа № 4.Элементы теории множеств и алгебры логики
Цель работы:применение знаний теории множеств и алгебры логики для решения практическойзадачи.
/> 
4.1Указание к выполнению
Даннаяпрактическая работа сочетает в себе использование элементов теории множеств иалгебры логики. Все теоретические сведения, необходимые для выполнения даннойработы, изложены в лекциях и в уже изданных методических пособиях [23], [25]. Выполнениеданной работы рекомендуется выполнять по образцу, рассмотренному далее.
/> 
4.2Задание к работе
1. Составитьмножества из букв Ф.И.О..
2. Представитьполученные множества на кругах Эйлера.
3. Представитьбуквы Ф.И.О. в двоичной системе.
4. Представитьдиаграмму Венна. СНДФ.
5. Перевестичисла даты рождения в двоичную систему счисления.
Примечание: желательно реализоватьосновные вычисления в приложении на Delphi.
/> 
4.3 Практическаячасть
Пример 1:
/>/>1 Множества из букв Ф.И.О.
МОРОЗОВ ОЛЕГ ЕВГЕНЬЕВИЧ
Ф = {М, О, Р, З, В};
И = {О, Л, Е, Г};
О = {Е, В, Г, Н, Ь, И, Ч};
/>/>2 Круги Эйлераи диаграммы Венна
 
/>
Рисунок 4.1 –Круги Эйлера
/>/> 
Таблица 4.1 –Буквы алфавита в двоичной системеА 00001 Л 01011 Ц 10110 Б 00010 М 01100 Ч 10111 В 00011 Н 01101 Ш 11000 Г 00100 О 01110 Щ 11001 Д 00101 П 01111 Ъ 11010 Е 00110 Р 10000 Ы 11011 Ж 00111 С 10001 Ь 11100 З 01000 Т 10010 Э 11101 И 01001 У 10011 Ю 11110 К 01010 Ф 10100 Я 11111 Х 10101
/>/> 
Таблица 4.2 –Буквы Ф.И.О. в двоичной системе М О Р З В О Л Е Г Е В Г Н Ь И Ч 1 1 1 3
F1 1 1 1 1 1 1 1 1 8
F2 1 1 1 1 1 1 1 1 1 1 10
F3 1 1 1 1 1 1 1 1 8 1 1 1 1 1 1 6
/>/> 

Таблица 4.3 –СНДФ из букв Ф.И.О.
x1 x2 x3 x4
F1
F2
F3 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1
/>
/>/>/>
/>
F1
/>

F2
/>
F3
/>
/>Рисунок 4.2 – ДиаграммыВенна для функций F1, F2, F3
3 Переводдаты рождения в двоичную систему
1982.0212
/>/>/>1982
/>/>/>2
/>/>/>991 0
/>/>/>2
/>/>/>495 1
/>/>/>2
/>/>/>247 1
/>/>/>2
/>/>/>123 1
/>/>/>2
/>/>/>61 1
/>/>/>2
/>/>/>30 1
/>/>/>2
/>/>/>15 0
/>/>/>2
/>/>/>7 1
/>/>/>2
/>/>/>3 1
/>/>/>2
/>/>/>1 1

0.0212 0.3568 1.4272 2 2 2 0.0424 0.7136 0.8544 2 2 2 0.0848 1 1.4272 1 1.7088 2 0.1696 2 0.3392 2 0.6784 2 1 1.3568
(1982.0212) 10=(11110111110.0000010101)2
Пример 2:автор – Якухин Дмитрий
var
k:byte;
Form1: TForm1;
typeR = set of 'A'..'Я';
implementation
{$R*.dfm}
procedureSNDF (y:byte; t:string);
vari:byte;
begin
fori:=1 to 5 do begin
Form1.StringGrid1. Cells [y, i]:=t[i];
end;
fori:=1 to 3 do begin
Form1.StringGrid2. Cells [i+4, y]:=t [i+1];
end;
end;
procedurePerebor (T:R; S:TMemo);
begin
if('А' in T) thenbegin S. Lines. Add ('А= '+' 00001'); inc(k); SNDF (k, '00001'); Form1. StringGrid1. Cells[k, 0]:='А'; end;
if('Б' in T) thenbegin S. Lines. Add ('Б= '+' 00010'); inc(k); SNDF (k, '00010'); Form1. StringGrid1. Cells[k, 0]:='Б'; end;
if('В' in T) thenbegin S. Lines. Add ('В= '+' 00011'); inc(k); SNDF (k, '00011'); Form1. StringGrid1. Cells[k, 0]:='В'; end;
if('Г' in T) thenbegin S. Lines. Add ('Г= '+' 00100'); inc(k); SNDF (k, '00100'); Form1. StringGrid1. Cells[k, 0]:='Г'; end;
if('Д' in T) thenbegin S. Lines. Add ('Д= '+' 00101'); inc(k); SNDF (k, '00101'); Form1. StringGrid1. Cells[k, 0]:='Д'; end;
if('Е' in T) thenbegin S. Lines. Add ('Е= '+' 00110'); inc(k); SNDF (k, '00110'); Form1. StringGrid1. Cells[k, 0]:='Е'; end;
if('Ж' in T) thenbegin S. Lines. Add ('Ж= '+' 00111'); inc(k); SNDF (k, '00111'); Form1. StringGrid1. Cells[k, 0]:='Ж'; end;
if('З' in T) thenbegin S. Lines. Add ('З= '+' 01000'); inc(k); SNDF (k, '01000'); Form1. StringGrid1. Cells[k, 0]:='З'; end;
if('И' in T) thenbegin S. Lines. Add ('И= '+' 01001'); inc(k); SNDF (k, '01001'); Form1. StringGrid1. Cells[k, 0]:='И'; end;
if('К' in T) thenbegin S. Lines. Add ('К= '+' 01010'); inc(k); SNDF (k, '01010'); Form1. StringGrid1. Cells[k, 0]:='К'; end;
if('Л' in T) thenbegin S. Lines. Add ('Л= '+' 01011'); inc(k); SNDF (k, '01011'); Form1. StringGrid1. Cells[k, 0]:='Л'; end;
if('М' in T) thenbegin S. Lines. Add ('М= '+' 01100'); inc(k); SNDF (k, '01100'); Form1. StringGrid1. Cells[k, 0]:='М'; end;
if('Н' in T) thenbegin S. Lines. Add ('Н= '+' 01101'); inc(k); SNDF (k, '01101'); Form1. StringGrid1. Cells[k, 0]:='Н'; end;
if('О' in T) thenbegin S. Lines. Add ('О= '+' 01110'); inc(k); SNDF (k, '01110'); Form1. StringGrid1. Cells[k, 0]:='О'; end;
if('П' in T) thenbegin S. Lines. Add ('П= '+' 01111'); inc(k); SNDF (k, '01111'); Form1. StringGrid1. Cells[k, 0]:='П'; end;
if('Р' in T) thenbegin S. Lines. Add ('Р= '+' 10000'); inc(k); SNDF (k, '10000'); Form1. StringGrid1. Cells[k, 0]:='Р'; end;
if('С' in T) thenbegin S. Lines. Add ('С= '+' 10001'); inc(k); SNDF (k, '10001'); Form1. StringGrid1. Cells[k, 0]:='С'; end;
if('Т' in T) thenbegin S. Lines. Add ('Т= '+' 10010'); inc(k); SNDF (k, '10010'); Form1. StringGrid1. Cells[k, 0]:='Т'; end;
if('У' in T) thenbegin S. Lines. Add ('У= '+' 10011'); inc(k); SNDF (k, '10011'); Form1. StringGrid1. Cells[k, 0]:='У'; end;
if('Ф' in T) thenbegin S. Lines. Add ('Ф= '+' 10100'); inc(k); SNDF (k, '10100'); Form1. StringGrid1. Cells[k, 0]:='Ф'; end;
if('Х' in T) thenbegin S. Lines. Add ('Х= '+' 10101'); inc(k); SNDF (k, '10101'); Form1. StringGrid1. Cells[k, 0]:='Х'; end;
if('Ц' in T) thenbegin S. Lines. Add ('Ц= '+' 10110'); inc(k); SNDF (k, '10110'); Form1. StringGrid1. Cells[k, 0]:='Ц'; end;
if('Ч' in T) thenbegin S. Lines. Add ('Ч= '+' 10111'); inc(k); SNDF (k, '10111'); Form1. StringGrid1. Cells[k, 0]:='Ч'; end;
if('Ш' in T) thenbegin S. Lines. Add ('Ш= '+' 11000'); inc(k); SNDF (k, '11000'); Form1. StringGrid1. Cells[k, 0]:='Ш'; end;
if('Щ' in T) thenbegin S. Lines. Add ('Щ= '+' 11001'); inc(k); SNDF (k, '11001'); Form1. StringGrid1. Cells[k, 0]:='Щ'; end;
if('Ъ' in T) thenbegin S. Lines. Add ('Ъ= '+' 11010'); inc(k); SNDF (k, '11010'); Form1. StringGrid1. Cells[k, 0]:='Ъ'; end;
if('Ы' in T) thenbegin S. Lines. Add ('Ы= '+' 11011'); inc(k); SNDF (k, '11011'); Form1. StringGrid1. Cells[k, 0]:='Ы'; end;
if('Ь' in T) thenbegin S. Lines. Add ('Ь= '+' 11100'); inc(k); SNDF (k, '11100'); Form1. StringGrid1. Cells[k, 0]:='Ь'; end;
if('Э' in T) thenbegin S. Lines. Add ('Э= '+' 11101'); inc(k); SNDF (k, '11101'); Form1. StringGrid1. Cells[k, 0]:='Э'; end;
if('Ю' in T) thenbegin S. Lines. Add ('Ю= '+' 11110'); inc(k); SNDF (k, '11110'); Form1. StringGrid1. Cells[k, 0]:='Ю'; end;
if('Я' in T) thenbegin S. Lines. Add ('Я= '+' 11111'); inc(k); SNDF (k, '11111'); Form1. StringGrid1. Cells[k, 0]:='Я'; end;
end;
procedureTForm1. BitBtn1Click (Sender: TObject);
varF, I, O:R;
h,j, S:byte;
begin
Memo1.Clear;
Memo2.Clear;
Memo3.Clear;
k:=0;
S:=0;
F:=['Я', 'К', 'У', 'Х', 'И', 'Н'];
I:=['Д', 'М', 'И', 'Т', 'Р'];
O:=['Е', 'Р', 'Г', 'В', 'И'];
perebor(F, Memo1);
perebor(I, Memo2);
perebor(O, Memo3);
forj:=1 to 5 do begin
forh:=1 to 19 do begin
ifStringGrid1. Cells [h, j]='1' then inc(s);
end;
StringGrid1.Cells [17, j]:=IntToStr(S);
S:=0;
(yegorov-pRulezzz;)}
end;
end;
procedureTForm1. FormCreate (Sender: TObject);
var
g:byte;
begin
StringGrid1.Cells [0,2]:='F1';
StringGrid1.Cells [0,3]:='F2';
StringGrid1.Cells [0,4]:='F3';
StringGrid2.Cells [1,0]:='X1';
StringGrid2.Cells [2,0]:='X2';
StringGrid2.Cells [3,0]:='X3';
StringGrid2.Cells [4,0]:='X4';
StringGrid2.Cells [5,0]:='F1';
StringGrid2.Cells [6,0]:='F2';
StringGrid2.Cells [7,0]:='F3';
forg:=0 to 15 do
StringGrid2.Cells [0, g+1]:=IntToStr(g);
forg:=0 to 7 do
StringGrid2.Cells [1, g+1]:='0';
forg:=8 to 15 do
StringGrid2.Cells [1, g+1]:='1';
forg:=0 to 3 do
StringGrid2.Cells [2, g+1]:='0';
forg:=4 to 7 do
StringGrid2.Cells [2, g+1]:='1';
forg:=8 to 11 do
StringGrid2.Cells [2, g+1]:='0';
forg:=12 to 15 do
StringGrid2.Cells [2, g+1]:='1';
forg:=1 to 2 do begin
StringGrid2.Cells [3, g]:='0';
StringGrid2.Cells [3, g+2]:='1';
StringGrid2.Cells [3, g+4]:='0';
StringGrid2.Cells [3, g+6]:='1';
StringGrid2.Cells [3, g+8]:='0';
StringGrid2.Cells [3, g+10]:='1';
StringGrid2.Cells [3, g+12]:='0';
StringGrid2.Cells [3, g+14]:='1';
end;
forg:=1 to 16 do begin
ifg div 2 = g/2 then
StringGrid2.Cells [4, g]:='1'
else
StringGrid2.Cells [4, g]:='0';
end;
end;
FunctionDec2Bin (j:integer):string;
begin
result:='';
whilej>=1 do
begin
result:=IntToStr(j mod 2)+result;
j:=jdiv 2;
end;
end;
FunctionDec2BinDrob (j:real):string;
var
i:byte;
begin
result:='';
fori:=1 to 11 do
begin
result:=FloatToStr(int(j*2))+result;
j:=j*2;
ifint (j*2)>1 then j:=j‑1;
end;
end;
procedureTForm1. BitBtn3Click (Sender: TObject);
varp, p2, S, S2, S3:string;
i:byte;
begin
p:=Edit1.Text;
p2:='0,'+Edit3.Text;
S:=Dec2Bin(StrToInt(p));
S2:=Dec2BinDrob(StrToFloat(p2));
fori:=11 downto 1 do begin
S3:=S3+S2[i];
end;
Edit2.Text:=S+'.'+S3;
end;
procedureTForm1. BitBtn4Click (Sender: TObject);
vari:byte;
P:string;
begin
fori:=1 to 16 do begin
ifStringGrid2. Cells [5, i]='1' then begin
P:=StringGrid2.Cells [1, i]+StringGrid2. Cells [2, i]+
StringGrid2.Cells [3, i]+StringGrid2. Cells [4, i];
Label7.Caption:=Label7. Caption+' '+P;
end;
end;
fori:=1 to 16 do begin
ifStringGrid2. Cells [6, i]='1' then begin
P:=StringGrid2.Cells [1, i]+StringGrid2. Cells [2, i]+
StringGrid2.Cells [3, i]+StringGrid2. Cells [4, i];
Label8.Caption:=Label8. Caption+' ' +P;
end;
end;
fori:=1 to 16 do begin
ifStringGrid2. Cells [7, i]='1' then begin
P:=StringGrid2.Cells [1, i]+StringGrid2. Cells [2, i]+
StringGrid2.Cells [3, i]+StringGrid2. Cells [4, i];
Label9.Caption:=Label9. Caption+' '+P;
end;
end;
end;
end.
/>
Рисунок 4.3 –Форма для примера 2
/> 
4.4 Вопросы для самопроверки
1) Чемотличается кортеж от обычного множества?
2) Приведитепример использования кортежей в программировании.
3. Какиеоперации над множествами Вы знаете?
4) Какойспособ существует для графического изображения множеств?
5) Приведитепример универсального множества, которое используется в данной практическойработе.
6) Какиеоперации (логические связки) из алгебры логики Вы знаете?
7) Возможноли провести аналогию между операциями над множествами и логическими операциями?
8) Какоеправило используется при построении СДНФ логической функции?
9) Какоеправило используется при построении СКНФ логической функции?
10) Каковалгоритм перевода числа из десятичной системы счисления в двоичную системусчисления?
11) Почемулогические функции и логические переменные часто называют двоичными?
12) Какаясвязь существует между логическими функциями и функционированием компьютера,отдельных его устройств?
/> 

Практическая работа № 5. Исследованиелогических функций
Цель работы:изучение существующих форм представления логических функций. Построениесовершенных нормальных форм логических функций. Построение таблиц истинности иарифметических моделей логических функций в приложениях на Delphi.
Примечание:все теоретические сведения, необходимые для выполнения данной работы, содержатсяв [25], в лекциях и в материалах семинарских занятий.
/> 
5.1 Заданиек работе
1. Используясредства Excel и Delphi, построить таблицы истинности заданных логическихфункций, если требуется, то предварительно упростить выражения, используязаконы алгебры логики и следствия из них.
2. Используясредства Excel и Delphi, построить арифметические модели заданных логическихфункций.
3. Представитьзаданные логические функции в виде СДНФ, СКНФ и СПНФ.
4. Построитьлогические функциональные схемы для заданных логических функций F1 и F2.
5. Сделатьвыводы.
 
5.2Практическая часть
 
5.2.1 Примервыполнения
Задание: Построить таблицуистинности, СДНФ, СКНФ, СПНФ и логические функциональные схемы для данныхлогических функций:
 
F1=/>
F2=/>/>
Код программыпостроения таблицы истинности логический функций:
ProcedureTForml. ButtonlClick (Sender: TObject);
varxl, x2, x3:boolean; i:byte;
a1,a2, a3: string;
begin
Stringgridl.Cells [l, 0]:='xl';
Stringgridl.Cells [2,0]:='x2';
Stringgridl.Cells [3,0]:='x3';
Stringgrid1.Cells [4,0]:=F1';
Stringgridl.Cells [5,0]:='F2';
fori:=l to 8 do begin Stringgrid1. Cells [0, i]:=inttostr (i‑1);
ifi
if(i
if(i mod 2 >0) then Stringgridl. Cells [3, i]:='0' else Stringgridl. Cells [3,i]:=1; end;
fori:=l to 8 do begin
x1:=strtobool(Stringgrid 1. Cells [1, i]);
x2:=strtobool(Stringgridl. Cells [2, i]);
x3:=strtobool(Stringgridl. Cells [3, i]);
if(x2 and x3) or (not(xl) and not(x2)) or (x3 and not(xl)) then
Stringgridl.Cells [4, i]:=’1’ else Stringgridl. Cells [4, i]:='0';
if(x2 and x3) or (not(xl) and not(x2) and not(x3)) then Stringgridl. Cells [5, i]:=1else Stringgridl. Cells [5, i]:='0'; end; end;

/>
Рисунок 5.1 –Форма с результатами
МДНФ:
F1 = />
F2 = />
МКНФ:
F1 = />
F2 = />
СПНФ:
F1 =/>
F2 =/>
/>
Рисунок 5.2 – Логическая схема для МКНФ функции F1
 

5.2.2 Вариантызаданий
1)        Заданылогические функции: F1= 1 на наборах 0, 3 и />
2)        Заданылогические функции: F1= 1 на наборах 0, 1, 3 и />
3)        Заданылогические функции: F1= 1 на наборах 3, 7 и />
4)        Заданылогические функции: F1= 1 на наборах 0, 1, 3, 7 и />
5)        Заданылогические функции: F1= 1 на наборах 0,1,2,3,7 и />
6)        Заданылогические функции: F1= 1 на наборах 2,5,6 и />
7)        Заданылогические функции: F1= 1 на наборах 0, 2,5,7 и />
8)        Заданылогические функции: F1= 1 на наборах 0, 1,3 и />
9)        Заданылогические функции: F1= 1 на наборах 3,4,6,7 и />
10)     Заданылогические функции: /> и />
11)     Заданылогические функции: /> и />
12)     Заданылогические функции: /> и />
13)     Заданылогические функции: /> и />
14)     Заданылогические функции: /> и />
15)     Заданылогические функции: /> и />
16)     Заданылогические функции: /> и />
17)     Заданылогические функции: /> и />
18)     Заданылогические функции: /> и />
19)     Заданылогические функции: /> и />
20)     Заданылогические функции: /> и />
21)     Заданылогические функции: /> и
22)     />
23)     Заданылогические функции: /> и />
24)     Заданылогические функции: /> и />
25)     Заданылогические функции: /> и />
26)     Заданылогические функции: /> и />
27)     Заданылогические функции: /> и />
28)     Заданылогические функции: /> и />
29)     Заданылогические функции: /> и />
30)     Заданылогические функции: /> и />
31)     Заданылогические функции: /> и />
32)     Заданылогические функции: F1=1 на наборах 4,5,7 и />
33)     Заданылогические функции: F1=0 на наборах 2,4 и />
34)     Заданылогические функции: /> и />
35)     Заданылогические функции: /> и />
36)     Заданылогические функции: /> и />
37)     Заданылогические функции: /> и />
/> 
5.3 Вопросы для самопроверки
1) Какиеформы представления логических функций Вы знаете?
2) В какихслучаях, на Ваш взгляд, какие формы представления логических функций являютсянаиболее предпочтительными?
3) Изобразитеобщую схему таблицы истинности функции 4‑х переменных.
4) Каковприоритет выполнения логических операций?
5) Какиелогические функции есть в алгоритмическом языке Object Pascal?
6) Дайтеопределение логической функции многих переменных.
7) Приведитепример тождественно ложной логической функции. Можно ли для этой функциипостроить СДНФ?
8) Приведитепример тождественно истинной логической функции. Можно ли для этой функциипостроить СКНФ?
9) Наосновании каких замен можно построить арифметическую модель логической функции?
10) Перечислитезаконы алгебры логики.
11) Какиеследствия из законов алгебры логики Вы знаете?
12) Назовитеучёных, которые считаются основателями алгебры логики.
/>/> 

Практическая работа № 6. Изучение методовминимизации логических функций
Цель работы:применение изученных методов минимизации логических функций для решенияконкретных задач.
/> 
6.1 Краткиетеоретические сведения
Общая задачаминимизации логических функций сводится к построению в базисе Буля функции,содержащей минимально возможное число двоичных переменных. Исходное выражениелогической функции может быть представлено формулой в любом базисе. Поэтому напервом этапе осуществляется переход к нормальной форме формулы булевой функции,как правило, совершенной дизъюнктивной нормальной форме.
F 0={×;Ú; – ;Å;«;®;½;¯} – сигнатура алгебрылогики;
F 1={×;Ú;–} – базис Буля;
F 2={×;–} – базис конъюнктивный;
F 3={Ú;–} – базис дизъюнктивный;
F 4={×;Å; 1} – базис Жегалкина;
F 5={¯} – базис Вебба;
F 6={½} – базис Шеффера;
F 7={®;–} – базис импликативный и т. д.
В таблицах 6.1–4приведены формулы в некоторых базисах и для некоторых значений функции f (x1,x2).
 
Таблица 6.1 –Формулы, описывающие функции в базисах F0 и F5
fi
Формулы в базисах F 0 и F 5
f1
(x1×x2)=(x1¯x2)¯(x1¯x2)
f6
(x1Åx2)=[(x1¯x1)¯(x2¯x2)]¯(x1¯x2)
f7
(x1Úx2)=(x1¯x2)¯(x1¯x2)
f9
(x1«x2)=[x1¯(x2¯x2)]¯[x2¯(x1¯x1)]
f13
(x1®x2)=[x2¯(x1¯x1)]¯[x2¯(x1¯x1)]
f14
(x1÷x2)=[(x1¯x1)¯(x2¯x2)]¯ [(x1¯x1)¯(x2¯x2)]
Таблица 6.2 –Формулы, описывающие функции в базисах F0 и F2
Fi
Формулы в базисах F 0 и F2
f6
(x1Åx2)=ù(`x1×`x2)×ù(x1×x2)
f7
(x1Úx2)=ù(`x1×`x2)
f8
(x1¯x2)=(`x1×`x2)
f9
(x1«x2)=ù(x1×`x2)×ù(`x1×x2)
f13
(x1®x2)=ù(x1×`x2)
f14
(x1÷x2)=ù(x1×x2)
Таблица 6.3 –Формулы, описывающие функции в базисах F0 и F3Fi Формулы в базисах F 0 и F3
f6
(x1×x2)=ù(`x1Ú`x2)
f7
(x1Åx2)=ù(`x1Úx2)Úù(x1Ú`x2)
f8
(x1¯x2)=ù(x1Úx2)
f9
(x1«x2)=(x1Úx2)Úù(`x1Ú`x2)
f13
(x1®x2)=(`x1Úx2)
f14
(x1½x2)=(`x1Ú`x2)
Таблица 6.4 –Формулы, описывающие функции в базисах F0 и F6
Fi
Формулы в базисах F 0 и F 6
f1
(x1×x2)=(x1½x2)½(x1½x2)
f6
(x1Åx2)=[x1½(x2½x2)]½[x2½ (x1½x1)]
f7
(x1Úx2)=(x1½x2)½(x1½x2)
f8
(x1¯x2)=[(x1½x1)½(x2½x2)½ (x2½x2)]
f9
(x1«x2)=[(x1½x1)½(x2½x2)]½ (x1½x2)]
f13
(x1®x2)=(x1½(x2½x2).
 

6.2 Практическая часть
 
6.2.1 Заданиек работе
1. Минимизироватьфункции с помощью карт Карно или таблицы Куайна.
2. Используя средстваExcel и Delphi, построить таблицы истинности заданных логических функций.
3. Сделатьвыводы.
 
6.2.2Примеры выполнения
Пример 1.
Задание:
1.Минимизировать функции с помощью таблицы Куайна.
2. Используяпрограммные средства Delphi, построить таблицы истинности заданных логическихфункций.
1 Минимизацияс помощью таблицы Куайна:
Пусть функцияF представлена в виде СДНФ
F1СДНФ = />
 
Таблица 6.5 –таблица Куайнах1x2x3 001 101 110 111
0 0 1
1 – 1
1 1 – 1 1 1 1
Упростим F1СДНФ, получим:
F1МДНФ =/>
Как мы видим,результат, полученный по таблице Куайна, совпадает с F1МДНФ.
/>
/>
Рисунок 6.1 –Графический интерфейс
2 Процедураосновного обработчика
procedureTForm1. BitBtn1Click (Sender: TObject);
Vari:byte;
x1,x2, x3:boolean;
begin
fori:=1 to 8 do begin
StringGrid1.Cells [0, i]:=IntToStr (i‑1);
Ifi
If(i=5) and (i
If(i mod 2>0) then StringGrid1. Cells [3, i]:='0' else StringGrid1. Cells [3, i]:='1';
Ifi
If(i=5) and (i
x1:=StrToBool(StringGrid1. Cells [1, i]);
x2:=StrToBool(StringGrid1. Cells [2, i]);
x3:=StrToBool(StringGrid1. Cells [3, i]);
if(not (x1) and not (x2) and x3) or (x1 and x3) or (x1 and x2)
thenStringGrid1. Cells [6, i]:='1'
elseStringGrid1. Cells [6, i]:='0';
end;end;
Пример 2.Пусть будут заданы номера наборов четырех переменных, на которых логическаяфункция принимает единичное значение: f(2,5,6,7,10,12,13,14)=1.
Выразим этулогическую функцию в СДНФ (символ конъюнкции писать не будем):
f(0010,0101, 0110, 0111,1010, 1100, 1101, 1110) =
/>.
 
Таблица 6.6 –карта Карно для функции 4‑х переменных
/>
/>
/>
/>
/> 1100 1110 0110 0100
/>
/> 1101 1111 0111 0101
/>
/> 1001 1011 0011 0001
/>
/> 1000 1010 0010 0000
/>
/>
/>
/>
/>
 
Таблица 6.7 –заполненная карта
/>/>/>
Карта Карнодля четырех переменных представлена в виде таблицы 6.6. Каждая клетка картысоответствует конституенте. Заполненная карта представлена таблицы 6.7.Согласно закону склеивания, две смежные конституенты с единичными значениямивсегда можно объединить для получения соответствующей импликанты. Причем смежнымисчитаются и те, которые лежат на границах карты. Какие именно единицы требуетсяобъединить для получения подходящей импликанты, легко определить визуально [5].В соответствии с законом идемпотентности одна и та же единица таблицы 6.7 можетсклеиваться с двумя или тремя смежными единицами.
/> 
6.3 Вопросы длясамопроверки
1)Перечислите законы алгебры логики, которые наиболее часто используются приупрощении сложных логических выражений?
2)Перечислите правила (следствия), полученные из законов алгебры логики, которыеобычно используются при упрощении сложных логических выражений?
3) Какое логическоевыражение называется конституентой?
4) Какоелогическое выражение называется импликантой?
5) В чёмзаключается задача минимизации логической функции? Основная операция,используемая при минимизации логической функции?
6) Каквыглядит карта Карно для логической функции трёх переменных? Каков принцип еёпостроения?
7) В чёмзаключается смысл метода карт Карно?
8) Еслилогическая функция не полностью определена, то каким образом можно задатьформулу, описывающую данную функцию?
9) Требует лиметод Куайна этапа предварительной (аналитической) минимизации?
10) Какимобразом строится таблица Куайна?
11) По какомупринципу выбираются импликанты, образующие минимизированное представлениелогической функции в методе Куайна?
12) Краткоопишите принцип, на котором базируется метод сочетания индексов.
13)Перечислите известные Вам методы минимизации логических функций.
14)Обязательным ли является условие того, что исходное выражение, описывающеелогическую функцию, которое требуется минимизировать, является дизъюнктивнойнормальной формой?
15) Какой изметодов минимизации логических функций, на Ваш взгляд, проще поддаётсяалгоритмизации?

/>/>Практическая работа № 7. Моделированиеработы узлов компьютера с помощью Еxcel
/> 
7.1Теоретическая часть
В основеработы логических схем и устройств компьютера лежит специальный математическийаппарат, называемый математической логикой [21].
Студентампредлагается при изучении данной темы не только спроектировать реальные узлыкомпьютера, но и смоделировать их работу с помощью электронной таблицы Excel.Это сделает изучение темы более интересным, полезным. Появится полноевпечатление, что создана действующую модель реального узла компьютера.
Посколькулогическая функция осуществляет однозначное отображение множества наборов {(x1;x2;……; xn)}, в которых компоненты xi принимают значение из множества {0;1}, в множество y={0; 1}, то для её реализации могут быть использованыпереключательные или вентильные элементы. Переключательные элементы обладаютдвумя состояниями и двухсторонней проводимостью. Такими элементами являютсявыключатели, реле, ключи, коммутаторы и т. п. Вентильные элементыобладают также двумя состояниями, но, как правило, односторонней проводимостью.Такими элементами являются диоды, триоды, микросхемы и т. п. Интегральныемикросхемы в одном корпусе реализуют большое число логических функций [13].
Чтобыупорядочить проектирование и разработку различных логических илипереключательных устройств, разработаны международной и общероссийскийстандарты для обозначения различных логических функций.
В таблице 7.1приведены основные условные обозначения логических функций [2].
Схемы,формируемые вентильными элементами, называют комбинационными схемами. Есликомбинационная схема реализует одну булеву функцию, то её называютодновыходовой комбинационной схемой, если несколько, то – многовыходовойкомбинационной схемой.
Схемасинтезируется из типовых логических элементов подобно тому, как сложная функцияполучается суперпозицией более простых функций.
Например, нарисунке 7.1 приведена комбинационная схема, реализующая функцию fmin.
/>
Рисунок 7.1 –Комбинационная схема для fmin
 
Таблица 7.1Стандартные обозначения логических элементов
Логическая функция
(имя, значение)
обозначение по
ГОСТ 2.743–82
«ИЛИ», дизъюнкция
f (x1; x2)=(x1Úx2)
/>
«И», конъюнкция
f (x1; x2)=(x1×x2)
/>
«ИЛИ – НЕ», стрелка Пирса
f (x1; x2)= ÷ (x1Úx2)=(x1¯x2)
/>
«И – НЕ», штрих Шеффера
f (x1; x2)= ÷ (x1×x2)=(x1÷ x2)
/>
«НЕ – ИЛИ», импликация
f (x1; x2)=(x1Úx2)=(x1®x2)
/>
Сложение по mod 2
f (x1; x2)=(x1Åx2)
/>
Понятиео синтезе логических схем
Логическиеустройства компьютера выполняют необходимые преобразования поступающей на входцифровой информации. При синтезе таких устройств большое применение находитматематический аппарат алгебры логики.
Обычнопроцесс синтеза логических устройств состоит из следующих основных этапов:
o   Наосновании анализа функций, которые должны выполняться данным устройством,формируются логические условия его функционирования в виде соответствующейтаблицы истинности.
o   Попостроенной таблице истинности записывается аналитическое выражение логическойфункции в виде СДНФ или в СКНФ.
o   Производитсяминимизация логической функции.
o   Поупрощенной логической формуле строится функциональная схема устройства, причемпредпочтение отдается минимальному числу и однородности логических элементов.
Средилогических узлов компьютера широкое распространение получили комбинационныеавтоматы (схемы). Такой автомат в общем случае представляются в видемногополюсника, имеющего r входов т1, т2,…, тr и l выходов k1,k2,…, kl. Поступающая на вход автомата информация задаетсянабором сигналов М (т1, т2,…, тr), образующим входное слово. При этом влюбой дискретный момент времени t. совокупность выходных сигналов – выходноеслово K (k1, k2,…, kl) – полностью определяетсявходным словом М, поступившим в тот же момент времени. При изменениинабора входных сигналов М меняется набор выходных сигналов K.Таким образом, выходные сигналы комбинационного автомата полностью определяютсявходными сигналами и не зависят от внутреннего состояния автомата. Эти автоматыне имеют памяти. Именно о синтезе таких комбинационных автоматов (схем) ипойдет речь далее.
Построениекомпьютера ведется по следующей цепочке:
элементы →узлы → устройства.
Элементы посвоему назначению делятся на следующие группы: логические; запоминающие; вспомогательные.
Насинтересуют логические элементы – на их основе строятся комбинационные схемы. Кчислу основных логических элементов, применяемых в ЭВМ и образующих функциональнополный набор (т. е. такой набор элементов, с помощью которого может бытьреализована любая сложная логическая функция), относятся логические элементы И(конъюнктор), ИЛИ (дизъюнктор), НЕ (инвертор). Хотя в ряде случаев некоторыелогические выражения могут быть проще реализованы с помощью более сложныхлогических элементов, таких, как И-НЕ, ИЛИ-НЕ, И-ИЛИ-НЕ, ограничимсяиспользованием первой группы элементов.
Узел – этосовокупность функционально связанных между собой элементов. Узлы компьютера посвоему функциональному назначению делятся на следующие группы: регистры; дешифраторы;шифраторы; схемы сравнения кодов; электронные счетчики; сумматоры.
/> 
7.2 Практическаячасть
Спроектируемнекоторые из узлов. Вся работа от построения таблиц истинности соответствующегоузла до вычерчивания его схемы будет представлена непосредственно в Excel. Всесоответствующие этапы синтеза будут иметь на рабочих листах соответствующуюнумерацию (см. выше). Для того чтобы не загромождать рабочий лист, вбольшинстве случаев не приводится минимизация функций, введены сразу упрощенныелогические выражения.
Excel имеет всвоем арсенале логические функции, представленные в окне Мастера функций,показанном на рисунке 7.2.
/>
Рисунок 7.2 –Иллюстрация к использованию Мастера функций
В качествеаргументов логические функции И, ИЛИ, НЕ одинаково трактуют значения «0» и«ЛОЖЬ», 1 и «ИСТИНА», а в качестве результата выдают только значения «ЛОЖЬ» или«ИСТИНА». Поэтому для перехода от значений «ЛОЖЬ» и «ИСТИНА» к привычным 0 и 1используется функция ЕСЛИ.
 
7.2.1 Схемысравнения кодов
Организациясравнения двух двоичных чисел заключается в выработке признака равенства(равнозначности) или признака неравенства (неравнозначности) двух сравниваемыхчисел. Ограничимся признаком равенства.
Одноразряднаясхема сравнения кодов
Значениепризнака равенства q при сравнении одноразрядных переменных описываетсятаблицей истинности, представленной на рисунке 7.3.
В ячейку в E7введена формула: =ЕСЛИ (C7=D7; 1; 0), которая затем скопирована вячейки D8:D10.
Значение q1функции виде СДНФ: />.
/>
Рисунок 7.3 –Образец выполнения работы
Упрощениевыражения не требуется, пункт 3 порядка проектирования логических схемотсутствует.
Схема имеетвид, представленный на рисунке 7.3. Схема начерчена непосредственно в Excel спомощью панели рисования с использованием таких приемов, как копированиеповторяющихся элементов, группировка.
Дальнейшаяработа проделана для того, чтобы получить действующую модель схемы, которая приподаче входных сигналов (сравниваемых одноразрядных двоичных чисел) будетвыдавать выходные сигналы (результат сравнения).
Ячейки C14и D14 отведены для ввода сравниваемых одноразрядных двоичных чисел. Имприсвоены имена а и b соответственно.
Установленапроверка данных на корректность (ввод только 0 и 1). (рисунки 7.4 – 7.5.)

/>
Рисунок 7.4 –Подсказка при вводе значений
/>
Рисунок 7.5 –Сообщение об ошибке, в случае ввода некорректных данных
Для этогоячейки C14 и D14 выделены и выполнена команда Данные, Проверка. Вдиалоговом окне Проверка вводимых значений установить нужные параметры (рисунки7.6, а-в).
/>
Рисунок 7.6 а – Настройка проверки вводимых значений
/>
Рисунок 7.6 б – Настройка проверки вводимых значений

/>
Рисунок 7.6 в-Настройкапроверки вводимых значений
В ячейку K22введена формула:
=ЕСЛИ (ИЛИ(И (НЕ(C14);НЕ(D14)); И (C14; D14))=ИСТИНА; 1; 0).
Функция ЕСЛИиспользуется лишь для преобразования значения «ИСТИНА» в 1, а значения «ЛОЖЬ» в0.
В ячейку K23введена формула:
=ЕСЛИ (K22=1;«Числа равны»; «Числа не равны»).
Для тогочтобы случайно что-то не испортить на листе, лист защищен, кроме ячеек, вкоторые вводятся сравниваемые числа. Эти ячейки выделены, и выполнена командаФормат, Ячейка, на вкладке Защита снят флажок Защищаемая ячейка. Затемвыполнена команда Сервис, Защита, Защитить лист.
На рисунке 7.3показан вариант, когда на входы схемы аi, и bi поступают двануля, на выходе схемы имеем q1 (числа равны). Подавая на входы другиекомбинации 0 и 1, можно увидеть, что схема работает точно так, как описываеттаблица истинности. Можно дополнительно ввести формулы для проверки сигналов навыходах любых элементов схемы.
Многоразряднаясхема сравнения кодов
Признакравенства двухразрядных чисел q принимает значение 1, если выполняетсяпопарно равенство всех разрядов двоичных чисел.
Для примераприведена двухразрядная схема (рисунок 7.7), что связано лишь с тем, чтонеудобно рассматривать работу схемы, если она выходит за пределы экрана.Двухразрядная схема состоит из двух одноразрядных схем.
Ячейки C7и D7 отведены для поразрядного ввода первого числа, им присвоены имена a1и а0 соответственно. Ячейки E7 и F7 отведены для вводавторого числа, им присвоены имена b1 и b0 соответственно.
В ячейку L7введена формула для выдачи результата сравнения старших разрядов чисел:
=ИЛИ (И(НЕ(C7);НЕ(E7)); И (C7; E7)).
В ячейку L46введена формула для выдачи результата сравнения младших разрядов чисел:
=ИЛИ (И(НЕ(F7);НЕ(D7)); И (F7; D7)).
В ячейку O22введена формула для выдачи признака равенства чисел:
=ЕСЛИ (И(L46;L7)=ИСТИНА; 1; 0).
В ячейку O23введена формула для выдачи сообщения о результате сравнения чисел:
=ЕСЛИ (O22=1;«Числа равны»; «Числа не равны»).
/>
Рисунок 7.7 –Двухразрядная схема сравнения кодов
На рисунке 7.7представлен результат сравнения чисел 10 и 11. На экране результат сравненияравен 0 и выдано сообщение «Числа не равны».

7.2.2 Дешифраторы
Дешифратором(избирательной схемой) называется комбинационная логическая схема, в которойопределенная комбинация входных сигналов вызывает появление сигнала на однойопределенной выходной шине.
Есликоличество двоичных разрядов дешифрируемого числа обозначить через n, то число выходовдешифратора равно К = 2n.
В компьютерес помощью дешифраторов осуществляется выборка необходимых ячеек запоминающихустройств, расшифровка кода операции с подачей управляющих сигналов на теэлементы, узлы и устройства машины, которые связаны с выполнением данной операции.
Дешифраторна 2 входа
Функционированиедешифратора, имеющего 2 входа и 4 выхода, описывается таблицей истинности,представленной на рисунке 7.8.
Выражения дляфункций F1, F2, F3, F4 в виде СДНФ, реализуемые соответствующимивыходами схемы: />, />, />, />.
Упрощениевыражения не требуется, пункт 3 порядка проектирования логических схемотсутствует.
Схема имеетвид, представленный на рисунке 7.8.

/>
Рисунок 7.8 –Дешифратор на 2 входа
Ячейки C13и D13 отведены для ввода комбинации входных сигналов. Им присвоены именаа и b соответственно.
Установленапроверка данных на корректность (ввод только 0 и 1).
В ячейку J19введена формула:
=И (НЕ(C13); НЕ(D13)).
В ячейку J26введена формула:
=И (НЕ(C13); D13).
В ячейку J32введена формула:
=И (НЕ(D13); C13).
В ячейку J38введена формула:
=И (C13; D13).
В ячейки J20,J27, J33, J39 введены формулы для преобразования значения«ИСТИНА» в 1, а значения «ЛОЖЬ» в 0.
Лист защищен,за исключением ячеек, в которые вводится входной код.
На рисунке 7.8показан вариант, когда на входы схемы а и b поступают 0 и 0соответственно. Сигнал 1 появляется лишь на выходе F1.
Подавая навходы другие комбинации 0 и 1, можно увидеть, что схема работает точно так, какописывает таблица истинности. Можно дополнительно ввести формулы для проверкисигналов на выходах любых элементов схемы.
Для большейнаглядности на рабочем листе снята сетка, для чего выполнена команда Сервис,Параметры и на вкладке Вид снят флажок Сетка.
С помощьюданной схемы легко показать (безусловно, упрощенно) применение дешифратора длярасшифровки кодов операций. Примите соглашение, что код 00 соответствуетсложению, 01 – вычитанию, 10 – делению, 11 – умножению. Вместо обозначенийвыходов Fl, F2, F3 и F4 сделайте подписи«Сложение», «Вычитание», «Деление», «Умножение». Тогда при появленииопределенной комбинации входных сигналов кода операции на входе дешифраторабудет показано, какую операцию следует выполнять, так как 1 появится лишь навыходе, соответствующем этой операции. Безусловно, следует сказать, что,например, дешифратор на 8 входов, имеющий полный набор выходных шин, сможетрасшифровать 28 = 256 различных кодов операций.
/> 
7.3 Заданияк работе
1. Выполнитьлогическое проектирование дешифратора на четыре входа и четыре выхода поиндивидуальному заданию, приведённому в таблице 7.3 [15].
2. Для однойиз предложенных булевых функции системы:
Написать СКНФпо данным таблицы 7.3.
Написать СДНФпо данным таблицы 7.3.
Минимизироватьбулеву функцию методом Квайна.
Минимизироватьбулеву функцию, используя карты Карно.
3. Сравнитьрезультаты минимизации.
4. Выполнитьлогическое проектирование схемы, реализующей минимальную булеву функцию,используя элементы на два входа и один выход.
5. Длясистемы частично определённых булевых функций (таблица 7.2): минимизировать ихописание, используя карты Карно.
Выполнитьлогическое проектирование схемы, реализующей минимизированную систему булевыхфункций, используя элементы на два входа и один выход.
Таблица 7.2 –Значение частично определённых функций fi (x1; x2; x3; x4)Аргумент
Индекс i логической функции fi (x1; x2; x3; x4)
x1
x2
x3
x4 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 1 1 1 1 * * * * 1 1 * * * * 1 1 1 1 1 * * * * * * * * 1 1 1 1 1 1 1 1 * * * * * * 1 1 1 1 * 1 1 1 1 1 1 * * * * 1 1 1 1 * * 1 1 1 1 1 1 * * 1 1 1 1 1 * * * 1 1 1 1 1 1 1 1 1 1 1 * * * * 1 1 1 1 1 1 1 1 1 1 1 * * * * 1 1 1 1 1 1 1 1 * * * * 1 1 1 1 1 1 1 1 * * * * 1 1 1 1 1 1 1 1 * * * * 1 1 1 1 1 1 1 1 1 1 * * * * 1 1 1 1 1 1 1 1 1 1 * * * * 1 1 1 1 1 1 1 1 1 1 1 1 * * * * 1 1 1 1 1 1 * 1 1 1 1 1 1 * * * * 1 1 1 1 1 1 * * 1 1 1 1 1 1 1 * * * * 1 1 1 1 * * *
Аргмент
Индекс i логической функции fi (x1; x2; x3; x4)
x1
x2
x3
x4 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 * * 1 1 1 1 1 1 1 1 1 1 * * * * 1 1 1 1 1 1 1 1 1 1 * * * * * * 1 1 1 1 1 1 1 1 1 * * * * * * * * 1 1 1 1 1 1 1 1 1 * * * * 1 * * * * 1 1 1 1 1 1 * * * * 1 1 * * * * 1 1 1 1 1 1 * * * * 1 1 1 * * * * 1 1 1 1 * * * * 1 1 1 1 * * * * 1 1 1 1 * * * * 1 1 1 1 1 * * * * 1 1 * * * * 1 1 1 1 1 1 * * * * 1 1 1 * * * 1 1 1 1 1 1 1 * * * 1 1 1 * * 1 1 1 1 1 1 1 1 * * 1 1 1 1 * 1 1 1 1 1 1 1 1 1 * Аргумент
Индекс i логической функции fi (x1; x2; x3; x4)
x1
x2
x3
x4 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 * * * * * * * * 1 1 1 1 1 1 1 * * * * * * * * 1 1 1 1 1 1 1 * * * * * * 1 1 1 1 1 1 1 1 * * * * 1 1 1 1 1 1 * 1 1 * * 1 1 1 1 1 1 * * 1 1 1 1 1 1 1 1 1 1 * * * 1 1 1 1 1 1 1 1 1 1 1 * * * * 1 1 1 1 1 1 1 1 1 1 1 1 1 * * * * 1 1 1 1 1 1 1 1 1 1 1 1 * * * * 1 1 1 1 1 1 1 1 1 1 1 1 * * * * 1 1 1 1 1 1 1 1 1 1 * * * * 1 1 1 1 1 1 1 1 1 1 * * * * 1 1 1 1 1 1 1 1 * * * * 1 1 1 1 1 1 * 1 1 * * * * 1 1 1 1 1 1 1 * * * * * * 1 1 1 1 1 1 1 1 1 * * * * * * * 1 1 1 1 1 1 Таблица 7.3 Вариант Логические функции 1
(f2; f1; f3; f4) 2
(f4; f3; f5; f6) 3
(f6; f5; f7; f8) 4
(f8; f7; f9; f10) 5
(f10; f9; f11; f12) 6
(f12; f11; f13; f14) 7
(f14; f13; f15; f16) 8
(f16; f15; f17; f18) 9
(f18; f17; f19; f20) 10
(f20; f19; f21; f22) 11
(f22; f21; f23; f24) 12
(f24; f23; f25; f26) 13
(f26; f25; f27; f28) 14
(f28; f27; f29; f30) 15
(f30; f29; f1; f2) 16
(f1; f3; f5; f7) 17
(f3; f5; f7; f9) 18
(f5; f7; f9; f11) 19
(f7; f9; f11; f13) 20
(f9; f11; f13; f15) 21
(f11; f13; f15; f17) 22
(f13; f15; f17; f19) 23
(f15; f17; f19; f21) 24
(f17; f19; f21; f23) 25
(f19; f21; f23; f25) 26
(f21; f23; f25; f27) 27
(f23; f25; f27; f29) 28
(f25; f27; f29; f1) 29
(f27; f29; f1; f3) 30
(f29; f1; f3; f5)

/>7.4 Вопросы для самопроверки
1) Вычислениепо алгоритму можно рассматривать как некоторый процесс. Перечислите три впринципе различных процесса.
2) Какимимножествами описывается конечный автомат?
3) С рядомкаких упрощающих предположений связано понятие конечного автомата?
4) Какиевопросы рассматриваются в теории автоматов?
5)Математической моделью каких устройств является конечный автомат?
6) Приведитепример конечного и бесконечного автоматов.
7) Дайтеопределение логического конечного автомата.
8) Какие Вызнаете стандартные обозначения элементов, используемые при составлениилогических схем?
9) Какиеклассы логических конечных автоматов Вы знаете?
10) Что такоетакт логического конечного автомата?
11) Приведитепример конечного автомата без памяти.
12) Приведитепример конечного автомата с памятью.
13) Приведитепример конечного автомата с обратной связью по выходу.
14) В чёмзаключается задача минимизации числа состояний автомата?

/>/>Список литературы
 
1   Р. ХаггартиДискретная математика для программистов Москва: Техносфера, 2003. – 320 с.
2   Гончарова Г.А., Мочалин А.А. Элементыдискретной математики: Учебное пособие. – М.: ФОРУМ: ИНФРА‑М, 2004. -128 с.
3   Романовский И.В. Дискретныйанализ. Учебное пособие для студентов, специализирующихся по прикладнойматематике и информатике. Издание 2‑е, исправленное, – СПб.: Невский диалект, 2000 г. -240 с., ил.
4   Д. Кнут Искусствопрограммирования для ЭВМ, т. 2, М.: Мир, 2000.
5   Новиков Ф.А. Дискретнаяматематика для программистов. – СПб.: Питер, 2001. – 304 с.: ил.
6   Ламуатье Ж.‑П. Упражненияпо программированию на Фортране IV, М.-Мир, 1978. – 168 с.: ил.
7   Светозарова Г.И. идр. Практикум по программированию на языке Бейсик: Учеб. пособие для вузов. – М.:Наука. Гл. ред. физ.-мат. лит., 1988. – 368 с.
8   Зеленяк О.П. Практикумпо программированию на Turbo Pascal. Задачи, алгоритмы и решения – К.: Издательство«ДиаСофт», 2001. – 320 с.
9   Абрамов С.А., Гнездилова Г.Г.и др., Задачи по программированию, М., Наука. Гл. ред. физ.-мат. лит., 1988. –224 с.
10       Абрамов С.А.,Зима Е.В. Начала информатики. – М., Наука. Гл. ред. физ.-мат.лит., 1989. – 224 с.
11       Юркин А.Г. Задачникпо программированию. – СПб.: Питер, 2002. – 192 с.
12       ХаггартиДискретная математика для программистов Москва: Техносфера, 2006. 350 с.
13       Шапорев С.Д. Математическаялогика. Курс лекций и практических занятий – СПб.: БХВ-Петербург, 2005. – 415 с. 6ил.
14       ВиртА. Алгоритмы и структуры данных: Пер. с англ., М.: Мир, 1989 – 360 с., ил.
15       Шестаков А.А.,Дружинина О.В. Дискретная математика. Часть I, II. М. РГОТУПС, 1998. ЧастьIII М. РГОТУПС, 1999.
16       Могилёв А.В.и др. Информатика: Учеб. Пособие для студентов пед. вузов под ред. Хённера Е.К.– М., 1999. – 816 с.
17       Коршунов Ю.М. Математическиеосновы кибернетики: Учебное пособие для вузов – М., Энергоатомиздат, 1987. –496 с.: ил.
18       Евстигнеев В.А. Применениетеории графов в программировании, М.,: Наука, 1985.
19       ОреО. Теория графов. – М.: Наука, 1980.
20       Справочникпо математике для экономистов под общ. ред. Ермакова – М.: Финансы истатистика, 1988
21       Судоплатов С.В.,Овчинникова Е.В. Элементы дискретной математики: Учебник. – М.: ИНФРА– М; Новосибирск: НГТУ, 2003. – 280 с. – (Серия «Высшее образование»)
22       Емельянов В.И.,Воробьёв В.И., Тюрина Т.П., Основы программирования на Delphi:Учебное пособие для вузов; Под ред. В.М. Чёрненького. – М.: Высш. шк.,2005.-231 с.: ил.
23       Тюрина Т.П.,Емельянов В.И. Дискретная математика (часть 1). Учебное пособие, НИРХТУ им. Д.И. Менделеева, Новомосковск, 2004, 94 с.
24       Тюрина Т.П.,Емельянов В.И. Дискретная математика (часть 2). Учебное пособие, НИРХТУ им. Д.И. Менделеева, Новомосковск, 2004, 34 с.
25       Тюрина Т.П.,Емельянов В.И. Дискретная математика (часть 3). Учебное пособие, НИРХТУ им. Д.И. Менделеева, Новомосковск, 2005, 60 с.