1.6.3. Свойства z-преобразования

1) Линейности -–

2) Задержки -–

где – функция единичного скачка

3) Умножения на экспоненту -–

4) Умножения на n -–

5) Опережающего сдвига -–

6) Свертки -–

Указанные свойства упрощают получение преобразований и их обращений.

1.6.4. Использование z-преобразований для решения рекуррентных уравнений

В качестве примера рассмотрим рекуррентное уравнение первого порядка

с начальным условием

Пусть на вход поступает последовательность (правая часть рекуррентного уравнения)

Умножаем обе части рекуррентного уравнения на величину и просуммируем по n от 0 до :

Используя свойство задержки, имеем

Откуда

Т.к. , то

То

Разложив второе слагаемое на простые дроби, получим

Вычислим обратное Z-преобразование

.

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

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

Таблица 4

	1
1
	Продолжение табл. 4

1.7. Трансверсали и перманенты

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

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

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

S = {s₁, s₂, …, s_n}

где s₁, s₂, …, s_n - элементы S, обязательно различные! Мощность множества S обозначается как |S|, для выписанного выше множества мощность записывается так |S| = n. Если S- конечное мультимножество, то будем записывать его в следующем виде:

S = {s₁, s₁, …, s_1, s₂, s₂, …, s₂,s₃…, s₃} = {m₁*s₁,m₂*s₂,m_n*s_n }

m₁ раз m₂ раз m₃ раз

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

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

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

Как и для последовательностей, наилучший метод представления множеств или мультимножеств существенно зависит от операций, которые выполняются над ними. Предположим, например, что имеем дело с непересекающимися подмножествами множества S = {s₁, s₂, …, s_n} и что над ними необходимо выполнить две следующие операции: объединение двух множеств и отыскание подмножества, содержащего данное s_i. Таким образом, в любой момент времени имеем разбиение 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 = {s₁, s₂, …, s_n} на nподмножеств, каждое из которых состоит из одного элемента

{[s₁], [s₂], …, [s_n]}

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