Файл: Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 21.10.2024

Просмотров: 56

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Транспонированной по отношению к А назовем матрицу

 

 

 

/

а\\

a,2i • • • ami

\

 

 

 

 

„,

I

«12

а22 • • •ат2

\

 

 

 

 

 

 

din

&2п

' ' '

 

 

 

 

получаемую из А заменой строк

столбцами.

 

 

Две матрицы равны в том и только

в том

случае, если

равны

их соответствующие

элементы. Очевидно,

что

размерности

тип

строк и столбцов равных матриц должны

совпадать.

 

Квадратная

матрица

называется

треугольной, если ее элемен­

ты ац для всех

i>j

(или для

всех i<lj)

равны

нулю.

 

Матрица

 

 

 

 

 

 

 

 

 

 

является

треугольной.

 

 

 

 

 

 

 

 

Матрица

А называется симметрической,

если

А=А',

т. е.

ац = ан

при любых i, j .

Если А——А',

т. е. ац = —ац,

матрица А

называется

кососимметрической.

Из

определения

вытекает,

что

все

элементы главной

диагонали

кососимметрической

матрицы

равны

нулю.

 

 

 

 

 

 

 

 

 

Все

элементы так называемой нулевой матрицы,

обозначаемой

0 = ( 0 ) ,

равны нулю.

 

 

 

 

 

 

 

 

 

Определим теперь операции сложения матриц и умножения

матриц

на

скаляр. Пусть даны некоторый

скаляр а

и

произволь­

ная

матрица

А. Их произведение аА определяется как

 

 

 

 

 

 

аА

 

 

 

 

 

 

 

 

 

Сумма

Л + В = С матриц А я В,

каждая

из

которых

содержит

т

строк

и

п столбцов, определяется

как

 

 

 

 

 

1.0

Операции умножения скаляра на матрицу

и сложения

мат­

риц

обладают

следующими

свойствами:

 

 

 

а)

(А +В) + С=А

+ (В + С)

(ассоциативный

закон);

 

б)

А+В = В+А.

(коммутативный

закон);

 

 

 

в)

( а + р ) Л =

а Л + р Л ,

а{А-\-В)—аА-\-аВ

(дистрибутивный

за­

кон) ;

 

 

 

 

 

 

 

 

 

г)

Л + 0 = Л .

 

 

 

 

 

 

 

 

Здесь матрицы А, В и

С имеют

размерности

т-п, а а и

р —

скаляры.

Произведение двух матриц А и В определяется только при ус­

ловии, что число столбцов матрицы А равно

числу строк матрицы

В. При этом условии элементы произведения

АВ = С определяют­

ся следующим

образом.

 

Элемент г'-й строки и /-го столбца матрицы С равен сумме про­

изведений элементов г'-й строки матрицы А

на соответствующие

элементы у'-го столбца матрицы В.

 

Например,

\

)

где сц = ац

Ь^ + щ2 b2j + ai3

b3j.

 

 

матрицу В

Произведением

матрицы

А размерности т-п на

размерности

n-q

является матрица

размерности

m-q.

Произведе­

ние матриц некоммутативно, т. е.

АВфВА.

 

 

Произведение

матриц обладает

следующими

свойствами:

a)(АВ)С=А(ВС) (ассоциативный закон);

б)

(А + В)С=АС + ВС, С(А + В) = СА + СВ

(дистрибутивный

закон);

 

b)

а(АВ) = (аА)В=А(аВ);

*• :

г)

АЕ=ЕА=А;

 

здесь матрицы А, В, С

и Е

имеют соответствующие

размерности и

а — скаляр.

Отметим,

что

(АВ)' —

В/-А'.

 

Матрица

В называется

обратной

по отношению

к квадратной

матрице А,

если АВ = Е. Матрица, обратная матрице А, обознача­

ется через А-1.

Для каждой неособенной

матрицы А

существует

единственная

матрица А~1,

такая, что

 

 

