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

Содержание 

§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 Счетность и несчетность множества

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

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

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

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

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

   . 

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

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

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

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

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

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

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

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

   Свойства:

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