2. Сортировка Бетчера
Параллельная сортировка Бэтчера. Если мы хотим получить, алгоритм Обм. С, время работы которого имеет порядок, меньший N2, то нужно подбирать для сравнений некоторые пары несоседних ключей (Кi, Kj).
Схема сортировки Бетчера несколько напоминает сортировку Шелла, но сравнения выполняются по новому, так что распространение обменов не обязятельно. Метод Бэтчера называют еще «Обм. С со слиянием», так как в нем происходит слияние пар отсортированных последовательностей.
Алгоритм (Бэтчера). Записи R1 ..., Rn переразмещаются на том же месте; после завершения сортировки их ключи будут упорядочены K1 < ... < KN. Предполагается, что N>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<i<N-d и iAp=r выполнить шаг 4. Затем перейти к шагу 5. (Здесь через iAp обозначена операция "логические и" над двоичными представлениями чисел i и р; все биты результата равны 0, кроме тех, для которых в соответствующих позициях i и р находятся единичные биты.
Так, 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 синтаксически правильной.
В множестве синтаксически правильных совокупностей выделяется некоторое подмножество А. Элементы А называются аксиомами. Процедура П(А) даёт ответ ка вопрос, принадлежит ли данная синтаксически правильная совокупность к множеству А.
Множество В - множество правил вывода. Применяя их к элементам А, можно получить новые синтакагчески правильные совокупности, к которым можно применять правила из В. Если имеется процедура П(В), с помощью которой можно определить для любой синтаксически правильной совокупности, является ли она выводимой, то соответствующая формальная система называется разрешимой.
Все предметы и события, которые составляют основу общего понимания необходимой для решения задачи информации, называются предметной областью. Предметная область представляется из реальных или абстрактных объектов, называемых сущностями.
Сущности предметной области находятся определённых отношениях друг к другу (ассоциациях), которые также можно рассматривать как сущности и включать в предметную область. Между сущностями наблюдаются различные отношения подобия. Совокупность подобных сущностей составляет класс сущностей, являющийся новой сущностью предметной области.
Отношения между сущностями выражаются с помощью суждений. Суждение - это мысленно возможная ситуация, которая может иметь место для представляемых сущностей или не иметь места.
В языке суждения отвечают предложения. Суждения и предложения также можно рассматривать как сущность и включать в предметную область.
Языки, предназначенные для описания предметных областей, называются языками представления знаний. Универсальным языком представления знаний является естественный язык. Однако использование естественного языка в системах машинного представления знаний наталкивается на большие трудности, связанные с двусмысленностью, нерегулярностью и т.д. Но главное препятствие заключается в отсутствии формальной семантики естественного языка, которая имела бы достаточно эффективную операционную поддержку.
Для представления математического знания в математической логике давно пользуются исчислением предикатов, которое имеет ясную формальную семантику и операционную поддержку (разработаны механизмы вывода).
Описания предметных областей, выполненные в логических языках, называются (формальными) логическими моделями.
0 комментариев