§ 1. 3. ОБЩЕЕ ПОНЯТИЕ АЛГОРИТМА

 

Алгоритмами в современной математике принято

называть

конструктивно

задаваемые

соответствия

между словами в абст­

рактных алфавитах.

Абстрактным алфавитом называется любая конечная совокуп­ ность объектов, называемых буквами или символами данного ал­ фавита.

11

Алфавит, как любое множество, задается перечислением его элементов, т. е. символов

 

A = {a,b,c,d},

В={х,у}-

 

 

Под словом

или строкой

алфавита будем

понимать

любую

конечную упорядоченную последовательность

символов.

Число

символов в слове называется длиной этого слова.

 

Алфавитным

оператором

или

алфавитным

отображением на­

зывается всякое соответствие, сопоставляющее словам некоторого алфавита слова того же самого или какого-то другого фиксирован­

ного алфавита. При этом первый алфавит

называется

входным,

второй — выходным алфавитом данного оператора.

 

Алфавитный оператор, сопоставляющий

слову

а из

входного

алфавита А слово р из выходного алфавита

В,

запишется как

Га = р.

 

 

 

В случае совпадения входного и выходного алфавитов говорят,

что

алфавитный оператор задан в соответствующем

алфавите.

 

Иначе говоря,

алфавитный оператор — функция,

задающая

соответствие между словами входного алфавита и

словами этого

же

или другого

выходного

алфавита.

 

 

 

В случае, если область

определения алфавитного

оператора

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

правой — выходные слова,

получающиеся

в результате примене­

ния оператора к каждому

слову из левой

части таблицы.

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

Алфавитные операторы, задаваемые с помощью конечной системы правил, принято называть алгоритмами.

Отсюда легко понять, что всякий алфавитный оператор, кото­ рый можно фактически задать, является непременно алгоритмом.

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

Таким образом, алгоритм — алфавитный оператор вместе с правилами, определяющими его действие.

Два алфавитных оператора считаются равными, если они име­ ют одну и ту же область определения и сопоставляют любому

12

наперед заданному

входному слову

из

этой

области

одинаковые

выходные слова.

 

 

 

 

 

 

Два алгоритма считаются равными, если равны соответствую­

щие им алфавитные операторы и совпадает

система

правил, за­

дающих действие этих алгоритмов на выходные слова.

 

Два алгоритма считаются эквивалентными, если у них совпа­

дают (равны) алфавитные операторы,

но не

совпадают

способы

их задания (система

правил). Обычно в

абстрактной

теории алго­

ритмов рассматриваются лишь такие алгоритмы, которым

соответ­

ствуют однозначные

алфавитные

операторы.

Всякий

алгоритм

такого рода любому входному слову сопоставляет только одно вы­

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

алфавит­

ные операторы

называются

детерминированными.

 

Таким образом, одним из

свойств

алгоритма является детер­

минированность. К числу других свойств

алгоритмов

относятся

массовость

и

результативность.

 

 

 

Массовость — свойство алгоритма

быть

применимым

для мно­

жества строк. Если алгоритм

применим для множества

строк, то

он обладает

свойством массовости.

 

 

 

Результативность — свойство алгоритма,

обеспечивающее полу­

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

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

Теперь эквивалентность алгоритмов может быть определена следующим образом: два алгоритма эквивалентны, если совпадают их области применимости и результаты переработки любого слова

из

этой области.

 

В общем случае различают еще случайные и самоизменяющие­

ся

алгоритмы.

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

Алгоритм называется самоизменяющимся, если он, перерабаты­ вая входные слова, сам изменяется в процессе такой переработки.

Результат действия самоизменяющегося

алгоритма

на то

или

иное входное слово зависит не только от этого слова, но и от

исто­

рии

предыдущей работы

алгоритма.

 

 

 

В

теории алгоритмов

большое внимание

уделяется

общим спо­

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

Всякий общий способ задания алгоритмов называется алгорит­ мической системой.

13

Смотрите также файлы