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

Содержание

§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 :

· Произведением нечётких множеств A и B называется нечёткое подмножество с функцией принадлежности:

.

· Объединением нечётких множеств A и B называется наименьшее нечёткое подмножество, содержащее одновременно A и B :

· Суммой нечётких множеств A и B называется нечёткое подмножество с функцией принадлежности:

· Отрицанием множества A при M = [0,1] называется множество с функцией принадлежности:

для каждого.

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

Задачей сортировки является преобразование исходной последовательности в последовательность, содержащую те же записи, но в порядке возрастания (или убывания) значений ключа.

Ключ сортировки – поле, выбранное в качестве ключевого в последовательности однотипных записей.

Сортировка включением

Одним из наиболее простых и естественных методов сортировки является сортировка с простыми включениями. Пусть имеется массив ключей a ₁ , a ₂ , ..., a_n . Для каждого элемента массива, начиная со второго, производится сравнение с элементами с меньшим индексом (элемент a_i последовательно сравнивается с элементами a_{i -1} , a_{i -2} ...) и до тех пор, пока для очередного элемента a_j выполняется соотношение a_j > a_i , a_i и a_j меняются местами. Если удается встретить такой элемент a_j , что a_j <= a_i , или если достигнута нижняя граница массива, производится переход к обработке элемента a[i+1] (пока не будет достигнута верхняя граница массива).

Можно сократить число сравнений, применяемых в методе простых включений, если воспользоваться тем фактом, что при обработке элемента a_i массива элементы

a ₁ , a ₂ , ..., a_{i -1} уже упорядочены, и воспользоваться для поиска элемента, с которым должна быть произведена перестановка, методом двоичного деления.

Сортировка «методом пузырька»

Простая обменная сортировка (в просторечии называемая "методом пузырька") для массива a ₁ , a ₂ , ..., a_n работает следующим образом. Начиная с конца массива сравниваются два соседних элемента (a_n и a_{n -1} ). Если выполняется условие a_{n -1} > a_n , то значения элементов меняются местами. Процесс продолжается для a_{n -1} и a_{n -2} и т.д., пока не будет произведено сравнение a ₂ и a ₁ . Понятно, что после этого на месте a ₁ окажется элемент массива с наименьшим значением.

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

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

Сортировка выбором

При сортировке массива a ₁ , a ₂ , ..., a_n методом простого выбора среди всех элементов находится элемент с наименьшим значением a_i , и a ₁ и a_i обмениваются значениями. Затем этот процесс повторяется для получаемых подмассивов a ₂ , a ₃ , ..., a_n , ... a_j , a_{j +1} , ..., a_n до тех пор, пока мы не дойдем до подмассива a_n , содержащего к этому моменту наибольшее значение.

Сортировка разделением (Quicksort)

Метод сортировки разделением был предложен Чарльзом Хоаром в 1962 г. Этот метод является развитием метода простого обмена и настолько эффективен, что его стали называть "методом быстрой сортировки - Quicksort".

Основная идея алгоритма состоит в том, что случайным образом выбирается некоторый элемент массива x, после чего массив просматривается слева, пока не встретится элемент a_i такой, что a_i > x, а затем массив просматривается справа, пока не встретится элемент a_j такой, что a_j < x. Эти два элемента меняются местами, и процесс просмотра, сравнения и обмена продолжается, пока мы не дойдем до элемента x. В результате массив окажется разбитым на две части - левую, в которой значения ключей будут меньше x, и правую со значениями ключей, большими x. Далее процесс рекурсивно продолжается для левой и правой частей массива до тех пор, пока каждая часть не будет содержать в точности один элемент.

Алгоритм поиска по бинарному дереву

Суть этого алгоритма достаточно проста. Представим себе, что у нас есть набор карточек с телефонными номерами и адресами людей. Карточки отсортированы в порядке возрастания телефонных номеров. Необходимо найти адрес человека, если мы знаем, что его номер телефона 222-22-22. Берем карточку из середины пачки, номер карточки 444-44-44. Сравнивая его с искомым номером, мы видим, что наш меньше и, значит, находится точно в первой половине пачки. Откладываем вторую часть пачки в сторону, она нам не нужна, массив поиска мы сузили ровно в два раза. Теперь берем карточку из середины оставшейся пачки, на ней номер 123-45-67. Из чего следует, что нужная нам карточка лежит во второй половине оставшейся пачки. Таким образом, при каждом сравнении, мы уменьшаем зону поиска в два раза. Отсюда и название метода - половинного деления или дихотомии.

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

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

