Избранные главы дискретной математики (стр. 5 из 7)
| A B | = | A | + | B |.
Обобщением правила суммы является правило произведения.
Правило произведения:
Если элемент A можно выбрать m способами, а после каждого выбора элемента A элемент B можно выбрать k способами, тогда, упорядоченную пару элементов (A, B) можно выбрать m*k способами.
Правило произведения можно распространить на выбор последовательности
(x1, x2, …, xn) произвольной конечной длины n.
На теоретико-множественном языке правило произведения формулируется так:
| A
B | = | A | | B |.Теория Рамсея
Теория Рамсея изучает наличие регулярных структур в случайных конфигурациях элементов. Примером утверждения из теории Рамсея может служить следующее:
в группе из 6 человек всегда можно найти трёх человек, которые либо попарно знакомы друг с другом, либо попарно незнакомы.
В терминах структурной комбинаторики это же утверждение формулируется так:
в любом графе с 6 вершинами найдётся либо клика, либо независимое множество размера 3.
Кликой в неориентированном графе называется подмножество вершин, каждые две из которых соединены ребром графа. Иными словами, это полный подграф первоначального графа. Размер клики определяется как число вершин в ней.
Теорема Холла о свадьбах
Теорема о свадьбах, доказанная Филиппом Холлом в 1935 г., отвечает на следующий вопрос, известный под названием задачи о свадьбах: рассмотрим некоторое конечное множество юношей, каждый из которых знаком с несколькими девушками; спрашивается, при каких условиях можно женить юношей так, чтобы каждый из них женился на знакомой ему девушке?
Эту задачу можно представить графически, взяв двудольный граф G с множеством вершин, разделенных на два непересекающихся подмножества V1 и V2 , представляющих юношей и девушек, соответственно, и соединив ребром каждого юношу со знакомой ему девушкой.
§8 Дискретизация
Дискретизация заключается в преобразовании аналогового сигнала в цифровую форму и состоит из двух не связанных друг с другом операций:
· собственно дискретизации,
· квантования.
Собственно дискретизация — это процесс определения моментов времени, в которые должны быть произведены отсчеты; квантование — перевод этих отсчетов в цифровую форму. Как правило, эти две операции осуществляются при помощи аналого-цифровых преобразователей (АЦП), которые связывают источник аналогового сигнала с компьютером. АЦП обычно представляют собой двоичные или двоично-десятичные системы. Двоичная система преобразует аналоговые сигналы в двоичный цифровой код, а двоично-десятичная система — в цифровой код, который может быть представлен десятью цифрами. Конструкция двоичной системы проще, но для обработки данных на ЭВМ нужно составлять программы в машинном коде. Двоично-десятичная система сложнее, но она позволяет производить обработку данных наблюдений с помощью программ, написанных на обычном алгоритмическом языке.
Перевод аналогового сигнала в дискретную форму для анализа на компьютере производится, как правило, через равные промежутки времени T. Важно правильно выбрать величину интервала дискретизации, т.е. правильно провести операцию собственно дискретизации. Согласно теореме Котельникова, этот интервал определяется частотой Найквиста Fn: чтобы представление сигнала x(t) в дискретной форме было однозначным, максимальный интервал дискретизации не должен превышать T = 1 / (2Fn). Если осуществлять выборки через интервалы времени, большие T, то можно столкнуться с эффектом маскировки (подмены) частот, т.е. возможно перепутывание низко- и высокочастотных составляющих исходного процесса. Явление подмены является источником ошибок, которые могут возникнуть лишь при работе с выборочными данными. Если обрабатываются аналоговые сигналы, то операция дискретизации не производится и ошибки подмены не возникают.
На практике при цифровом анализе данных избавиться от ошибок маскировки частот можно единственным способом. Для этого еще до процесса дискретизации необходимо подавить в исходном аналоговом сигнале ту его часть, которая может содержать частоты, превышающие частоту Найквиста. Это делают с помощью низкочастотного фильтра, который устанавливается перед аналого-цифровым преобразователем. Такие низкочастотные фильтры называются противоподменными.
Рассмотрим теперь операцию квантования, которая состоит в переводе значений сигнала из аналогового непрерывного представления в цифровую форму. Как известно, цифровое представление чисел в ЭВМ заключается в их двоичном кодировании посредством целого числа бит. Точность цифрового (машинного) представления числа в виде непрерывного множества значений определяется количеством используемых бит. В типичных преобразователях аналогового сигнала в цифровой формат для кодирования применяется от 6 до 16 бит, что соответствует диапазону от 64 до 65536 уровней квантования. Так, если для представления чисел x из интервала (0,5) используется 8 бит, то это означает, что весь непрерывный интервал разбит на 28 = 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 дискретные сигналы, квантованные по уровню (цифровые).
Детерминированность
Детерминированность — определяемость. Детерминированность может подразумевать определяемость на общегносеологическом уровне или для конкретного алгоритма. Под детерминированностью процессов в мире понимается однозначная предопределённость.
Детерминированность в решении какой-либо практической задачи или в алгоритме означает, что способ решения задачи определён однозначно в виде последовательности шагов. На любом шаге не допускаются никакие двусмысленности или неопределённости и независимо от единичных вещей.
В теории игр — существование выигрышной стратегии для одного из игроков. То есть алгоритма, следуя которому один (и только один) из игроков неизбежно выигрывает.
Интерполяция
Интерполяция — в вычислительной математике способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений.
Определение интерполяции
Рассмотрим систему несовпадающих точек xi (
) из некоторой области D. Пусть значения функции f известны только в этих точках: