Анализ технологии методами дискретной математики icon

Анализ технологии методами дискретной математики



НазваниеАнализ технологии методами дискретной математики
Дата конвертации27.08.2012
Размер244.5 Kb.
ТипАнализ

Анализ технологии методами дискретной математики

Предварительные замечания

Этот текст представляет собой соединение некоторых фрагментов диссертации, связанных друг с другом весьма общим образом. На концептуальном уровне проблема описания технологии нами уже рассматривалась, в частности, для уровня «технологический маршрут». Здесь же укажем путь к применению с этой целью некоторых разделов собственно математики (прежде всего теории нормальных алгорифмов Маркова, казалось, бы весьма абстрактного раздела математической логики). Нумерация пунктов мною оставлена старая; после раскрытия физического смысла задачи следует ряд результатов, весьма далеких от завершенности, собственно говоря, это наброски. Быть может, энтузиасты, более подкованные в математике, чем я, смогут плодотворно поработать в этой сфере- им и предназначается в первую очередь данный текст.


Дискретная математика в приложении к технологии сборки

Среди немногочисленных книг, затрагивающих вопросы моделирования производства средствами дискретной математики, можно выделить [60] (Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам.–Пер. с англ.– М.: Наука, 1986.–288с.) и работу В.Г.Тимковского [61] (Тимковский В.Г. Дискретная математика в мире станков и деталей: Введение в математическое моделирование задач дискретного производства.–// сер. Кибернетика: неограниченные возможности и возможные ограничения.– М.: Наука, 1992.– 144с.). Содержание последней книги можно охарактеризовать как коллекцию этюдов по формализации и сводимости задач. Вот фрагмент из нее.

Всякое производство можно назвать дискретным, если реализуемый в его рамках технологический процесс представляет собой множество технологических операций обработки деталей на ряде станков. Причем обработка каждой детали, как правило, сопровождается ее перемещением от одного станка к другому. Хотя термины “станок” и “деталь” относятся в большей мере к механосборочному производству, в научно-технической литературе они получили самое широкое толкование для обозначения орудия и предмета труда. Таким образом, под станком может пониматься токарный станок в цехе механообработки, участок термической обработки на поточной линии производства интегральных схем, компьютер в вычислительной сети, а под деталью – металлическая заготовка, партия пластин, вычислительная задача. Словосочетание “станки и детали” является, наверное, самым ярким символом дискретного производства. Типичными примерами дискретного могут служить механообрабатывающее, сборочное и штамповочное производство, учебное заведение, вычислительный центр, а также любая система обслуживания типа парикмахерской. Антиподом дискретного является непрерывное производство, в рамках которого технологический процесс не разбивается на отдельные операции обработки деталей со сменой станков.
Например, выплавка стали, изготовление тканей, соляной кислоты являются непрерывными производствами.

^ Представление сборочных изделий упорядоченными множествами. Рассмотрим простейшее сборочное изделие, представляющее собой консольное крепление колеса К на рычаге Р с помощью оси О, шайбы Ш и гайки Г (рис.1.2). Эти детали можно рассматривать как элементы универсума D={О,К,Р,Ш,Г} и как атомы булеана 2D. Его множества задают всевозможные сочетания деталей сборочного изделия. Некоторые сочетания образуют сборочные узлы, возможные с точки зрения технолога сборки. Например, члены семейства ={{O},{K},{P},{Ш},{Г}, {O,K},{K,P},{Р,Ш},{Ш,Г},{O,K,P},{K,P,Ш},{P,Ш,Г},{О,К,Р,Ш},{K,P,Ш,Г}, {О,К,Р,Ш,Г} можно считать возможными узлами. Множество {O,K,P} следует интерпретировать как принципиально возможный промежуточный узел сборки, содержащий ось, колесо и рычаг, которые соединены между собой. Остальные множества в  интерпретируются аналогично. Множество {O,K,P,Ш,Г} представляет собой окончательный сборочный узел сборки, т.е. само сборочное изделие. Очевидно, что семейство  является кланом на этом семействе. Легко проверить, что члены дополнительного семейства 2D| нельзя считать возможными сборочными узлами. Например, пустое множество не представляет собой никакого сочетания деталей, а множество {О,Ш,Г} представляет собой ось с шайбой и накрученной гайкой. Ясно, что после сборки такого промежуточного узла консольное соединение колеса собрать уже невозможно, поскольку ось можно вставить в рычаг только при снятых шайбе и гайке. Другие 15 членов дополнительного семейства не годятся на роль промежуточных узлов по сходным причинам. На рис.1.2 отображена диаграмма включений клана . Эта диаграмма содержит в себе информацию о всех допустимых способах сборки. Чтобы найти наиболее технологический способ сборки, в котором промежуточные узлы собираются из небольшого числа других, нужно решить задачу поиска наибольшего точного подклана.


Общие сведения из теории нормальных алгорифмов

Рассмотрим пример, показывающий связь этой теории с технологией. Предположим, поставлена задача описать структуру некоторого ассортимента тортов. Кулинар умеет делать следующие слои: шоколада, масла, коржа. Естественно ввести множество слоев, состоящее из трех элементов: X={a,b,c}. Приверженец теории алгорифмов аналогично введет алфавит A={a,b,c}. Структуру торта он опишет словом «cbca» (если торт «считывать» снизу вверх). Для теории множеств законна структура {a,b} (подмножество X), она неотличима от {b,a} (если не вводить кортежи), от первых двух неотличима структура {a,b,a}, и уж совсем непонятна конструкция {c,b,c,a} (в ней явно 4 элемента, но во всяком подмножестве элементов не больше, чем в множестве). Есть, правда, конструкция булеана, и ассортимент тортов можно в принципе описать родовой структурой DB(NX), N- множество натуральных чисел. На эту структуру требуется также наложить ряд ограничений. Очевидно, что это весьма сложный путь, и легче работать со словами в алфавите A. (По устному сообщению В.К.Леонтьева, в теории множеств существует понятие «мультимножества» (multiset), с помощью которого вроде бы удается ликвидировать эту проблему. В этой связи хочу также напомнить, что со стороны Колмогорова было весьма умно ввести в аксиоматику теории вероятностей помимо множества элементарных событий и вероятностей также и сигма-алгебру) Кроме этого аспекта, теория алгорифмов позволяет естественным образом учесть процессный аспект технологии. Схеме алгорифма и исходному слову, к которому он применяется, мы поставим в соответствие совокупность “ноу-хау”, которыми владеет предприятие (с экономической точки зрения- нематериальные активы) и реальное состояние производственной базы. Такой способ наиболее предпочтителен. По нашему мнению, непродуктивно другое соответствие: схема алгорифма → запись технологического маршрута, исходное слово → субстрат. Таким образом, мы уже переходим от концептуализации к формализации, от выявления базовых понятий и отношений к постановке более или менее конкретных математических проблем, интересных уже самой математике.

В качестве математического аппарата мы будем также использовать теорию алгорифмов (иначе «алгоритмов»), разработанную А.А.Марковым в 50-60-х годах ХХв [59] (Марков А.А., Нагорный Н.М. Теория алгорифмов.–М.: Наука, 1984.- 432с.).

(Любопытно, что второй автор,ученик Маркова, судя по тексту книги, всячески старался затушевать критические стрелы, брошенные учителем в сторону теории множеств. Его позицию можно передать примерно так- «Философские вопросы математики очень сложны, поэтому не будем ими заниматься, предоставив это занятие для бездельников-философов, а мы лучше употребим все усилия на технику, попытаемся нормальные алгорифмы получше связать с привычной нам теорией множеств и логикой, основанной на ней (типа диаграммы Эйлера-Вена, отражающей также и логические отношения)». Такая позиция не редкость, к сожалению, среди профессиональных математиков. Марков же, эмоционально не приемля теорию множеств, старался создать ей альтернативу).

Многослойная структура интегральных схем (ИС) делает технологические процессы микроэлектроники чрезвычайно удобным объектом для применения нормальных алгоритмов. Технология– это прежде всего алгоритм действий. Математический аппарат теории алгоритмов может быть крайне полезен для описания таких понятий, как технологическая операция (ТО) и технологический маршрут (ТМ). Это связано также со сложной структурой компонентов ТО и ТМ. Теория нормальных алгорифмов может представлять альтернативу теории родов структур в качестве средства выражения концептуальной схемы ТМ. Нормальный алгорифм может не только иметь физический смысл, но и использоваться в качестве синтаксического средства, что чрезвычайно удобно.

Ну теперь собственно по книге А.А.Маркова.

Алгорифм есть предписание, однозначно определяющее ход некоторых конструктивных процессов. Слово “предписание” в определении алгорифма указывает на наличие некоторого адресата - субъекта, о котором предполагается, что он будет выполнять это предписание. В частности, это может быть человек или какая-нибудь его хорошая модель. Выполняя предписание, его адресат будет осуществлять некоторый процесс, однозначно определенный этим предписанием. Этот процесс будет идти в некоторой системе (например, в системе: “доска, мел, тряпка”), состояние которой будет в ходе процесса изменяться. Все эти изменения должны полностью определяться предписанием и осуществляться адресатом-исполнителем, который, разумеется, должен понимать предписание. Иногда предписание может потребовать окончание процесса. В нашем определении алгорифма о процессах говорится во множественном числе. Алгорифм может, вообще говоря, определять много процессов, отличающихся друг от друга начальным состоянием системы. Слово “однозначно” в определении алгорифма не должно пониматься слишком буквально. Для состояний системы может быть установлено то или иное отношение одинаковости. Например, для системы “доска, мел, тряпка” состояниями могут считаться слова, написанные мелом на доске. В этом случае будет естественно считать состояния одинаковыми, если одинаковы соответствующие слова. Процесс, определяемый алгорифмом при задании начального состояния системы, должен определяться однозначно лишь “с точностью до одинаковости” получаемых в его ходе состояний. Потребовать, чтобы этот процесс был единственным, мы можем, лишь условившись естественным образом применять абстракцию отождествления к состояниям нашей системы и процессам, протекающим в ней.

Для формулировки и понимания алгорифма необходим тот или иной язык - язык данного алгорифма. Естественно потребовать, чтобы на этом языке можно было назвать любое состояние системы, с которой имеет дело алгорифм. Состояние при этом должно однозначно определяться своим названием. Это означает, что язык имеет алфавит, состоящий из элементарных знаков–букв, причем выражения данного языка (высказывания, названия, предписания и т.п.) являются “словами”, т.е. линейными рядами букв. Процесс осуществления алгорифма может быть тогда смоделирован некоторым другим процессом, имеющим дело со словами – с названиями состояний. Таким образом, мы сводим рассмотрение алгорифмов к рассмотрению вербальных алгорифмов. Так мы будем называть алгорифмы, работающие над словами в каком-нибудь данном алфавите. Процесс работы вербального алгорифма в алфавите А состоит в последовательном порождении слов в алфавите А согласно сформулированному предписанию. Перед началом этого процесса выбирается некоторое исходное слово в алфавите А. Процесс может закончиться порождением некоторого слова, которое мы объявляем тогда результатом работы нашего алгорифма над исходным словом. Мы будем также говорить, что наш алгорифм перерабатывает исходное слово в результат своей работы над ним. Мы будем говорить, что алгорифм применим к данному слову, если процесс его работы над этим словом заканчивается, т.е. если имеется результат его работы над данным словом как исходным.

Введенное выше понятие алгорифма в данном алфавите не является достаточно четким, чтобы дать возможность рассматривать алгорифмы как объекты математической теории. Прежде всего “общепонятность” предписания нельзя рассматривать как вполне четкую характеристику. Постепенный переход от понятного предписания к совсем непонятному путем все большего и большего усложнения, очевидно, вполне возможен. Естественно поэтому мысль о той или иной регламентации предписания путем его расчленения на правила определенного стандартного типа, общепонятность которых не вызывало бы никаких сомнений. Процесс применения алгорифма будет тогда состоять из отдельных элементарных шагов, каждый из которых будет выполняться согласно одному из этих правил. Процессы, ход которых определяется предписанием, разнообразны. Выяснилось, однако, что если интересоваться алгорифмами лишь с точностью до эквивалентности, то их плохо обозримое разнообразие, по-видимому, сводится к более простой идее. Мы введем в рассмотрение вербальные алгорифмы специального типа – т.н. нормальные алгорифмы. В этой связи важен принцип нормализации алгорифмов, не выводимый математическими средствами: “Всякий вербальный алгорифм в алфавите А вполне эквивалентен относительно А некоторому нормальному алгорифму над А”.

При рассмотрении двух букв какого-нибудь алфавита мы констатируем, что они одинаковы или что они различны. Например, мы видим, что пятая и седьмая буквы слова “констатируем” одинаковы, а первая и последняя буквы этого слова различны. Одинаковость и различие букв мы определяем при этом “на глаз”. Для приемлемого алфавита распознавание одинаковости или различия букв происходит легко. Для этого требуется лишь, чтобы различие неодинаковых букв значительно превосходили мелкие различия букв одинаковых. Рассуждая о буквах какого-нибудь алфавита, мы обычно привлекаем абстракцию отождествления, т.е. позволяем себе говорить о двух одинаковых буквах как об одной и той же букве. Точнее, вводится в рассмотрение одна абстрактная буква, с которой снимаются “копии” – представители (экземпляры) этой абстрактной буквы, участвующие в различных конструктивных процессах.

Напомним, что набор букв, который мы можем использовать, называется алфавитом. Ряд букв данного алфавита, записываемый слева направо, есть слово в этом алфавите. Пустое слово есть слово в любом алфавите. Любое слово можно рассматривать как результат последовательного приписывания нескольких букв справа к пустому слову, обозначаемому . Слова далее будем обозначать латинскими большими буквами, буквы- греческими малыми. Слово P является началом Q, если, по определению, существует такое слово X, что QPX (знак "" есть знак графического равенства двух слов). Длину слова X обозначим [X (длина пустого слова равна нулю). Проекцией слова X в алфавите А на алфавит Б мы будем называть слово, полученное из X выбрасыванием всех букв, не являющихся буквами алфавита Б: [XБ. Слово P входит в Q, если существует такая пара слов R и S (RS), что QRPS. Вхождение есть слово в алфавите A* вида R*P*S. Одно и то же слово может иметь различные вхождения в другое слово, имея разные крылья R и S (например, "ра" имеет 2 различных вхождения в "арарат"). **P есть начальное вхождение пустого слова в Р, P**— концевое. Слова в алфавите A, оканчивающиеся и начинающиеся на , будем называть -системами в алфавите А. Пустая -система состоит из одной буквы . Атомом назовем систему вида P, где P- слово в A. Очевидно, что всякая непустая система состоит из атомов, имея вид, например, PQR...ST. Слово вида PQ, где P и Q- слова в А, - одна из букв алфавита , назовем формулой подстановки. Мы будем говорить о -схеме в алфавите Б=А, если ее члены суть формулы подстановок. Например, XP1Q1P2Q2P3Q3P4P5 является схемой, причем предпоследняя формула подстановки с пустой правой частью, а последняя- с пустой левой частью. Естественно считать, что формула подстановки предшествует другой, если она находится ближе к началу схемы, "левее".

Мы будем говорить, что формула подстановки F действует на слово X (в алфавите А), если левая часть F входит в X. Результатом действия F на X будет слово Y в А, которое получается подстановкой правой части F вместо первого вхождения ее левой части в слово X. Например, для атома рами результатом действия на "арарат" будет "амират", а не "арамит". Очевидно, что результат действия определяется так однозначно. Схема X действует на Р тогда, когда хотя бы один член системы X действует на Р. Элемент F активен на слове P в схеме X, если F действует на P и предшествует всякому другому элементу F1 схемы, дейстующему на P. Результатом действия схемы X на Р будем считать результат действия на P активной формулы подстановки. Так, результом действия схемы рамиарим на слово "арарат" будет слово "амират", а не "имарат". Здесь активна первая формула подстановки. Будем писать X: P|=Q и говорить "схема Х переводит слово P в слово Q", если схема X действует на P. Если в активной формуле , то будем говорить "просто переводит" и писать X:P|—Q; если же , то будем говорить "заключительно переводит" и писать X:P|—Q. В последнем примере "арарат" был "просто переведен" в "амират". Запись X:P будет означать, что схема Х не действует на данное слово P.

Прежде чем сделать дальнейший шаг, т.е. рассмотреть многократное последовательное применение схемы к слову и результатам его перевода, дадим определение переводной системы. Система X является переводной системой схемы Z при истинности высказывания: "если PQ входит в X, то Z:P|—Q".

Системе γPγ, соединяющей P c P, отвечает ситуация либо Z:P, либо Z:P|—•Q. Всякая γ-система в А, входящая в переводную систему схемы Z, является переводной системой схемы Z. Если X— переводная система схемы Z, соединяющая Q c R, и Z:Q|—•P, то X=γQγ и Q=R. Cхема Z просто преобразует P в Q, если существует переводная система схемы Z, соединяющая P с Q, и запишем это в виде Z:P|=Q. Очевидно, что если Z:P|—Q, то Z:P|=Q. Также, если Z:P|=Q и Z:Q|=R, то Z:P|=R. Схема Z естественно преобразует P в Q (пишем Z:P|=Q), если Z:P|=Q и Z:Q. Схема Z заключительно преобразует P в Q (пишем Z:P|=•Q), если существует такое слово R, что Z:P|=R и Z:R|—•Q. Схема Z перерабатывает P в Q (пишем Z:P=>Q), если Z:P|=Q или Z:P|=•Q. Схема Z применима к P (пишем !Z(P)), если существует такое слово Q, что Z:P=>Q. Если Z:P|=Q, то существует единственная переводная система Х схемы Z, соединяющая P c Q, и такая, что X есть начало любой переводной системы схемы Z, соединяющей P и Q. Эту систему X назовем естественной. Заметим, что если Z:P , то Z перерабатывает Р в Р за нуль шагов. Пример: γβQγ:P=>QP — данная схема присоединяет слева к любому слову P слово Q, завершая на этом свою работу. Для схемы γαQγ верно γαQγ: P|—QP, однако она неприменима ни к какому слову P в алфавите А.

Нормальный алгоритм  будет задаваться указанием следующих трех объектов: некоторого алфавита А, некоторого вспомогательного алфавита αβγ, не имеющего букв, общих с алфавитом А, и некоторой γ-схемы Z в алфавите А. Очевидно, что буквы α, β, γ играют роль знаков препинания. На первом шаге процесса, определяемого нормальным алгорифмом  в алфавите А и словом P в этом алфавите, берется само слово Р. Если на некотором шаге процесса было взято слово Q и если :Q|—R для некоторого R, то на следующем шаге берется слово R и процесс продолжается. Если же :Q или :Q|—•S для некоторого S, то процесс обрывается и в первом случае результатом его (P) считается слово Q, а во втором— слово S. Алгоритм  не является применимым к слову P, если процесс его применения никогда не кончается.

Для удобства записи (в столбик) схемы алгорифма можно заменить γ знаком перевода строки, α– стрелкой, β— стрелкой с точкой. Так, схема γabαbaγacαcaγaβγαaγ запишется в виде:



Нам понадобится определение вычислимой вербальной функции. Она по смыслу сходна с n-местной операцией f:An—>А (A— множество, f— знак функции), но ее определение по-прежнему сводится к применению некоторого алгорифма к какому-либо слову. Системы слов в A будем рассматривать как слова в алфавите Aγ (с учетом отбрасывания начальной и конечной буквы γ). Добавим к Aγ εще две буквы α и β, чтобы иметь возможность произвольные нормальные алгорифмы над Aγ трактовать как нормальные алгорифмы в алфавите A+=Aαβγ. Записи нормальных алгорифмов определим именно для этого алфавита, так что, в частности, нормальные алгорифмы в A+ тоже смогут фигурировать в качестве значений аргументов вводимых нами функций. Вычислимой вербальной функцией N переменных в алфавите A мы будем называть любой нормальный алгорифм в алфавите A+, перерабатывающий всякую N-членную систему слов в A, к которой он применим, в какое-либо слово в алфавите A, которое и будет считаться значением функции на данной системе.


Применение нормальных алгорифмов для описания технологических маршрутов в микроэлектронике

Пусть есть некоторый вспомогательный алфавит А0, семантический смысл его букв максимально приближен к научно-технической лексике с вкраплениями числовых и функционального типа математических структур. Из букв образуем слова и группы слов. Первую группу слов условно назовем “Слои”, она состоит пусть из n слов S1, S2, ..., Sn и одного слова S0. Каждое слово S приблизительно характеризует назначение, материал, толщину, удельное сопротивление, количество дефектов, подвижность электронов, механические напряжения, температуру и иные параметры слоя. Оговорку “приблизительно” мы объясним ниже. Слово S0 характеризует параметры подложки. Заметим, что у каждого слова S свой набор параметров. Вторую группу слов условно назовем “Области”, она состоит из слов Q1, Q2,..., Qm. Каждое слово описывает такие параметры изолированной области в слое, как геометрические размеры и форма, концентрация примесных атомов, тип кристаллической решетки основного вещества. Вообще говоря, каждое слово Q может иметь свой набор параметров. Третья группа, “Технологические операции”, состоит из r слов Р1, Р2,... Рr и одного слова Р0. Каждое слово, имея собственную структуру, характеризует отдельную технологическую операцию (длительность, температурный режим, осаждаемое вещество, присутствие посторонних примесей и т.п.). Слово Р0 выражает время перерыва ТМ, т.е. отсутствие активных действий с образцом. В микроэлектронике для S-слов наиболее критично сопротивление, Q-слов - концентрация примеси, Р-слов - безусловно, длительность выполнения операции. Четвертая группа означает “Завершение процесса” и может состоять из одного слова Z, его мы используем для отражения крупного недостатка данной реализации ТМ (неисправный прибор). Эти слова в алфавите А0 суть буквы основного алфавита А, т.е.:

А = {S0,S1,..., Sn, Q1,..., Qm, P0, P1,..., Pr, Z1, ..,Zs, } (3.2.1)

Таким образом, алфавит А состоит из четырех подалфавитов (S,Q,P и Z) и двух букв , имеющих синтаксический смысл. Начальное слово в А, которое перерабатывает алгоритм, имеет вид 0П, где П– слово в Р-подалфавите, 0 слово в SQ–подалфавите. Пусть  - произвольные буквы, взятые из Р-подалфавита, ij k l -буквы, взятые из S- или Q-подалфавита, - буква из Z-подалфавита. Тогда схему алгоритма можно записать в виде столбца:

1) i®1j

2) i®jk

3) i®1

4) i®