Теория графов — раздел дискретной математики, изучающий свойства графов. Первая работа по теории графов принадлежит Леонарду Эйлеру. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Но термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг.

Графами называются схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых.

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

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

Если полный граф имеет n вершин, то количество ребер будет равно .

Граф называется ориентированным (или орграфом), если некоторые ребра имеют направление. Это означает, что в орграфе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет. Геометрически граф часто изображают точками плоскости, причем соседние вершины соединены дугами (для орграфа некоторые дуги имеют направление, что обычно отмечают стрелкой).

Помимо этого, в теории графов рассматриваются также мультиграфы – это такие графы, в которых могут быть петли (т. е. некоторая вершина соединена сама с собой ребром) или некоторые пары вершины могут быть соединены между собой несколькими ребрами.

Маршрут в графе – это последовательность соседних (смежных) вершин. Ясно, что можно определить маршрут и как последовательность смежных ребер (в этом случае ребра приобретают направление). Заметим, что в маршруте могут повторяться вершины, но не ребра. Маршрут называется циклом, если в нем первая вершина совпадает с последней.

Путь в графе (иногда говорят простой путь) – это маршрут без повторения вершин (а значит, и ребер).

Контур – это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней.

Последовательности вершин (рис. 1): 1–2–3–4–2–5 не простой путь, а маршрут; последовательности 1–2–3–4–7–5 и 1–2–5 – простые пути; 1–2–3–4–2–5–6–1 –это цикл (но не контур); 1–2–5–6–1 – это контур.

Рис.2

Граф называется связным , если любые две его вершины можно соединить маршрутом (или путем). На рис.2 изображен связный граф.

Ребро, при удалении которого граф перестает быть связным, иногда называют мостом или перешейком.

Следующее определение имеет смысл только для графов или мультиграфов без петель (но не для орграфов).

Степень вершины – это число ребер, входящих в эту вершину. Вершина называется висячей , если ее степень равна единице.

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

Двудольный граф или биграф — это математический термин теории графов, обозначающий граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части.

Применение теории графов

· Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.

· В химии (для описания структур, путей сложных реакций[1], правило фаз также может быть интерпретировано как задача теории графов); компьютерная химия — сравнительно молодая область химии, основанная на применении теории графов. Теория графов представляет собой математическую основу хемоинформатики. Теория графов позволяет точно определить число теоретически возможных изомеров у углеводородов и других органических соединений.

· В информатике и программировании

· В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете.

· В экономике

· В логистике

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

Термин "комбинаторика" был введён в математический обиход Лейбницем.

В 1666 году Лейбниц опубликовал "Рассуждения о комбинаторном искусстве". В своём сочинении Лейбниц, вводя специальные символы, термины для подмножеств и операций над ними находит все k -сочетания из n элементов выводит свойства сочетаний.

Элиаким Гастингс Мур (1862-1932) ввёл термин тактическая конфигурация в статье "Tactical memoranda", понимая под этим термином систему n множеств, содержащих, соответственно, a₁ , a₂ , … , a_n элементов.

Термин "тактика" ввёл в математику английский математик Джеймс Джозеф Сильвестр (1814-1897) в 1861 году. Сильвестр определял тактику как раздел математики, изучающий расположение элементов друг относительно друга. В сфере этого раздела находится, по мнению Сильвестра, теория групп, комбинаторный анализ и теория чисел.

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

Условно в комбинаторной теории можно выделить следующие три большие части (см. схему):

· Теорию конфигураций, включающую блок - схемы, группы подстановок, теорию кодирования.

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

· Теорию порядка, включающую конечные упорядоченные множества и решётки, матрицы и теоремы существования, подобные теоремам Холла и Рамсея.

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

В комбинаторике производящая функция последовательности {a_n } — это формальный степенной ряд

Зачастую производящая функция последовательности чисел является рядом Тейлора некоторой аналитической функции, что может использоваться для изучения свойств самой последовательности. Однако, в общем случае производящая функция не обязана быть аналитической.

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

Примерами комбинаторных конфигураций являются:

· Размещением из n элементов по k называется упорядоченный набор из k различных элементов некоторого n -элементного множества.

· Перестановкой из n элементов (обычно чисел 1,2,…,n ) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n .

· Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

Основные свойства сочетаний:

1.Условились, что

2.

3.

4.

· Композицией числа n называется всякое представление n в виде упорядоченной суммы целых положительных чисел.

· Разбиением числа n называется всякое представление n в виде неупорядоченной суммы целых положительных чисел.

Правило суммы:

Если элемент A можно выбрать m способами, а элемент B можно выбрать k способами, то выбор элемента A или B можно осуществить m + k способами.

Правило суммы можно перефразировать на теоретико-множественном языке. Обозначим через | A | число элементов множества A, через A B - объединение множеств A и B, через AB - декартово произведение множеств A и B. Тогда для непересекающихся множеств A и B выполняется равенство:

| A B | = | A | + | B |.

Обобщением правила суммы является правило произведения.

Правило произведения:

Если элемент A можно выбрать m способами, а после каждого выбора элемента A элемент B можно выбрать k способами, тогда, упорядоченную пару элементов (A, B) можно выбрать m * k способами.

Правило произведения можно распространить на выбор последовательности

(x₁ , x₂ , …, x_n ) произвольной конечной длины n .

На теоретико-множественном языке правило произведения формулируется так:

| A B | = | A | | B |.

Теория Рамсея

Теория Рамсея изучает наличие регулярных структур в случайных конфигурациях элементов. Примером утверждения из теории Рамсея может служить следующее:

в группе из 6 человек всегда можно найти трёх человек, которые либо попарно знакомы друг с другом, либо попарно незнакомы.

В терминах структурной комбинаторики это же утверждение формулируется так:

в любом графе с 6 вершинами найдётся либо клика, либо независимое множество размера 3.

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

Теорема Холла о свадьбах

Теорема о свадьбах, доказанная Филиппом Холлом в 1935 г., отвечает на следующий вопрос, известный под названием задачи о свадьбах: рассмотрим некоторое конечное множество юношей, каждый из которых знаком с несколькими девушками; спрашивается, при каких условиях можно женить юношей так, чтобы каждый из них женился на знакомой ему девушке?

Эту задачу можно представить графически, взяв двудольный граф G с множеством вершин, разделенных на два непересекающихся подмножества V ₁ и V ₂ , представляющих юношей и девушек, соответственно, и соединив ребром каждого юношу со знакомой ему девушкой.

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

Дискретизация заключается в преобразовании аналогового сигнала в цифровую форму и состоит из двух не связанных друг с другом операций:

· собственно дискретизации,

· квантования.

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

Перевод аналогового сигнала в дискретную форму для анализа на компьютере производится, как правило, через равные промежутки времени T . Важно правильно выбрать величину интервала дискретизации, т.е. правильно провести операцию собственно дискретизации. Согласно теореме Котельникова, этот интервал определяется частотой Найквиста F_n : чтобы представление сигнала x ( t ) в дискретной форме было однозначным, максимальный интервал дискретизации не должен превышать T = 1 / (2 F_n ) . Если осуществлять выборки через интервалы времени, большие T , то можно столкнуться с эффектом маскировки (подмены) частот, т.е. возможно перепутывание низко- и высокочастотных составляющих исходного процесса. Явление подмены является источником ошибок, которые могут возникнуть лишь при работе с выборочными данными. Если обрабатываются аналоговые сигналы, то операция дискретизации не производится и ошибки подмены не возникают.

На практике при цифровом анализе данных избавиться от ошибок маскировки частот можно единственным способом. Для этого еще до процесса дискретизации необходимо подавить в исходном аналоговом сигнале ту его часть, которая может содержать частоты, превышающие частоту Найквиста. Это делают с помощью низкочастотного фильтра, который устанавливается перед аналого-цифровым преобразователем. Такие низкочастотные фильтры называются противоподменными .

Рассмотрим теперь операцию квантования , которая состоит в переводе значений сигнала из аналогового непрерывного представления в цифровую форму. Как известно, цифровое представление чисел в ЭВМ заключается в их двоичном кодировании посредством целого числа бит. Точность цифрового (машинного) представления числа в виде непрерывного множества значений определяется количеством используемых бит. В типичных преобразователях аналогового сигнала в цифровой формат для кодирования применяется от 6 до 16 бит, что соответствует диапазону от 64 до 65536 уровней квантования. Так, если для представления чисел x из интервала (0,5) используется 8 бит, то это означает, что весь непрерывный интервал разбит на 2⁸ = 256 уровней c , 0 ≤ c ≤ 255, с шагом квантования и только 256 целых чисел в цифровой форме можно использовать для записи любого числа из этого интервала (рис. 25). Математически операцию квантования можно записать в виде:

здесь INT означает округление до целой части числа. Ошибка квантования равна

и ограничена интервалом (-0.5,0.5). Если преобразователь работает правильно, то ошибка квантования имеет нулевое среднее, распределена равномерно с плотностью вероятности, равной единице (p( c )=1), а дисперсия ошибки равна:

Частота дискретизации

Частота дискретизации (или частота сэмплирования) — частота взятия отсчетов непрерывного во времени сигнала при его дискретизации (в частности, аналого-цифровым преобразователем). Измеряется в герцах.

Термин применяется и при обратном, цифро-аналоговом преобразовании, особенно если частота дискретизации прямого и обратного преобразования выбрана разной (Данный приём, называемый также «Масштабированием времени», встречается, например, при анализе сверхнизкочастотных звуков, издаваемых морскими животными).

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

Используемые частоты дискретизации звука:

· 8 000 Гц — телефон, достаточно для речи, кодек Nellymoser;

· 11 025 Гц;

· 22 050 Гц — радио;

· 44 100 Гц — используется в Audio CD;

· 48 000 Гц — DVD, DAT.

· 96 000 Гц — DVD-Audio (MLP 5.1)

· 192 000 Гц — DVD-Audio (MLP 2.0)

· 2 822 400 Гц — SACD Super audio CD 5.1 — максимальная на данный момент (2008)

Сигналы

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

Классификация сигналов

· По физической природе носителя информации:

o электрические,

o электромагнитные,

o оптические,

o акустические

o и др.;

· По способу задания сигнала:

o регулярные (детерминированные), заданные аналитической функцией;

o нерегулярные (случайные), принимающие произвольные значения в любой момент времени. Для описания таких сигналов используется аппарат теории вероятностей;

· В зависимости от функции, описывающей параметры сигнала, выделяют:

o непрерывные (аналоговые), описываемые непрерывной функцией;

o дискретные, описываемые функцией отсчетов, взятых в определенные моменты времени;

o квантованные по уровню;

o дискретные сигналы, квантованные по уровню (цифровые).

Детерминированность

Детерминированность — определяемость. Детерминированность может подразумевать определяемость на общегносеологическом уровне или для конкретного алгоритма. Под детерминированностью процессов в мире понимается однозначная предопределённость.

Детерминированность в решении какой-либо практической задачи или в алгоритме означает, что способ решения задачи определён однозначно в виде последовательности шагов. На любом шаге не допускаются никакие двусмысленности или неопределённости и независимо от единичных вещей.

В теории игр — существование выигрышной стратегии для одного из игроков. То есть алгоритма, следуя которому один (и только один) из игроков неизбежно выигрывает.

Интерполяция

Интерполяция — в вычислительной математике способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений.

Определение интерполяции

Рассмотрим систему несовпадающих точек x_i () из некоторой области D . Пусть значения функции f известны только в этих точках:

Задача интерполяции состоит в поиске такой функции F из заданного класса функций, что

· Точки x_i называют узлами интерполяции , а их совокупность — интерполяционной сеткой .

· Пары (x_{i ,} y_{i )} называют точками данных или базовыми точками .

· Разность между «соседними» значениями — шагом интерполяционной сетки . Он может быть как переменным так и постоянным.

· Функцию F ( x ) — интерполирующей функцией или интерполянтом .

Экстраполяция

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

Экстраполяция — приближённое определение значений функции f(x) в точках x , лежащих вне отрезка [x₀ ,x_n ], по её значениям в точках x₀ < x₁ < ... < x_n

Сплайны

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

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

Классический сплайн одной переменной строится так: область определения разбивается на конечное число отрезков, на каждом из которых сплайн совпадает с некоторым алгебраическим полиномом. Максимальная степень из использованных полиномов называется степенью сплайна. Разность между степенью сплайна и получившейся гладкостью называется дефектом сплайна. Например, непрерывная ломаная есть сплайн степени 1 и дефекта 1.

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

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

Хотя в определении алгоритма требуется лишь конечность числа шагов, требуемых для достижения результата, на практике выполнение даже хотя бы миллиарда шагов является слишком медленным. Также обычно есть другие ограничения (на размер программы, на допустимые действия). В связи с этим вводят такие понятия как сложность алгоритма (временная, по размеру программы, вычислительная и др.).

Для каждой задачи может существовать множество алгоритмов, приводящих к цели. Увеличение эффективности алгоритмов составляет одну из задач современной информатики. В 50-х гг. XX века появилась даже отдельная её область — быстрые алгоритмы. В частности, в известной всем с детства задаче об умножении десятичных чисел обнаружился ряд алгоритмов, позволяющих существенно (в асимптотическом смысле) ускорить нахождение произведения.

Теория сложности алгоритмов является разделом теории вычислений, изучающим стоимость работы, требуемой для решения вычислительной проблемы. Стоимость обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством элементарных шагов, необходимых для решения проблемы, тогда как пространство определяется объёмом памяти или места на носителе данных. Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: «как изменится время исполнения и объём занятой памяти в зависимости от размера входа и выхода?». Здесь под размером входа понимается длина описания данных задачи в битах (например, в задаче коммивояжера длина входа пропорциональна количеству городов и дорог между ними), а под размером выхода — длина описания решения задачи (оптимального маршрута в задаче коммивояжера).

Теория сложности вычислений возникла из потребности сравнивать быстродействие алгоритмов, чётко описывать их поведение (время исполнения и объём необходимой памяти) в зависимости от размера входа и выхода.

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

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

Аналогично понятию временной сложности в худшем случае определяется понятие временная сложность алгоритма в наилучшем случае. Также рассматривают понятие среднее время работы алгоритма, то есть математическое ожидание времени работы алгоритма. Иногда говорят просто: «Временная сложность алгоритма» или «Время работы алгоритма», имея в виду временную сложность алгоритма в худшем, наилучшем или среднем случае (в зависимости от контекста).

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

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

Теория конечных автоматов , часть теоретической кибернетики, объектом исследования которой являются различные преобразователи дискретной информации; возникла в начале 50-х гг. 20 в. в связи с требованиями практики проектирования вычислительных машин и с разработкой математических моделей процессов переработки информации в биологических, экономических и других системах. Теория конечных автоматов — самостоятельный раздел математики, имеющий разнообразную проблематику и приложения.

Основными понятиями теории конечных автоматов являются понятия абстрактного автомата и понятие композиции автоматов. Эти понятия являются разумными абстракциями реально существующих дискретных устройств — автоматов. Понятие абстрактного автомата позволяет характеризовать устройство с точки зрения алгоритма его функционирования, т. е. алгоритма переработки информации, который оно реализует. Понятие композиции автоматов позволяет характеризовать устройство с точки зрения его структуры, иными словами, даёт представление, каким образом данное устройство построено из других, более элементарных.

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

Один из разделов : абстрактно-алгебраическая теория конечных автоматов. В этом разделе абстрактные автоматы изучаются с точки зрения исследования их свойств и различных способов задания.

