Избранные главы дискретной математики (стр. 3 из 7)

Определение

Под нечётким множеством A понимается совокупность

где X — универсальное множество, а

— функция принадлежности (характеристическая функция), характеризующая степень принадлежности элемента x нечёткому множеству A.

Функция

принимает значения в некотором вполне упорядоченном множестве M. Множество M называют множеством принадлежностей, часто в качестве M выбирается отрезок [0,1]. Если M = {0,1}, то нечёткое множество может рассматриваться как обычное, чёткое множество.

Для пространства рассуждения X и данной функции принадлежности

нечёткое множество определяется как

Функция принадлежности

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

Основные определения

Пусть A нечёткое множество с элементами из универсального множества X и множеством принадлежностей M = [0,1]. Тогда

· Носителем (суппортом) нечёткого множества supp A называется множество

.

· Величина

называется высотой нечёткого множества A. Нечёткое множество нормально, если его высота равна 1. Если высота строго меньше 1, нечёткое множество называется субнормальным.

· Нечёткое множество пусто, если

. Непустое субнормальное нечёткое множество можно нормализовать по формуле:

.

· Нечёткое множество унимодально, если

только на одном x из X.

· Элементы

, для которых , называются точками перехода нечёткого множества A.

Операции над нечёткими множествами

При M = [0,1]

· Пересечением нечётких множеств A и B называется наибольшее нечёткое подмножество, содержащееся одновременно в A и B:

· Произведением нечётких множеств A и B называется нечёткое подмножество с функцией принадлежности:

.

· Объединением нечётких множеств A и B называется наименьшее нечёткое подмножество, содержащее одновременно A и B:

· Суммой нечётких множеств A и B называется нечёткое подмножество с функцией принадлежности:

· Отрицанием множества A при M = [0,1] называется множество

с функцией принадлежности:

для каждого

.

§5 Алгоритмы сортировки и поиска

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

Ключ сортировки – поле, выбранное в качестве ключевого в последовательности однотипных записей.

Сортировка включением

Одним из наиболее простых и естественных методов сортировки является сортировка с простыми включениями. Пусть имеется массив ключей a₁, a₂, ..., a_n. Для каждого элемента массива, начиная со второго, производится сравнение с элементами с меньшим индексом (элемент a_i последовательно сравнивается с элементами a_i-1, a_i-2 ...) и до тех пор, пока для очередного элемента a_j выполняется соотношение a_j > a_i, a_i и a_j меняются местами. Если удается встретить такой элемент a_j, что a_j <= a_i, или если достигнута нижняя граница массива, производится переход к обработке элемента a[i+1] (пока не будет достигнута верхняя граница массива).

Можно сократить число сравнений, применяемых в методе простых включений, если воспользоваться тем фактом, что при обработке элемента a_i массива элементы

a₁, a₂, ..., a_i-1 уже упорядочены, и воспользоваться для поиска элемента, с которым должна быть произведена перестановка, методом двоичного деления.

Сортировка «методом пузырька»

Простая обменная сортировка (в просторечии называемая "методом пузырька") для массива a₁, a₂, ..., a_n работает следующим образом. Начиная с конца массива сравниваются два соседних элемента (a_n и a_n-1). Если выполняется условие a_n-1 > a_n, то значения элементов меняются местами. Процесс продолжается для a_n-1 и a_n-2 и т.д., пока не будет произведено сравнение a₂ и a₁. Понятно, что после этого на месте a₁ окажется элемент массива с наименьшим значением.

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

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

Сортировка выбором

При сортировке массива a₁, a₂, ..., a_n методом простого выбора среди всех элементов находится элемент с наименьшим значением a_i, и a₁ и a_i обмениваются значениями. Затем этот процесс повторяется для получаемых подмассивов a₂, a₃, ..., a_n, ... a_j, a_j+1, ..., a_n до тех пор, пока мы не дойдем до подмассива a_n, содержащего к этому моменту наибольшее значение.

Сортировка разделением (Quicksort)

Метод сортировки разделением был предложен Чарльзом Хоаром в 1962 г. Этот метод является развитием метода простого обмена и настолько эффективен, что его стали называть "методом быстрой сортировки - Quicksort".

Основная идея алгоритма состоит в том, что случайным образом выбирается некоторый элемент массива x, после чего массив просматривается слева, пока не встретится элемент a_i такой, что a_i > x, а затем массив просматривается справа, пока не встретится элемент a_j такой, что a_j < x. Эти два элемента меняются местами, и процесс просмотра, сравнения и обмена продолжается, пока мы не дойдем до элемента x. В результате массив окажется разбитым на две части - левую, в которой значения ключей будут меньше x, и правую со значениями ключей, большими x. Далее процесс рекурсивно продолжается для левой и правой частей массива до тех пор, пока каждая часть не будет содержать в точности один элемент.

Алгоритм поиска по бинарному дереву

Суть этого алгоритма достаточно проста. Представим себе, что у нас есть набор карточек с телефонными номерами и адресами людей. Карточки отсортированы в порядке возрастания телефонных номеров. Необходимо найти адрес человека, если мы знаем, что его номер телефона 222-22-22. Берем карточку из середины пачки, номер карточки 444-44-44. Сравнивая его с искомым номером, мы видим, что наш меньше и, значит, находится точно в первой половине пачки. Откладываем вторую часть пачки в сторону, она нам не нужна, массив поиска мы сузили ровно в два раза. Теперь берем карточку из середины оставшейся пачки, на ней номер 123-45-67. Из чего следует, что нужная нам карточка лежит во второй половине оставшейся пачки. Таким образом, при каждом сравнении, мы уменьшаем зону поиска в два раза. Отсюда и название метода - половинного деления или дихотомии.