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

Содержание 

§1. Системы счисления……………………………….………………..……3

§2. Счетность и несчетность множеств………………………………6

§3. Трансфинитные числа и множества……………………………….10

§4. Теория нечетких множеств………………………………………….12

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

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

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

§8. Дискретизация…………………………………………………………..21

§9.Теория сложности алгоритмов………………………………………25

§10. Теория конечных автоматов………………………………….……26 

Список  литературы…………………………………………..…….…….…..29

§1 Системы счисления 

     Система счисления — символический метод записи чисел, представление чисел с помощью письменных знаков. 

     Система счисления:

• даёт представления множества чисел (целых или вещественных)
• даёт каждому числу уникальное представление (или, по крайней мере, стандартное представление)
• отражает алгебраическую и арифметическую структуру чисел.

     Системы счисления подразделяются на:

• позиционные,
• непозиционные,
• смешанные.

    В позиционных системах счисления один и тот же числовой знак (цифра) в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен. Изобретение позиционной нумерации, основанной на поместном значении цифр, приписывается шумерам и вавилонянам; развита была такая нумерация индусами и имела неоценимые последствия в истории человеческой цивилизации. К числу таких систем относится современная десятичная система счисления, возникновение которой связано со счётом на пальцах. В средневековой Европе она появилась через итальянских купцов, в свою очередь заимствовавших её у мусульман.

    Наиболее  употребляемыми в настоящее время  позиционными системами являются:

    1 — единичная (как позиционная  может и не рассматриваться;  счёт на пальцах, зарубки, узелки  «на память» и др.);

    2 — двоичная (в дискретной математике, информатике, программировании);

    3 — троичная;

    4 — четверичная;

    8 — восьмеричная;

    10 — десятичная (используется повсеместно);

    12 — двенадцатеричная (счёт дюжинами);

    16 — шестнадцатеричная (используется в программировании, информатике, а также в шрифтах);

    60 — шестидесятеричная (единицы измерения времени, измерение углов и, в частности, координат, долготы и широты).

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

    Смешанная система счисления является обобщением b-ричной системы счисления и также зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая последовательность чисел и каждое число x представляется как линейная комбинация: 
 
 

    где на коэффициенты a_k (называемые как и прежде цифрами) накладываются некоторые ограничения.

    Записью числа x в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса k, начиная с первого ненулевого. 

   Системы счисления разных народов

   Древнеегипетская  система счисления:

   Древнеегипетская  десятичная непозиционная система  счисления возникла во второй половине третьего тысячелетия до н.э. Для  обозначения чисел 0, 1, 10, 102, 103, 104, 105, 106, 107 использовались специальные цифры. Числа в египетской системе счисления  записывались как комбинации этих цифр, в которых каждая из цифр повторялась  не более девяти раз. Значение числа  равно простой сумме значений цифр, участвующих в его записи.

   Вавилонская система счисления:

   Вавилонская система счисления применялась  за две тысячи лет до н. э. Для записи чисел использовались всего два  знака: прямой клин ↓ для обозначения  единиц и лежачий клин ← для  обозначения десятков внутри шестидесятиричного разряда. Новый шестидесятиричный разряд начинался с появлением прямого клина после лежачего клина, если рассматривать число справа налево:

   ↓↓  ←↓↓ = (60*2)+(10*1+2) = 132₁₀

   2-й  1-й разряды

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

   Греческая система счисления:

Греческая система счисления, также известная  как ионийская или новогреческая  — непозиционная система счисления, в которой, в качестве символов для  счёта, употребляют греческие буквы, а также дополнительные символы, такие как ς (стигма), Ϙ (копа) и  Ϡ (сампи).

Эта система  пришла на смену аттической, или  старогреческой, системе, которая господствовала в Греции в III веке до н.э..

Необходимость сохранять порядок букв ради сохранения их числовых значений привела к относительно ранней (4 век до н.э.) стабилизации греческого алфавита.

   Римская система счисления:

   Каноническим  примером почти непозиционной системы  счисления является римская, в которой в качестве цифр используются латинские буквы:

   I обозначает 1,

   V — 5,

   X — 10,

   L — 50,

   C — 100,

   D — 500,

   M — 1000 

   Например, II = 1 + 1 = 2

   здесь символ I обозначает 1 независимо от места в числе.

   На  самом деле, римская система не является полностью непозиционной, так как меньшая цифра, идущая перед большей, вычитается из неё, например:

   IV = 4, в то время как:

   VI = 6 

   Еврейская система счисления

   Еврейская система счисления в качестве цифр используются 22 буквы еврейского алфавита. Каждая буква имеет своё числовое значение от 1 до 400. «Ноль» отсутствует. Наиболее часто можно встретить  цифры, записанные таким образом  в нумерации лет по иудейскому календарю. 

   Система счисления майя

   Майя  использовали 20-ричную систему счисления  за одним исключением: во втором разряде  было не 20, а 18 ступеней, то есть за числом (17)(19) сразу следовало число (1)(0)(0). Это было сделано для облегчения расчётов календарного цикла, поскольку (1)(0)(0) = 360 примерно равно числу дней в солнечном году.

   Для записи основными знаками были точки (единицы) и отрезки (пятёрки).

