| Компьютерное моделирование |
| 1 | компьютерное моделирование В случае, когда исследуемый объект имеет конечный набор дискретных состояний, а переходы из одного состояния в другое происходят по определенным правилам, исключающим элемент случайности, используется дискретно-детерминированный или автоматный подход Ф- схемы |
| 2 | он позволяет создать компьютерные модели огромного множества объектов, которым присущи дискретный характер работы: автоматические устройства контроля, регулирования и управления, программируемые исполнители, системы коммутации, нейросети и т.д. Развитием автоматного подхода являются метод клеточных автоматов и мультиагентный подход, использующиеся для решения большого класса задач 1 3 5 10 12. |
| 3 | 4 1 сущность автоматного подхода Автоматом обычно называют дискретное устройство, выполняющее заданную последовательность действий, в результате чего происходит преобразование информации, материальных объектов или энергии. Для изучения поведения автоматических устройств вводят понятие абстрактного автомата, воображаемого черного ящика, имеющим несколько внутренних состояний, вход и выход 11 13. |
| 4 | Абстрактный автомат задает- ся множеством внутренних состояний Q = {q1, q2 , ..., qk } , множествами входных и выходных символов (сигналов) X = {x1, x2 , ..., xn } и Y = { y1, y2 , ..., ym } , а также функцией перехода и функцией выходов . В не- которых случаях указывают начальное состояние z0 . Функция перехода связывает внутреннее состояние устройства q t +1 в момент времени t + 1 с внутренним состоянием q t и входным сим- волом x (сигналом) в предыдущий момент времени t : q Функция выходов связывает внутреннее состояние q входной сигнал x в момент t с выходным сигналом y в тот же момент времени: y = ( q , x ) . |
| 5 | Компоненты F = < X , Y , Q, , > однозначно t Майер Р.В. Компьютерное моделирование определяют конечный автомат, который можно рассматривать как мате- матическую F-схему (от англ. finite automata). Множество внутренних состояний Q образует внутреннюю память автомата. Если автомат имеет только одно внутреннее состояние, то он называется автоматом без памяти. Они задаются тройкой компонентов < X , Y , > . |
| 6 | Такие автоматы не меняют своего поведения: выходной сигнал (символ) определяется только входным и не зависит от ранее по- ступивших сигналов (символов) в предыдущие моменты времени: y tj = ( xit ) . К автоматам без памяти относятся: 1) цепь из источника, пере- ключателей и лампочек; 2) комбинационная схема, состоящая из логиче- ских элементов И, ИЛИ, НЕ и не содержащая триггеров; 3) кодер, осуще- ствляющий побуквенный перевод входного сообщения, и т.д. |
| 7 | Рассмотрим комбинационную схему с тремя входами и двумя выхо- дами (рис. 1.1). Состояния ее выходов, описываются логическими функ- циями: y1 = not( x1 or x2 ), y2 = ( x1 or x2 ) and x3 . Исследовать работу этой цифровой схемы можно с помощью программы ПР – 1 (Приложение). В ней перебираются всевозможные состояния входов x1 , x2 , x3 и опреде- ляются состояния выходов y1 и y 2 . На экране монитора появляется таб- лица истинности. |
| 8 | Рис. 1. Комбинационная схема. Диаграмма Мура автомата с памятью. Если автомат имеет два или более внутренних состояния, то он на- зывается автоматом с памятью. Рассмотрим автомат с четырьмя внут- ренними состояниями Q = { 1, 2, 3, 4} , входным алфавитом X = {a, b, c} и выходным алфавитом Y = {A, B, C , D, E , F } . Для задания правил переключения автомата будем использовать диаграмму Мура, представ- ляющую собой ориентированный граф (рис. 1.2). |
| 9 | Вершины графа изобра- Майер Р.В. Компьютерное моделирование жают состояния автомата Q = { 1, 2, 3, 4} , а ребра –– переходы из одного состояния в другое. Команда "2с 4А" означает, что если автомат нахо- дится в состоянии 2 и на его вход приходит символ "c", то он переходит в состояние 4 и на его выходе появляется символ "А". Промоделировать работу этого автомата на компьютере можно с помощью программы ПР – 2. |
| 10 | Пусть на вход поступает последователь- ность символов "babacaabcbabcbcbaaccbcbabcbccaacbb". Программа по- следовательно перебирает входные символы x , на каждом временном шаге t + 1 определяя новое состояние автомата Q t t +1 . Результаты выводятся на экран в виде таблицы. Рис. 2. Фигуры, которые рисует исполнитель "черепашка". Поведение автомата может никак не зависеть от состояния входа, а определяться лишь номером шага (дискретным временем t ) и заложенной в него программой. |
| … |
Комментарии