1. Понятие дискретной динамической системы
 Скачать 0.51 Mb.
|
1.Понятие дискретной динамической системы.Динамическая система − математическая абстракция, используемая для описания и изучения систем, эволюционирующих с течением времени; представляет собой математическую модель некоторого объекта, процесса или явления. ДС может быть представлена как система, обладающая состоянием (находящаяся в некоторой ситуации). При таком подходе, ДС описывает процесс перехода системы из одного состояния в другое. Таким образом, ДС характеризуется своим начальным состоянием и законом перехода системы из начального состояния в другое. Различают ДС с дискретным временем (поведение ДС описывается последовательностью состояний) и с непрерывным временем (состояние ДС определено для каждого момента времени). Параллелизм - возможность одновременного выполнения действий, переходов в нескольких подсистемах ДС. Асинхронность - отсутствие ограничений на относительную длительность осуществления перехода, зависящую от многочисленных неконтролируемых факторов. При детерминированности каждая следующая ситуация в системе однозначно определяется предыдущей (иначе система является недетерминированной). 2.Дискретное время. Дискретная информация.В дискретном устройстве могут быть выделены каналы, через которые оно осуществляет обмен информацией с внешней средой. Информация поступает через входные каналы, перерабатывается устройством в соответствии с его назначением; результат выдается через выходные каналы. Работа различных устройств осуществляется тактами. На каждом такте под действием входного воздействия протекает переходный процесс, связанный с изменением внутреннего состояния и выдачей выходной информации. После завершения процесса может быть подано следующее воздействие, относящееся к следующему такту. В одних случаях тактность обеспечивается специальным устройством – генератором синхронизирующих импульсов. При этом длительность такта определяется временем протекания самого длительного переходного процесса. В других случаях новый такт начинается сразу после получения сигнала о завершении переходного процесса, относящегося к предыдущему такту. Это повышает быстродействие устройства, но требует дополнительных аппаратных затрат. Пусть t=0, 1, 2, … – начальные моменты времени тактов. Ноль соответствует началу работы. Процесс, относящийся к такту t (подача входного воздействия, изменение состояния, выдача выходного воздействия) происходит мгновенно в момент времени t. Обычно входная и выходная информация имеет вид сигналов, принимающих конечное множество значений, т.е. информация дискретна. Каждому значению можно поставить в соответствие некоторый символ (букву). Множество букв называется алфавитом. В этом случае информацию называют словесной. Последовательность букв алфавита называется словом. Непрерывную информацию можно с любой степенью точности в том или ином смысле аппроксимировать дискретной, а дискретную представить в виде словарной. Наиболее часто используются дискретные устройства, осуществляющие переработку слов над алфавитом {0, 1}. 3.Понятие асинхронного процесса. Траектория АП. Максимальная траектория.Понятие АП описывает поведение системы следующего вида. Есть множество ситуаций и за один такт система может перейти к новой ситуации. При этом есть два выделенных множества ситуаций:
Формально АП - четверка <S, F, I, R>, где S ={si}, i=  - непустое множество ситуаций;F - бинарное отношение непосредственного следования, определенное на множестве S  S (F SS);I - множество инициаторов (I S), т.е. таких ситуаций из S, что из skI, skFsp следует, что spI. Далее будем обозначать i1, i2, … .R - множество результантов (R S), то есть таких ситуаций из S, что из siFsj, siR следует, что sjR (I R= ). Далее будем обозначать r1, r2, … .Как правило, I≠ и R ≠ . Если I=R= , то АП называется автономным.Их выбор также делается на основе семантики процесса. Отношение F можно изобразить орграфом, вершины которого соответствуют ситуациям асинхронного процесса. Дуга исходит из si и входит в sk, тогда и только тогда, когда sjFsk. Поведение системы описывается последовательностью ситуаций системы (s1, s2, …, sk) такой, что siFsi+1 (i=1,k). Такая последовательность называется траекторией. Любую подпоследовательность траектории, не совпадающую с самой траекторией, будем называть отрезком траектории. Траектории, которые не являются отрезками никаких других траекторий, называются максимальными. |