Содержание к диссертации
Введение
1 АМТ в чистой среде 29
1.1 О количестве состояний в АМТ 29
1.2 О стартовых состояниях АМТ . 30
1.3 О переводимости состояний АМТ 46
1.4 О функции Шеннона процесса полного самоочищения и глубине диаграммы Мура АМТ 51
2 АМТ в загрязненных стационарных средах 69
2.1 О финальных состояниях АМТ 69
2.2 О стартовых состояниях АМТ 71
2.3 О переводимости состояний АМТ и глубине диаграммы Мура АМТ 76
3 АМТ в загрязненных нестационарных средах 85
3.1 О свойствах диаграммы Мура АМТ 85
3.2 О допустимых входных словах и сверхсловах для АМТ 86
3.3 Об автоматной представимости допустимых входных слов и сверхслов для АМТ 101
Литература 105
- О стартовых состояниях АМТ
- О функции Шеннона процесса полного самоочищения и глубине диаграммы Мура АМТ
- О переводимости состояний АМТ и глубине диаграммы Мура АМТ
- Об автоматной представимости допустимых входных слов и сверхслов для АМТ
Введение к работе
Транспортировка вещества в биологических системах относится к числу важнейших характеристик их жизнедеятельности. В многообразии форм механизмов такой транспортировки обращают на себя внимание так называемые ресничковые механизмы, которые присутствуют в иммунной системе, почках, легких и других органах. Нас будет интересовать такой механизм в легочной системе. Этот механизм осуществляет клиренс (самоочищение) легких. Этот процесс осуществляется следующим образом.
Как известно, легкие представляют собой древовидную структуру [3, 4], в которой реализуются различные необходимые для жизнидеятельности процессы, такие как газообмен, иммунная защита, самоочищение (транспортировка вещества по легким из нижних слоев в верхние) и другие.
Процесс транспортировки вещества по легким осуществляется за счет ресничкового механизма. Его образует поле ресничек, покрывающих внутреннюю часть бронхов легких, которое способно загружаться веществом, поступающим из вне, и перемещать его, а также вещество, образовавшееся за счет жизнидеятельности организма, из нижних слоев в верхние, и в итоге удалять его во вне с потоком выдыхаемого воздуха. Этот механизм, который осуществляет транспортировку вещества снизу вверх, и является предметом нашего изучения.
Основным результатом для нас будет построение математической модели механизма транспортировки вещества по легким, постановок ключевых задач для этой модели и их решения, которые имеют содержательную интерпретацию.
Построенная нами математическая модель выступает как идеализация
реальной ситуации и изучается в предположениях дискретности времени и вещества, а также расширенных возможностей для вариаций характеризующих эту модель параметров, например глубины дерева легких, емкостей ресничек и их мер переброса, а также продолжительности времени функционирования модели.
Подобная ситуация возникает в математической физике, когда исследуются модели колебания струны или распространения тепла по стержню и отвлекаются от того, что реальные струны и стержни всегда ограниченной длины.
Работа состоит из трех глав.
В первой главе рассматривается случай функционирования здоровых легких в экологически чистой среде, то есть не содержащей загрязнений по отношению к легким.
Оказалось, что в этом случае в качестве модели может быть использован подходящий автомат [21], свойства которого могут дать ответ на основные вопросы, связанные с функционированием механизма транспортировки.
Основным понятием, характеризующим процесс транспортировки является конфигурация распределенного по легким вещества. Эти конфигурации могут по-тактово переходить друг в друга по законам, которые определяются локальным взаимодействием ресничек между собой. Эти законы могут моделироваться автоматом, а тем самым осуществляется сведение изучения механизма транспортировки к свойствам возникающего автомата, состояниями которого являются конфигурации, а законы их перехода друг в друга — функциями перехода для этого автомата.
К числу основных вопросов здесь относятся описание диаграммы Мура построенного автомата, оценка числа состояний в ней, нахождение диаметра этой диаграммы, описание стартовых состояний и их числа, нахождение средней глубины диаграммы, указание критерия переводимости одного состояния в другое и оценка времени переводимости, нахождение времени полного самоочищения и др.
Важно отметить, что возникший в случае чистой среды автомат явля-
ется автономным и потому его диаграмма образует частичный порядок, что позволяет использовать имеющиеся в теории автоматов результаты, что и было использовано автором.
Основным итогом первой главы является решение перечисленных выше задач.
Во второй главе рассматривается случай функционирования легких в загрязненных стационарных средах. В этом случае оказалось возможным обобщить рассмотрения первой главы до представления механизма транспортировки в виде автомата, который уже не является автономным и состояния которого по-прежнему представляют собой конфигурации, означенные в первой главе.
В третьей главе обобщается явление стационарности до рассмотрения переменных сред. Оказалось возможным на основе рассмотрений стационарных сред из первой и второй глав получить ответы на наши основные вопросы и для нестационарных сред.
Рассмотрены также новые вопросы, к числу которых относится описание сред, в которых функционируют легкие с заданной долей своей загрязненности. Это достигнуто как за счет рекуррентно-комбинаторных средств, так и алгебраических средств.
Таким образом, предлагаемое исследование привело к намеченной цели. Построена модель, содержательно адекватная механизму транспортировки вещества по легким. Поставлены естественные задачи для нее и получены их решения. В метрических случаях они доведены до конца либо даны с достаточно точными оценками, а в качественных описаны аналитически и конструктивно.
Для нашей модели мы здесь введем необходимый формализм, с помощью которого и будет построена автоматная модель транпортировки вещества по легким (АМТ). Этот формализм будет широко использоваться далее в тексте уже без специальных повторений и ссылок на введение.
В то же время для наглядности изложения мы будем широко использовать терминологию, характерную для описания функционирования легких на содержательном уровне, употребляя такие термины, как вещество, рес-
ничка, переброс, моменты времени, загрязнение, самоочищение и т.п.
Перейдем к более формальному изложению работы по главам.
В первой главе формализуется механизм транспортировки вещества по легким в чистой среде путем построения конечного автомата, поведение которого адекватно указанному явлению. Сведение механизма транспортировки к автомату позволяет поставить актуальные вопросы по отношению к этому механизму и получить на них ответы за счет исследований соответствующего автомата.
К числу таких вопросов относятся описание многообразия типов загрязнения легких, оценка их числа, выделение таких загрязнений, которые не имеют "предшественников", описание всей схемы типов загрязнений и логики их переходов друг в друга, указание времени полного самоочищения легких как в среднем, так и в худшем случаях.
Все эти свойства имеют прозрачную интерпретацию на языке автоматов и в этой главе получают исчерпывающее описание в автоматных терминах.
Легкие представляются полным дихотомическим ориентированным к корню деревом, которое называется 1-деревом и обозначается -D-1, со следующими параметрами.
Пусть N - множество натуральных чисел, No = {0}UN, Njt = {1,2,3,..., /г} и Z, І Є N, считается глубиной этого 1-дерева. Считается, что ребро 1-дерева D-1, инцидентное корню, имеет глубину 1.
Каждое ребро из D~l разделено на п, п Є N, равных частей, называемых ресничками, и занумерованных числами і, г Є Nn, возрастающими в направлении, обратном ориентации ребра.
Каждому ребру глубины j, j Є N/, приписывается два числа 2l~^b и 2l~ir, где Ь, г Є N и г < Ь, называемых емкостью и мерой переброса ресничек ребер глубины j, соответственно.
Такое I-дерево D~l с описанными выше параметрами Ь, г, п и / обозначается -D_1(6, г, п, /).
С этим 1-деревом связывается некоторый процесс, который называется процессом транспортировки вещества по I-дереву D~l(b, г, п,1). Он обусловлен рядом допущений.
Считается, что в D~l{b, г, п, I) заданы распределения нагрузок по всем ресничкам, учитывая, что нагрузка может быть нулевой. Пусть V — суммарная нагрузка по всем ресничкам, а V — максимально возможная суммарная нагрузка по всем ресничкам. V назовем объемом 1-дерева (легких), а V — исходным объемом загруженности 1-дерева.
I-дерево D~l{b, г, п,1) с исходным объемом загруженности V обозначается D~l{b, г, n,l\V).
Каждая ресничка осуществляет прием вещества извне и переброс своей нагрузки на следующую ресничку с меньшим номером внутри ребра.
Прием ресничкой вещества, имеющего массу d, d Є No и d ^ V — V, из внешней среды внутри ребра уровня j, j Є N/, осуществляется по следующему правилу (для этого правила ориентация считается обратной к заданной).
Ai) Если нагрузка реснички равна ее емкости, то прием вещества не осуществляется.
Бі) При нагрузке а?ь меньшей емкости первой с такой назрузкой реснички, она осуществляет прием вещества максимально возможной массы <^2, такой что di < min(2'_:7'6 — d\,d), где 2l~^b - емкость этой реснички.
Вх) Следующая за ресничкой из Бі) принимает массу d%, как и в Б^, с заменой там d на d — g^.
Гі) Оставшаяся масса вещества опускается до следующей реснички с большим номером в ребре, для которой не выполняется условие Ai). Она осуществляет прием вещества по правилу Bi) или Бі).
Ді) Если ресничка в рассматриваемом ребре является последней, не удовлетворяющей условию Аі), то оставшаяся масса вещества делится пополам (если число нечетное, то та из частей, которая на единицу больше другой, опускается на левое ребро, при условии, что реснички поддерева, инцидентного этому ребру, могут принять это вещество, в противном случае оставшееся вещество передается правому ребру); и каждая из частей вещества воспринимается соответствующими ребрами, как описано выше.
Ei) Процесс, описываемый позициями Аі) — Ді), начинается с ребра, которое инцидентно корню.
Переброс ресничкой вещества осуществляется на соседнюю ресничку с меньшим номером внутри ребра уровня j, j Є N/, по такому правилу.
А2) Если следующая ресничка имеет не нулевую нагрузку, то переброс с реснички не осуществляется.
Б2) Если нагрузка реснички не превосходит ее меры переброса 21~^г и не выполнено условие А2), то перебрасывается на следующую вся нагрузка реснички и считается, что ее нагрузка становится равной нулю.
В2) Если на ресничке нагрузка тит> 2'~V, то она перебрасывает на следующую ресничку нагрузку 21~^г и оставляет у себя нагрузку т — 21~^г.
Если ресничка в ребре последняя, то переброс нагрузки осуществляется по правилам А2), Б2), В2).
Г2) Если ребро инцидентно корню, то переброс с наименьшей по номеру реснички осуществляется в среду по правилам Б2) и В2) в предположении, что среда играет роль реснички с нулевой нагрузкой.
Д2) Если ребро не инцидентно корню, то есть его вершина инцидентна следующему ребру, то нагрузка с наименьшей по номеру реснички этого ребра передается наибольшей по номеру ресничке другого ребра по правилам А2), Б2), В2).
Считается, что процесс транспортировки вещества по 1-дереву D~l(b,r,n,l\V') осуществляется в дискретные моменты времени *= 1,2,3,...
В первый момент I-дерево D~~l{b, г, п, I; V) имеет заданное распределение нагрузок по его ресничкам.
Ко второму моменту осуществляется прием вещества массой d(l) по правилам Ai) — Ei), и затем осуществляется переброс нагрузок с реснички на ресничку во всем 1-дереве или выброс в среду в соответствии с правилами А2), Б2), В2), Г2), Д2). А если подается масса d, не превосходящая объема I-дерева, то та ее часть, которая не осела на ресничках, выбрасывается в среду.
Если в каждый момент t = 1,2,3,... все реснички I-дерева -D-1(6, г, п,1; V) осуществляют прием вещества нулевой массы, то такой процесс называется процессом транспортировки вещества по этому I- де-
реву в чистой среде. При наступлении момента t, в который все реснички I-дерева D~1(b, г, п, I; V) впервые стали равными нулю, считается, что произошло полное самоочищение этого I-дерева.
Под распределением нагрузки V I-дерева -D_1(6, r,n, Z; V) понимается любое из возможных распределений нагрузок всех его ресничек таких, что суммарный объем их нагрузок равен V. Ясно, что V < V, где V - объем 1-дерева )^(6,7^,71,/) mV = 2l~1bnl. Такие распределения называются конфигурациями нагрузки V по ресничкам 1-дерева -D_1(6, г, п,/).
Занумеруем все реснички 1-дерева D~l(b, г, тг, /) таким образом, что ресничка с номером ijk является fc-ой ресничкой j-vo ребра глубины г, где 1 1 < j < 2г_1, 1 < k < п, а нумерация ребер одной глубины идет слева направо. Тогда в каждый момент t конфигурацию нагрузки V'(t) в I-дереве D~l(b, г, п,1) можно задать набором
q{t) = (дш(і), qm(t),..., qijk{t),..., Яп^пШ ,
в котором каждая координата qijk(t) равна нагрузке реснички с номером ijk в момент , причем 0
Пусть в процессе транспортировки конфигурации нагрузки V'{t) в каждый момент t изменяются по правилам Лг) — Дг)- Тогда процесс транспортировки можно представить некоторым конечным автономным автоматом Л(6, г, п, /) с одним финальным состоянием [21]. Состояниями этого автомата являются конфигурации нагрузок V'(t) в I-дереве D~1(b: г, п, /), которые называются также состояниями этого 1-дерева, а законы перехода из одного состояния в другое считаются указанными выше.
Далее в параграфах этой главы изучаются свойства автомата А(Ь, г, п, /).
О количестве состояний АМТ.
Если В — некоторое множество, то \В\ означает его мощность.
Понятие состояния 1-дерева не зависит от параметра г, а полностью определяется параметрами 6, п, I и распределением вещества по его ресничкам. Учитывая отмеченную независимость понятия состояния 1-дерева
от г, обозначим через Q(6, n, /) множество состояний 1-дерева D~x(b, г, п, /), полагая далее, что п > 1.
Возникает задача нахождения величины |Q(6, п,/)|, решение которой доставляет следующее утверждение.
Теорема 1. Имеет место соотношение
|Q(M,0l=ni=1(2'-Wl)^4 Следствие. Справедливы следующие оценки
6(2'-1).п . 2(2'-1-1).„ < |Q(b>njQ| < (Ь+ !)(2'-1).» . 2(2М-1).«
Следствие. Имеет место log2 |<5(Ь, тг, Z) | ж 2г при / —> оо.
О стартовых состояниях АМТ в чистой среде.
Диаграмма Мура для автомата Л(6, г, п, /) образует частичный порядок по отношению к переходу от одного сотояния в другое и допущением того, что финальное состояние никуда не переходит. Тогда последнее является наименьшим элементом этого порядка, в нем есть максимальные элементы и, вообще говоря, нет наибольшего элемента. Максимальный элемент этого частичного порядка называется стартовым состоянием. Оно характеризуется тем, что оно переходит в какое-то состояние, а в него не переходит ни одно сотояние, то есть оно не имеет "предшественников".
Следующими задачами будут выяснение того, какие состояния из Q(b,n,l) являются стартовыми и нахождение их количества. Свойство состояния из Q(b,n,l) быть стартовым зависит от параметра г, а потому для множества всех стартовых состояний из Q(b:n,l) вводится обозначение St(b,r,n,l).
Для решения этих задач выделяются некоторые свойства состояний, которые называются sv-ceoucmeaMU при b = г и ти-свойствами при b > г, где v Є N3 и и Є N5. В первом случае состояния допускают локальную характериацию через нагрузки ресничек, а во втором она доопределяется
возможным продолжением конфигураций в виде загруженных цепей (их описание см. на стр. 30 — 36).
Пусть S = {sv\v Є N3} и М = {mv\v N5}. Класс всех состояний q из Q(b,n,l) с «„-свойством при sv Є S обозначается через KSv, а класс всех состояний q из Q(b, п, I) с mv-свойством при mv Є М — через Kmv.
Теорема 2. При Ъ = г выполнено
( KSl, если I = 1 ип = 2, (1)
5t(b, г, n, /) = < Я"Л1 U ^Firs2, если / = 1 и п > 2, (2)
[ ЯГв1 U KS2 U #Яз> если 1>2 ип>2, (3) где ifSt, 7^ 0 ^Pw ecea; f из N3 и если j Є {(2), (3)}, mo для элементов строки (j) при v фи выполнено KSv $ if5и.
Теорема 3. При Ь> г выполнено
| Кт1, если I = 1 и n = 2, (1)
5t(6, г, п,/) = < ifmi U Кт2, если I = 1 и п > 2, (2)
I LUnb ^"г„, если 1>2ип>2, (3)
где ifm<, т^ 0 при всех v из N5 и если j Є {(2), (3)}, то для элементов строки (j) при v фи выполнено Kmv ^ Кти.
Теорема 4. Имеет место
\St{b, Г, 71,/)(
- |Q(6,n,0l - '
где С = (зетщ) npub = г, С = ^-іь+і)і приг < b < 2г и С = 2ч>+1 при b > 2г.
Следствие. Имеет место при I —» со:
а,) |5і(Ь,г,n,/)| ~ |Q(6,n,/)|, если 6 = г, 6^ |S(6, г, n,Z)| х |Q(6,n, 1)\, если b> г.
О переводимости состояний АМТ в чистой среде.
Заметим, что диаграмма Мура автомата A(b,r,nJ) является ориентированным к корню q* деревом. В состояние д*, которое называется финальным, переходят все остальные состояния. Финальному состоянию соответствует такая конфигурация дерева легких, при которой нагрузки всех ресничек 1-дерева D~1(b,r,n,l) равны нулю.
Возникает вопрос, как по двум данным конфигурациям 1-дерева понять, существует ли в диаграмме Мура ориентированный путь между состояниями, соответствующими данным двум конфигурациям, и если существует, то какова длина этого пути? То есть следующей задачей является нахождение критерия переводимости состояний диаграммы Мура в терминах свойств конфигураций дерева легких.
Пусть 1-дерево D~l{b,r,n,l) находится в состоянии q. Тогда через q(t) обозначено состояние этого 1-дерева в момент , полагая, что в первый момент оно находится в состоянии q, то есть q(l) = q.
Состояние q1 I-дерева D_1(6, г, n,/) переводимо в состояние q2 этого 1-дерева, если для некоторого , такого что t > 1, будет выполнено ql(t) = q2. Очевидно, такое t единственное.
В состоянии q ресничка с номером ijk 1-дерева D~x{b} г, п, /) при ( > О называется характеристической ресничкой этого состояния, если для любой другой реснички с номером i'j'k' со свойством qi'j'k' > 0 справедливо г1 > г и при і' ~ і выполнено к' > к.
Пусть состояние q 1-дерева D~l{b, г, п, /) имеет s характеристических ресничек с номерами i\j\k\, 1232^2, , isjsks, где s Є N. Из определения характеристических ресничек вытекает, что і\ = Ї2 — — is и Лгі = / = = kS) то есть все характеристические реснички состояния q принадлежат ребрам ju hi - > js одной и той же глубины 1-дерева, которая обозначена через і, и имеют один и тот же номер внутри ребер этой глубины, который обозначен через к. Следовательно, множество характеристических ресничек состояния q можно задать их номерами следующим образом: {ijik,iJ2kt... ,ijsk}, где s Є N2<-i. Множество ребер, которым принадлежат характеристические реснички состояния q обозначено Js, то
есть Js — {ji7J2, ,js}, а множество характеристических ресничек состояния q обозначено Afq(i, k,Js).
Величина Vq(t), равная Yli=iYlj=iY^=iQijk(t), называется объемом состояния q(t).
Очевидно, что состояние меньшего объема не переводимо в состояние большего объема. Поэтому рассматривается задача о переводимости состояний ql в д2 из Q(b, п, /) в случае, когда Vqi > Vq2.
Задача о переводимости состояний ql в q2 в случае, когда Vqi — О и Vq2 = 0, тривиальна, так как q1 и q2 равны и совпадают с финальным состоянием д*, которое переводимо в себя за любое время.
В случае, когда Vqi > 0 и Vq2 = О, задача о переводимости этих состояний легко решается. В этом случае q2 = q*, и, очевидно, д1 переводимо в
Далее решается задача о переводимости состояния ql в состояние q2 в случае, когда Vqi > 0 и Vq2 > 0.
Теорема 5. Если {g\g2} С Q(b,n,l), q2 $ St(b,r,n,l), Vqi = Vqi, Vqi > 0, Vq2 > 0, Л/^і(г'і, ki,J~Sl) и Л/"д2(г2, k2,JS2) — множества характеристических ресничек состояний q1 и q2, соответственно, то q1 переводимо в q2 точно тогда, когда выполнены следующие условия:
а) Ч > Н и при г'і = г2 имеет место k\> к2,
б) q\{ii - г2)п + к1-к2 + 1) = q2
Теорема 5 решает задачу о переводимости двух любых состояний q1 в д2 из Q(b,n,l) в случае, когда объемы этих состояний равны. Далее рассматривается та же задача в случае, когда объемы этих состояний различны,
ТО ЄСТЬ Vqi > Vq2.
Главная идея решения этой задачи заключается в том, чтобы найти момент t = (g\g2), такой что Vqi^_^ > Vq2 и VqX^ < Vq2. Если в момент t будет выполнено V info = Vq2, то используется теорема 5 для решения этой задачи. Если же в момент t выполняется Vqin\ < Vq2: то заключается, что д1 не переводимо в д2. Нахождение t описывается на стр. 48.
Теорема 6. Если {q1,q2} С Q(b,n,l), q2 St(b,r,n,l), Vqi > Vq2, Vqi > 0, Vqi > 0, Mqi(ii, ki, JSl), Л/*92(г, к, Js) uJV^^ij, kf, JSi) — множества характеристических ресничек состояний q1, q2 и q1^), соответственно, mo q1 переводимо в q2 точно тогда, когда выполнены следующие условия:
б) Ц > і и при ц — г имеет место k$ > к,
в) q1(t+ (ц - i)n + k~t - к) = q2.
О функции Шеннона процесса полного самоочищения и о глубине диаграммы Мура АМТ в чистой среде.
Введем функцию L(b, г, п, I, V) для 1-дерева D~l{b, г, п,1\ V), которая равна наибольшему из времен, за которое происходит полное самоочищение D~1(b, г, п, /; V) при произвольном начальном распределении загрузки V этого 1-дерева. Эту функцию обычно называют сложностной функцией Шеннона.
Теорема 7. Функция L(b: г, п, /, V) в зависимости от соотношений параметров b, г,п,1 и V принимает следующие значения:
если (21 - l)bn
если 0 < V < (21 - 1)Ьп, то г) при г = 1 имеем:
а) если V < Ьп, то
Ь{Ь,1,щ1У)
і -1 \/ і
V + Ь{п — 1), если I = 1 и п Нтf' 2Vr—]-[+nl — 1, иначе;
б) если bn
L(b, 1, п, I, V) = V' + n(l + b-l)- 1;
в) если Vі > Ьп+ (I — 1)п, то
]-^[+2b(ni-i), если к3 = 1 и h3 = 1,
L{b,r,nJ,V) = < f b. \
1 2П^[+(Ь-1)(п(*-*з+1)-/»з)+пМЬ иначе;
гі) при г > 1 имеем:
а) если V < пі, то L(b, r,n,l, V) = V' + nl — 1;
б) если V > пі, то
г/. , тл/ч ґ l^:[+2]|l(ni-i), если k3 = luh3 = l,
L(b,r,n:l,V) = < / ь, \
fe - 1 + [i - ^2(^ + l)j, h = nH^-j^^H,
ЬЛз = V - nl - (2'-*3 -1)(6- l)n - 2'-*3(6 - l)(n - h3) + 1.
Как отмечалось выше, диаграмма Мура автомата A(b, г, n, /) является деревом, глубина которого считается глубиной G(A(b, г, п, /)) этой диаграммы.
Следствие. G(A(b,r,n,l)) =][(2^ ~ !)
Далее находится среднее значение по всем функциям L(b, r,n,l, V) для всевозможных загрузок V7, то есть величина
1 J^ Lap. (b,r,n,l) = — - 2^ Ь(6, г, п, /, V).
Пусть L(b,r,n,l) — maxi
Теорема 8. Для Lcp.(b,r,n,l) выполнено
Lcp.(b, г, п, I) ~ 2п][/ при I —> оо.
Следствие. Lcp. (b, r, n, I) ~ L(6, r, n, l) при I —> со.
Во второй главе формализация механизма транспортировки вещества по легким из первой главы распространяется на случай загрязненной стационарной во времени среды.
В этой главе процесс транспортировки вещества по легким представим некоторым конечным автоматом Аа(Ь, г, п, I) со входом. Входной алфавит автомата Аа(Ь, г, тг, /) состоит только из одной буквы а, где а Є Ny, то есть он является автономным. На вход такого автомата могут подаваться как слова, так и сверхслова.
Далее в параграфах этой главы изучаются свойства автомата Aa(b,r:n,l).
О финальных состояниях АМТ в загрязненных стационарных средах.
Состояние q из Q(b,n,l) называется финальным для автомата Аа(Ь, г, n,Z), если оно переходит только в себя.
Главными задачами этого параграфа являются описание всех финальных состояний автомата Ла(6, г, п,/) для каждого а из Ny и указание их числа.
Пусть Fm(6, г, п, /, а) — множество финальных состояний автомата Aa{b,r,n,l).
Через q* обозначено состояние автомата Aa(b,r:n,l), при котором все реснички, кроме реснички с номером 111, имеют нагрузки, равные своей емкости, а ресничка с номером 111 имеет нагрузку 21~г(Ь — г).
При а > 2l~lr автомат Ла(&, г, п, /) имеет только одно состояние, которое переходит в себя, и оно совпадает с а > 21~гг, то Fin(b,r,nJ,a) = {q*}.
При а < 2;_1г все финальные состояния описываются так.
Теорема 9. Для q из Q(b, п, I) при а < 2l~lr выполнено q Є Fin(b, г, п, /, а) точно тогда, когда для q одновременно выполнены следующие условия: a) qui < 2г-1(6 — г) при a = 2l~lr и дш = 0 при а < 2l~lr,
б) для любого номера ijk, такого что ijk ф 111, ijk -ф Ijn при j Є N2i-i и qijk = 0, при к <п имеет место —0, а при к — п имеет место ?(г+1)/1 = 4(i+i)j"i — 0; где ребра f uj" уровня i + 1 инцидентны ребру j уровня г.
Теорема 10. Если а < 21~1г, то log2\Fin(b, г,п, 1,cl)\ х 21 при I —» со.
Следствие. Диаграмма Мура автомата Ла(Ь, г, п, Г) предсталяет собой дерево при а > 2l~lr и лес при а < 2l~lr.
О стартовых состояниях АМТ в загрязненных стационарных средах.
Состояние g из Q(b,n,l) называется стартовым для автомата Aa(b,r,n,l), если в него не переходит ни одно из состояний множества Q(b,n,l).
Входная буква а при заданных / и b представима в виде a = k-2l~lb+kf, где к' < 21~1Ь. Если а > 21-1г, то к > 0 при 6 > г и к > 0 при b = г.
Пусть D~l{b,г,п, I) — неполное поддерево 1-дерева Z?_1(6,г,п,I), такое что оно имеет глубину Щ в случае, когда либо п не делит к нацело, либо п делит к нацело и при этом к' = 0, или глубину ~ + 1, когда либо п делит к нацело и к' > 0, либо к = 0. При этом количество ресничек на последнем (нижнем) уровне этого поддерева равно либо к — [^] п, если к' = 0, либо к— [] п + 1, если А/ > 0.
Это неполное поддерево D~1(6, г, п, I) загружается таким образом, как если бы к полностью пустому этому поддереву применился один шаг процесса транспортировки в стационарной загрязненной среде подачей на вход буквы а, где а > 21~1г. Поддерево Z^"1 (6, г, ?г, Z), загруженное таким образом, обозначается D~l(b, г, п, I).
Таким образом, при а > 21~1г и b = г для D~l(b,r,n,l) выполнено: ресничка с номером 111 имеет нулевую нагрузку, все остальные реснички кроме, быть может, самых нижних ресничек имеют нагрузки, равные своим емкостям, а суммарная нагрузка по всем нижним ресничкам равна к'.
При а > 21~1т и b > г для D~l{b, г, п,) выполнено: если к = 0, то ресничка с номером 111 имеет нагрузку а — 2z_1r, а если к > 0, то ресничка
с номером 111 имеет нагрузку 2 (6 — г) и все остальные реснички кроме, быть может, самых нижних ресничек имеют нагрузки, равные своим емкостям, а суммарная нагрузка по всем нижним ресничкам равна к'.
Загруженное некоторым образом поддерево D~l(b, г, тг, /) 1-дерева D~l{b, г, 71, /), находящегося в некотором состоянии д, поресничково меньше загружено, чем D~x(b,г,тг,Г) (обозначение D~x{b^r,n,l) < D~l(b,r,n,l)), если нагрузка хотя бы одной реснички поддерева D~l(b, г, п, I) 1-дерева D~~l(b, г, тг, /) в состоянии q меньше соответствующей ей реснички поддерева D~l(b, г, тг, /) этого 1-дерева.
Состояние q из Q(b, п, I) при b — г обладает:
— Sa-свойством, если при данном q для поддерева D~2(6, г, тг, /) 1-дерева
D_1(6, г, тг,/) выполнено D~l(b,r,n,l) < D~l{b,r,n,l)\
— si-свойством, если при данном g выполнено дш > 0.
Состояние q из Q(6, тг, /) при b > г обладает:
— та-свойством, если при данном g для поддерева D~1(6,r,n, Z) I- де
рева D~x(b, г, тг, /) выполнено D~ 1(6, г, тг, /)
Класс всех состояний из Q{b,n,l) с за-свойством обозначен через KSa, класс всех состояний из Q(b:n,l) с si-свойством обозначен через К^, а класс всех состояний из Q(6, тг, /) с 7тга-свойством — через Кта.
Пусть St(b,r,n,l,a) — множество стартовых состояний 1-дерева )-1(6, г, тг, /) в стационарной среде с входным алфавитом {а}, где а Є Ny.
Теорема 11. Справедливы положения:
1) Если а > 2l~lr, то имеет место:
а) St(b, г, тг, /, а) = KSa U St(b, г, тг, Z) тг_ри b — г,
б) St(b, г, тг, /, a) = Кта U 5і(6, г, тг, /) при Ь> г.
2) Если а < 2l~lr, то имеет место:
а) St(b, г, тг, /, а) = К^ U St(b, г, тг, /) при b = г,
б) St(b, г, тг, /, а) = St(b, г, тг, I) при Ь> г.
При этом KSa ф 0, K-Sl ф 0, Кта ф 0, К8а St{b,r,nJ), Кта St(b,r,n,l) и K-Sl < St(b,r,n,l).
Теорема 12. Имеет место при I —> со;
а) St(b, г, п, I, а) ~ Q(b, п, I), если Ъ — г,
б) St(b,r,n,l,a) >: Q(b,n,l), если b> г.
О переводимости состояний АМТ в загрязненных стационарных средах и о глубине диаграммы Мура АМТ.
Здесь рассматривается задача переводимости друг в друга состояний автомата Аа(Ь, г, п, /).
Понятие переводимости состояний в загрязненной среде аналогично случаю чистой среды.
По следствию из теоремы 10 при а > 2l~lr автомат Л0(6, г, п, I) имеет только одно финальное состояние д*. В этом случае решение проблемы переводимости доставляет следующее утверждение.
Теорема 13. Если а > 2l~lr, {g\g2} С Q(b,n,l), q2 Ф g* и q2 . St(b} r, n, /, a), mo ql переводимо в q2 точно тогда, когда выполнены следующие условия: a)Vq2>Vqi,
Следствие 1. Любое состояние g из Q(b,n,l) автомата Аа(Ь,г, п, І) в случае, когда Vq > Vq*, переходит в д* за время 1, в противном случае — за
вРемя )^=wl
Следствие 2. В диаграмме Мура автомата v4a(6, г, п, I) все состояния
из Q(b,n,l), имеющие одинаковый объем, имеют путь до д* одинаковой
длины.
Следствие 3. Если а > 2'"V, то G(A*{b,r,n,l)) ==]2'ДЬГ-Ггг)[
Далее рассматривается случай, когда 0 < a < 2l~lr. По следствию из теоремы 10 в этом случае диаграмма Мура автомата Аа(Ь, г, п,1) представляет собой лес, финальные состояния которого образуют множество Fin(b,r,n,l,a). В связи с этим возникает задача о переводимости g из Q(b,n,l) в д* из Fin(b,r,n,l,a).
Цепь с номером і (цепи I-дерева D~1(b, г, п, I), идущие от листа до корня, занумерованы слева направо) обозначается С;, где і є N2j-i-
Рассматривается некоторое состояние q I-дерева Z)_1(6,r, п,1). Конфигурация нагрузок цепи Сі (ее состояние) в этом состоянии обозначается
Цепь 1-дерева D~l(b, г, п,/), функционирующая отдельно от этого I- дерева, называется изолированной цепью.
Финальным состоянием изолированной цепи (7, находящейся в состоянии qCi, называется такое ее состояние qa{T), что для любого t > 0 выполнено qc. (T + i) = qCi (Т).
Пусть Tq. - время перехода изолированной цепи С% 1-дерева D~~l(b,r}n,l), находящегося в состоянии
Рекуррентно определяемая величина Г^. описывается в леммах 2.3.1 и 2.3.2 (см. стр. 78).
Теорема 14. Если 0 < а < 2l~1r, q Є Q(b, n, I) uq*a Є Fin(b, r, n, /, a), mo g
переводимо в q* точно тогда, когда q(T) = q*, где T = maxcuieE ,_i Tq.+2.
Теорема 14 для диаграммы Мура автомата Аа(Ь: г, п, /) при О < а < 21~1г дает описание всех деревьев, корнями которых являются элементы множества Fin(b, г, п, I, а).
Решение задачи о переводимости двух любых состояний q1 и q2 из Q(6, п,/) автомата Aa(b, г,7г,/) при 0 < а < 21~гг доставляет следующее утверждение.
Теорема 15. Если 0 < а < 2l~lr, {ql,q2} С Q(b,n,l), mo q1 переводимо в q2 точно тогда, когда существует натуральное Т из отрезка [1; тахс^іеЩі-і 7 + 2], такое что ql{T) — q2.
По следствию из теоремы 10 диаграмма Мура автомата Ла(Ь, г, n, /) при 0 < а < 21~1г представляет собой лес. Наибольшая глубина дерева из всех деревьев леса называется глубиной этой диаграммы и обозначается G(Aa{b,r,nJ)).
Ы-2
Теорема 16. Если 0 < а < 2l~lr, то G(Aa(b, г, п, 1)) = 21п —
В третьей главе формализация транспортировки из предыдущих глав распространяется на случай загрязненной переменной во времени среды. Учитывается, что реально в механизме транспортировки всегда имеется загрязнение, допустимое до определенного порога, а тем самым важной становится задача описания таких переменных по загрязнению сред, в которых механизм транспортировки может функционировать с непревышением по загрязненности этого порога.
Эта ситуация, в действительности, является ключевой. Ее анализу и посвящена глава. В ней решена задача описания всех таких сред как при ограниченном времени функционирования легких, так и в потенциально неограниченном времени.
Развиты два подхода к решению этой задачи. В первом случае найдены рекуррентные описания таких сред, а во втором дано их полугрупповое описание, которое оказалось автоматным.
Все построения третьей главы основаны на автоматной идеологии, представляющей в себе механизм транспортировки как автомат, а переменную среду как множество входных слов и сверхслов для этого автомата, что позволило использовать понятия и результаты из теории автоматов для решения поставленных задач.
О свойствах диаграммы Мура АМТ в загрязненных нестационарных средах.
На основе изученного в первых двух главах случая стационарных сред в параграфе 3.1 описано построение диаграммы Мура для автоматной модели процесса самоочищения легких в нестационарных средах.
О допустимых входных словах и сверхсловах для АМТ в загрязненных нестационарных средах.
Объем загруженности 1-дерева D~l{h, г, п,1; V), равный ]5V[, где О < S < 1, называется предельным порогом загруженности этого I- дерева. Далее пишется 5V вместо ]5V[, считая, что 5V Є N.
Пусть Лт — множество всех слов ат = а(1)а(2).. .а(т), где a{t) Є Ny U {0} при t Є Nm, на котором вводится отношение частичного порядка <, полагая ат < а'т, если a (t) < a'(t) для всех t из Nm.
Для I-дерева D~l{b, г, п, I] V) слово ат из Ат называется допустимым, если при подаче на него буквы a(t) из ат в каждый момент времени t всегда выполнено a(t) + V'(t) ^ JF, где У'() — объем загруженности I- дерева D~l{b, г, п, /; V) в момент t, t Є Nm. Такое слово называется предельно допустимым для 1-дерева D~l(b,r, п, /; V), если не существует допустимого слова а/т из Ат такого, что а'т ^ ат и a/m ^ скт.
Пусть A* = (J Лт, а Aw — множество всех сверхслов (то есть слов бес-
конечной длины) aw = а(1)а(2)... а()..., где а() Є No, на котором вводится отношение частичного порядка ^, полагая аш ^ a'w, если a(t) ^ а!(і) для всех і из N.
Для 1-дерева -D_1(6, г, тг, /; V) сверхслово сґ из Аш называется допустимым, если при подаче на него буквы а (і) из а" в каждый момент времени t всегда выполнено a(t)+V'(t) ^ 5V. Такое сверхслово называется предельно допустимым для 1-дерева D~l{h,r,n,l\ V), если не существует допустимого сверхслова аГи} из Аш такого, что a,UJ ^ сҐ и o;/w 7^ aw-
Ясно, что предельно допустимые сверхслова существуют. Например, сверхслово (SV — V')5V5V ... 5V ... при 5V ^ г является предельно допустимым.
Более того, можно показать, что для всякого допустимого сверхслова а" найдется предельно допустимое а'ш такое, что сґ ^ а'ш.
Множество А — A* U Аш называется множеством квазислов. Понятия допустимости и предельной допустимости распространяются на квазислова.
Здесь главным является описание всех квазислов, как допустимых, так и не допустимых.
Пусть v(t) — нагрузка реснички с номером 111 в момент t.
Теорема 17. Слово а(1)<з(2)... a(t)... а(т) при т > 1 является предельно допустимым для дерева D~l(p,r,n,l\V') точно тогда, когда для него
выполнены следующие рекуррентные соотношения: а) для t = 1 выполнено
0(1) є <
\$-\5V], если V = О,
{0} U [2l~lr,6V - У], если и(1) = 0 и V > О,
[О, «$У - У], если v(l) ^ 2i_1r,
[2Z~V - v(l),<5V - У], если 0 < v(l) < 2l~lr\
б) для всех t = 2,..., т — 1 имеет место
t-\
[0,6V -V-J2 а{г) + 2l-lrk{t)}, если v{t) > 2^,
*=i
t-i
[2l~lr - v{t),5V -V-J2 Ф) + 1l~lrk{t)},
t=i
если 0 < v(t) < 2l~lr,
t-i
a(t) Є і
{0} U [2Z-V, 8V-W-Y, Ф) + 2Z-Vjfe(t)],
г=1
если v(t) = 0 и V'(i) ^ О, [2'"V, SV-V-J2 a(i) + г^гВД],
если v(t) = 0 и V(t) = 0,
где fc(l) = 0, &() = k(t — 1) + p(tf — 1), причем
О, если г;(і - 1) = 0, a{t - 1) = 0 и V(t - 1) ^ О,
1, иначе;
p(t - 1) =
t-i
в) для t — m выполнено а(т) ~ 6V — V — J2 а00 + 2 rk{m).
г=1
Для предельно допустимого слова ат его буква а() называется максимально возмооюной, если после подачи вещества объема а(і) в I-дерево D~l{b, г, п, I; V) в этот момент времени общий объем нагрузки V'(t) данного I-дерева будет в точности равен 5V.
Понятие максимально возможной буквы распространяется на предельно допустимые сверхслова. Буква a(t), t Є N, сверхслова оґ, называется максимально возможной, если после подачи вещества объема a(t) в I-дерево
D-1(6, r, n, Z; У) в этот момент времени общий объем нагрузки V'(t) данного I-дерева будет в точности равен 6V.
Префиксы предельно допустимых квазислов, последняя буква которых является максимально возможной, называются предельными префиксами.
Суффиксы предельно допустимых квазислов, последняя буква которых является максимально возможной, называются предельными суффиксами.
Минимальным предельным префиксом предельно допустимого квазислова называется такой его предельный префикс, длина которого больше единицы и из всех возможных предельных префиксов этого квазислова он является наименьшим по длине.
Минимальным предельным суффиксом предельно допустимого квазислова называется такой его предельный суффикс, длина которого больше единицы и из всех возможных предельных суффиксов этого квазислова, имеющих одинаковую первую букву, он является наименьшим по длине.
Ясно, что если каждый префикс сверхслова допустим, то это сверхслово является допустимым.
Теорема 18. Все минимальные предельные префиксы и суффиксы длины т, т > 1, являются предельно допустимыми словами а(1)а(2)... a(t)... а{т) длины т, где a{t) определяются рекуррентно так: а) для t = 1 выполнено
' \2l-lr,8V), еслиУ = 0,
I {0} U [21~\ 5V - V], если v(l) = 0uV>0, Є I [0,^ - V], если v{l) > 2'-V,
[2'-V - v(l), 5V - V], если 0 < v(l) < 2'-V;
б) для всех t = 2,..., т — 1 имеет место
[0,5V-V-Y1 а{і) + 2l~lrk{t) - 1], если v(t) ^ 2l~lr,
г=1
[2l~lr - v(t),6V - V - а(г') + ї1~1гЩ - 1],
г=1
a(t) Є <
если О < v(i) < 2/_1r, {0} U [^"V, <5V - V - Ё а(0 + ^rkit) - 1],
если v(t) =0 и V'(t) ф О, [2^V, 5V - V - Ё а(«) + ^гВД - 1],
если v(t) = OuV'(t) = О, где &(1) = 0, k(t) = k(t — 1) +p(t — 1), причем
О, если v(t - 1) = 0, a(t - 1) = 0 и V'(t - 1) ф О,
1, иначе;
К* - 1) =
t-i
в) для t = т выполнено а(т) = SV — V — ]Г) а(г') + 2 гк(т).
Пусть Р(6, г, (5, У) — множество всех минимальных предельных префиксов для 1-дерева D~l{b, г, п,1; V) с предельным порогом загруженности 5V, а 5(6, г, 5, 5V — 2/-1г) — множество всех минимальных предельных суффиксов для 1-дерева D~1(b1r:n,l;5V — 2l~lr) с предельным порогом загруженности 5V.
Вводится операция конкатенации над словами и сверхсловами. Если ат Є А*, а (5 Є A* U Аш, то выражение ат /? будет определять слово или сверхслово, получаемое приписыванием к ат последовательно справа всех букв из р.
Если С С А\ aDC A*UAW, то полагается С > = (J а-/3.
Через Рт(6, г, , V) обозначено множество всех минимальных предельных префиксов длины т для 1-дерева D-1(6, г, n, Z; V) с предельным порогом загруженности 5V, а через 5m(6, г, 5,5V — 2z_1r) — мно-
жество всех минимальных предельных суффиксов длины т для I-дерева D_1(6, г, та, /; 6V — 2l~lr) с предельным порогом загруженности 5V. Пусть
5(6, г, 5,6V - 2l~lr) = (J 5і(6, г, 5, У - 2'_1г),
оо г=2
Пусть е — пустое слово, для которого считаются выполненными для любого А из 5(6, г, д, 6V — 2l~lr) соотношения е А = А е = А. Полагается, что є Є S{b,r,5,5V-21^).
Распространяется операция А* и Аш на случай произвольного множества В С А* в предположении, что В* состоит из всех слов, являющихся конкатенациями слов из В, а Вш — из всех сверхслов, получаемых последовательным приписыванием слов из В.
Пусть ^д-і(6, г, n>l,6V, V) — множество всех предельно допустимых квазислов для I-дерева D~1(b, г, та, 1\ V).
Теорема 19. Имеет место
3jd-i(Ь, г, та, /, (5V, У) = Р(6, г, (5, V) (5(6, г, 5, <5У - 2/_1г) {е, 2l~lr})* U
U (5(6, г, 5, ЯУ - 2z_1r) {е, 2Z-V})W .
Следствие 1. Мощность мнооїсества всех предельно допустимых сверхслов для I- дерева D~1(b,r,n,l;V) континуальна.
Пусть T^i(5V,6,г,та,/, V) — множество всех предельно допустимых слов длины таг для 1-дерева D_1(6,r,n,/; V), Q1g-l(SV,b,r}n}l,V) — множество всех допустимых слов длины таг для 1-дерева D~l{b, г, та, /; V).
Следствие 2. Для ат из Ат выполнено ат Є Q#-i (^V, 6, г, та, Z, К') точно тогда, когда существует (5т из T^l^SV, b, г, та, I, V), что ат ^ /Зт.
Пусть Q^-i^F, 6, г, та, , У') — множество всех допустимых сверхслов для 1-дерева D~l (6, г, та, /; V) и T$_i (V, 6, r,n,l, V') — множество всех предельно допустимых сверхслов для этого 1-дерева.
Следствие 3. Для оґ из Аш выполнено аш Є Qq-i(SV, b, г, n, /, V) точно тогда, когда существует @" из Tp_i(<5V, 6, г, п,/, V), что сґ < /Зш.
Таким образом, указав все предельно допустимые квазислова, получается описание всего множества допустимых квазислов.
Об автоматной представимости допустимых входных слов и сверхслов для АМТ в загрязненных нестационарных средах.
Через QD-i(5V,b,r,n,l,V) обозначено множество всех допустимых слов для 1-дерева D~l{b,г,п, /; V), а через Td-\(5V} b,r, п, l,V) - множество всех предельно допустимых слов для 1-дерева D~l{b, г,п}1; V).
Теорема 20. Множества Qi)-i(5V,b,г,n,l,V) и Td-i(6V,b,г,n,l,V) регулярны, а множества Q^-^SV,b,r,n,l:V) u Tp-i(V,b, г, n,/, V") обще-регулярны.
Теорема 21. Для \T^i(5V,b,г,п,l,V')\ выполнены следующие соотношения:
а) еслидУ <2l~lr, то \T^(5V,b,r,n,l,V')\ = I,
б) если 6V > 2l~lr, то Іод2\Т^у (6V, 6, г, n, /, V')\ x m при m —> oo.
Основные результаты работы опубликованы в статьях [15] — [25].
Они неоднократно докладывались на семинарах механико-математического факультета МГУ им. М.В. Ломоносова "Теория автоматов" (2003-2008 гг.) и "Кибернетика и информатика" (2003-2008 гг.) под руководством академика В.Б. Кудрявцева.
Эти результаты докладывались на следующих конференциях: международная конференция по теоретической кибернетике (Пенза, 2005г.), конференции молодых ученых механико-математического факультета МГУ им. М.В. Ломоносова (Москва, МГУ им.Ломоносова, 2005 и 2006 гг.), конференция молодых исследователей института пульмонологии РАМН (Москва, ГКБ № 57, 2005г.), международные научные конференции студентов, аспирантов и молодых ученых "Ломоносов" (Москва,
МГУ им.Ломоносова, 2005, 2006, 2007 и 2008 гг.), школа-симпозиум "Биоинформатика в медицине" в рамках XV-ro юбилейного Национального Конгресса по болезням органов дыхания (Москва, Российская Академия Государственной Службы, 2005г.), международная конференция "Дискретные модели в теории управляющих систем" (Москва, МГУ им.Ломоносова, 2006г.), научные конференции "Ломоносовские чтения" (Москва, МГУ им.Ломоносова, 2006, 2007 и 2008 гг.), международная конференция "Интеллектуальные системы и компьютерные науки" (Москва, МГУ им.Ломоносова, 2006г.), третья научная конференция студентов и аспирантов кафедры МаТИС механико-математического факультета МГУ (Москва, МГУ им.Ломоносова, 2007г.).
О стартовых состояниях АМТ
Считается, что в D l{b, г, п, I) заданы распределения нагрузок по всем ресничкам, учитывая, что нагрузка может быть нулевой. Пусть V — суммарная нагрузка по всем ресничкам, а V — максимально возможная суммарная нагрузка по всем ресничкам. V назовем объемом 1-дерева (легких), а V — исходным объемом загруженности 1-дерева. I-дерево D l{b, г, п,1) с исходным объемом загруженности V обозначается D l{b, г, n,l\V). Каждая ресничка осуществляет прием вещества извне и переброс своей нагрузки на следующую ресничку с меньшим номером внутри ребра. Прием ресничкой вещества, имеющего массу d, d Є No и d V — V, из внешней среды внутри ребра уровня j, j Є N/, осуществляется по следующему правилу (для этого правила ориентация считается обратной к заданной). Ai) Если нагрузка реснички равна ее емкости, то прием вещества не осуществляется. Бі) При нагрузке а?ь меньшей емкости первой с такой назрузкой реснички, она осуществляет прием вещества максимально возможной массы 2, такой что di min(2 _:7 6 — d\,d), где 2l b - емкость этой реснички. Вх) Следующая за ресничкой из Бі) принимает массу d%, как и в Б , с заменой там d на d — G . ГІ) Оставшаяся масса вещества опускается до следующей реснички с большим номером в ребре, для которой не выполняется условие Ai). Она осуществляет прием вещества по правилу Bi) или Бі). Ді) Если ресничка в рассматриваемом ребре является последней, не удовлетворяющей условию Аі), то оставшаяся масса вещества делится пополам (если число нечетное, то та из частей, которая на единицу больше другой, опускается на левое ребро, при условии, что реснички поддерева, инцидентного этому ребру, могут принять это вещество, в противном случае оставшееся вещество передается правому ребру); и каждая из частей вещества воспринимается соответствующими ребрами, как описано выше. Ei) Процесс, описываемый позициями Аі) — Ді), начинается с ребра, которое инцидентно корню. Переброс ресничкой вещества осуществляется на соседнюю ресничку с меньшим номером внутри ребра уровня j, j Є N/, по такому правилу. А2) Если следующая ресничка имеет не нулевую нагрузку, то переброс с реснички не осуществляется. Б2) Если нагрузка реснички не превосходит ее меры переброса 21 г и не выполнено условие А2), то перебрасывается на следующую вся нагрузка реснички и считается, что ее нагрузка становится равной нулю. В2) Если на ресничке нагрузка тит 2 V, то она перебрасывает на следующую ресничку нагрузку 21 г и оставляет у себя нагрузку т — 21 г. Если ресничка в ребре последняя, то переброс нагрузки осуществляется по правилам А2), Б2), В2). Г2) Если ребро инцидентно корню, то переброс с наименьшей по номеру реснички осуществляется в среду по правилам Б2) и В2) в предположении, что среда играет роль реснички с нулевой нагрузкой. Д2) Если ребро не инцидентно корню, то есть его вершина инцидентна следующему ребру, то нагрузка с наименьшей по номеру реснички этого ребра передается наибольшей по номеру ресничке другого ребра по правилам А2), Б2), В2). Считается, что процесс транспортировки вещества по 1-дереву D l(b,r,n,l\V ) осуществляется в дискретные моменты времени = 1,2,3,... В первый момент I-дерево D l{b, г, п, I; V) имеет заданное распределение нагрузок по его ресничкам. Ко второму моменту осуществляется прием вещества массой d(l) по правилам Ai) — Ei), и затем осуществляется переброс нагрузок с реснички на ресничку во всем 1-дереве или выброс в среду в соответствии с правилами А2), Б2), В2), Г2), Д2). А если подается масса d, не превосходящая объема I-дерева, то та ее часть, которая не осела на ресничках, выбрасывается в среду. Если в каждый момент t = 1,2,3,... все реснички I-дерева -D-1(6, г, п,1; V) осуществляют прием вещества нулевой массы, то такой процесс называется процессом транспортировки вещества по этому I- дереву в чистой среде. При наступлении момента t, в который все реснички I-дерева D 1(b, г, п, I; V) впервые стали равными нулю, считается, что произошло полное самоочищение этого I-дерева. Под распределением нагрузки V I-дерева -D_1(6, r,n, Z; V) понимается любое из возможных распределений нагрузок всех его ресничек таких, что суммарный объем их нагрузок равен V. Ясно, что V V, где V - объем 1-дерева ) (6,7 ,71,/) mV = 2l 1bnl. Такие распределения называются конфигурациями нагрузки V по ресничкам 1-дерева -D_1(6, г, п,/). Занумеруем все реснички 1-дерева D l(b, г, тг, /) таким образом, что ресничка с номером ijk является fc-ой ресничкой j-vo ребра глубины г, где 1 i 1, 1 j 2г_1, 1 k п, а нумерация ребер одной глубины идет слева направо. Тогда в каждый момент t конфигурацию нагрузки V (t) в I-дереве D l(b, г, п,1) можно задать набором q{t) = (дш(і), qm(t),..., qijk{t),..., Яп пШ , в котором каждая координата qijk(t) равна нагрузке реснички с номером ijk в момент , причем 0 qijk(t) 2l lb и Хлп " qijk{t) — V(i).
Пусть в процессе транспортировки конфигурации нагрузки V {t) в каждый момент t изменяются по правилам Лг) — Дг)- Тогда процесс транспортировки можно представить некоторым конечным автономным автоматом Л(6, г, п, /) с одним финальным состоянием [21]. Состояниями этого автомата являются конфигурации нагрузок V (t) в I-дереве D 1(b: г, п, /), которые называются также состояниями этого 1-дерева, а законы перехода из одного состояния в другое считаются указанными выше.
О функции Шеннона процесса полного самоочищения и глубине диаграммы Мура АМТ
Во второй главе формализация механизма транспортировки вещества по легким из первой главы распространяется на случай загрязненной стационарной во времени среды.
В этой главе процесс транспортировки вещества по легким представим некоторым конечным автоматом Аа(Ь, г, п, I) со входом. Входной алфавит автомата Аа(Ь, г, тг, /) состоит только из одной буквы а, где а Є Ny, то есть он является автономным. На вход такого автомата могут подаваться как слова, так и сверхслова.
Далее в параграфах этой главы изучаются свойства автомата Aa(b,r:n,l). О финальных состояниях АМТ в загрязненных стационарных средах. Состояние q из Q(b,n,l) называется финальным для автомата Аа(Ь, г, n,Z), если оно переходит только в себя. Главными задачами этого параграфа являются описание всех финальных состояний автомата Ла(6, г, п,/) для каждого а из Ny и указание их числа. Пусть Fm(6, г, п, /, а) — множество финальных состояний автомата Aa{b,r,n,l). Через q обозначено состояние автомата Aa(b,r:n,l), при котором все реснички, кроме реснички с номером 111, имеют нагрузки, равные своей емкости, а ресничка с номером 111 имеет нагрузку 21 г(Ь — г). При а 2l lr автомат Ла(&, г, п, /) имеет только одно состояние, которое переходит в себя, и оно совпадает с / . Таким образом, если а 21 гг, то Fin(b,r,nJ,a) = {q }. При а 2;_1г все финальные состояния описываются так. Теорема 9. Для q из Q(b, п, I) при а 2l lr выполнено q Є Fin(b, г, п, /, а) точно тогда, когда для q одновременно выполнены следующие условия: a) qui 2г-1(6 — г) при a = 2l lr и дш = 0 при а 2l lr, б) для любого номера ijk, такого что ijk ф 111, ijk -ф Ijn при j Є N2i-i и qijk = 0, при к п имеет место ?{j(fc+i) —0, а при к — п имеет место (г+1)/1 = 4(i+i)j"i — 0; где ребра f uj" уровня i + 1 инцидентны ребру j уровня г. Теорема 10. Если а 21 1г, то log2\Fin(b, г,п, 1,CL)\ х 21 при I —» со. Следствие. Диаграмма Мура автомата Ла(Ь, г, п, Г) предсталяет собой дерево при а 2l lr и лес при а 2l lr. О стартовых состояниях АМТ в загрязненных стационарных средах. Состояние g из Q(b,n,l) называется стартовым для автомата Aa(b,r,n,l), если в него не переходит ни одно из состояний множества Q(b,n,l). Входная буква а при заданных / и b представима в виде a = k-2l lb+kf, где к 21 1Ь. Если а 21-1г, то к 0 при 6 г и к 0 при b = г. Пусть D l{b,г,п, I) — неполное поддерево 1-дерева Z?_1(6,г,п,I), такое что оно имеет глубину Щ в случае, когда либо п не делит к нацело, либо п делит к нацело и при этом к = 0, или глубину + 1, когда либо п делит к нацело и к 0, либо к = 0. При этом количество ресничек на последнем (нижнем) уровне этого поддерева равно либо к — [ ] п, если к = 0, либо к— [] п + 1, если А/ 0. Это неполное поддерево D 1(6, г, п, I) загружается таким образом, как если бы к полностью пустому этому поддереву применился один шаг процесса транспортировки в стационарной загрязненной среде подачей на вход буквы а, где а 21 1г. Поддерево Z "1 (6, г, г, Z), загруженное таким образом, обозначается D l(b, г, п, I). Таким образом, при а 21 1г и b = г для D l(b,r,n,l) выполнено: ресничка с номером 111 имеет нулевую нагрузку, все остальные реснички кроме, быть может, самых нижних ресничек имеют нагрузки, равные своим емкостям, а суммарная нагрузка по всем нижним ресничкам равна к . При а 21 1т и b г для D l{b, г, п,) выполнено: если к = 0, то ресничка с номером 111 имеет нагрузку а — 2z_1r, а если к 0, то ресничка с номером 111 имеет нагрузку 2 (6 — г) и все остальные реснички кроме, быть может, самых нижних ресничек имеют нагрузки, равные своим емкостям, а суммарная нагрузка по всем нижним ресничкам равна к . Загруженное некоторым образом поддерево D l(b, г, тг, /) 1-дерева D l{b, г, 71, /), находящегося в некотором состоянии д, поресничково меньше загружено, чем D x(b,г,тг,Г) (обозначение D x{b r,n,l) D l(b,r,n,l)), если нагрузка хотя бы одной реснички поддерева D l(b, г, п, I) 1-дерева D l(b, г, тг, /) в состоянии q меньше соответствующей ей реснички поддерева D l(b, г, тг, /) этого 1-дерева. Состояние q из Q(b, п, I) при b — г обладает: — Sa-свойством, если при данном q для поддерева D 2(6, г, тг, /) 1-дерева D_1(6, г, тг,/) выполнено D l(b,r,n,l) D l{b,r,n,l)\ — si-свойством, если при данном g выполнено дш 0. Состояние q из Q(6, тг, /) при b г обладает: — та-свойством, если при данном g для поддерева D 1(6,r,n, Z) I- де рева D x(b, г, тг, /) выполнено D 1(6, г, тг, /) d D x(b, г, тг, Z). Класс всех состояний из Q{b,n,l) с за-свойством обозначен через KSa, класс всех состояний из Q(b:n,l) с si-свойством обозначен через К , а класс всех состояний из Q(6, тг, /) с 7тга-свойством — через Кта. Пусть St(b,r,n,l,a) — множество стартовых состояний 1-дерева )-1(6, г, тг, /) в стационарной среде с входным алфавитом {а}, где а Є Ny. Теорема 11. Справедливы положения: 1) Если а 2l lr, то имеет место: а) St(b, г, тг, /, а) = KSa U St(b, г, тг, Z) тг_ри b — г, б) St(b, г, тг, /, a) = Кта U 5і(6, г, тг, /) при Ь г. 2) Если а 2l lr, то имеет место: а) St(b, г, тг, /, а) = К U St(b, г, тг, /) при b = г, б) St(b, г, тг, /, а) = St(b, г, тг, I) при Ь г. При этом KSa ф 0, K-Sl ф 0, Кта ф 0, К8а St{b,r,nJ), Кта St(b,r,n,l) и K-Sl St(b,r,n,l).
О переводимости состояний АМТ и глубине диаграммы Мура АМТ
Покажем, что, если q является стартовым, то оно принадлежит KSl. Рассмотрим все возможные нагрузки ресничек 1-дерева -D_1(6, г, п,1) в состоянии q: 1) qui = 0 и дш = 0; 2) дш = 0 и дц2 0; 3) qm 0 и 112 = 0; 4) дш 0 и дш 0. Заметим, что в случаях 1) — 3) состояние q не является стартовым. Действительно, в каждом из этих случаев существует предшественник q состояния g, такой что: в случае 1) q ln = 1 и q n2 = 0; в случае 2) q[n = 1 и 9ii2 = 9п2; в случае 3) q m = 0 и q[n = qm. В случае 4) состояние q, очевидно, является стартовым и при этом обладает Si-свойством. Следовательно, q Є KSl. Лемма доказана. Лемма 1.2.2. Если b = r,l=lun 2, то справедливы следующие утверждения: а) состояние q из Q(b,n,l) 1-дерева D l{b,г,п,Г) является старто вым точно тогда, когда при некотором v, таком что v Є N2, выполнено ?Є K3v; б) для любых su, sv из {si,S2} при и = v выполнено KSu j KSv. Доказательство. Докажем утверждение а). Нетрудно видеть, что, если q из Q(b: п, Ї) принадлежит классу KSv, где v Є N2, то q является стартовым. Покажем, что, если q является стартовым, то оно принадлежит хотя бы одному из классов KSv, где и Є N2. Заметим, что, если q стартовое, то для него выполняется хотя бы одно из следующих условий: 1) qm 0 и qn2 0; 2) qnn 0, дц(„_і) = 0 и Qu(n 2) — 0; 3) при п 3 существуют четыре соседние реснички с номерами Ilk, ll(k + 1), 11(А: + 2) и Щк + 3), где к п - 2, такие что qnk = 0, ?ii(fc+i) = 0i Qu(k+2) 0 и qu(k+3) 0. Действительно, пусть для q не выполняется ни одно из условий 1), 2), 3). Тогда существует предшественник q состояния q, такой что для всех пар ресничек с номерами 11(р — 1) и lip, р 1, таких что gn(p_i) 0 и Чіір — 0, выполнено (і щр-\л = 0 и q llp = 9ц(р_і), а при qm = 0 выполнено q ln = 1, остальные реснички 1-дерева D-1(6,r, п,1) в состоянии q имеют те же нагрузки, что и в состоянии q. Следовательно, при невыполнении ни одного из трех указанных условий состояние q стартовым не является, а при выполнении хотя бы одного из этих условий q, очевидно, является стартовым. Если для q выполняется условие 1), то q обладает si-свойством, а, следовательно, q Є KSl. Если для q выполняется условие 2) или 3), то q обладает 52-свойством, а, следовательно, q Є KS2. Таким образом, показали, что, если q является стартовым, то имеет место q Є KSv) где v Є Щ Докажем утвеждение б). Пусть состояние ql из KSl такое, что q\n — 1, 9іі2 її а остальные реснички в 1-дереве D l(b,r,n,l) имеют нулевые нагрузки. Легко видеть, что q1 JfS2. Следовательно, KSl $ JCS2. Пусть состояние q2 из XS2 такое, что q\ln = 1, а остальные реснички в 1-дереве D l(b, г, п, /) имеют нулевые нагрузки. Легко видеть, что q2 ф KSl. Следовательно, KS2 $ KSl. Лемма доказана. Лемма 1.2.3. Если Ъ = г,1 2ип 2, то справедливы следующие утверждения: а) состояние q из Q(b,n,l) 1-дерева )_1(&, г, п, I) является старто вым точно тогда, когда при некотором v, таком что v Є Щ, выполнено ge KSv; б) для любых su, sv из S при и = v выполнено KSu (jt. KSv. Доказательство. Докажем утверждение а). Нетрудно видеть, что, если q из Q(b, п, /) принадлежит классу KSv, где v Є N3, то q является стартовым. Покажем, что, если q является стартовым, то оно обладает хотя бы одним из Su-свойств, а, следовательно, принадлежит классу KSv, где г? Є N3. Предположим, что состояние q является стартовым и при этом не обладает ни одним из указанных трех свойств. Тогда у q существует предшественник q , который можно построить следующим образом. Для каждого ребра j уровня г для всех пар ресничек с номерами ij(k-l) и ijk, к 1, таких что %j(/c-i) 0 и q j. = 0, выполнено q n. = 0 и Яф = 9n(Jb-i) гДе г Є Nj и j Є N2 -i, а при qm = 0 выполнено q[n = 1. Для каждой тройки инцидентных ребер, состоящей из ребра j уровня г и ребер f и j" уровня г + 1, где і Є Nj_i и j Є N2i-i, такой что: 1) 1 qijn 2l (l+l)r, q(i+i)j i = 0 и g(i+i)/ i = 0, выполнено tfijn = 0, 9(«+i)j i= и Q(i+i)j»i= Qijn i; 2) 0 gijn 2 -(i+1V, g(i+i)j i = 0 и g(i+i)j 2 0, выполнено q ijn = 0, 9(i+i)i i = Фі" и 9(t+i)j 2 = % +i)i 2 только в том случае, если имеет место одно из следующих условий (где ребра j[ и j 2 уровня і + 2 инцидентны ребру j уровня і + 1): - п 2 и д(і+і)уз 0, - п — 2яг = 1 — 1, - п = 2, г I - 1, д(г+1) 2 21 №г, д(г+2) 1 0 и g(i+2)jj2 О или q(i+2)j 2i О, - п = 2, г Z - 1, c?(i+i)j 2 2l (i+2h и g(i+2)jii О; 3) 2Иг +1)г $,„ 2 V, g +ijjV! = 0 и g(i+i)j"i = 0, выполнено q ijn - О, Wi =2 (т)г и +ш"і = «У» - 2Ий 1)г Остальные реснички I-дерева D 1(b,r n,l) в состоянии q1 имеют те же нагрузки, что и в состоянии q. Получили противоречие, так как стартовое состояние не имеет предшественников. Таким образом, показали, что, если q является стартовым, то имеет место q Є KSv) где г; Є N3. Докажем утвеждение б). Пусть состояние q1 из KSl такое, что q\n = 1 и q\u = lj а нагрузки остальных ресничек в I-дереве D_1(b, г, п,1) равны нулю. Легко видеть, что q1 ф. KS2UKS3. Следовательно, при всех v Є {2, 3} выполнено KSl $ KSv. Пусть состояние q2 из KS2 такое, что дцп = 1, а нагрузки остальных ресничек в I-дереве .D-1(6, г, п, Z) равны нулю. Легко видеть, что q2 ф KSl\J KS3. Следовательно, при всех v Є {1,3} выполнено KS2 j KSv. Пусть состояние q3 из KS3 такое, что g _1\ln = 1, gf12 = 1, 4 2 = 1 и если п 2, то еще qf13 = 1 и ?f23 = 1, а нагрузки остальных ресничек в I-дереве D_1(6, г, п, /) равны нулю. Легко видеть, что q3 . KSlUKS2. Следовательно, при всех v Є {1,2} выполнено К3з KSv. Лемма доказана.
Об автоматной представимости допустимых входных слов и сверхслов для АМТ
Если распределение RD-I(V) сосредоточено не только в пределах одной цепи, то за счет того, что процесс транспортировки вещества идет параллельно во всех цепях, время освобождения от V при распределении До-1 (У) в этом случае не превосходит времени освобождения от этой же загрузки V при распределении Д3#-і(У, кз, Кз, 6).
Пусть распределение До-і (V) сосредоточено в пределах только одной цепи, тогда покажем как перейти от RD-I(V) к Д3 -і(У, &з, /із,Ь/і3) не увеличивая при этом время полного самоочищения этой цепи. Так как мера переброса ресничек ребер глубины Z — 1 в двое больше меры переброса ресничек ребер глубины / (и чем меньше глубина ребер, тем больше меры их переброса), то, пользуясь леммой 1.4.2, получаем распределение нагрузки Ьп + п{1 — 1) с помощью RlD-l(bn + п{1 — 1), 1,1). Далее, оставшуюся нагрузку V — Ьп — п(1 — 1) распределяем по цепи таким образом, чтобы п-ая ресничка ребра глубины I оставалась блокированой на передачу нагрузки как можно дольше, потому что время полного самоочищение всей цепи, очевидно, равно времени освобождения от своей нагрузки указанной реснички плюс пі — 1 шагов. Этому описанию как раз и удовлетворяет распределение R3D-r (V, k3, /із, bh3). Таким образом получили R3D-1 (V, &з, /із, bh3) из RD 1 (V) и при этом не уменьшили время полного самоочищения I- дерева D-1(6,r, п,1; V). Тем самым, время освобождения от загрузки V I- дерева D_1(b,г,п, /; V) при распределении RD-I(V ) не больше времени освобождения от V при Я3Г)-І(У,/І;З,/ІЗ, З) Рассмотрим случай г), когда г 1 и V пі.
Покажем, что в этом случае распределение Л2 -і(У, &2 г) загрузки Vі I-дерева D 1(b,r,n)l]V) будет иметь более долгое время полного самоочищения по сравнению с любым другим распределением загрузки V этого 1-дерева.
Рассмотрим некоторое распределение RD-I(V ) загрузки V 1-дерева D_1(6, г, п, I; V), отличное от R2D-I(V, fo, fo) Если распределение RD-I(V) сосредоточено не только в пределах одной цепи, то за счет того, что процесс транспортировки вещества идет параллельно во всех цепях, время освобождения от V при распределении Яр-і (V) в этом случае не превосходит времени освобождения от этой же загрузки V при распределении R2E -I(V, fo, I12).
Если распределение Дд-і(У ) сосредоточено в пределах только одной цепи, то, так как RQ \{V ) отлично от Я2х}-і(У, 2, 2), в распределении RD-I(V) либо имеются реснички с нулевыми нагрузками, выше которых есть реснички с ненулевыми нагрузками; либо какие-то реснички с ненулевыми нагрузками в этой цепи имеют нагрузки, большие, чем 1; либо имеют место эти две ситуации одновременно. Из леммы 1.4.2 и того факта, что при смещении нагрузок (или их частей) с ресничек с ненулевыми нагрузками на нижележащие реснички с нулевыми нагрузками время полного самоочищения цепи не уменьшается, получаем, что время освобождения от загрузки V 1-дерева D l(b, r,n,l; V) при распределении RD-I(V) не больше времени освобождения от V при R2D-l{Vt,k2,h2) Рассмотрим случай д), когда г 1 и Vі пі.
Покажем, что в этом случае распределение Я3)-і(У, /сз, /із, bh3) загрузки V 1-дерева D l(b, г, п,/;У) будет иметь более долгое время полного самоочищения по сравнению с любым другим распределением загрузки V этого 1-дерева.
Рассмотрим некоторое распределение RD-1{V) загрузки V 1-дерева D l{b, г, тг, /; У), отличное от R D-1 (У , &з, з, &Аз) Если распределение RD I(V) сосредоточено не только в пределах одной цепи, то за счет того, что процесс транспортировки идет параллельно во всех цепях, время освобождения от V при распределении RD-I (V) в этом случае не превосходит времени освобождения от этой же загрузки V при распределении R3 -i(V\ /%, Ы, bh3).
Пусть распределение RQ-I (V) сосредоточено в пределах только одной цепи, тогда покажем как перейти от RD-ІІУ ) К R3о-1(У\кз,Ы,Ьн3), не увеличивая при этом время полного самоочищения этой цепи. Так как справедливо неравенство г 1, то, пользуясь леммой 1.4.2, получаем распределение нагрузки пі с помощью R2Q-i{nl, 1,1). Далее, оставшуюся нагрузку V — пі распределяем по цепи таким образом, чтобы n-ая ресничка ребра глубины / оставалась блокированой на передачу нагрузки как можно дольше, потому что время полного самоочищение всей цепи, очевидно, равно времени освобождения от своей нагрузки указанной реснички плюс пі — 1 шагов. Этому описанию как раз и удовлетворяет распределение Д3)-і(У,А;з, з,Ь/гз)- Таким образом, получили R3 D-1 (У Лз з: bh3) из Я/з-1 (V) и при этом не уменьшили время полного самоочищения I- дерева D 1(b,r,n,l]V). Тем самым, время освобождения от загрузки V I- дерева D l{b, г, п, I; V) при распределении RD-I(V) не больше времени освобождения от V при R3D-I(V, кз, /ІЗ, bh3)- Лемма доказана.
Лемма 1.4.4. Если распределение загрузки V 1-дерева D l{b,rrn,l\V) таково, что (21 — 1)Ьп V 2i 1bnl и в нем существует цепь С, все реснички которой имеют нагрузки, равные своим емкостям, то время полного самоочищения цепи С совпадает со временем полного самоочи-щенния всего 1-дерева D l(b,r,n,l\V), причем время полного самоочищения 1-дерева -1(6,г,n,l;V) при указанном распределени загрузки V не меньше времени полного самоочищения этого 1-дерева при любом другом распределении той эюе загрузки, в котором такая цепь С отсутствует. Доказательство. Ясно, что нагрузка цепи С равна (21 — 1)Ьп. Распределение этой нагрузки в цепи С имеет вид Дд-і((2 — l)bn, 1,1,2г_16). Рассмотрим некоторую цепь С\ в I-дереве D l{b, г, п, /), отличную от С. Пусть ее загрузка равна V\. Распределение загрузки V\ этой цепи Сі обозначим Rc iVi)- Так как С\ отлична от С, то, во-первых, V\ (2і — l)bn, а во-вторых, в распределении Rcx(y{) либо есть реснички с нулевыми нагрузками; либо некоторые реснички в этом распределении имеют нагрузки, меньшие своих емкостей; либо имеют место эти две ситуации одновременно. Учитывая тот факт, что ресничка с нагрузкой, равной своей емкости, освобождается от своей нагрузки за не меньшее время, чем та же ресничка, но имеющая нагрузку, меньшую своей емкости (в том числе и нулевую нагрузку), получаем, что время полного самоочищения цепи С не мешьше времени полного самоочищения цепи С\. Осталось показать, что "стыки", то есть те места, где два ребра входят в одно, не повлияют на собственное время полного самоочищения цепи С. Пусть некоторой цепи С принадлежат ребра, образующие "стык" с ребрами цепи С. Заметим, что увеличение числа шагов возможно только в ситуации, показанной на Рис. 7 на стр. 63.
Похожие диссертации на Автоматная модель одной транспортной системы в биологии