§2 Счетность и несчетность множества

   Основные  числовые множества:

   Натуральные числа, получаемые при естественном счёте.

   Множество натуральных чисел обозначается , (иногда к множеству натуральных чисел также относят ноль, то есть).  

   Целые числа получаемые объединением натуральных чисел с множеством отрицательных чисел и нулём, обозначаются.  

   Рациональные  числа — числа, представленные в виде дроби

   . 

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

   Для перечисленных множеств чисел справедливо  следующее выражение: 
 

Счетное множество

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

     Мощность  множества вещественных чисел  называется континиуумом и обозначается (алеф).

     Счётное множество является «наименьшим» бесконечным  множеством, то есть в любом бесконечном  множестве найдётся счётное подмножество(минимум континиуума). Мощность множества всех натуральных чисел обозначается символом (произносится: "алеф-нуль"). 

   Примеры счетных множеств:

• Натуральные числа
• Целые числа
• Рациональные числа
• Алгебраические числа
• Простые числа
• Целочисленные координаты декартовой плоскости

   Свойства:

• Любое подмножество счётного множества конечно или счётно.
• Объединение конечного или счётного числа счётных множеств счётно.
• Декартово произведение двух счетных множеств счетно.
• Множество всех конечных подмножеств счётного множества счётно.
• Множество всех подмножеств счётного множества континуально и, в частности, не является счётным.

      Многие доказательства счетности множеств можно провести с помощью их диагональной записи, предложенной Г. Кантором. Так Кантор доказал счетность множества рациональных чисел: 
 
 
 
 
 
 
 
 
 
 
 
 

     Бесконечное множество рациональных чисел (т.е. чисел, которые можно представить  как частное двух целых чисел) могло бы показаться значительно  бóльшим, чем множество целых чисел. Например, между двумя любыми соседними целыми числами, допустим 0 и 1, имеется бесконечно много рациональных чисел. Тем не менее в 1874 г. Кантор показал, что рациональные числа можно одно за другим объединить в пары с целыми числами. Всякое рациональное число можно разместить в квадратной таблице, как показано на рисунке. Тогда каждое из них может быть связано с целым числом путём проведения цветной линии. Таким образом, множество рациональных чисел является счётным.

     Всякое  множество чисел, элементы которого можно расположить один за другим или фактически сосчитать, используя множество целых положительных чисел, Кантор назвал счётным множеством. 
 

     Несчетные множества 

     Множество, не являющееся конечным или счетным, называется несчетным. 

     Примеры несчетных множеств:

• Вещественные числа
• Комплексные числа

     Доказательство  существования несчетных  множеств.

     Множество всех действительных чисел несчетно и равномощно интервалу (0,1). Докажем несчетность последнего.

     Будем считать известным, что каждое число  интервала (0, 1) записывается в виде конечной или бесконечной десятичной дроби вида 

     0, a₁ a₂ a₃ ... 

     При этом хотя бы одна из цифр a_i отлична от нуля (т. к. число 0 = 0,000... не принадлежит интервалу). Далее, для чисел, имеющих запись в виде конечной десятичной дроби, существует и другая запись, где все цифры a_i, начиная с некоторого места, равны 9. Например, 

     0,53000... = 0,52999... 

     Остальные числа (т. е. иррациональные и те рациональные, которые разлагаются в периодическую  дробь с периодом, не равным 9) имеют  единственную запись. Из двух возможных  записей для первых чисел выберем  какую-нибудь одну, например, в виде конечной десятичной дроби. Тогда все  числа интервала (0, 1) будут единственным образом записываться в виде 

     0, a₁ a₂ a₃ ..., 

     где не все a_i равны 0 и никогда все цифры, начиная с некоторой, не могут равняться 9. Обратно, всякая десятичная дробь дает число интервалов (0, 1).

       Легко видеть, что интервал (0, 1) есть бесконечное множество, т. к. он содержит множество 
 

     равномощное множеству натуральных чисел. Покажем, что (0, 1) не является счетным множеством.

     Предположим обратное. Тогда все числа интервала  можно занумеровать так: 

     (0, 1) = {c₁, c₂, c₃, ...}. 

     Запишем каждое число десятичной дробью указанного вида: 

        (1.1) 

     Построим  число 

     c = 0, b₁ b₂ b₃ ... 

