Избранные главы дискретной математики

 

• Произведением нечётких множеств 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. Из чего следует, что нужная нам карточка лежит во второй половине оставшейся пачки. Таким образом, при каждом сравнении, мы уменьшаем зону поиска в два раза. Отсюда и название метода - половинного деления или дихотомии.

   Скорость сходимости этого алгоритма пропорциональна . Это означает буквально то, что не более, чем через сравнений, мы либо найдем нужное значение, либо убедимся в его отсутствии.

 

   §6 Теория графов

   Теория  графов — раздел дискретной математики, изучающий свойства графов. Первая работа по теории графов принадлежит Леонарду Эйлеру. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Но термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг.

   Графами называются схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых.

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

   Графы, в которых не построены все  возможные ребра , называются неполными графами. В противном случае граф называется полным.

   Если полный граф имеет n вершин, то количество ребер будет равно .

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

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

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

   Путь в графе (иногда говорят простой путь) – это маршрут без повторения вершин (а значит, и ребер).

   Контур – это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней.

 

                                                                                     Последовательности вершин (рис. 1): 1–2–3–4–2–5 не простой путь, а маршрут; последовательности 1–2–3–4–7–5 и 1–2–5 – простые пути; 1–2–3–4–2–5–6–1 –это цикл (но не контур); 1–2–5–6–1 – это контур. 
 

Рис.2

   Граф  называется связным, если любые две его вершины можно соединить маршрутом (или путем). На рис.2 изображен связный граф.

   Ребро, при удалении которого граф перестает  быть связным, иногда называют мостом или перешейком.

   Следующее определение имеет смысл только для графов или мультиграфов без петель (но не для орграфов).

   Степень вершины – это число ребер, входящих в эту вершину. Вершина называется висячей, если ее степень равна единице.

   Кликой в неориентированном графе называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это полный подграф первоначального графа. Размер клики определяется как число вершин в ней.

   Двудольный  граф или биграф — это математический термин теории графов, обозначающий граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части.

   Применение  теории графов

• Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.
• В химии (для описания структур, путей сложных реакций[1], правило фаз также может быть интерпретировано как задача теории графов); компьютерная химия — сравнительно молодая область химии, основанная на применении теории графов. Теория графов представляет собой математическую основу хемоинформатики. Теория графов позволяет точно определить число теоретически возможных изомеров у углеводородов и других органических соединений.
• В информатике и программировании
• В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете.
• В экономике
• В логистике 
  

   §7 Комбинаторика

   Термин "комбинаторика" был введён в  математический обиход Лейбницем.

   В 1666 году Лейбниц опубликовал "Рассуждения  о комбинаторном искусстве". В  своём сочинении Лейбниц, вводя  специальные символы, термины для  подмножеств и операций над ними находит все k -сочетания из n элементов  выводит свойства сочетаний.