МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИКИЇВСЬКА ДЕРЖАВНА АКАДЕМІЯ ВОДНОГО ТРАНСПОРТУіменігетьмана Петра-Конашевича Сагайдачного КОНТРОЛЬНАРОБОТАЗ ДИСЦИПЛІНИ “ Моделюванняінформаційних потоків ”
студента 5 курсу
заочноговідділення спеціальності
“Менеджменторганізацій”К И ЇВ — 2 0 06
1. Сортировка вставками
Пусть надо упорядочить N элементов R1, R2…Rn.
Назовем их записями, а всю совокупность N назовем файлом. Каждаязапись Rjимеет свой ключ Kj, который и управляет процессом сортировки.Помимо ключа, запись может содержать дополнительную«сопутствующую информацию», которая не влияет на сортировку, но всегдаостается в этой записи.
Отношение порядка «
1) справедливо одно и толькоодно из соотношений: а
2) если а
Эти 2 свойства определяют математическое понятие линейногоупорядочения, которое называют еще совершенным упорядочением. Любоемножество с отношением «
Задача сортировки — найти такую перестановку записей p(1), p(2), p(n) после К ключи расположились бы в неубывающем порядке:
Kp(1)
Сортировка называется устойчивой, еслиона удовлетворяет дополнительному условию, что записи с одинаковымиключами остаются в прежнего порядке, то есть:
Р(i)
Обычно сортировку подразделяют на 2 класса:
• внутреннюю, если записи, которыесортируются, находятся в операционной памяти;
• внешнюю, если некоторые иззаписей, которые сортируются, находятся во вспомогательной памяти.
Ограничим нашерассмотрение лишь внутренними сортировками. Алгоритмы сортировки можноподразделить на несколько групп:
A. Сортировка вставками.Элементы просматриваются по одному, и каждый новый
элементвставляется в подходящее место среди ранее упорядоченных элементов.
B. Обменная сортировка.Если два элемента расположены не по порядку, то они
меняютсяместами. Этот процесс повторяется до тех пор, пока элементы не будутупорядочены.
C. Сортировка посредством выбора.Сначала выделяется наименьший (или, может быть,
наибольший) элемент и каким-либо- образом отделяется от остальных, затемвыбирается
наименьший(наибольший) из оставшихся и так далее.
Д. Сортировка подсчетом.Каждый элемент сравнивается со всеми остальными, окончательное положение элементаопределяется подсчетом числа наименьших ключей.
Е. Специальная сортировка, которая хороша длянескольких элементов, но не поддается простому обобщению на случай большегочисла элементов.
Сортировка выполняется илинад самими записями, или над указателями некоторой вспомогательной таблицы,например, рассматриваем рис.1, на котором представлен файл с 5 записями. Если этот файл отсортировать ввозрастающем порядке по указанному числовому ключу, то результирующий файл будет таким, как показано на рис.2. В этомслучае были отсортированы и сами записи.
/>
Если записи и/или ключи занимают несколькослов памяти, то часто лучше составить новую таблицу адресов(ссылок), которые указывают на записи и работают с этими адресами, не перемещаягромоздкие записи. Такой метод называется сортировкой таблицы адресов.
/>
Если ключи короткие, а сопутствующаяинформация в записях велика, то для повышения скорости ключи можно вынести втаблицу адресов; это называется сортировкой ключей. Другие схемысортировки используют вспомогательное поле связи, которое включается в каждую запись.Связи обрабатываются т.о., что в результате все записи оказываются связанными влинейный список, в котором каждая связь указывает на следующую попорядку запись. Это называется сортировкой списка.
/>
Достаточно хороший алгоритм затрачивает на сортировку N записей время порядка NlogN; при этом требуетсяоколо log N «проходов» по данным.
При N--»oo время работает на N (log)2, если все ключи различны, так каки размеры ключей увеличиваются с ростом N, но практически N всегда остаетсяограниченным.
Сортировкавставками.
Простые вставки. Пусть 1
Будем сравнивать по очереди Kj с Kj-1 Kj-2>… дотех пор, пока не обнаружим, что запись Rj следует вставить в R1 и R1+i; тогда подвинем записи Ri+1, ..., Rj-1 на одно место вверх ипоместим новую запись в позицию i+1. Удобно совмещать операции сравнения и перемещения,перемежая их друг с другом. Поскольку запись Rj как бы «проникает наположенный ей уровень», этот способ частоназывают просеиванием или погружением.
Алгоритм (Сортировка простыми вставками). Записи R1...,RN переразмещаются на том жеместе; после завершения сортировки их ключи будут упорядочены: К1
Шаг 1 [Циклпо j]. Выполнить шаги 2-5 приj=2,3,...,N и после этого завершитьалгоритм.
Шаг 2 [Установить i, К, R]. Установить i=j-l,K=Kj, R=Rj. (В последующих шагах мыпопытаемся вставить запись R в нужное место, сравнивая К с Кi при убывающих значениях i).
Шаг 3 Сравнить К, K1. Если К > Ki, то перейти к шагу 5 (Мынашли искомое место для записи R).
Сортировка простыми вставками.
98 12 13 7 3 21 99 128
j=2 K2=
i=l K=12 R=R2
R2=R1 i=0
12 98 13 7 321 99 128
j=3
i=2 K=K3=13 R=R3 R3=R2i=2
12 13 98 7 3 2199 128
j=4
i=3 K=K4=7 R=R4 R4=R3 i=3
12 13 7 98
j=2
i=l K=K2=13 R=R2
12 13 7 98
j=3
i=2 K=K3=7 R=R3 R3=R2i=2
12 7 13 98
j=4
i=3 K=K4=98 R=R4
12 7 13 98
j=2
i=l K=K2=7 R=R2 R2=R1 i=0
7 12 13 98
j=3
i=2 K=K3=13R=R3
7 12 13 98
j=4
i=3 K=K4=98R=R4
7 12 13 98
10 просмотров.
Шаг 4 [Переместить Ri, уменьшить i]. Установить Ri+1=Ri, i =i-l. Если i>0, то вернуться кшагу 3. (Если i=0,то К — наименьший из рассмотренных до сих пор ключей, а значит, запись R должназанять первую позицию).
Шаг 5 [R на место Ri+1]. Установить Rj+1= R
2. Сортировка Бетчера
Параллельная сортировка Бэтчера.Если мы хотим получить, алгоритм Обм. С, время работы которого имеет порядок, меньший N2, то нужно подбирать длясравнений некоторые пары несоседних ключей (Кi, Kj).
Схема сортировки Бетчеранесколько напоминает сортировку Шелла, но сравнения выполняютсяпо новому, так что распространение обменов не обязятельно. Метод Бэтчераназывают еще «Обм. С со слиянием», так как в нем происходит слияние паротсортированных последовательностей.
Алгоритм (Бэтчера). Записи R1 ..., Rn переразмещаются на том же месте; после завершениясортировки их ключи будут упорядочены K1 2.
Шаг 1 [Начальная установка р]. Установить р=2t-1 где t=[log2N] — наименьшее целоечисло такое, что 2t>N. Шаги 2-5 будут выполняться с р=2t-1 ,2t-1,… 1.
Шаг 2 [Начальная установка q, г, d]. Установить q=2t-1, r=0, d=p.
Шаг 3 [Цикл по i]. Для всех i, таких, что o
Так, 13A21=(1101)2A(10101)2=(00101)2=5.К этому моменту d — нечетное кратное р (т.е. частное от деления d на р нечетно), а р- степень двойки, так что i^p^=(i+d) ^p; (отсюда следует, чтодействия шага 4 можно выполнять при всех нужных значениях i в любом порядке или даже одновременно).
Шаг 4 [Сравнение / обмен Ri+1 и Ri+d+1]. Если Ki+1>Ki+d+1, то поменять местами Ri+1 и Ri+d+l
Шаг 5 [Цикл по q]. Если q=p, то установить d=q-p, q=q/2, r=p и возвратиться к шагу 3.
Шаг 6 [Цикл по р]. (К этомумоменту перестановка К1 К2,… KN будет р-упорядочена).Установить p=[p/2]. Если р>0, товозвратиться к шагу 2.
Быстрая сортировка Бетчера. В методе Бетчерапоследовательность сравнений предопределений каждый раз сравнивается одни и теже пары ключей независимо от того, что мы могли узнать о файле из предыдущихсравнений. Это утверждение в большей мере справедливо и применительно к методупузырька хоть алгоритм Бетчера и использует в ограниченой степени получениесведения, с тем, сократить количество работы в правом конце файла.
3. Структура, задачи и формализация предметной области
В основе логического моделирования лежитформальная система, задаваемая четвёркой вида М=. Множество Т — множествобазовых элементов различной природы. Дляэтого множества существует некоторый способ определения принадлежностиили не принадлежности любого элемента к этому множеству. Процедура проверки может быть любой, но за конечное числошагов она должна дать положительныйили отрицательный результат на вопрос, является ли х элементом множестваТ. Обозначим эту процедуру П(Т).
Множество Р — множество синтаксических правил. Сих помощью из элементов Т образуютсясинтаксически правильные совокупности. Существует процедура П(Р), с помощьюкоторой за конечное число шагов можно получить ответ на вопрос, является лисовокупность Xсинтаксически правильной.
В множестве синтаксически правильныхсовокупностей выделяется некоторое подмножествоА. Элементы А называются аксиомами. Процедура П(А) даёт ответ ка вопрос,принадлежит ли данная синтаксически правильная совокупность к множеству А.
Множество В — множество правил вывода. Применяяих к элементам А, можно получить новыесинтакагчески правильные совокупности, к которым можно применять правила из В. Если имеется процедура П(В), спомощью которой можно определить для любойсинтаксически правильной совокупности, является ли она выводимой, то соответствующая формальная система называется разрешимой.
Все предметы и события,которые составляют основу общего понимания необходимой для решениязадачи информации, называются предметной областью. Предметная областьпредставляется из реальных или абстрактных объектов, называемых сущностями.
Сущности предметной области находятсяопределённых отношениях друг к другу (ассоциациях),которые также можно рассматривать как сущности и включать в предметнуюобласть. Между сущностями наблюдаются различные отношения подобия. Совокупность подобных сущностей составляет класссущностей, являющийся новой сущностьюпредметной области.
Отношения между сущностями выражаются с помощьюсуждений. Суждение — это мысленновозможная ситуация, которая может иметь место для представляемых сущностей или не иметь места.
В языке суждения отвечают предложения. Сужденияи предложения также можно рассматривать как сущность и включать в предметнуюобласть.
Языки, предназначенные дляописания предметных областей, называются языками представлениязнаний. Универсальным языком представления знаний является естественный язык. Однакоиспользование естественного языка в системах машинного представления знаний наталкивается на большие трудности, связанные с двусмысленностью, нерегулярностью и т.д. Но главноепрепятствие заключается в отсутствии формальной семантики естественногоязыка, которая имела бы достаточно эффективнуюоперационную поддержку.
Для представленияматематического знания в математической логике давно пользуются исчислениемпредикатов, которое имеет ясную формальную семантику и операционную поддержку (разработаны механизмывывода).
Описания предметныхобластей, выполненные в логических языках, называются (формальными) логическимимоделями.