следующим образом: берем цифру b₁, отличную от a₁₁, 0 и 9; берем b₂, отличную от a₂₂, 0 и 9; b₃, отличную от a₃₃, 0 и 9; b_n, отличную от a_nn, 0 и 9, ... Наличие десяти цифр оставляет для такого выбора достаточно возможности (именно, каждый раз в нашем распоряжении остается еще семь цифр). Дробь 0, b₁ b₂ b₃... обладает нужными свойствами и даже в усиленной форме — она вовсе не имеет цифр 0 и 9. Значит, число c принадлежит интервалу (0, 1). Но запись c отлична от записей всех чисел (1.1). В самом деле, запись c отличается от c₁, т. к. b₁ ≠ a₂₂, от c₂, т. к.  и т. д. Но дробью нашего типа числа интервала записываются однозначно. Значит, 

     c ≠ c₁, c ≠ c₂, c ≠ c₃,.., c ≠ c_n,… 

     Оказалось, что число c не входит во множество чисел (1.1), тогда как мы предположили, что в (1.1)перенумерованы все числа интервала. Полученное противоречие доказывает наше утверждение. 

§3 Трансфинитные числа и множества

     Порядковое  число, или трансфинитное число, или ординал в теории множеств — некоторое обобщение понятия натурального числа «за пределы бесконечности».  

     История

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

     Между точками плоскости и точками  прямой можно установить взаимно  однозначное соответствие.

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

     Затем эти группы комбинируются и превращаются в одну бесконечную десятичную дробь, представляющую точку на плоскости. Вся процедура обратима.

     Трансфинитные числа, введённые в конце концов Кантором, широко известны в обозначении, которое он принял для них позже: в виде буквы א (алеф) — первой буквы еврейского алфавита. Этой буквой обозначается мощность, или число элементов бесконечного множества, так что отношения эквивалентности между бесконечными множествами, которые Кантор доказал в 70-х годах, часто выражают через трансфинитные кардинальные числа, алефы. Поэтому значительный исторический интерес представляет то, что первыми трансфинитными числами были не кардинальные числа, а ординальные.

     Ординальное число определяется его порядком или положением в некотором перечне. Этот перечень порождается в соответствии с двумя принципами.

     Во-первых, каждое новое ординальное число получается из непосредственно предшествующего ординального числа добавлением одной единицы, в точности также как если бы мы «считали» за пределами трансфинитного ординального числа ω, т.е. числа, связанного с множеством целых чисел, расположенных в их естественном порядке.

     Во-вторых, если существует последовательность трансфинитных ординальных чисел, у которой нет наибольшего числа, то новое ординальное число определяется как следующее число, большее всех остальных чисел последовательности. Такие числа помещаются в перечне непосредственно после отметки пропуска. Например, 2ω представляет собой следующее трансфинитное ординальное число, большее всех чисел ω, ω+1, ω+2, ... На рисунке представлены два примера множеств, соответствующих ординальным числам ω, ω+1, ω+2, и 2ω. Однако всякое бесконечное множество, представляемое ординальным числом этого перечня, имеет одно и то же кардинальное число, а именно 0א, другими словами, каждое множество содержит одно и то же число элементов.

     Ординальное число, ассоциируемое с конечным множеством, соответствует кардинальному  числу этого множества. Например, всякое множество, состоящее из пяти элементов (т.е. всякое множество, кардинальное число которого равно пяти), можно в некотором роде мыслить как непосредственно следующее за любым множеством из четырёх элементов. Другими словами, ординальное число этого множества тоже равно пяти; оно является пятым множеством в перечне множеств. Однако ординальное число бесконечного множества следует отличать от его кардинального числа. Кантор показал, что можно построить бесконечное число бесконечных множеств, имеющих различные ординальные числа, но одно и то же кардинальное число. Фактически Кантор позднее сумел превратить это свойство бесконечных множеств в критерий отличия их от конечных множеств: множество конечно, если его кардинальное и ординальное числа совпадают.

     Кантор  показал, что ординальное число последовательности конечных множеств возрастающей величины 1, 2, 3, ... получается путём повторного прибавления единицы. Не существует наибольшего ординального числа, ассоциированного с последовательностью конечных множеств, но, так же как возможно определить иррациональное число π в виде предела последовательности рациональных чисел, можно, как считал Кантор, определить новое, трансфинитное ординальное число ω как первое число, следующее за всей последовательностью числе 1, 2, 3, ... . Как только ω определено, становится возможным путём последовательного прибавления единицы порождать другие трансфинитные ординальные числа: ω+1, ω+2, ω+3, ... . Поскольку у этой последовательности не существует наибольшего элемента, то можно представить следующее ординальное число ω+ω или 2ω в виде первого ординального числа, следующего за последовательностью ω+1, ω+2, ω+3, ... . Повторяя попеременно эти два принципа порождения, Кантор определил некую иерархию трансфинитных ординальных чисел: 

§4 Теория нечетких множеств

     Нечёткое (или размытое, расплывчатое, туманное, пушистое) множество — понятие, введённое Лотфи Заде в 1965 г. в статье «Fuzzy Sets» (нечёткие множества) в журнале «Information and Control». Л. Заде расширил классическое канторовское понятие множества, допустив, что характеристическая функция (функция принадлежности элемента множеству) может принимать любые значения в интервале [0,1], а не только значения 0 или 1.

     Определение

     Под нечётким множеством 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: