Пособие ДМ2

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

1.6.5. Таблица односторонних Z-преобразований

1

⁄

{

1.7.ТРАНСВЕРСАЛИ И ПЕРМАНЕНТЫ

1.7.1.Множества и мультимножества

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

емое кратностью.

Конечное множество S будем записывать в следующем виде:

S = {s1, s2, …, sn}

где s1, s2, …, sn - элементы S,обязательно различные! Мощ-

ность множества Sобозначается как |S|, для выписанного выше множества мощность записывается так |S| = n. Если S- конечное мультимножество, то будем записывать его в следующем виде:

S = {s1, s1, …, s1, s2, s2, …, s2,s3…, s3} = {m1*s1,m2*s2,mn*sn }

m1 раз m2 раз m3 раз

Здесь все Si различны и mi- кратность элемента si. В этом случае мощность Sравна

|S| = ∑mi (i = 1..n)

Наиболее общими операциями на множествах и мультимножествах являются операции объединения и пересечения.

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

Как и для последовательностей, наилучший метод представления множеств или мультимножеств существенно зависит от операций, которые выполняются над ними. Предположим, например, что имеем дело с непересекающимися подмножествами множества S = {s1, s2, …, sn} и что над ними необходимо выполнить две следующие операции: объединение двух множеств и отыскание подмножества, содержащего данное si. Таким образом, в любой момент времени имеем разбиение S на непустые непересекающиеся подмножества. Рассмотрим эти операции в конце данной лекции.

С целью идентификации считаем, что каждое из непересекающихся подмножеств множества S имеет имя. Имя - это просто один из элементов подмножества, или, иначе, - представитель подмножества. Когда мы будем ссылаться на имя подмножества, то будем под этим подразумевать его представителя. Рассмотрим, например, множество

разбитое на четыре непересекающихся подмножества {1, 6, [7], 8, 11}, {[3], 4, 5}, {[2]}, {9, [10]}.

В каждом из подмножеств, взятый в скобки элемент является его именем. Если нам нужно найти подмножество, в котором содержится восьмерка, искомым ответом будет 7, то есть имя подмножества, содержащего восьмерку. Если нужно взять объединение подмножеств с именами 2 и 10, получим разбиение множества Sследующего вида:

{1, 6, [7], 8, 11}, {[3], 4, 5}, {[2]} {9, 10]}

Именем множества {[2]} {9, 10]}может быть или 2, или 10.Предполагаем, что вначале имеется разбиение множества S = {s1, s2, …, sn} на nподмножеств, каждое из которых состоит из одного элемента

{[s1], [s2], …, [sn]}

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

ееполезности виден в "жадном" алгоритме.

1.7.2.Трансверсали

Системой различных представителей (транверсалью) для совокупности множеств M(S) называется множество эле-

1.,

2., при .

Критерием существования трансверсали для M(S) служит следующая теорема.

Теорема Холла. Совокупность множеств M(S) имеет

| |

то есть число элементов объединения множеств не меньше k.

Если для некоторого подсемейства семейства M(S) имеет место равенство

| |

то такое подсемейство называется критическим.

Перманентом матрицы A называется число, определяемое следующим выражением

∑

Где суммирование производится по всевозможным выборкам объема n из m различных элементов.

Рассмотрим примеры

∑

Многие свойства перманента подобны свойствам определителя для квадратных матриц, однако свойство

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

1.7.4. Число трансверсалей

Важнейшее применение перманентов определяется сле-

гда и только тогда, когда для соответствующей матрицы инцидентности выполняется условие.

Пример 1. (задача о встречах). Требуется определить число трансверсалей семейства , где Xi = X\{i} и x = {1,2,..,n}. Эта задача имеет и другие разнообразные формулировки, но обычно называется задачей о встречах. В

{

Обозначим hn = per(1-δij) и разлогая перманент по первой строке, получим

,

Где матрица получается из матрицы заменой эле-

мента a11 на 1.

Разлагая perA′n-1 по элементу a11 получим

то есть получим рекуррентное соотношение

с начальными условиями h0=1 и h1=0

Перепишем рекуррентное соотношение в виде hn-nhn-1=-(hn-1-(n-1)hn-2)=…=(-1)k(hn-k-(n-k)hn-k-1)=…=(-1)n

Пологая , получим

Отсюда следует что

∑

Таким образом, окончательный ответ

∑

Пример 2.

Требуется найти число трансверсалей семейства (Xi , 1≤i≤n), где

X1={1,2}, X2={1,2,3}, X3={2,3,4},…, Xn-1={n-2, n-1, n}, Xn={n-1, n}, являющихся подмножествами множества

X={1,2,…,n}.

Решение.

Число трансверсалей

Разлагая этот перманент сначала по первой строке, а затем получившийся перманент разлагаем по первому столбцу, получаем рекуррентное соотношение

Cn=Cn-1+Cn-2

с начальным условием C1=1, C2=2

Полученные числа Cnявляются числами Фибоначчи.

1.8.Матрицы Адамара

1.8.1.Определение матрицы Адамара и ее свойства

Матрица H=(hij), i,j=1,2,_,n, hij= 1 называется матрицей

Следовательно, если H1,H2,..,Hn – строки матрицы H, то эти строки, как векторы, удовлетворяют условию ортогональности

.

Из матричного равенства (1) следует , что

det(HHT) = (detH)2 = det(nIn) = nn

и, следовательно, |detH| = nn/2.

А это означает что detH 0 и, следовательно, матрица H – невырожденная. Это, в свою очередь, говорит о том, что для матрицы H существует обратная ей матрица H-1. Запишем сле-

дующую систему равенств.

HTH =H-1 HHTH =H-1(nIn)H = nIn = HHT

Следовательно, матрица H удовлетворяет условию нор-

мальности, то есть

HTH = HHT

1.8.2. Эквивалентные преобразования матриц Адамара

Перестановки строк или столбцов, а так же умножение строк или столбцов на (-1) переводит матрицу Адамара H в эквивалентную матрицу Адамара H1. Действительно, перестановка строк матрицы H, в соответствии, с (3) сохраняет все скалярные произведения строк. Перестановка столбцов связана с изменением порядка слагаемых в формуле (2). Аналогичным образом не изменяются в соответствии с (2) скалярные произведения строк или столбцов при умножении на (-1). С помощью эквивалентных преобразований матрицу Адамара можно привести к нормализованному виду H , в котором первая строка и первый столбец состоят из положительных единиц. Нормализованными матрицами Адамара 1-го и 2-го по-

(4)

Рассмотрим нормализованную матрицу Адамара порядка

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