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

   Элиаким Гастингс Мур (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 / (2F_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)

 

Сигналы

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

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

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

• электрические,
• электромагнитные,
• оптические,
• акустические
• и др.;

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

<