5
(3.2.2)
) ij®kl

6) ij®

7) ®

®

Слово П примерно соответствует тому, что называется “технологическим маршрутом” и описывает временную последовательность ТО (слева направо). Левая часть формул (1–4) означает действие ТО на произвольный слой или область, результатом которого может быть или изменение слоя (например, улучшение морфологии гетерослоя при отжиге), или наращивание нового слоя (осаждение пленки Al на Si-подложку), или исчезновение слоя (снятие фоторезиста при фотолитографии), или фатальный дефект (нарушение p-n изоляции). В первых двух случаях появляется буква , что позволяет нам на следующем шаге алгоритма применять одну из формул (5-6), а не формулу из (1-4), как было бы в противном случае. Смена Р-буквы в правой части формул (1-4) вынуждена, иначе мог получиться, например, неприятный результат: плавиковая кислота (HF) при травлении также действует на удаленный слой, как и на соприкасающийся с травителем. Иными словами, влияние ТО на нижние слои зависит от состояния верхних, которые меняют саму ТО. Формулы (5-6) описывают взаимодействие двух рядом расположенных слоев или областей, инициированное ТО. Оно ведет либо к изменению слоев (эффект автолегирования при эпитаксии), либо к фатальному дефекту (это, конечно, завершит работу схемы алгоритма). Буква тогда исчезает, определяя активной (в большинстве случаев) на следующем шаге формулу (6). Формула (7) исключает из начала переработанного слова “отработавшую” ТО, здесь возможны иные варианты написания этой формулы. Формула (8) совершенно необходима, указывая на выполнение следующей ТО только при завершении предыдущей, т.е. когда схема алгоритма учла все влияния предыдущей ТО. Формулы (1-6) должны содержать описание, в данном случае, важнейших физических процессов, происходящих в ходе ТО.

