Главная страница
Навигация по странице:

  • 2. АВТОМАТНОЕ ОПИСАНИЕ СИСТЕМ. ТЕОРИЯ КОНЕЧНЫХ АВТОМАТОВ

  • 2.1. Основные понятия. Способы задания автоматов

  • Математическая теория систем. Математические основы теории систем


    Скачать 2.07 Mb.
    НазваниеМатематические основы теории систем
    Дата20.01.2023
    Размер2.07 Mb.
    Формат файлаpdf
    Имя файлаМатематическая теория систем.pdf
    ТипУчебное пособие
    #895603
    страница4 из 35
    1   2   3   4   5   6   7   8   9   ...   35
    x(входной алфавит); б) множество
    Y значений выходных величин y (выходной алфавит); в) множество
    Q значений переменных состояния q (алфавит состоя- ний).
    Вектор
    q(
    t) (также как и вектор q(τ)) является тогда элементом n- кратного декартового произведения
    ( )
    :
    n
    n
    Q
    t
    Q

    q
    . Соответственно для k выходных величин вектор y(
    t) является элементом k-кратного декартово- го произведения
    ( )
    :
    k
    k
    Y
    t
    Y

    y
    Вообще говоря, не обязательно эти множества должны быть множе- ством вещественных чисел
    R, т.е. не обязательно должно быть
    X=Y=Q=R. Чтобы получить более общее определение системы, под мно- жествами
    X,Y,Q следует понимать множества более общего вида. При этом каждая компонента
    ( ) (
    )
    1, 2,...,
    x
    m
    ν
    τ ν =
    входного вектора
    x(τ)
    (
    )
    0
    t
    t
    ≤ τ <
    уже определяется как некоторое отображение интервала
    [ ]
    0
    ,
    t
    T
    t t
    =
    действительной временной оси
    T=R или в более общем случае множества
    0 0
    0
    (
    )
    t
    t
    T
    T
    T T
    R
    = ∩

    на множество
    X:

    30
    ( )
    0 0
    0 0
    0
    :
    ,
    ,
    ,
    ( , ),
    1, 2,..., .
    t
    t
    t
    t
    x
    T
    X T
    T
    T T
    R T
    t t
    m
    ν
    τ

    = ∩


    ν =
    Здесь вектор
    ( )
    n
    X
    τ ∈
    x
    . Если через
    {
    }
    0
    m
    t
    T
    X
    =

    X
    обозначить множество всех отображений всех множеств
    0
    t
    T в декартово произведе- ние
    m
    X (или в некоторое подмножество этого множества), то соотноше- ния (1.3.2.) можно записать как отображения вида
    :
    ;
    :
    n
    n
    n
    k
    Q
    Q
    Q
    Y
    δ
    ×

    λ
    ×

    X
    X
    (1.3.5)
    Конкретизируя множества
    , и
    Y Q
    X
    , приходим к математическим моделям различных систем. Если эти множества
    конечны, то такая систе- ма будет называться
    конечным автоматом, и для ее исследования разра- ботана соответствующая теория конечных автоматов. Это довольно про- стой класс систем в том смысле, что для исследования конечных автома- тов необходимы лишь методы логики, алгебры и теории множеств. И в то же время это достаточно важный и широкий класс систем, так как в него входят все дискретные (цифровые) измерительные, управляющие и вы- числительные устройства.
    Если
    ,
    и
    k
    n
    Y
    Q
    X
    являются метрическими или в более общем случае топологическими пространствами [6], а отображения и
    λ δ непрерывны в этих пространствах, то мы переходим к так называемым
    гладким систе- мам. Для такого класса систем характерно, что переходное отображение δ
    является общим решением векторно-матричного уравнения: f( , , ),
    d
    t
    t R
    dt
    =

    q
    q x
    . (1.3.6)
    Если же в уравнении (1.3.6) время
    t является элементом счетного множества, т.е. течет дискретно, шагами или квантами (это будет в слу- чае, если
    0 0
    T
    N

    , где
    N
    0
    – множество натуральных чисел), то от выраже- ния (1.3.6) приходим к разностному уравнению:
    ( )
    (
    )
    1 0
    (
    ) f
    ,
    ,
    ,
    k
    k
    k
    t
    t
    t
    k N
    +
    =

    q
    q
    x
    , (1.3.7) являющемуся описанием дискретных во времени систем.

    31
    Если отображение λ не зависит явно от времени и отображение δ
    инва- риантно (неизменно) к сдвигу во времени, то получаем описание
    стацио-
    нарных систем. У таких систем их свойства со временем не меняются.
    Особо нужно остановиться на таком свойстве реальных систем, как принцип причинности. Этот принцип означает, что отклик (выход) си- стемы на некоторые воздействия не может появиться раньше самого воз- действия. Это условие не всегда выполняется в рамках математических моделей систем, и одна из проблем теории таких систем состоит как раз в выяснении условий физической реализуемости теоретических моделей.
    Следует также отметить, что в основных уравнениях (1.3.1) – (1.3.2) всегда предполагается, что
    0
    t t
    > . Физически это означает, что из состоя- ния системы в данный момент времени q(
    t
    0
    ) можно сделать заключение о поведении системы только в
    последующие моменты времени. Таким об- разом, не предполагается, что по заданным значениям q(
    t
    0
    )
    и
    ( )
    τ
    x
    можно также определить и q(
    t) при
    0 0
    (
    )
    t t t
    t
    <
    < τ ≤
    . Иными словами, если из- вестно конечное состояние q(
    t
    0
    ) и входное воздействие
    ( )
    τ
    x
    на предше- ствующем интервале времени
    0
    τ
    t
    t
    < ≤
    ,
    то восстановить первоначальное состояние q(
    t) не всегда представляется возможным. Эти же рассуждения справедливы и для y(
    t). Это означает, что будущее поведение некоторой динамической системы зависит от всей ее предшествующей эволюции только в той мере, насколько эта предыстория влияет на начальное со- стояние. То есть динамические системы по определению не обязательно являются обратимыми (во времени)
    [6]
    1.3.6. Классификация систем
    Когда мы сравниваем системы, начинаем их различать, мы тем самым вводим некоторую классификацию.
    Основания классификации, т.е. свой- ства систем, по которым мы их различаем, могут быть самыми различны- ми. Необходимо только помнить, что всякая классификация – это модель реальности и, как любая модель, конечна, упрощённа, приближенна и условна. Разграничение внутри класса приводит к подклассам и, в конце концов, получается многоуровневая, иерархическая классификация. Важ- ным моментом является полнота классификации. Когда нет уверенности в полноте классификации, имеет смысл вводить класс «все остальное».
    Системы можно разделить на искусственные (т.е. созданные челове- ком), естественные и смешанные. К искусственным системам относятся механизмы, орудия, машины, роботы и т.д. В естественных системах

    32 можно выделить подклассы систем живых, неживых, социальных, эколо- гических. Примером подклассов смешанных систем могут служить эрго- номические системы (человек-оператор и машина), биотехнические си- стемы (системы, в которые входят живые организмы и технические устройства), автоматизированные системы.
    Поскольку классификация – это модель, то она, как и всякая модель, носит целевой характер: новые цели порождают и новые классификации.
    Чтобы как-то упорядочить эту классификацию, рассмотрим общую функциональную схему системы управления, приведенную на рис. 1.6.
    На этой схеме выделен объект управления О и управляющее устрой- ство УУ, вырабатывающее управляющие воздействия
    U. И методы нахождения управления
    U, и способы его осуществления, и сам результат управления зависит от того, что известно об объекте и как эти знания используются управляющим устройством. Рассматривая разные аспекты вышеизложенного, можно строить разные классификации систем.
    Например, по типам входных, выходных переменных и переменных со- стояния. На рис. 1.7 приведен фрагмент такой классификации:
    Рис. 1.6. Функциональная схема системы управления
    О
    УУ
    Y
    V
    V
    1
    U
    X
    Рис. 1.7. Классификация систем по описанию переменных смешанное описание формализованное описание содержательное описание
    Системы с качественными переменными с количественными переменными со смешанными переменными дискретные
    … непрерывные детерминированные стохастические размытые смешанные смешанные


    33
    Принципиально разных подходов требуют переменные, описываемые количественно и качественно, что и приводит к первому уровню класси- фикации. Могут быть ситуации, когда часть переменных описывается количественными, а часть – качественными характеристиками, поэтому и появляется класс смешанного описания. Для систем с качественными переменными следующий уровень классификации подразумевает описа- ние переменных на уровне естественного языка и на более формализо- ванном уровне (например, на уровне предикатных переменных). Воз- можно также и смешанное описание. Для систем с количественным опи- санием переменных разного подхода требуют переменные непрерывные и дискретные. Выделен также подкласс дискретно-непрерывного описа- ния переменных. Для третьего класса систем (со смешанным описанием переменных) второй уровень классификации является объединением подклассов систем двух первых ветвей и на рис. 1.7 не показан. Третий уровень классификации можно принять одинаковым для всех подклассов второго уровня. На рис. 1.7 он показан только для одного подкласса.
    В зависимости от того, входит управляющее устройство в систему или является внешним по отношению к ней, можно выделить системы управляемые извне, самоуправляемые и смешанные, а в каждом из этих подклассов, в свою очередь, можно предложить четыре основных спосо- ба управления. Для пояснения представим движение динамической си- стемы в виде траектории, например, в пространстве состояний
    n
    Q . Пер- вый (простейший) случай соответствует полной известности заданной
    (требуемой) траектории при точном программном управлении
    U
    0
    (
    t). В этом случае управление осуществляется без контроля за состоянием объ- екта.
    Если движение системы отличается от заданного (что может быть при отклонении неуправляемых переменных
    V
    0
    (
    t) от ранее предполагаемых), возникает необходимость контроля за состоянием объекта. В этом случае мы приходим ко второму способу управления.
    Для таких систем, в которых точную требуемую траекторию движения задать невозможно, а известна только конечная целевая окрестность, предусмотрен третий способ управления. Для систем этого подкласса осу- ществляется подстройка параметров заранее непредсказуемым образом.
    Наконец, когда никакой подстройкой параметров невозможно достичь целевой области, приходится идти на изменение структуры системы (то есть, по сути, заменять систему другой системой). В этом случае (это четвертый подкласс) имеет место перебор разных систем (имеющих оди-

    34 наковые выходы
    Y), создаваемых, тем не менее, не произвольно, а с уче- том наличных средств.
    Ясно, что для обеспечения определенного управления в любой систе- ме требуются ресурсы: материальные, энергетические, информационные.
    Причем в зависимости от достаточности или недостатка этих видов ре- сурсов возможны принципиально различные случаи систем. Это и дает основания для классификации, приведенной на рис. 1.8.
    Энергетические затраты на выработку управления, как правило, малы по сравнению с энергопотреблением объекта управления, и в этом случае их просто не принимают во внимание в классе обычных систем. Но в не- которых случаях управляемая и управляющая части могут потреблять соизмеримое количество энергии и питаться от одного источника. При этом возникает нетривиальная задача перераспределения ограниченной энергии между этими частями, и мы приходим к классу энергокритичных систем.
    Материальные затраты на функционирование систем также могут со- здавать определенные ограничения. Например, в случае управления объ- ектом большой размерности с помощью ЦВМ такими ограничениями могут быть объем оперативной памяти и быстродействие. В соответствии
    Рис. 1.8. Классификация систем по ресурсообеспеченности неполная полная энергетические
    Системы обычные энергокритичные малые большие простые сложные ресурсы обеспеченность информационные материальные

    35 с этим большими можно назвать системы, моделирование которых за- труднено вследствие их большой размерности. Перевод систем из боль- ших в малые можно осуществить двумя способами. Это либо применение более мощной вычислительной базы, либо декомпозиция многомерной задачи на задачи меньшей размерности (если такое возможно).
    Третий тип ресурсов – информационный. Если информации о системе достаточно (а признаком этого служит успешность управления), то си- стему можно назвать простой. Если же управление, выработанное на ос- нове имеющейся информации об объекте, приводит к неожиданным, непредвиденным или нежелательным результатам, то систему можно интерпретировать как сложную. Поэтому сложной системой можно назвать систему, в модели которой недостаточно информации для эффек- тивного управления
    1
    . Два способа можно предложить для перевода си- стемы из подкласса сложных в подкласс простых. Первый состоит в вы- яснении конкретной причины сложности, получении недостающей ин- формации и включении ее в модель системы. Второй способ связан со сменой цели, что в технических системах неэффективно, но в отношени- ях между людьми часто является единственным выходом.
    Поскольку перечисленные виды ресурсов являются более или менее независимыми, возможно самое различное сочетание между подклассами этой классификации.
    Безусловно, эту классификацию (как, впрочем, и все предыдущие классификации) можно при необходимости развивать: либо при более подробном рассмотрении видов ресурсов, либо в результате введения большего числа градаций.
    Контрольные вопросы
    1. Перечислите основные свойства систем.
    2. Приведите основания классификации моделей.
    3. Классификация абстрактных моделей.
    4. Классификация материальных моделей.
    5. Различия между моделью и оригиналом.
    6. Сходство между моделью и оригиналом.
    7. Модель «черного ящика». Приведите пример, когда эта модель единственно возможна.
    8. Модель состава системы. Приведите пример:
    1
    Существуют и другие подходы к определению понятия сложной системы.

    36 а) моделей, имеющих одинаковый элементный состав, но различаю- щихся делением на подсистемы; б) моделей, имеющих одинаковые подсистемы, но различающиеся элементным составом.
    9. Второе определение системы.
    10. Динамическая модель «черного ящика». Приведите пример.
    11. Динамический вариант модели состава. Приведите пример.
    12. Динамический вариант структурной схемы.
    13. Понятие состояния системы и переменных состояния системы.
    14. Классификация математических моделей систем.
    15. Условия физической реализуемости математических моделей.
    16. Основания классификации систем.
    17. Классификация систем по происхождению.
    18. Классификация систем по типам переменных (входных, выходных и состояния).
    19. Классификация систем по способам управления.
    20. Виды систем в соответствии с ресурсным обеспечением. Приведи- те пример системы: а) малой и сложной; б) большой и простой; в) большой и сложной.

    37
    2. АВТОМАТНОЕ ОПИСАНИЕ СИСТЕМ. ТЕОРИЯ
    КОНЕЧНЫХ АВТОМАТОВ
    В том случае, если множества входных
    X, выходных Y и внутренних переменных
    Q являются конечными, мы приходим к так называемому автоматному описанию системы. Для этого случая разработана достаточ- но разветвленная, хорошо формализованная
    теория конечных автома-
    тов. Конечными автоматами можно описывать любые цифровые устрой- ства и элементы. Анализ и синтез цифровых устройств также успешно может быть осуществлен с применением теории конечных автоматов.
    Для изучения этого раздела достаточно знать методы формальной логи- ки, теорию множеств, теорию графов и основы абстрактной алгебры.
    Естественно, что и пользоваться при этом мы будем понятиями, опре- делениями и терминологией (то есть профессиональным языком), приня- тыми в соответствующих разделах дискретной математики [7].
    2.1. Основные понятия. Способы задания автоматов
    2.1.1. Определение абстрактного автомата
    Пусть
    X={x
    1
    ,
    x
    2
    ,

    x
    m
    } и Y={y
    1
    ,
    y
    2
    ,
    … y
    k
    } – два произвольных множе- ства элементов, которые будем называть
    алфавитами, а их элементы –
    буквами алфавита. Конечную упорядоченную последовательность букв назовем
    словом в данном алфавите. Обозначим
    *
    X и Y

    – множества всех слов в алфавитах
    X и Y соответственно. Тогда произвольное преоб- разование дискретной информации можно задать как однозначное отоб- ражение
    S множества слов
    *
    X во множество слов
    *
    Y . Отображение S называется алфавитным отображением или алфавитным оператором, а алфавиты
    X и Y – входным и выходным алфавитами оператора S. Каждо- му входному слову
    1 2
    k
    i
    i
    i
    x x
    x
    =
    x
    оператор
    S сопоставляет выходное слово
    1 2
    k
    j
    j
    j
    y y
    y
    =
    y
    . Поэтому для каждого
    *
    X

    x
    существует свое
    *
    Y

    y
    , та- кое, что y
    =S(x). То есть S есть функция, область определения которой
    *
    X , а область значений –
    *
    Y .
    В общем случае отображение
    S может быть частичным, т. е. не всюду определенным. Это позволяет рассматривать отображение
    S как оператор в одном и том же расширенном алфавите
    Z = XY. Частичное отображе- ние
    S множества
    *
    Z в себя, определенное на словах, состоящих только из
    {x
    1
    …x
    m
    }, можно выбрать таким образом, что оно будет совпадать с отоб-

    38 ражением
    S множества
    *
    X
    в
    *
    Y
    . Любой абстрактный автомат реализует некоторый оператор
    S или индуцирует некоторое отображение S.
    Условия, накладываемые на автоматные отображения, рассмотрим несколько позже, а сейчас отметим ряд допущений, связанных с поняти- ем абстрактного автомата: а) наличие произвольного числа отличных друг от друга состояний ав- томата и свойство мгновенного перехода из одного состояния в другое; б) переход из одного состояния в другое оказывается возможным не ранее, чем через некоторый промежуток времени ∆
    (
    0
    ∆ > – интервал дискретности) после предыдущего перехода; в) число различных входных и выходных сигналов конечно; г) входные сигналы − причина перехода автомата из одного состояния в другое, а выходные сигналы – реакция автомата на входные сигналы и относятся они к моментам времени, определенным соответствующим переходом автомата из состояния в состояние.
    Учитывая это, можно интерпретировать автомат как устройство, ра- ботающее в дискретном времени '
    t
    n
    = × ∆
    0
    (
    )
    n N

    . На каждый входной сигнал
    x(t) автомат реагирует выходным сигналом y(t), где
    0
    t = – норми- рованное время. Связь между входом и выходом определяется текущим состоянием автомата
    q и задается функцией выхода y=λ(q, x), а переход автомата из одного состояния в другое – функцией переходов
    q=δ(q, x).
    Теперь можно дать определение абстрактного автомата. Это пятерка объектов:
    (
    )
    , , , ,
    A
    X Y Q
    =
    λ δ , где
    X = {x
    1
    ,
    x
    2
    ,
    … x
    m
    } − входной алфавит или множество входных состоя- ний;
    Y={y
    1
    ,
    y
    2
    ,
    … y
    k
    } − выходной алфавит или множество выходных со- стояний;
    Q={q
    1
    ,
    q
    2
    ,
    … q
    n
    } − множество внутренних состояний; δ: Q×XQ
    – функция перехода;
    λ: Q×XY – функция выхода.
    Если
    Q < ∞ , то мы имеем дело с конечным автоматом, если Q – мно- жество счетное – то с бесконечным. Если начальное состояние зафикси- ровано (например,
    q
    1
    ), то автомат называется инициальным. Таким обра- зом, по неинициальному автомату можно
    n способами задать инициаль- ный автомат.
    В приведенном определении ничего не сказано о времени, ни о непре- рывном, ни о дискретном. Таким образом, представление абстрактного автомата или его интерпретация как некоторого устройства, на вход ко- торого в дискретные моменты времени поступают сигналы и в эти же

    39 моменты времени выдаются выходные сигналы, позволяет только более наглядно представить его работу.
    С другой стороны, описание реального устройства, функционирую- щего в реальном времени, в виде автомата является абстрактной моде- лью. Следовательно, как всякая модель, автоматная модель является упрощенной (фактически время перехода не нулевое), конечной (описы- вает систему только на уровне входов, выходов и состояний) и прибли- женной (реальное поведение системы может отличаться от модельного за счет помех, непредусмотренных внешних воздействий и т.п.).
    Покажем теперь, каким образом определить отображение
    S, индуци- руемое заданным конечным автоматом. Возьмем интерпретацию автома- та как устройства, функционирующего в дискретном времени. Предпо- ложим, что автомат инициальный и задано начальное состояние
    q
    1
    . В каждый момент времени, отличный от нулевого, на вход автомата посту- пает входной сигнал
    x(t) – произвольная буква входного алфавита x(t)∈X, а на выходе возникает некоторый выходной сигнал
    y(t) – буква выходно- го алфавита
    y(t)∈Y. Для данного автомата его функции δ и λ могут быть определены не только на множестве
    Х всех входных букв, но и на множе- стве
    *
    X
    всех входных слов. Действительно, для любого входного слова
    1 2
    k
    i
    i
    i
    x x
    x
    =
    1   2   3   4   5   6   7   8   9   ...   35


    написать администратору сайта