Конспект лекций Киров 2010 удк 681. 332




НазваниеКонспект лекций Киров 2010 удк 681. 332
страница9/17
Дата публикации21.08.2013
Размер0.75 Mb.
ТипКонспект
zadocs.ru > Химия > Конспект
1   ...   5   6   7   8   9   10   11   12   ...   17
^

11. Минимизация числа внутренних состояний автомата


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

Будем говорить, что две последовательности А=а1…..аi и В=b1….bi являются непротиворечивыми, если в них не содержится ни одной пары элементов i, bi] таких, что и .

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

Имеется соотношение:

,

где ^ М – число внутренних состояний, которые может хранить ЭП,

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

В настоящее время существует две группы методов построения автомата с минимальным числом внутренних состояний. Для первой группы характерно то, что сначала берётся автомат с одним внутренним состоянием, а затем производится увеличение числа его внутренних состояний до тех пор, пока он не станет реализующим автоматом.

Во второй группе методов берётся заведомо реализующий автомат с каким-то числом внутренних состояний, а затем производится уменьшение внутренних состояний до тех пор, пока автомат при числе внутренних состояний (N-1) не станет нереализующим.

Методы минимизации первой группы нашли применение при задании автомата таблицами включений. Методы второй группы применяются, когда автомат задан другими стандартными способами.

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

1. Разработка приближённых, но алгоритмизуемых методов, которые не гарантируют построение минимального реализующего автомата, но позволяют запрограммировать данный процесс. Метод Е.А. Бутакова.

2. Разработка методов минимизации отдельных частных классов недоопределённых автоматов, для которых имеется возможность построения минимального автомата.

1   ...   5   6   7   8   9   10   11   12   ...   17

Похожие:

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций по дисциплине "инвестирование"
Конспект лекций по дисциплине «Инвестирование» для студентов экономических специальностей всех форм обучения Сост.: В. М. Гридасов...

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций по дисциплине “Каналообразующие устройства”, 2010 Перечень лекций
Тема №1 (4 часа) Назначение, основные параметры и состав каналообразующих устройств 5

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций Витебск 2010 министерство образования республики...
Конспект предназначен для самостоятельного изучения, подготовки к практическим занятиям и экзамену по экономической теории

Конспект лекций Киров 2010 удк 681. 332 iconЭтика курс лекций (на основе книги: Этика (конспект лекций)
Этика (конспект лекций). – М.: «Приор-издат», 2002. Автор-составитель Аристотель. Никомахова этика. Сочинения: в 4-х т. Т. М.: Мысль,...

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций для студентов направления 070104 «Морской и речной транспорт»
Конспект лекций рассмотрены и одобрены на заседании кафедры «Судовождение» кгмту

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций по патологической анатомии инфекционных болезней. Киров, 2003
Вирусные инфекции представляют собой одну из многочисленных групп инфекционных заболеваний разнообразных по клиническому течению...

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций Утверждено Редакционно-издательским советом в качестве...
Чижов М. И., Юров А. Н. Информатика и информационные системы: Конспект лекций. Воронеж: Воронеж гос техн ун-т, 2003. 148 с

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций по дисциплине «Безопасность жизнедеятельности»
Безопасность в чрезвычайных ситуациях и гражданская оборона. Конспект лекций. Рубцов Б. Н. М. Миит, 2001

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций
Цифровые системы управления и обработки информации. Конспект лекций. Модуль 1: Организация и программирование систем чпу. (для студентов...

Конспект лекций Киров 2010 удк 681. 332 iconКонспект лекций для студентов сектора второго высшего образования...
Конспект лекций разработан кандидатом экономических наук, доцентом кафедры «Экономическая теория и кибернетика» Одесского государственного...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
zadocs.ru
Главная страница

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