Графически работа алгоритма выглядит так. Начальное слово разделялось буквой на структурную часть (0) и операционную часть (П). Затем эти части начинают взаимодействовать: минуя знак , одна из букв П переходит в левую часть и постепенно, то приобретая префикс , то теряя его, становится в начало слова, где и исчезает; в это время длина структурной части, как правило, увеличивается. После исчезновения последней буквы из П работа алгоритма оканчивается, конечное слово состоит только из структурной части и буквы справа.

Если , то алгоритм  неприменим к данному -слову, т.е. :. Если 0, то алгоритм  естественно преобразует его в . Действительно, активна всегда последняя формула подстановки. Или, по индукции 1) : (точнее, :=). При  см. выше. При 1 и П2 : П21–21. Легко показать (– QS-слово, – P–слово):

а) : =11 и далее : 11=1 (активна 1-я или 2-я, или 3-я формулы и затем 7-я);

б) : 12=1/12/ (активна 1-я или 2-я, или 3-я формулы при 1; случай 1 возможен только, если 2, поскольку ни одна из правых частей формул не начинается на , кроме 7-й; заметим, что [1/ [1); затем имеем при 1/ : 1/12/=1//2// (активна 5-я формула, при этом [1//[1/);

в) : =1 (активна 8-я формула, и очевидно [П[П1);

г) : =1 (активна 3-я формула) или : =11 (активна 1-я или 2-я формулы, при этом [1/  или [1/ );

д) : = (активна 7-я формула).

Рассмотрим работу алгорифма для слова , причем  и . Из в) либо 1), либо г). Если г), то либо д), либо б). Если д), то 1). Если б), то б) до тех пор, пока не 1//. В таком случае а) и снова в). За один оборот цикла имеем :=11, но теперь [П[П1. В вышеприведенных выкладках не учитывалась возможность заключительного преобразования -слова в какое-либо другое, что вполне возможно в соответствии с 4-й и 6-й формулами. Таким образом, приходим к теореме:

Теорема 3.1. Алгоритм, заданный схемой (3.2.2) , применим к любому –слову, причем либо: 1) :|=1**1 2) :|= 3) :|=П.

Лемма 3.1. Для записи схемы алгорифма (3.2.2.) требуется (MN+M2N+2) формул постановки, а длина слова 5MN+7M2N+11L8MN+9M2N+11 букв, включая служебные . (M– число букв в QS-алфавите, N– число букв в P–алфавите).

 В формулах (1-4) буква i пробегает все M значений, буква – все N значений. Следовательно, имеется MN формул (1-4). Рассуждая аналогично, получим, что формул (5-6) должно быть ровно M2N. Формулы (7), (8) присутствуют в одном экземпляре. Отсюда, первое утверждение. Пусть ni– число формул (i). Тогда при n1+ n2+ n3+ n4=MN и n5+ n6=M2N число букв равно 7n1+ 8n2+5n3+5n4+ 9n5+ 7n6+4+6+1, что больше 5MN+7M2N+11 и меньше 8MN+9M2N+11.

Теорема 3.2. Сложность, выражаемая числом шагов N до естественного завершения, работы алгорифма (3.2.2), применяемого к –слову с длиной структурной части n и операционной части m, равна:

-по слабой оценке m+nNm+2n(2m-1);

