Особенности дискретных автоматов

Теория конечных автоматов характеризуется широким использованием в различных областях применения дискретной техники. Эта теория получила первоначальное развитие на базе

Особенности дискретных автоматов

Контрольная работа

Радиоэлектроника

Другие контрольные работы по предмету

Радиоэлектроника

Сдать работу со 100% гаранией
слов в некотором конечном алфавите в множество слов в том же самом или любом другом конечном алфавите. Такие отображения принято называть алфавитными операторами.

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

Алгоритмы могут быть однозначные, вероятностные, нечеткие, самосовершенствующиеся и т. д.

Примером однозначного алгоритма может быть система правил сложения целых чисел в произвольной позиционной системе счисления (двоичной, восьмеричной, десятичной и т. д.), которая состоит из правил поразрядного сложения и определения поразрядного переноса в старший разряд. Этот алгоритм сложения чисел С = А + В можно задать в формульном виде так [65]:

(1.3)

где сі — цифра і-го разряда результата;

рі+1 — перенос в і+1 разряд;

q – основание системы счисления.

Этот алгоритм перерабатывает слова а+b в алфавите, состоящим из q цифр и знака сложения, в слова в том же алфавите, но без знака суммы (+). Примером вероятностного алгоритма могут быть различные игры (в кости, в шашки, в шахматы и т. д.). Применительно к вероятностным алгоритмам выбор «лучшего» хода определяется не однозначно, а случайно, в соответствии с какими-либо вероятностными критериями.

Игру в шахматы можно трактовать как преобразование слов в конечном алфавите. В качестве алфавита здесь применяются символы шахматной нотации. Словами считают конечные последовательности букв алфавита. Одни последовательности представляют собою шахматные позиции, а другие – бессмысленные наборы символов, как например, 3КЛad. Алгоритм задается лишь для слов, представляющих осмысленные позиции в позицию, возникающую из нее после выполнения очередного хода. Опыт игры в шахматы показывает, что можно составить конечную систему стратегических правил, позволяющих в каждой конкретной ситуации выбрать единственный наилучший (в некотором смысле) ход. Присоединяя эту систему стратегических правил к правилам движения фигур, получаем алгоритм, который, несмотря на свою неоднозначность, можно назвать алгоритмом шахматной игры. Разработанный машинный алгоритм шахматной игры позволил компьютеру выиграть у чемпиона мира Каспарова [47].

Нечеткие (размытые, расплывчатые или неопределенные) алгоритмы, допускающие использования нечетких инструкций, широко распространены в различных сферах человеческой деятельности. Они позволяют описывать приближенные рассуждения и, следовательно, являются полезным инструментом для приближенного анализа таких систем и процессов принятия решений, которые слишком сложны для применения общепринятых количественных методов [34–35; 49].

Интересными типами алгоритмов являются самосовершенствующиеся (обучающие), которые обычно задаются в виде специальным образом организованной системы алгоритмов [25].

В простейшем случае система состоит из двух алгоритмов, один из которых является рабочим (многофункциональным) и осуществляет переработку информации (преобразование входных слов в выходные), а второй – контролирующий или обучающий алгоритм. Контролирующий алгоритм воздействует на рабочий алгоритм, изменяя режим его работу.

Характер изменений, вносимый обучающим алгоритмом, обычно делится на два типа. Первый тип изменений обычно меняет те или иные числовые параметры в неизменной схеме алгоритма. В самосовершенствующихся алгоритмах второго типа обучающий алгоритм меняет не только числовые параметры, но и структуру схемы рабочего алгоритма. Ступенчатая организация системы самосовершенствующихся алгоритмов позволяет моделировать формы самосовершенствования и самоорганизации.

Одно из важнейших фундаментальных понятий теории алгоритмов является рекурсия. Под рекурсией в общем смысле понимают такой способ организации системы, при котором она в отдельные моменты своего развития, определяемые ее правилами, может создавать (вызывать) собственные изменения копий, взаимодействовать с ними и включать их в свою структуру. Законы изменения копий при вызове также включаются в правила системы и могут зависеть от многих параметров: от состояния системы и других подсистем в момент вызова копии, от информационного наполнения заданных параметров, от правил самой системы. Частным случаем является чистая рекурсия, в которой отсутствуют изменения при вызове копии. Существует многообразие вариантов поведений копий. Они могут существовать и развиваться параллельно с главной системой, исчезать после своего этапа функционирования, по-разному взаимодействовать между собой. Все определяется правилами системы. В теории алгоритмов доказано, что, используя рекурсию, можно из ограниченного количества функциональных единиц получить все многообразие вычислительных функций [10].

При организации цикличных процессов используются рекурсивные выражения, которые описывают любой член последовательности чисел. Таким примером могут быть числа Фибоначчи, где первые два члена равны 1, а остальные вычисляются с помощью формулы ai = ai-2 + ai-1. Такая формула называется рекурсивною. Входными данными для каждого последующего шага являются результаты предыдущего [128; 130].

Структурная блок схема алгоритма определения ряда чисел Фибоначчи, чтобы последнее число не превышало 100, представляет вычислительный рекурсивный процесс с неизвестным числом повторений (рис. 1.1).

Многочисленные попытки уточнения понятия алгоритма привели к установлению способов точного задания произвольных алгоритмов. В.М.Глушков приводит один из таких способов, принадлежащий А.А. Маркову [25].

Алгоритмы А.А. Маркова, называемые также нормальными алгоритмами, преобразуют слова, заданные в любом конечном алфавите А = А(а1, ..., an), в слова в том же самом алфавите, причем, как правило, алгоритм оказывается определенным лишь для части слов и задает, следовательно, частичное отображение.

Рис. 1.1. Определение чисел Фибоначчи

С достаточной убедительностью В.М. Глушков показал, что любой алгоритм эквивалентен некоторому нормальному алгоритму. Поэтому, не нарушая общности, говоря о произвольном алгоритме, иметь в виду только нормальные алгоритмы.

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

Вычислительные машины (компьютеры) являются аппаратной реализацией конечных автоматов. Они могут быть цифровыми, аналоговыми или гибридными.

В данной работе основное внимание будет уделяться цифровым автоматам (компьютерам), которые функционируют в автоматном времени. Начиная с 40-х годов ХХ столетия, вся цифровая вычислительная техника проектировалась в целом с использованием классической теории автоматов Мили и Мура, память в которых использовалась в основном на триггерах (элементарных монофункциональных схемах памяти с закрытой структурой и с «нулевой» избыточностью). Все существующие машинные алгоритмы в той или другой мере использовали только один однозначный тип перехода в автоматах Мили и Мура – детерминированный переход за один машинный такт из одного состояния в другое, который зависел от предыдущего состояния автомата а(ti-1) и входного сигнала х(ti) в дискретный момент времени ti. Это обстоятельство определило последовательность работы машинных алгоритмов. Для параллельных алгоритмов необходимо было использовать аналогичную дополнительную аппаратуру. Примером может служить использования не менее двух сопроцессоров в компьютере и т. д.

С появлением многофункциональных автоматов Мараховского на схемах автоматной памяти [55; 58–64; 66–67; 70–85], возможности теории алгоритмов расширились в связи с качественно новыми дополнительными переходами в устройствах компьютера (hardware) [59]. Автоматная схема памяти, используя меньшее количество аппаратуры на одно запоминаемое состояние по сравнению с триггерами, в тоже время, оказалась в состоянии осуществлять качественно новые переходы в автоматах.

Автоматная схема памяти способна еще выполнять качественно новые переходы, такие как [64]:

    детерминированный переход за счет входного «пустого» сигнала е, то есть осуществлять переход за один машинный такт по двум переменным х и е;

    вероятностный переход в одно из подмножеств автомата, которые сохраняются под влиянием входных сигналов е;

    нечеткий переход в одно из четких подмножеств автомата, которое входит в нечеткое множество.

Появление возможности осуществлять качественно новые переходы в схемах памяти позволило Мараховскому и его ученикам расширить теорию автоматов [56–64; 66–85]. Авторы надеются, что это обогатить в дальнейшем и теорию компьютерных алгоритмов, и теорию построения устройств компьютеров, а также сможет явиться элементной базой для построения реконфигурируемых устройств, которой недостает в современных работах по когнитивному направлению при создании модели человеческого мозга [1–2; 101].

Подводя итоги можно сказать, что рассмотрение многофункциональных автоматов, предложенных Мараховским [55], функционирование которых рассматривается в непрерывное автоматное время, расширяет теорию классических автоматов Мили и Мура и создает в ней новое направление, позволяющее описывать устройства на схемах автоматной памяти, создавать качественно

Похожие работы

<< < 1 2 3 4 5 > >>