Разработка недетерминированных программных систем на основе вероятных автоматов
Система цифровых автоматов: основные понятия и определения, классификация, способы задания. Структурная схема конечного автомата. Основные формулы комбинаторики. Предмет теории вероятностей. Дискретные распределения. Реализация вероятностного автомата.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | русский |
| Дата добавления | 05.11.2015 |
| Размер файла | 1,2 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
|
|
(12) |
и именуется количеством сочетаний из n частей по k частей.
Доказательство. Заметим, что, согласно следствию 1, из всякой подборки данного состава (состоящей из k частей) разрешено сформировать k! выборок, отличающихся друг от друга лишь порядком частей.
То имеется количество выборок, различающихся еще и порядком, в k! раз больше, чем количество выборок, различающихся лишь составом. Поделив на k!, получим утверждение теоремы.
Урновая схема: отбор с возвращением и с учетом порядка. Общее количество выборок в схеме выбора k частей из n с возвращением и с учетом порядка определяется формулой (13)
|
(13) |
Доказательство. 1-ый шарик разрешено избрать n методами. При каждом из данных методик 2-ой шарик разрешено избрать также n методами, и так k раз.
Урновая схема: отбор с возвращением и в отсутствии учета порядка. Рассмотрим урну с 2-мя шариками и перечислим итоги выбора 2-ух шариков из данной урны при выборе с возвращением (таблица 30).
Таблица 30. Таблица выбора 2 шариков
Заметим, что в схеме «без учета порядка» вышло 3 разных итога в отличие от 4 в схеме «с учетом порядка» (количество 4 появляется и согласно теореме 4); и что никаким делением на «количество каких-нибудь перестановок» количество 3 из 4 заполучить не получится.
Теорема 5. Общее численность выборок в схеме выбора k частей из n с возвращением и без учета распорядка определяется формулой (14)
|
(14) |
Доказательство. Рассмотрим тщательно, чем различаются друг от друга 2 различных итога такой схемы выбора. Нам не важен распорядок номеров, то имеется мы предусматриваем лишь, сколько раз в нашем комплекте из k номеров шариков появился шарик номер 1, шарик номер 2, … , шарик номер n. То имеется итог выбора разрешено представить комплектом количеств k1, k2, …kn, в котором ki - количество появлений шарика номер i в выборке, и k1+ k2+ …+kn.= k. При этом 2 итога опыта различны, если соответствующие им комплекты k1, k2, …,kn никак не схожи.
Предположим себе другой опыт, имеющий точно такие же итоги (и, следовательно, их столько же). Имеется n ящиков, в которых располагается k шариков. Нас интересует лишь численность шариков в каждом ящике. То имеется, итогом опыта снова является комплект чисел k1, k2, …kn , в котором ki - количество шариков в ящике с номером i, и k1+ k2+ … +kn.= k. Числа ki по-прежнему принимают натуральные значения либо равны 0.
А теперь изобразим итог такого размещения в виде схемы, в которой вертикальные линии означают перегородки между ящиками, а кружки - находящиеся в ящиках шарики:
Мы видим итог размещения 9 шариков по 7 ящикам. Тут 1-й ящик содержит 3 шарика, 2-й и 6-й ящики пусты, 3-й ящик содержит 1 шарик, и в 4-м и 5-м ящиках имеется по 2 шарика. Переложим один шарик из первого ящика во 2-ой и изобразим таким же образом еще один итог размещения:
И еще один:
Видим, что все размещения разрешено получить, изменяя между собой шарики и перегородки, либо расставляя k шариков на n-1+k месте. Количество n-1+k получается так: у n ящиков имеется ровно n+1 перегородка, считая крайние, либо n-1 перегородка, если не считать крайние, которые двигать нельзя. И имеется k шариков. Перебрав все вероятные методы расставить k шариков на этих n-1+k местах (и устанавливая на оставшиеся места перегородки), переберем все нужные размещения.
Но способов расставить k шариков на n-1+k местах ровно - это в точности количество методик избрать из n-1+k номеров мест k номеров мест (в отсутствии учета порядка и в отсутствии возвращения), на которые необходимо поместить шарики. Заметим, что равенство верно как по определению биномиальных коэффициентов или свойствам треугольника Паскаля, так и в силу того, что разрешено вместо выбора k мест для шариков избирать n-1 пространство для перегородок ящиков, заполняя шариками оставшиеся места. [10]
2.2 Предмет теории вероятностей
Теория вероятностей исследует закономерности, возникающие в случайных опытах (явлениях). Случайным именуют опыт, итог которого нельзя предсказать заблаговременно. Неосуществимость предсказать заблаговременно - основное, что отличает случайное явление от детерминированного.
Не все случайные явления (опыты) разрешено изучать способами теории вероятностей, а только те, которые имеют все шансы быть воспроизведены в 1 и тех же критериях и владеют (почему-то как проверяемым заблаговременно) свойством «статистической устойчивости : «если А - некое явление, могущее произойти либо никак не случится в итоге опыта, то порция n(А)/n числа опытов, в которых данное явление произошло, имеет тенденцию стабилизироваться с подъемом общего количества опытов n, приближаясь к некоторому количеству Р(А). Наверное количество служит объективной чертой «степени возможности» событию А произойти.
В предстоящем мы станем говорить только о случайных экспериментах, обладающих данными качествами, а свойство статистической устойчивости докажем в утверждении, известном как закон больших чисел Бернулли.
Приведем примеры случайных явлений.
1. Производится стрельба из орудия, установленного под заданным углом к горизонту.
Воспользовавшись способами внешней баллистики (науки о движении снаряда в воздухе), разрешено найти теоретическую линию движения снаряда. Данная линия движения вполне определяется условиями стрельбы: исходной скоростью снаряда , углом кидания и баллистическим коэффициентом снаряда . Фактическая линия движения всякого отдельного снаряда неизбежно несколько отклоняется от теоретической за счет совокупного воздействия многих факторов. Среди этих факторов можно, к примеру, назвать: оплошности производства снаряда, отклонение веса заряда от номинала, разнородность структуры заряда, оплошности установки ствола в заданное положение, метеорологические условия и т.д. Если изготовить несколько выстрелов при неизменных основных условиях (,,), мы получим не 1 теоретическую линию движения, а целый пучок либо «сноп» траекторий, образующих так именуемое «рассеивание снарядов».
2. Одно и то же тело некоторое количество раз взвешивается на аналитических весах; итоги повторных взвешиваний несколько различаются друг от друга. Эти различия обусловлены воздействием многих второстепенных причин, сопровождающих операцию взвешивания, таких, как состояние тела на чашке весов, случайные вибрации техники, оплошности отсчета показаний устройств и т.д.
3. Самолет совершает полет на заданной высоте; теоретически он летит горизонтально, умеренно и прямолинейно. Практически полет сопровождается отклонениями центра массы самолета от теоретической линии движения и колебаниям самолета около центра массы. Эти отклонения и колебания считаются случайными и связаны с турбулентностью атмосферы; от раза к разу они не повторяются.
4. Делается ряд подрывов осколочного снаряда в конкретном расположении относительно цели. Итоги отдельных подрывов несколько различаются друг от друга: изменяются общее количество осколков, взаимное расположение их траекторий, вес, форма и скорость каждого отдельного осколка. Данные изменения считаются случайными и связаны с воздействием таких факторов, как неоднородность металла корпуса снаряда, неоднородность взрывчатого вещества, непостоянство скорости детонации и т.п. В связи с этим разные подрывы, осуществленные, казалось бы, в одинаковых критериях, могут приводить к разным итогам: в 1 подрывах цель станет поражена осколками, в остальных - нет.
Все приведенные примеры рассмотрены тут под одним и тем же углом зрения: подчеркнуты случайные вариации, неодинаковые итоги ряда экспериментов, основные условия которых остаются постоянными. Данные вариации постоянно связаны с наличием каких-то второстепенных факторов, оказывающих большое влияние на финал эксперимента, но не заданных в количестве его основных критерий. Основные условия эксперимента, характеризующие в общих и грубых чертах его протекание, сохраняются постоянными; второстепенные - изменяются от эксперимента к эксперименту и вносят случайные отличия в их итоги.
Совершенно очевидно, что в природе нет ни 1-го физического явления, в котором никак не присутствовали бы в той или иной мере составляющие случайности. Как бы точно и подробно ни были фиксированы условия эксперимента, нереально добиться того, чтоб при повторении эксперимента итоги полностью и в точности были схожими.
Случайные отличия неизбежно сопровождают любому закономерному действу. Тем не менее, в ряде практических задач этими случайными элементами можно пренебречь, рассматривая вместо реального явления его упрощенную схему, «модель», и предполагая, что в этих критериях эксперимента явление проходит вполне конкретным образом. При этом из бесчисленного большого колличества факторов, оказывающих большое влияние на данное явление, выделяются наиболее главные, основные, решающие; воздействием остальных, второстепенных факторов просто пренебрегают. Такая методика исследования явлений постоянно используется в физике, механике, технике. При пользовании данной схемой для решения хоть какой задачи прежде всего выделяется основной круг учитываемых критерий и выясняется, на какие характеристики задачи они влияют; затем используется тот либо другой математический аппарат (к примеру, составляются и интегрируются дифференциальные уравнения, описывающие явление); таким образом выявляется основная закономерность, характерная этому явлению и дающая вероятность предречь итог эксперимента по его заданным условиям. По мере становления науки количество учитываемых причин становится все больше; явление изучается подробнее; научный прогноз становится точнее.
Но для решения ряда вопросов описанная методика - классическая методика так именуемых «точных наук» - как оказалось плохо адаптированной. Есть такие задачи, где интересующий нас финал эксперимента находится в зависимости от столь огромного количества факторов, что практически нереально зарегистрировать и учесть все данные причины. Это - задачи, в которых многочисленные второстепенные, тесно переплетающиеся меж собой случайные причины играют заметную роль, а вместе с тем количество их так велико и влияние настолько сложно, что использование классических способов изучения себя не оправдывает.
Рассмотрим пример. Производится стрельба по некой цели Ц из орудия, установленного под углом к горизонту. Линии движения снарядов, как было указано выше, не схожи между собой; в итоге точки падения снарядов на земле рассеиваются. Если размеры цели велики по сопоставлению с областью рассеивания, то этим рассеиванием, очевидно, можно пренебречь: при правильной установке орудия хоть какой выпущенный снаряд попадает в мишень. Если же (как обычно и бывает на практике) область рассеивания снарядов превышает габариты цели, то некоторые из снарядов в взаимосвязи с воздействием случайных причин в мишень не попадут. Появляется ряд вопросов, к примеру: какой процент выпущенных снарядов в среднем попадает в мишень? Насколько необходимо потратить снарядов для того, чтоб достаточно надежно поразить мишень? Какие надлежит принять меры для уменьшения расхода снарядов?
Чтобы ответить на подобные вопросы, обычная схема точных наук оказывается недостаточной. Данные вопросы органически связаны со случайной природой явления; для того, чтобы на них ответить, разумеется, невозможно просто пренебречь случайностью, - нужно изучить случайное явление рассеивания снарядов с точки зрения закономерностей, свойственных ему именно как случайному явлению. Нужно изучить закон, по которому распределяются точки падения снарядов; необходимо выяснить случайные причины, вызывающие рассеивание, сопоставить их между собой по ступени значимости и т.д.
Рассмотрим другой пример. Некоторое техническое приспособление, к примеру, система автоматического управления, решает конкретную задачу в условиях, когда на систему постоянно действуют случайные помехи. Присутствие помех приводит к тому, что система решает задачу с некоторой ошибкой, в ряде случаев выходящей за пределы возможной. Появляются вопросы: как часто станут возникать эти ошибки? Какие следует принять меры для того, чтобы практически исключить их вероятность?
Чтобы ответить на эти вопросы, нужно исследовать природу и структуру случайных возмущений, воздействующих на систему, изучить реакцию системы на эти возмущения, выяснить воздействие конструктивных характеристик системы на вид данной реакции.
Все подобные задачи, количество которых в физике и технике чрезвычайно велико, требуют исследования не только основных, главных закономерностей, характеризующих явление в общих чертах, но и анализа случайных возмущений и искажений, связанных с наличием второстепенных факторов и придающих финалу эксперимента при заданных критериях элемент неопределенности.
Пример. Один раз подбрасывается 1 игральная кость (кубик). Самый разумный метод установить пространство элементарных исходов таков: Щ = {1,2,3,4,5,6}, элементарные исходы здесь соответствуют числу выпавших очков.
Примеры событий: А = {1,2} - выпало одно либо 2 очка; А = {1,3,5} - выпало нечетное количество очков.
Пример. 2 раза подбрасывается 1 игральная кость (кубик). Либо, что, то же наиболее, один раз подбрасываются 2 игральные кости. Как мы увидим в предстоящем, здесь самый разумный метод установить место элементарных исходов - считать итогом опыта упорядоченную пару количеств (i, j), в которой 1 i, j 6и i - число очков выпавших первый раз, j - число очков, выпавших второй раз. Щ = {(i, j), где 1 i, j 6}
Примеры событий:
А = {(1,1), (1,2), (1,3), (1,4), (1,5), (1,6)} - при первом подбрасывании выпало одно очко;
А = {(1,1),(2,2), (3,3), (4,4), (5,5), (6,6)} - при двух подбрасываниях выпало одинаковое число очков.
Пример. На плоскость стола бросается монетка. Итогом опыта разрешено полагать координату центра монеты (а если нам не безразличен угол поворота монеты, то разрешено добавить и величину данного угла). Пространство элементарных исходов - множество точек стола (в другом случае - очень много пар {х, ц}, где х - координата точки стола ц [0, 2р]- угол поворота). Количество элементарных исходов такового опыта несчетно.
Пример. Монетка подбрасывается по тех пор, пока не выпадет вверх гербом. Место элементарных исходов состоит из бесконечного, но счетного количества исходов:
Щ = {г, рг, ррг, рррг, ррррг, рррррг, …}, где р и г означают выпадение решки и герба при одном подкидывании, соответственно.
Пример. Приведем пример неправильно выбранного места элементарных событий. Пусть при кидания игральной кости Ч = {четное количество очков}, Т = {количество очков, кратное 3}. Тогда Щ = {Ч, Т, 1, 5} составляет все исходы опыта, однако исходы Ч и Т могут наступать одновременно.
1) Достоверным именуется явление, которое обязательно проистекает в итоге опыта, то есть единственное явление, включающее все без исключения элементарные исходы - событие Щ.
2) Невозможным именуется явление которое никак не имеет возможность произойти в итоге опыта, то есть явление, не содержащее ни 1-го элементарного исхода («пустое множество» ). Заметим, что постоянно Щ.
Пусть А и В - событие.
1) Объединением А U В событий А и В именуется явление, состоящее в том, что произошло или А , или В, или оба действия сразу. На языке теории множеств А U В имеется очень много, содержащее как элементарные исходы, входящие в А, так и элементарные исходы, входящие в В.
2) Пересечением А ? В событий А и В именуется событие, состоящее в том, что случились оба действия А и В одновременно. То имеется А ? В имеется множество, содержащее элементарные исходы, входящие одновременно в А и в В.
3) Дополнением А\В действия А по В именуется явление, состоящее в том, что произошло явление А, но не произошло В. То имеется А\В есть множество, содержащее элементарные исходы, входящие в А, однако никак не входящие в В.
4) Противоположным к событию А именуется явление , состоящее в том, что явление А в итоге опыта никак не произошло. Иначе говоря, имеется очень много, содержащее элементарные исходы, никак не входящие в А.
1) События А и В называются несовместными, если А ? В = .
2) События А1, А2 , … Аn называются попарно несовместными, если для любых i ? j, 1 i,j n, события Аiи Аj несовместны.
3) Говорят, что явление А влечет явление В, и пишут А В, если постоянно, как только проистекает явление А, проистекает и явление В. На языке теории множеств это значит, что любой элементарный исход, поступающий в А, сразу входит и в явление В.
Вероятность на дискретном пространстве элементарных исходов
Допустим, что мы имеем дело с дискретным пространством элементарных исходов, то есть пространством, состоящим из конечного либо счетного числа элементов:
Щ = {щ1, щ2 , … щn , … }.
Поставим каждому элементарному исходу щi Щ в соответствие число р(щi ) [0,1] так, что
|
(15) |
Назовем число р(щi) вероятностью элементарного исхода щi . Вероятностью события А Щ называется число
|
(16) |
равное сумме возможностей элементарных исходов, входящих в очень много А.
Позднее, познакомившись с аксиоматикой теории возможностей, мы установим вероятности событий непосредственно, а никак не через вероятности элементарных исходов. Тем более что сложением возможностей элементарных исходов разрешено заполучить только вероятность события, состоящего никак не более чем из счетного количества элементарных исходов (иначе само понятие суммирования никак не определено). Однако на дискретном пространстве элементарных исходов определить вероятности событий так, как это сделано в определении 6, постоянно возможно.
Перечислим очевидные в случае дискретного пространства элементарных исходов характеристики вероятности, которые мы скоро докажем сразу в общем случае.
1) 0 Р(А) 1;
2) Р(Щ) = 1;
3) Р() = 0;
4) Р(Ф) = 1 - Р(О);
5) если А и В несовместны, то Р(А U В) = Р(А) + Р(В);
6) в общем же случае Р(А U В) = Р(А) + Р(В) - Р(А ? В);
7) если А В, то Р(А) Р(В).
2.3 Классическое определение вероятности
Допустим, что мы имеем дело с пространством элементарных исходов, состоящим из конечного числа N частей: Щ = {щ1, щ2, … щN}. Более того, допустим, что из каких-либо суждений мы можем полагать элементарные исходы равновозможными. Тогда возможность хоть какого из них воспринимается равной 1/ N.
Данные суждения чаще всего не имеют отношения к математической модели и базируются на какой-либо симметрии в опыте (симметричная монетка, отлично перемешанная колода карт, правильная кость). Или мы можем заблаговременно полагать исходы эксперимента равновозможными, однако тогда рано или поздно все равно появится вопрос о согласовании такой математической модели действительному эксперименту.
Если явление А = {} состоит из k элементарных исходов, то возможность данного действия равняется
|
(17) |
где ¦А¦ обозначено число элементов конечного множества А.
Определение. Говорят, будто опыт удовлетворяет классическому определению вероятности (или классической вероятностной схеме), если пространство элементарных исходов состоит из окончательного числа ¦А¦ = N равновозможных исходов.
В данном случае возможность хоть какого действия А рассчитывается по формуле (18)
|
(18) |
именуемой классическим определением вероятности. Данная формула читается так: «возможность действия А одинакова отношению количества исходов, благоприятствующих событию А, к общему количеству исходов».
Полезно держать в голове классическую формулировку Якоба Бернулли: «Возможность есть степень правдивости, и различается от нее как дробь от целого».
Мы видим теперь, что подсчет вероятности в классической схеме сводится к подсчету количества «шансов» (элементарных исходов), благоприятствующих какому-либо событию, и общего количества шансов. Как правило, это делается с поддержкою формул комбинаторики.
Напомним, что речь идет о извлечении k шариков из урны, содержащей n шариков. При этом 3 схемы: с возвращением и с учетом распорядка, в отсутствии возвращения и с учетом распорядка, а также в отсутствии возвращения и в отсутствии учета распорядка удовлетворяют классическому определению вероятности.
Общее количество элементарных исходов в данных схемах подсчитано в теоремах 4, 2, 3 и равно, поэтому,
4-ая же схема - схема выбора с возвращением и в отсутствии учета распорядка - имеет заранее неравновозможные исходы.
Рассмотрим, к примеру, отбор 2-ух шариков из 2-ух либо, что то же самое, два раза подбросим монету. Если учесть распорядок, то исходов получится 4, и все они равновозможны, то есть имеют возможность по 1/4:
(герб, герб), (решка, решка), (решка, герб), (герб, решка).
Если распорядок никак не учитывать, то следует объявить 2 последних исхода одним и тем же итогом опыта, и получить 3 исхода вместо 4: выпало 2 герба, или 2 решки, или один герб и 1 решка.
При данном 1-ые 2 исхода имеют возможность 1/4, а последний - возможность 1/4+1/4=1/2.
2.4 Случайные величины
Для очень многих опытов недостает никаких различий в подсчете возможностей событий, тогда как элементарные исходы в данных опытах очень отличаются. Однако нас и должны занимать именно вероятности событий, а никак не структура пространства элементарных исходов. Поэтому во всех таких «похожих» опытах вместо самых различных элементарных исходов употребляют числа. То есть ввести соотношение между элементарными исходами и вещественными числами.
Пускай имеется случайный опыт и задано вероятностное пространство (Щ,Ш,Р).
Функция о: Щ >R называется случайной величиной, если для любого
хR множество {о<х}={щ: о(щ) < х} является событием, то есть принадлежит у-алгебре событий Ш.
Замечание. Можно смело полагать, будто хоть какое множество элементарных исходов есть явление, и, следовательно, случайная размер есть случайная функция из Щ в R. Никаких неприятностей на практике это обычно не влечет. [9]
Будем говорить, что функция о: Щ >R является Ш -измеримой, если {щ: о(щ) < х} принадлежит Ш для любого х R.
Итак, случайная величина есть Ш - измеримая функция, ставящая в соответствие каждому элементарному исходу щ Щ число о(щ) R.
Пример. Подбрасываем 1 раз кубик. Пусть Щ = {1, 2, 3, 4, 5, 6} , и две функции из Щ в заданы так: о(щ)= щ , з(щ)= щ2.
Если Ш есть множество всех подмножеств Щ, то о и з являются случайными величинами, поскольку любое множество элементарных исходов принадлежит Ш, в том числе и {щ: о(щ) < х} или {щ: з (щ) < х}. Можно записать соотношение между значениями случайных величин о и з возможностями воспринимать данные значения в виде «таблицы распределения возможностей» либо, коротко, «таблицы распределения» (таблицы 31, 32).
Таблица 31. Таблица распределения о
Таблица 32. Таблица распределения з
Здесь 1/6 = Р(о=1)=…= Р(о=6) = Р(з =1)= …= Р(з =36). Пусть у - алгебра событий Ш состоит всего из четырех множеств: Ш={Щ ,, {1,3,5},{2,4,6}}, то событием является, кроме достоверного и невозможного событий, выпадение четного (поэтому, нечетного) количества очков. Убедимся, что при такой «бедной» у - алгебре ни о, ни з не являются случайными величинами, так как эти функции не Ш - измеримы. Возьмем х = 3,967. Видим, что {щ Щ: о(щ) < 3,967}= {1, 2, 3} Ш и {щ Щ: з (щ) < 3,967}= {1} Ш.
Теперь попробуем понять, зачем нужна Ш - измеримость и почему требуется, чтобы {щ: о(щ) < х} являлось событием. Если задана случайная величина о, нам может потребоваться вычислить вероятности типа
Р(о=5)= Р{щ: о(щ)=5},
Р (о[-3,7]),
Р(о 3,2),
Р(о > 0)
2.5 Дискретные распределения
Говорят, что случайная величина о имеет дискретное распределение, если существует конечный или счетный набор чисел {а1, а2, …} такой, что:
а) рi = Р{ о = аi} > 0 для всех i;
б).
То есть случайная величина о имеет дискретное распределение, если она принимает не более чем счетное число значений. Если случайная величина о имеет дискретное распределение, назовем таблицей распределения соответствие аi - рi, которое чаще всего рисуют так (таблица 33).
Таблица 33.Таблица распределения
2.6 Виды дискретных распределений
Вырожденное распределение. Говорят, что случайная величина о имеет вырожденное распределение с параметром а, и пишут о Iа если о принимает единственное значение а с вероятностью 1, то есть Р(о = а) = 1. Таблица распределения о имеет вид (таблица 34).
Таблица 34. Таблица распределения
Распределение Бернулли. Говорят, что случайная величина о имеет распределение Бернулли с параметром р, и пишут о Вр, если о принимает значения 1 и 0 с вероятностями р и 1 - р, соответственно. Случайная величина о с таким распределением равна числу успехов в одном испытании схемы Бернулли с вероятностью успеха (0 успехов или 1 успех). Таблица распределения о имеет вид (таблица 35).
Таблица 35. Таблица распределения
Биномиальное распределение. Говорят, что случайная величина о имеет биномиальное распределение с параметрами n и р, где 0рn и пишут о Вn,р, если о принимает значения 0, 1,…,n с вероятностями:
|
Р(о=k)=Сnkрk(1-р)n-k |
(19) |
Случайная величина о с таким распределением имеет смысл числа успехов в n испытаниях схемы Бернулли с вероятностью успеха р. Таблица распределения о имеет вид (таблица 36).
Таблица 36. Таблица распределения
Геометрическое распределение. Говорят, что случайная величина ф имеет геометрическое распределение с параметром р, где 0 р , n, и пишут ф Gр, если ф принимает значения 1, 2, 3, …с вероятностями
|
Р(ф=k)=р(1-р)k-1 |
(20) |
Случайная величина ф с таким распределением имеет смысл номера первого успешного испытания в схеме Бернулли с вероятностью успеха р. Таблица распределения ф имеет вид (таблица 37).
Таблица 37. Таблица распределения
Распределение Пуассона. Говорят, что случайная величина о имеет распределение Пуассона с параметром л, где л > 0 , и о Пл, если о принимает значения 0, 1, 2 … с вероятностями
|
(21) |
Таблица распределения о имеет вид (таблица 38).
Таблица 38.
Таблица распределения
Гипергеометрическое распределение. Говорят, что случайная величина о имеет гипергеометрическое распределение с параметрами n, N и K, K N, n N если о принимает целые значения от mах (0, N - K - n ) до min (K ,n ) с вероятностями:
|
(22) |
Случайная размер с таким распределением имеет смысл числа белых шаров среди n шаров подобранных наудачу и без возвращения из урны, содержащей К белых шаров и N-K не белых.
Заметьте, что со всеми данными распределениями мы уже хорошо знакомы.
Но распределения случайных величин далеко никак не исчерпываются дискретными распределениями. Так, к примеру, если точка кидается наудачу на отрезок [0,1], то разрешено установить случайную величину, равную координате данной точки. Однако количество значений данной случайной величины несчетно, так что ее распределение дискретным не является. Да и возможность данной случайной величине принять каждое из собственных вероятных значений (угодить в точку) равна нулю. Так что не только таблица распределения никак не существует, но и соотношение «значение величины возможность его принять» ничто не говорит о распределении случайной величины.
3. РЕАЛИЗАЦИЯ ВЕРОЯТНОСТНОГО АВТОМАТА
3.1 Методология системного анализа
Если попытаться охарактеризовать современный уровень развития компьютерных и информационных технологий, то первое, на что следует обратить внимание - это возрастающая сложность не только отдельных физических и программных компонентов, но и лежащих в основе этих технологий концепций и идей. Кажется, еще совсем не так давно профессиональному программисту было довольно в совершенстве владеть одним-2-мя языками программирования, чтоб разрабатывать нешуточные программы. Отбор платформы и операционной системы, как правило, не считался серьезной проблемой. А сопровождение программы, желая и было связано с беспристрастными трудностями, могло быть реализовано обычным прибавлением либо изменением кода начальной программы. [7]
Системный анализ как научное направленность имеет наиболее давнюю историю, нежели ООП, и свой объект изучения. Центральным понятием системного анализа считается понятие системы, под которой понимается совокупность объектов, компонентов либо частей случайной природы, образующих некую целостность. Характеризующей посылом выделения некой совокупности как системы считается происхождение у нее новейших параметров, каких не имеют составляющие ее составляющие. Образцов систем можно привести довольно немало - это персональный компьютер, автомобиль, человек, биосфера, программа и др. Наиболее ортодоксальная точка зрения подразумевает, будто все окружающие нас вещи считаются системами.
Важными чертами, какой системы считаются ее структура и процесс функционирования. Под структурой системы понимают стабильную во времени совокупность связей между ее элементами либо составляющими. Конкретно структура связывает воедино все составляющие и мешает распаду системы на отдельные составляющие. Конструкция системы имеет возможность защищать наиболее разные связи, в том количестве и вложенность частей одной системы в иную. В данном случае принято именовать наиболее малую либо вложенную систему подсистемой, а наиболее крупную - метасистемой.
Процесс функционирования системы тесно связан с конфигурацией ее параметров либо поведения во времени. При данном принципиальной характеристикой системы является ее состояние, под которым понимается совокупность параметров либо показателей, которые в любой момент времени отображают более значительные индивидуальности поведения системы. [6]
Процесс функционирования системы отображает поведение системы во времени и имеет возможность существовать представлен как методичное изменение ее состояний: Если система изменяет одно свое положение на иное, то принято говорить, что система переходит из 1-го состояния в иное. Совокупность показателей либо критерий конфигурации состояний системы в данном случае именуется переходом. Для системы с дискретными состояниями процесс функционирования имеет возможность существовать представлен в виде последовательности состояний с соответствующими переходами.
Методология системного анализа служит концептуальной основой системно-направленной декомпозиции предметной области. В данном случае исходными составляющими концептуализации считаются системы и связи между ними. При данном понятие системы считается более общим, нежели понятия классов и объектов в ООП. Итогом системного анализа считается возведение некой модели системы либо предметной области. [8]
Более общей моделью системы считается так именуемая модель «черного ящика». В данном случае система представляется в виде прямоугольника, внутреннее устройство которого скрыто от специалиста либо непонятно. Но система не считается вполне изолированной от наружной среды, так как последняя оказывает на систему некие информационные либо материальные воздействия. Такие воздействия получили название входных воздействий. В свою очередь, система еще оказывает на среду либо остальные системы конкретные информационные либо материальные воздействия, которые возымели название выходных воздействий. Графически предоставленная модель имеет возможность быть изображена следующим образом (рисунок 16).
Рисунок 16. Модель системы «черный ящик»
3.2 Выбор среды разработки программы
Языки программирования, парадигмы, и практика никак не стоят на месте слишком долго. Нередко как оказалось, что способы и технические приемы, которые мы использовали вчера, сейчас уже устарели. Естественно, крупная скорость конфигураций -- это также одно из обстоятельств, которые совершают занятие программированием очень привлекательным времяпрепровождением. Постоянно есть что-то свежее на горизонте.[3]
Может быть, никакой язык никак не иллюстрирует предшествующие утверждения лучше, чем Jаvа. В последние несколько лет Jаvа подрос из концепции в один из глобально преобладающих машинных языков. Ко всему иному, в движение такого же короткого периода времени Jаvа прошел через 2 большие проверки. 1-ая случилась, когда была выпущена версия 1.1. Модифицирование в младшем номере версии (от 1.0 по 1.1) не отображает значительности спецификаций данной версии. К примеру, Jаvа 1.1 значительно поменял метод отделки событий, были добавлены такие характеристики, как Jаvа Bеаns и усовершенствованный АРI. [12]
В дипломной работе «Разработка недетерминированных программных систем на основе вероятных автоматов» избранной средой исследования считается 2-ая крупная версия -- Jаvа 2. В Jаvа 2 сохраняются все многофункциональные способности Jаvа 1.1 и прибавляется огромное численность новейших и усовершенствованных старых. К примеру, добавляется структура коллекций (соllесtiоns frаmеwоrk), наиболее мощный, нежели АWT, комплект классов Swing, новая поточная (thrеаding) модель и бессчетные АРI-способы и классы. [4]
Достоинства языка программирования Jаvа. Одно из основных преимуществ языка Jаvа - его самостоятельность от платформы, на которой выполняются программы. Таким образом, один и тот же код разрешено запускать под управлением операционных систем Windоws, Linuх, FrееBSD, Sоlаris, Аррlе Mас и др. Это делается совсем важным, когда программы загружаются посредством глобальной сети интернет и используются на разных платформах.
Иным, не менее принципиальным превосходством Jаvа, считается крупная сходство с языком программирования С++. Поэтому тем программистам, которые знакомы с синтаксисом С и С++ станет элементарно овладеть Jаvа.
Важно и то, что разрабатывать на Jаvа программы, которые никак не содержат погрешностей, существенно проще, нежели на С++.[11]
Все дело в том, что разработчиками языка Jаvа из фирмы Sun был проведен фундаментальный анализ программ на языке С++. Анализировались «узкие места» исходного кода, которые и приводят к появлению трудновыявимых погрешностей. Поэтому было принято решение планировать язык Jаvа с учетом способности творить программы, в которых были бы скрыты более распространенные оплошности. Для данного было сделано следующее:
- Создатели ликвидировали вероятность очевидного выделения и избавления памяти. К образцу, память в Jаvа высвобождается автоматом с поддержкою преспособления сбора мусора. Выходит, будто программер застрахован от погрешностей, которые появляются от неверного применения памяти.
- Введение истинных массивов и запрещение указателей. Теперь программисты никак не могут стереть данные из памяти по фактору неверного использования указателей.
- Была исключена вероятность спутать оператор присваивания с оператором сопоставления на равенство. Как правило, неувязка со знаком «=« очень нередко приводит в С и С++ к логическим ошибкам, которые не так просто найти. В особенности в больших программах.
- Вполне исключено многократное наследование. Оно было заменено новым понятием - интерфейсом, идея которого была позаимствована из языка Оbjесtivе С. Это становится совсем важным, когда программы загружаются посредством глобальной сети веб и используются на разных платформах.
Интерфейс дает программисту фактически все, что тот может заполучить от множественного наследования, избегая при этом сложностей, которые возникают при управлении иерархиями классов. [5]
3.3 Структура программы
В программе реализована возможность построения вероятного автомата, который можно представить в виде системы конечного автомата и генератора матриц вероятностного перехода. В программе возможен выбор вероятностного автомата Мили и Мура. В автомате Мили выходной сигнал зависит как от текущего состояния, так и от текущего входного символа. В автомате Мура выходной сигнал зависит только от текущего состояния автомата. В программе возможно задать количество символов в входном алфавите («число входов»), в выходном алфавите («число выходов»), в алфавите состояний («число состояний»), выбор вероятностного распределения из числа предложенных (Вырожденное распределение, Бернулли распределение, Пуассоновское распределение)
В программе имеется возможность задавать:
- входную последовательность;
- число входов;
- число выходов;
- число состояний.
Осуществлять выбор:
- вероятностного автомата (Мили или Мура);
- вероятностное распределение (вырожденное, Бернулли, Пуассоновское)
Главное окно программы продемонстрированно на рисунке 17.
Рисунок 17. Окно основной программы
Для того чтобы построить вероятностный автомат нужно выполнить следующие шаги:
- Заполнить поле «Входная последовательность».
- Заполнить поле «Число входов».
- Заполнить поле «Число выходов».
- Заполнить поле «Число состояний».
- Выбрать необходимое распределение.
- Выбрать необходимый автомат.
- И нажать кнопку «Построить».
После нажатия кнопки «Построить», в правой части окно будут выведены следующие таблицы (Рисунок 18):
- Таблица переход состояний.
- Таблица выходов.
А также будет выведен в отдельном окне граф, в вершинах которого будут состояния, а ребра графа будут указывать на переход из одного состояния автомата в другое (Рисунок 19). Подробный листинг можно просмотреть в приложении А.
Рисунок 18. Заполненное окно основной программы
Рисунок 19. Вывод графа
Таким образом, программа реализует построение вероятностного автомата с выбором необходимых для нас параметров и дальнейшее наглядное представление автомата в виде графа.
ЗАКЛЮЧЕНИЕ
В работе проведено исследование вероятностных автоматов, выделены основная классификация автоматов. Проанализирована каждая подзадача процесса построения вероятностного автомата и оценена возможность ее решения.
Модели взаимодействия вероятностных автоматов со случайными средами могут быть рассмотрены в качестве моделей адаптивных устройств управления трудными системами, для каких типично отсутствие необходимой информации о значениях входных сигналов и о соотношениях, связывающих входные воздействия и характеристики объектов с выходными переменными. Но широкое введение этих моделей в практику управления никак не происходило по многим факторам. Всесторонний их анализ позволил отметить среди них основные и на их базе сориентировать на вероятные направленности последующих исследований. Нужно развитие теории и способов применения автоматных моделей в направлениях:
- исследования моделей взаимодействия автоматов с наиболее трудными, чем стационарные и случайно переключающиеся средами;
- создания способов описания моделей определенных классов объектов в виде случайных сред, исследования и изучения моделей, названных автоматно-ситуационными, основанных на совместном применении принципов автоматного и ситуационного подходов.
Задачи, решенные в дипломной работе:
- исследование вероятностных автоматов;
- исследование классификации вероятностных автоматов;
- выбор представления вероятностных автоматов;
- разработка программного обеспечения.
В результате выполнения дипломной работы «Разработка недетерминированных программных систем на основе вероятных автоматов» был реализован алгоритм построения конечных вероятностных автоматов. Для демонстрации работы данного алгоритма было разработано Windоws- приложение на языке программирования высшего уровня Jаvа (ПРИЛОЖЕНИЕ А), позволяющее:
- инициализировать исходный вероятностный автомат;
- производить выбор вероятностного распределения заданного автомата;
- моделировать работу самого автомата, полученного в результате построения;
Таким образом, в дипломной работе были решены основные поставленные задачи.
Электронный вариант программы по дипломной работе «Разработка недетерминированных программных систем на основе вероятных автоматов» передан на кафедру Вычислительная техники на компакт диске по акту (ПРИЛОЖЕНИЕ Б).
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
1. Карпов Ю.Г. Теория автоматов. СПб.: Питер, 2003.
2. Поспелов Д.А. Вероятностные автоматы. М.: Энергия, 1970.
3. Чернова Н.И. Теория вероятностей. Новосибирск: Институт математики, 2004.
4. Шилдт Г. Полный справочник по Jаvа SЕ 6 Еditiоn. М.: Вильямс, 2007.
5. Бухараев Р.Г. Основы теории вероятностных автоматов. М.: Наука, 1985
6. Непейвода А.Н. Автоматное программирование. Потенциал, 2008. №5. С. 1-5
7. Непейвода Н.Н. Стили и методы программирования. М.: ИНТУИТ, 2004.
8. Шалыто А.А. SWITСH-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука, 2000.
9. Якубайтис Э.А., Васюкевич В.О., Гобземис А.Ю.,Зазнова Н.Е.,Курмит А.А., Лоренц А.А.,Петренко А. Ф., Чапенко В.П. Теория автоматов, Итоги науки и техники Сер. Теор. вероятн. Мат. стат. Теор. кибернет., 1976, том 13, С. 109-188
10. Гудрич М.Т., Тамассия Р. Структура данных и алгоритмы в Jаvа. Минск: Новое знание, 2003.
11. Методология системного анализа и системного моделирования, httр://www.znаnnyа.оrg/?viеw=Mеthоdоlоgy_аnаlysis_systеm_dеsign.
12. Преимущества языка программирования Jаvа, httр://www.соdеguru.соm.uа/аrtiсlе/а-204.html.
ПРИЛОЖЕНИЕ А
Листинг модуля вероятностного автомата:
class Avtomat{
public int state; // текущие состояние
public int input; // текущий входной символ
public int output; // текущий выходной символ
public int in; // количество входов
public int st; // количество состояний
public int out; // количество выходов
public int[][] q=new int[in][st];
public int[][] y=new int[in][st];
public int getState(){
return state;
}
public int getInput(){
// for(int i=1, i<s1.length();i++)
// return s1[int i];
// while (i<s1.length()) i++;
return input;
}
public void setState(){
getState();
getInput();
state=q[state][input];
}
public void setOutput(){
getState();
getInput();
output=y[state][input];
}
new Main();
}
}
/*
* ProbabilisticView.java
*/
Листинг модуля создания основной формы программы:
@Action
public void AddRow() {
// if (jRadioButton1.) then ;
// jRadioButton1.SELECTED_ICON_CHANGED_PROPERTY
Avtomat a = new Avtomat();
DataModel tm = new DataModel(); // создание тпблицы переходов состояния
DataModel tm1 = new DataModel(); // создание тпблицы выходов
int i;int j;
Random random = new Random();
String x = jTextField1.getText(); // число входов
String y = jTextField2.getText(); // число выходов
String s = jTextField3.getText(); // число состояний
String x1 = jTextField4.getText(); // входная комбинация
String y1=««; // выходная комбинация
String s1=««; // комбинация состояний
//jLabel10.setText(x1);
jLabel11.setText(«error»);
jLabel12.setText(«error»);
tm.setColumnCount(Integer.parseInt(x));
tm1.setColumnCount(Integer.parseInt(x));
for(i=0;i<Integer.parseInt(s); i++)
{
tm.setValueAt(Dat);
}
jTable1.setModel(tm);
for(i=0;i<Integer.parseInt(s); i++)
{
tm1.setValueAt(Dat);
}
jTable2.setModel(tm1);
int[][] output_table = new int[Integer.parseInt(s)][Integer.parseInt(x)]; // таблица выходов
int[][] state_table = new int[Integer.parseInt(s)][Integer.parseInt(x)]; // таблица переходов состояний
// случайное заполнение таблицы переходов состояния
for(i=0;i<Integer.parseInt(s);i++) {
for(j=0;j<Integer.parseInt(x);j++){
output_table[i][j]=random.nextInt(Integer.parseInt(s));
tm.updateValue(Integer.toString(output_table[i][j]),i,j);}}
// случайное заполнение таблицы выходов
for(i=0;i<Integer.parseInt(s);i++) {
for(j=0;j<Integer.parseInt(x);j++){
@Action
public void AddRow() {
// if (jRadioButton1.) then ;
// jRadioButton1.SELECTED_ICON_CHANGED_PROPERTY
Avtomat a = new Avtomat();
DataModel tm = new DataModel(); // создание тпблицы переходов состояния
DataModel tm1 = new DataModel(); // создание тпблицы выходов
int i;int j;
Random random = new Random();
String x = jTextField1.getText(); // число входов
String y = jTextField2.getText(); // число выходов
String s = jTextField3.getText(); // число состояний
String x1 = jTextField4.getText(); // входная комбинация
String y1=««; // выходная комбинация
String s1=««; // комбинация состояний
//jLabel10.setText(x1);
jLabel11.setText(«error»);
jLabel12.setText(«error»);
tm.setColumnCount(Integer.parseInt(x));
tm1.setColumnCount(Integer.parseInt(x));
for(i=0;i<Integer.parseInt(s); i++)
{
tm.setValueAt(Dat);
}
jTable1.setModel(tm);
for(i=0;i<Integer.parseInt(s); i++)
{
tm1.setValueAt(Dat);
}
jTable2.setModel(tm1);
int[][] output_table = new int[Integer.parseInt(s)][Integer.parseInt(x)]; // таблица выходов
int[][] state_table = new int[Integer.parseInt(s)][Integer.parseInt(x)]; // таблица переходов состояний
// случайное заполнение таблицы переходов состояния
for(i=0;i<Integer.parseInt(s);i++) {
for(j=0;j<Integer.parseInt(x);j++){
output_table[i][j]=random.nextInt(Integer.parseInt(s));
tm.updateValue(Integer.toString(output_table[i][j]),i,j);}}
// случайное заполнение таблицы выходов
for(i=0;i<Integer.parseInt(s);i++) {
for(j=0;j<Integer.parseInt(x);j++){
state_table[i][j]=random.nextInt(Integer.parseInt(y));
tm1.updateValue(Integer.toString(state_table[i][j]),i,j);}}
/*
// преобразование входной последовательности в выходную
a.setTableQ(Integer.parseInt(s), Integer.parseInt(x), beta1);
a.setTableY(Integer.parseInt(y), Integer.parseInt(x), beta);
int l=x1.length(); a.state=1;
for(i=0;i<l;i++){
a.input=x1.toCharArray()[i];
a.output=a.y[a.state][a.input];
y1=y1+a.output;
a.state=a.q[a.state][a.input];
s1=s1+a.state;
}
jLabel11.setText(y1);
jLabel12.setText(s1);
*/
// преобразование входной последовательности в выходную
//a.setTableQ(Integer.parseInt(s), Integer.parseInt(x), beta1);
//a.setTableY(Integer.parseInt(y), Integer.parseInt(x), beta);
int l=x1.length();
int state1=1;
int input1; int output1;
char c;
jLabel11.setText(Character.toString((char)x1.toCharArray()[1]));
for(i=0;i<l;i++){
input1=Integer.parseInt(Character.toString((char)x1.toCharArray()[i]));
output1=output_table[state1][input1];
y1=y1+output1;
state1=state_table[state1][input1];
s1=s1+state1;
}
jLabel12.setText(«xxxxxxxxx»);
jLabel11.setText(y1);
jLabel12.setText(s1);
tm.resizeColumnsByNameWithHTMLSupports(jTable1);
//jLabel15.setText(«true»);
}
public void AddRow2() {
//Avtomat A = new Avtomat();
String x = jTextField4.getText();
//String y=« «;
//for(int i=0;i<x.length(); i++)
// y[i]=getValueAt(1 ,x[i]);
//jTextField4.getText()
// jTextField5.setText(jTextField4.getText());
// jTextField5.setText(«123»);
//jLabel10.setText(x);
// jTextField4.getText()
}
@Action
public void Graph() {
// main.java;
}
@Action
public void qwerty() {
String[] items = {
«Элемент списка 1»,
«Элемент списка 2»,
«Элемент списка 3»
};
}
int l=x1.length();
int state1=1;
int input1; int output1;
char c;
jLabel11.setText(Character.toString((char)x1.toCharArray()[1]));
for(i=0;i<l;i++){
input1=Integer.parseInt(Character.toString((char)x1.toCharArray()[i]));
output1=output_table[state1][input1];
y1=y1+output1;
state1=state_table[state1][input1];
s1=s1+state1;
}
jLabel12.setText(«xxxxxxxxx»);
jLabel11.setText(y1);
jLabel12.setText(s1);
tm.resizeColumnsByNameWithHTMLSupports(jTable1);
//jLabel15.setText(«true»);
public int input; // текущий входной символ
public int output; // текущий выходной символ
public int in; // количество входов
public int st; // количество состояний
public int out; // количество выходов
public int[][] q=new int[in][st];
public int[][] y=new int[in][st];
public int getState(){
return state;
}
public int getInput(){
// for(int i=1, i<s1.length();i++)
// return s1[int i];
// while (i<s1.length()) i++;
return input;
}
public void setState(){
getState();
getInput();
state=q[state][input];
}
public void setOutput(){
getState();
getInput();
output=y[state][input];
}
new Main();
}
}
/*
* ProbabilisticView.java
*/
int[][] output_table = new int[Integer.parseInt(s)][Integer.parseInt(x)]; // таблица выходов
int[][] state_table = new int[Integer.parseInt(s)][Integer.parseInt(x)]; // таблица переходов состояний
// случайное заполнение таблицы переходов состояния
for(i=0;i<Integer.parseInt(s);i++) {
for(j=0;j<Integer.parseInt(x);j++){
output_table[i][j]=random.nextInt(Integer.parseInt(s));
tm.updateValue(Integer.toString(output_table[i][j]),i,j);}}
// случайное заполнение таблицы выходов
for(i=0;i<Integer.parseInt(s);i++) {
for(j=0;j<Integer.parseInt(x);j++){
state_table[i][j]=random.nextInt(Integer.parseInt(y));
tm1.updateValue(Integer.toString(state_table[i][j]),i,j);}}
...Подобные документы
Понятие автомата как дискретного преобразователя информации, особенности его состояний. Синтез конечных автоматов, их задания и структурных анализ. Построение синтеза функций возбуждения элементарных автоматов. Комбинационный синтез конечных автоматов.
курсовая работа [336,4 K], добавлен 01.06.2014Минимизация абстрактного автомата Мили, моделирование его работы. Синтез схемы конечного автомата, микропрограммного автомата и счетчика числа микрокоманд. Разработка цифровой линии задержки. Построение граф-схем исходного и оптимизированного автоматов.
курсовая работа [823,8 K], добавлен 19.07.2012Составление треугольной таблицы. Нахождение списка максимальных классов совместимости, минимального замкнутого покрытия. Получение логических функций выходов автомата. Синтез конечного автомата и функциональной схемы. Принципиальная электрическая схема.
контрольная работа [215,8 K], добавлен 22.06.2012Теоретические и практические основы грамматик, теория конечных автоматов-распознавателей. Эквивалентные и недостижимые состояния конечных автоматов. Классификация грамматик и порождаемых ими языков. Разработка программного комплекса построения грамматик.
курсовая работа [654,2 K], добавлен 14.11.2010Разработка модели процессора, выполняющего набор машинных команд. Структурная схема процессора (операционного и управляющего автоматов), анализ принципа работы. Содержательный алгоритм микропрограммы, синтез управляющего автомата на основе жесткой логики.
курсовая работа [871,9 K], добавлен 16.09.2010Понятие и свойства конечного автомата, его назначение и сферы применения. порядок разработки специальной функции, реализующей конечный автомат. Способы описания данной функции, обоснование выбора одного из них. Программная реализация решения задачи.
курсовая работа [466,4 K], добавлен 20.01.2010Изучение методов построения конечного автомата, распознающего заданный язык, и принципы его программной реализации. Проектирование комбинационной и принципиальной схем распознающего конечного автомата с использованием библиотеки интегральных микросхем.
дипломная работа [1,8 M], добавлен 18.08.2013Принцип работы процессора (одномагистральная структура). Временные диаграммы, описывающие выполнение микроопераций для каждой команды. Структурная схема управляющего автомата на основе памяти с одним полем адреса. Описание процессора на языке Active VHDL.
курсовая работа [621,0 K], добавлен 24.09.2010Анализ использования цифровых автоматов в системах обработки информации и управления технологическими процессами. Знакомство с основными положениями электротехники. Элементы проектирование цифрового автомата, его функционирование и электрическая схема.
курсовая работа [941,6 K], добавлен 22.06.2012Построение праволинейной грамматики, автоматной грамматики по полученным результатам. Построение недетерминированного конечного автомата. Сведение недетерминированного конечного автомата к детерминированному. Описание программы и контрольного примера.
курсовая работа [674,9 K], добавлен 13.06.2012Последовательность выполнения задания и рекомендации по проектированию. Проектирование несложных дискретных устройств (цифрового автомата), структурная схема и алгоритм функционирования. Применение синхронного триггера и его отличия от асинхронного.
методичка [258,6 K], добавлен 28.04.2009Составление формальной грамматики, недетерминированный конечный автомат. Построение конечного автомата, программное моделирование работы конечного автомата. Граф детерминированного автомата, Синтаксическая диаграмма. Блок-схемы, примеры разбора строк.
курсовая работа [486,2 K], добавлен 19.11.2010Синтез автомата для преобразования двоично-десятичного кода. Кодировка алфавитов и состояний. Построение булевых функций, минимизация. Разметка вход-выходных слов для автомата Мили и автомата Мура. Реализация на элементах малой степени интеграции.
контрольная работа [141,5 K], добавлен 14.10.2012Построим содержательные графы выполнения трёх команд языка Ассемблера. Команда умножения двоичных чисел без знака mul. Команда преобразования типов cwde. Логическая команда xor. Синтез канонического автомата. Синтез М-автомата. Управляющие сигналы.
реферат [35,7 K], добавлен 18.11.2004Важный частный случай недетерминированного конечного автомата. Проверка нечетности числа единиц в произвольной цепочке, состоящей из нулей и единиц. Составление формальной грамматики, блок-схемы и программы, моделирующей работу конечного автомата.
курсовая работа [210,8 K], добавлен 05.12.2013Основные понятия структурных автоматов. Этапы канонического метода синтеза. Кодирование алфавитов автомата и выбор элементов его памяти. Построение уравнений булевых функций возбуждения и выходов. Методы устранения гонок в структурных автоматах.
курсовая работа [496,3 K], добавлен 27.01.2011Сведение недетерминированного конечного автомата к детерминированному. Построение минимального детерминированного автомата из праволинейной грамматики двумя различными способами: с помощью сетей Петри и с помощью таблиц. Описание контрольного примера.
курсовая работа [903,9 K], добавлен 14.07.2012В статье рассмотрено применение конечных автоматов для создания системы автоматов, связанных графами. Документооборот представляется в виде автомата, обрабатывающего автоматы, каждый из которых моделирует поведенческую единицу системы документооборота.
статья [80,8 K], добавлен 19.04.2006Разработка управляющего автомата, ориентированного на выполнение заданной микрооперации. Разработка алгоритма работы управляющего автомата. Листинг программы. Выбор оптимального варианта кодирования состояний автомата. Синтез функции возбуждения.
курсовая работа [506,9 K], добавлен 26.12.2012Понятие, последовательность построения и схемная реализация цифрового автомата. Описание форм представления функций алгебры логики. Принципы минимизации функций выходов и переходов автомата, их перевода в базис. Сведенья о программе Electronics Workbench.
курсовая работа [2,0 M], добавлен 27.10.2010