-по сильной оценке (при n>m) 2mn+1-(m–1)2 N2mn+m2.

 Наименьшее число шагов алгорифма будет в случае применения 3) на каждом возможном для этого шаге. Структурная часть «съедается» еще первой операционной буквой. Последовательно применяются: 8)+3)(n раз)+8)(m-1 раз). Имеем N1+n+(m-1)=m+n. Наибольшее число шагов будет в случае применения 2) на каждом возмножном для этого шаге. При отрыве первой P-буквы выполняются: 8)+{2),5) n-1 раз}+2)+7). Длина структурной части изменяется с n до 2n за 1+2(n-1)+2=2n+1 шагов. При отрыве второй P-буквы выполняются: : 8)+{2),5) 2n-1 раз}+2)+7). Длина структурной части изменяется с 2n до 4n за 1+2(2n-1)+2=4n+1 шагов. Таким образом, получаем сумму членов геометрической прогрессии:

(3.2.3)

Реальный технологический маршрут вряд ли (см. выше пример с травлением в HF), характеризуется таким быстрым убыванием или возрастанием числа слоев. Для него можно принять такое ограничение на схему алгорифма: всякая буква 1, стоящая в правых частях какой-либо из формул 2) и 3), будет находиться в левой части одной из формул 1). В этом случае мы получим более сильную оценку. Наибольшая сложность достигается, если любая P-буква –слова находится в левой части какой-либо из 2). При отрыве первой буквы имеем: 8)+2)+5)+{1),5) n-2 раз}+1)+7). Длина структурной части изменяется с n до n+1 за 1+2+2(n-2)+2=2n+1 шагов. При отрыве второй буквы имеем: 8)+2)+5)+{1),5) n-2 раз}+1)+7). Длина структурной части изменяется с n+1 до n+2 за 1+2+2(n-1)+2=2(n+1)+1 шагов. Таким образом, для оценки сверху получаем сумму арифметической прогрессии:

