Избранные главы дискретной математики (стр. 1 из 7)
Содержание
§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 представляется как линейная комбинация:
где на коэффициенты ak (называемые как и прежде цифрами) накладываются некоторые ограничения.
Записью числа x в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса k, начиная с первого ненулевого.
Системы счисления разных народов
Древнеегипетская система счисления:
Древнеегипетская десятичная непозиционная система счисления возникла во второй половине третьего тысячелетия до н.э. Для обозначения чисел 0, 1, 10, 102, 103, 104, 105, 106, 107 использовались специальные цифры. Числа в египетской системе счисления записывались как комбинации этих цифр, в которых каждая из цифр повторялась не более девяти раз. Значение числа равно простой сумме значений цифр, участвующих в его записи.
Вавилонская система счисления:
Вавилонская система счисления применялась за две тысячи лет до н. э. Для записи чисел использовались всего два знака: прямой клин ↓ для обозначения единиц и лежачий клин ← для обозначения десятков внутри шестидесятиричного разряда. Новый шестидесятиричный разряд начинался с появлением прямого клина после лежачего клина, если рассматривать число справа налево:
↓↓ ←↓↓ = (60*2)+(10*1+2) = 13210
2-й 1-й разряды
Вначале нуля не было. Позже ввели обозначение для пропущенных шестидесятиричных разрядов, что соответствует появлению нуля, но в первом разряде справа этот знак не ставился, что приводило к неоднозначности записи чисел и для определения абсолютного значения числа требовались дополнительные сведения.
Греческая система счисления:
| 1 α | 10 ι | 100 ρ |
| 2 β | 20 κ | 200 σ |
| 3 γ | 30 λ | 300 τ |
| 4 δ | 40 μ | 400 υ |
| 5 ε | 50 ν | 500 φ |
| 6 ς | 60 ξ | 600 χ |
| 7 ζ | 70 ο | 700 ψ |
| 8 η | 80 π | 800 ω |
| 9 θ | 90 Ϙ | 900 Ϡ |
Греческая система счисления, также известная как ионийская или новогреческая — непозиционная система счисления, в которой, в качестве символов для счёта, употребляют греческие буквы, а также дополнительные символы, такие как ς (стигма), Ϙ (копа) и Ϡ (сампи).
Эта система пришла на смену аттической, или старогреческой, системе, которая господствовала в Греции в 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 Счетность и несчетность множества
Основные числовые множества:
Натуральные числа, получаемые при естественном счёте.
Множество натуральных чисел обозначается
, (иногда к множеству натуральных чисел также относят ноль, то есть).Целые числа получаемые объединением натуральных чисел с множеством отрицательных чисел и нулём, обозначаются
.Рациональные числа — числа, представленные в виде дроби
.Действительные (вещественные) числа представляют собой расширение множества рациональных чисел. Множество вещественных чисел обозначается
. Кроме рациональных чисел 
, включает множество иррациональных чисел 
, не представимых в виде отношения целых. Кроме подразделения на рациональные и иррациональные, действительные числа также подразделяются на алгебраические и трансцендентные. При этом каждое трансцендентное число является иррациональным, каждое рациональное число — алгебраическим.Для перечисленных множеств чисел справедливо следующее выражение:
Счетное множество
Множество А называется счетным, если оно равномощно множеству натуральных чисел
, то есть между множеством А и множеством натуральных чисел 
можно установить взаимно однозначное соответствие, или, как говорят, можно пронумеровать элементы множества А, понимая под номером каждого элемента А соответствующее ему при указанном соответствии натуральное число.Мощность множества вещественных чисел
называется континиуумом и обозначается 
(алеф).Счётное множество является «наименьшим» бесконечным множеством, то есть в любом бесконечном множестве найдётся счётное подмножество(минимум континиуума). Мощность множества всех натуральных чисел обозначается символом
(произносится: "алеф-нуль"). Примеры счетных множеств: