Избранные главы дискретной математики
Содержание
§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
Оценок: 1000 (Средняя 5 из 5)
Одними из наиболее популярных услуг на рынке IT-технологий являются создание и продвижение лендингов. Они способны положительно влиять на деятельность любого бизнес-проекта в интернете. Судя по многочисленным отзывам, заказавшие создание лендингов люди ни разу не пожалели о потраченных деньгах. Они вложили в будущее, которое неразрывно связано с интернетом. Всё больше и больше предпринимателей обращаются к услугам разных агентств, веб-студий, чтобы заказать создание лендинга у профессионалов. © 2017 - 2022 ReferatWorld.ru
|