(3.2.4)

Для оценки снизу сделаем непринципиальное предположение n>m. По аналогии с предыдущим случаем будем иметь:

(3.2.5)

Приведенные рассуждения показывают формальную полезность классификации технологических операций [46], см. п.4.1. 

Рассмотрим пример, показывающий необходимость доработки предложенной модели ТМ с учетом сложной структуры компонентов ТО. При проведении ионного легирования необходима доза излучения, большая минимальной, чтобы прошедший через технологический слой пучок атомов примеси мог сформировать легирующую область в другом скрытом слое. Таким образом, возникает проблема скрытых параметров, порождающих псевдостохастичность. Иными словами, нужно учитывать, что внутренная структура букв в алфавите А может влиять на используемую формулу подстановки. Предложим метод решения, частично снимающий эту проблему.

Пусть теперь А– алфавит названий компонент, В– алфавит физических свойств, С– алфавит бинарных отношений. Алфавиты попарно не имеют общих букв. Условимся считать буквами из А малые греческие буквы, буквами из B– малые латинские, буквами из С– заглавные греческие буквы. Введем алфавит D=АBC{(,),}. Упомянутый во выше торт может быть описан как abc()dae()ac()ef(), если интерпретировать  как слой коржа, – промежуточный слой масла, – шоколад сверху; – отношение “лежать выше”, – отношение “граничить с”, – пустое отношение. Слово состоит из четырех частей: 1) название (1 буква); 2) состояние (слово из B-алфавита); 3) открывающей и закрывающей скобок; 4) пар «имя отношения– второй операнд», которые перечисляют все буквы, стоящие правее, и соответствующее отношение, быть может, пустое. Таким образом, можно задать аналог элемента булеана множества компонент ТО плюс их допустимые конфигурации. Данная конструкция может задавать сразу несколько отношений, в которых состоят компоненты попарно.

Слово R является конфигурационным, если:

1. R= (пустое); 2. R=R1, где R1– конфигурационное, – слово в алфавите отношений, – буква из A-алфавита.

Слово Q является комплексным, если:

  1. Q=P(), где – буква из A-алфавита, P– слово в B–алфавите;

  2. Q=P(R)Q1, где Q1– комплексное слово, R– конфигурационное слово;

  3. Для слова Q в п.2. из того, что R=R1**R2 (– буква из А–алфавита, – слово в С–алфавите), следует, что Q1=Q2*P0(R0)*Q3 (R0– конфигурационное слово, P0– слово в B–алфавите) и [[R1A=[[Q2), [[R2A=[[Q3(.

Слово T является технологическим, если:

  1. T=Q1Q2, где Q1,Q2– комплексные.

  2. T=Q1T1, где T1– технологическое слово.

Эти определения даны в индуктивной форме, читатель может заняться доказательством их непротиворечивости (например, п.3. для комплексных слов). Технологическое слово в редуцированном виде воспроизводится –словом, к которому применяется алгорифм (3.2.2). Оно содержит как минимум две компоненты: структурную и операционную. В качестве третьей компоненты интересно, например, взять показатели качества, которые в этом случае вычислялись бы в процессе применения алгорифма к предыдущим частям T-слова.

Компоненты технологической операции разбросаны по разным частям T–слова (они отделяются вертикальной чертой ), формула подстановки схемы алгорифма имеет своей левой частью сочетание этих компонент. Кроме того, результат действия формулы должен быть вновь разбросан. Поэтому возникает необходимость в совершении определенного рода технических действий, не связанных с физическим смыслом ТМ. Особенно отметим, что данная схема действий сходна с той, что возникает в задачах распознавания образов. Любопытно, что уже есть работы, посвященные применению теории распознавания образов для анализа многофакторного технологического процесса [62]. Симуляция ТМ применением некого алгорифма к Т–словам предъявляет, по-видимому, следующие требования к его схеме: а) формулы подстановки с наиболее длинной левой частью, выражающие собой сложные «ноу-хау», предшествуют более коротким, выражающим побочные эффекты от совершения ТО (если не брать в расчет технические формулы); б) заключительные формулы подстановки, выражающие недопустимые сочетания компонентов ТО, т.е. заведомый брак, также ставятся впереди; в) алгорифм является сочетанием нескольких алгорифмов. Требование а) позволяет также естественным образом удлинять схему алгорифма при появлении усовершенствований ТО. Требование б) выражает наше желание учесть вероятность брака в ходе ТМ. Эта интереснейшая задача ввести вероятности в детерминированный ход работы алгорифма, по-видимому, не может быть решена в рамках теории нормальных алгорифмов. Для этих целей целесообразно использовать аппарат ассоциативных исчислений (в конструктивной форме), где допускается присутствие в схеме алгорифма формул подстановок с одинаковой левой частью. Вероятностный аспект, впрочем, может быть учтен без понятия вероятности, если ее рассматривать как показатель качества– процент выхода годных изделий. Требование в) возникло из того ощущения, что сама по себе задача моделирования ТМ посредством нормальных алгорифмов является сложной, и потому должна быть произведена ее декомпозиция.

Для поддержания дисциплины проектирования актуальна задача: найти алгорифм, проверяющий: является ли слово Q из алфавита D комплексным. На практике важно задавать такие свойства отношений, как рефлексивность, симметричность, транзитивность. Только последнее свойство ограничивает наш произвол в составлении комплексных слов. Например, если – «лежать выше», – «лежать ниже» (т.е. эти отношения транзитивны), то противоречиво слово Q=()()(). Следовательно, актуальна задача проверки, является ли комплексное слово Q непротиворечивым с помощью некоторого алгорифма. Легко увидеть также, что одну и ту же структуру можно записать разными способами (например, по-разному нумеровать слои-компоненты). Таким образом, актуальна задача проверки эквивалентности двух непротиворечивых комплексных слов с помощью некоторого алгорифма.

Мы видим, что моделирование технологического маршрута (операции) с помощью теории нормальных алгорифмов требует декомпозиции задачи. Этому помогают следующие теоремы о сочетаниях алгорифмов. Композиция алгорифмов заключается в том, что к слову применяется первый алгорифм, а затем к результату его работы второй. Каковы бы ни были алгорифмы  и , может быть построен такой нормальный алгорифм  над объединением А их алфавитов, что P в  (P)=((P)). Иными словами, технологический маршрут продолжаем. Для описания сборочного производства полезна задача: «исходя из произвольного слова P в объединении алфавитов А, развернуть процессы применения к нему алгорифмов  и , по окончании этих процессов построить слово (P)(P) и считать его результатом. Теорема об объединении гласит, что можно построить такой , что P в  (P)=(P)(P). Если во время прохождения ТМ обнаружен брак, то дальнейшие ТО выполнять нежелательно. Полезна теорема о разветвлении: каковы бы ни были алгорифмы ,, может быть построен алгорифм  над объединением их алфавитов такой, что . P из  имеют место три условия одновременно:

  1. (P)(P)(P); 2) (P)(P)(P); 3) если определено (P), то определено (P).

