Смекни!
smekni.com

Избранные главы дискретной математики (стр. 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 Счетность и несчетность множества

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

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

Множество натуральных чисел обозначается

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

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

.

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

.

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

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

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

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

Множество А называется счетным, если оно равномощно множеству натуральных чисел

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

Мощность множества вещественных чисел

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

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

(произносится: "алеф-нуль").

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