Абстрактным автоматом называют объект А = А (U, X, Y, d, l) , состоящий из трёх непустых множеств: U — состояний, Х — входных сигналов, Y — выходных сигналов, и двух функций, осуществляющих однозначное отображение множества U´Х в U, d (а, х) переходов и множества U´Х в Y, l (а, x) выходов. Абстрактный автомат называется конечным, если множества U, X, Y — конечны. В абстрактно-алгебраической теории конечных автоматов можно выделить теорию конечных автоматов и теорию бесконечных автоматов. Основные вопросы теории конечных автоматов можно считать решенными. Наиболее интересными результатами теории конечных автоматов являются: теорема анализа и синтеза конечных автоматов, которая даёт характеристику событий, представленных в конечных автоматах, теоремы об определяющих соотношениях в алгебре регулярных событий, оценки длины экспериментов с конечными автоматами, а также ряд результатов по исследованию алгебраических свойств абстрактных автоматов. В теории бесконечных автоматов рассматриваются различные концепции бесконечных автоматов, точнее выделяются классы бесконечных автоматов специального вида. Этот раздел важен тесной связью с общей теорией формальных языков и грамматик а также с теорией алгоритмов. В рамках абстрактно-алгебраической теории конечных автоматов наметился (конец 60-х гг.) подход к решению проблемы создания алгебры алгоритмов и построения аппарата для формальных преобразований выражений в этой алгебре, что позволяет совершенно по-новому подойти к решению такого рода задач, как эквивалентность схем алгоритмов, и даёт возможность эффективно решать оптимизационные задачи в проектировании дискретных устройств.

Другим разделом теории конечных автоматов является структурная теория конечных автоматов. Здесь автомат представляется в виде сети, элементы которой выбираются из некоторой заданной совокупности элементарных автоматов, соединены между собой некоторым специальным образом и осуществляют запоминание и преобразование элементарных сигналов. Основными результатами структурной теории конечных автоматов являются: практическая методика построения сложных логических сетей, исследования по асимптотическим оценкам сложности их, решению проблемы полноты системы элементарных автоматов, кодированию состояний автоматов, оптимальной реализации логических сетей в различных элементных структурах и т. д. Структурная теория конечных автоматов тесно связана с теорией кодирования, общей теорией переключательных функций, теорией комбинационных схем, теорией информации, теорией надёжности дискретных устройств и т. п.

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

Основные приложения теория конечных автоматов имеет в практике проектирования и автоматизации проектирования дискретных устройств и, в частности, вычислительных машин. Она приобретает всё более важное значение для таких классических математических дисциплин, как теория алгоритмов, с одной стороны, и таких современных теорий в математике и кибернетике, как теория формальных систем, теория программирования, теория формальных языков и грамматик — с другой.

По способу формирования функций выходов выделяют автоматы Мили и Мура.

Автомат Мили

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

Конечным детерминированным автоматом типа Мили называется совокупность пяти объектов

,

где S, X и Y — конечные непустые множества, а δ и λ — отображения вида:

со связью элементов множеств S, X и Y в абстрактном времени T = {0, 1, 2, …} уравнениями:

(Отображения δ и λ получили названия, соответственно функции переходов и функции выходов автомата A ).

Особенностью автомата Мили является то, что функция выходов является двухаргументной и символ в выходном канале y(t) обнаруживается только при наличии символа во входном канале x(t) . Функциональная схема не отличается от схемы абстрактного автомата.

Автомат Мура

Зависимость выходного сигнала только от состояния представлена в автоматах типа Мура . В автомате Мура функция выходов определяет значение выходного символа только по одному аргументу — состоянию автомата. Эту функцию называют также функцией меток, так как она каждому состоянию автомата ставит метку на выходе.

Функциональная схема автомата Мура

Конечным детерминированным автоматом типа Мура называется совокупность пяти объектов:

,

где S, X, Y и δ — соответствуют определению автомата типа Мили, а μ является отображением вида: μ : S → Y , с зависимостью состояний и выходных сигналов во времени уравнением:

Особенностью автомата Мура является то, что символ y(t) в выходном канале существует все время пока автомат находится в состоянии s(t) .

Для любого автомата Мура существует автомат Мили, реализующий туже самую функцию. И наоборот: для любого автомата Мили существует соответствующий автомат Мура.

Функциональная схема автомата Мура

Список литературы:

1. Ru.wikipedia.org

2. http://chaos.ssu.runnet.ru

3. Столл Р. Р. Множества. Логика. Аксиоматические теории. — М.: Просвещение, 1968. — 232 с.

4. Intuit.ru

5. Уилсон Р. Введение в теорию графов. Пер с англ. М.: Мир, 1977. 208с.

6. http://www.citforum.ru/

7. Ерош И. Л. Дискретная математика. Комбинаторика — СПб.: СПбГУАП, 2001. — 37 c.

8. Риордан Дж. Введение в комбинаторный анализ. — пер. с англ.. — М.: 1963.