Важное значение, когда мы хотим возможность применять алгорифм к записям других алгорифмов, т.е. к схеме и какого-либо алгорифма , имеет теорема об универсальном алгорифме: “Может быть построен такой универсальный алгорифм  над алфавитом A, что (иP)=(P) имеет место для любого слова P из А и алгорифма  над А».




Похожие:

Анализ технологии методами дискретной математики iconГромов Г. Р. Очерки информационной технологии
Анализ производительности ЭВМ методами теории массового обслуживания, М.: «Энергия», 1972. 176 с
Анализ технологии методами дискретной математики iconДокументы
1. /Основы дискретной математики - 1ч.doc
2. /Основы...

Анализ технологии методами дискретной математики iconДокументы
1. /Пособие АЛГОРИТМЫ ДИСКРЕТНОЙ МАТЕМАТИКИ.doc
Анализ технологии методами дискретной математики iconЛитература и Интернет-источники
Артамонов Г. Т. Анализ производительности ЭВМ методами теории массового обслуживания
Анализ технологии методами дискретной математики iconАнализ деятельности мо учителей математики и физики моу сош №7 за III четверть 2010-2011 учебного год
В мо учителей математики и физики входят 6 учителей: 4 человека- учителя математики (Морщинова Т. Н., Гладышева Е. И., Киселева Л....
Анализ технологии методами дискретной математики iconОбучение математике по технологии уде учитель математики: Кравченко Лидия Сергеевна
Цели технологии уде: создание действенных и эффективных условий для развития познавательных способностей детей, их интеллекта и творческого...
Анализ технологии методами дискретной математики iconВиртуальная школа компьютерных технологий
Артамонов Г. Т. Анализ производительности цвм методами теории массового обслуживания. М.: Энергия, 1972. – 176 с
Анализ технологии методами дискретной математики iconКонкурс по информатике «Современные компьютерные технологии»
«Современные компьютерные технологии», конкурс грамот с математической символикой, дипломов, благодарственных писем среди учащихся...
Анализ технологии методами дискретной математики iconКонкурс «А ну ка, математики!» Составили: учителя математики Сорокина Н. В., Шагова Т. В
Велико значение математики в повседневной жизни человека. Математика возникла из повседневной практики, из жизненных нужд людей в...
Анализ технологии методами дискретной математики iconКонкурс «А ну ка, математики!» Составили: учителя математики Сорокина Н. В., Шагова Т. В цель
Велико значение математики в повседневной жизни человека. Математика возникла из повседневной практики, из жизненных нужд людей в...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов