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

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

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

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

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

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

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

Сдать работу со 100% гаранией

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

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

Содержание

1. Развитие теории автоматов

2. Понятия автомата: термины и определения

2.1 Алфавитный способ преобразования информации

2.2 Понятие об алгоритме

2.3 Понятие о дискретном автомате

Заключение

Литература

1. Развитие теории автоматов

Теория конечных автоматов характеризуется широким использованием в различных областях применения дискретной техники. Эта теория получила первоначальное развитие на базе булевой алгебры и модели дискретного устройства в виде так называемого конечного автомата. На ней основано развитие методов логического проектирования дискретных устройств и методов построения тестов для проверки последних, обеспечение надежности и устойчивости их работы, решения задач «конструирования» дискретных устройств. Возникли отдельные ответвления теории конечных автоматов в виде теории вероятностных и нечетких автоматов, коллективного поведения автоматов, экспериментов и т. д. [14; 18–21; 24–26; 34–35; 90; 119; 125; 140],

Теория автоматов представляет собой раздел теории управляющих машин, изучающий математические модели преобразователей дискретной информации, называемые автоматами (от греч. аutómatos – самодействующий). С теоретической точки зрения, такими преобразователями являются как реальные устройства (вычислительные машины, автоматы, живые организмы и т. п.), так и абстрактные системы (математические машины, аксиоматические теории и т. д.). Характерной особенностью этих преобразователей является дискретность функционирования и конечность областей значений параметров, описывающих их.

В Библии сказано, что в начале было слово... Когда-то язык был слабым преобразованием вещей в сознании человека, прозрачной зыбкой моделью, отделяющий человека от неживой материи. За прошедшие тысячелетия язык развился до такой степени, что сам проявляет тенденцию к независимому движению и управляет развитием разума. Он сконцентрировал в себе все тайны Вселенной, в нем, возможно, скрыты ответы на извечные вопросы бытия.

Одна и та же модель одного и того же явления разными людьми воспринимается по-разному: формула может оставаться неизменной, но интерпретация ее может быть разной. Мир человеком воспринимается с помощью моделей, совершенствующих друг друга и увязываемых между собой до тех пор, пока не происходит революция в идеях, прекращающая такое понятие моделей и выводящее ее на новый уровень развития.

Наши модели вначале нечеткие. Это наглядно видно на примере изучения счета ребенком с 2 до 5 лет [65]. Ему необходимо повторить от 6-ти до 10 раз, чтобы он мог вначале различать один палец от двух. Наши мысли, сформированные на основе независимых моделей тоже нечеткие. Этим мы существенно отличаемся от дискретного компьютера!

Человек, помимо способности рассуждать и логически мыслить, обладает, как все живые существа, способностью принимать в расчет параллельно соображения, как общего, так и сопутствующего характера. Не рискуя сильно ошибиться, как писал французский профессор Арнольд Кофман, – «можно предсказать, что технология будет развиваться по пути, сближающем идеи компьютерного и обычного человеческого мышления в ожидании того дня, когда компьютеры начнут обрабатывать общую информацию принципиально параллельно с частной, без предварительной последовательной обработки» [49].

Понятие вероятности развивалось с XVII века. Идея вероятности появилась в процессе развития квантовых представлений в физике в начале ХХ столетия. Возник вопрос о соотношения динамических и статических законов. Известна дискуссия между Нильсом Бором и Альбертом Эйнштейном. В этой дискуссии Бор отстаивал вероятностный характер микропроцессов, а Эйнштейн отстаивал классическое представление, утверждая, что «Бог не играет в кости». К сожалению, эта дискуссия не завершилась и до сих пор.

Нобелевский лауреат, философ Илья Пригожин внес один новый и истинно важный момент в эту центральную для нас проблему, который позволяет решить вопрос о соотношении причиной детерминированности и многовариантности решений в сложных системах. Почему случайность реализуется именно так, как это происходит, а не иначе. Только ответ на данный вопрос позволяет понять, что такое условие и в чем специфика его влияния [133].

Теория автоматов возникла в середине ХХ столетия в связи с изучением свойств конечных автоматов. Исторически наиболее рано начала развиваться теория комбинационного синтеза релейно-контактных схем с использованием булевой алгебры [3–6;15; 21; 36; 87; 93].

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

В работах академика В.М. Глушкова и его школы была решена задача сопряжения этапов абстрактного и структурного синтеза и представление всей структурной теории автоматов в виде, пригодном для решения проблем синтеза цифровых автоматов с запоминающими двоичными элементами любой природы. Эта объединенная математическая теория цифровых автоматов была доведена до практического применения при разработке автоматизированной системы логического проектирования дискретных устройств [24–26]. В основу этой теории были положены автоматы Мили (автоматы 1-го рода) и Мура (автоматы 2-го рода) с памятью на двоичных триггерах [24].

В настоящее время вся теория автоматов делится на теорию абстрактных и структурных автоматов Мили и Мура, функционирующих в дискретные моменты времени ti (i = 1, 2, 3 ...,n,...).

Настоящий раздел посвящен изложению существующей классической теории автоматов Мили и Мура с памятью на двоичных триггерах и функционирующих в дискретные моменты времени ti, выявлению их ограничений. В этом разделе также предлагается более общая теория многофункциональных автоматов Мараховского 1-го и 2-го рода, частным случаем которой являются автоматы Мили и Мура, и теория автоматов 3-го рода [55; 59; 64].

Этот материал неоднократно излагался автором и его последователями в ряде работ [70–71; 79; 83–84], в учебных пособиях при чтении обязательного раздела по теории автоматов в курсе «Компьютерная схемотехника» [54–55; 66; 74], а также частично изложен в ряде статей и патентов. А также автором была предложена теория автомата 4-го рода, решающая вопрос выявления катастрофических отказов в базовых схемах памяти, что позволяет частично контролировать работоспособность базовых схем памяти в используемых устройствах компьютерных систем.

В настоящее время широко разрабатывается теория построения реконфигурируемых систем на «автоматном» уровне. Память на триггерах, которая применяется в этих устройствах и имеет жесткую (неизменяемую) структуру, не дает возможность использовать «элементный» уровень в теории построения реконфигурируемых систем [32; 39; 42; 91; 104–106; 138; 143].

Расширенная автором теория автоматов позволила создать теорию проектирования реконфигурируемых устройств с учетом «элементного» уровня с памятью на элементарных многофункциональных и многоуровневых схемах памяти [61–63].

2. Понятия автомата: термины и определения

2.1 Алфавитный способ преобразования информации

Философы и математики, заметив одинаковые законы развития разнообразных объектов, предложили общее понятие – сложная система.

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

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

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

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

Реальные устройства обладают рядом ограничений при приеме информации:

    чувствительность воспринимающего устройства дает ему возможность различать лишь конечное число градаций значений величин, характеризующих процесс;

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

    полосы пропускания воспринимающего информацию устройства не позволяют ему различать очень близкие моменты времени.

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

С учетом ограничений устройства, воспринимающего информацию, любая непрерывная информация сводится, фактически,

Лучшие

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

1 2 3 4 5 > >>