WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

Pages:   || 2 | 3 | 4 | 5 |   ...   | 6 |

«ОСНОВЫ НОВОЙ ИНФОРМАЦИОННОЙ ТЕХНОЛОГИИ Фундаментальные основы построения реконфигурируемых устройств компьютерных систем и искусственного нейрона Киев 2012 УДК 004.274 ББК 32.973.2-02 М25 ...»

-- [ Страница 1 ] --

Л. Ф. МАРАХОВСКИЙ

ОСНОВЫ НОВОЙ ИНФОРМАЦИОННОЙ

ТЕХНОЛОГИИ

Фундаментальные основы построения реконфигурируемых

устройств компьютерных систем и искусственного нейрона

Киев 2012

УДК 004.274

ББК 32.973.2-02

М25

Мараховский Л. Ф.

Основы новой информационной технологии. Фундаментальные

основы проектирования реконфигурируемых устройств компьютерных систем и искусственного нейрона: монография.

Л. Ф. Мараховский, Н. Л. Михно – Germany: Saarbrcken, LAP LAMBERT, 2012. – 347 с.

Монография рассматривает новое научное междисциплинарное направление, состоящее из четырех новых научных направлений в обработки информации, предложенных автором. Это теорию многофункциональных автоматов 1-го, 2-го, 3-го рода, разработка элементарных схем автоматной памяти, построение реконфигурируемых устройств компьютерной техники на схемах автоматной памяти и теория построения цифрового искусственного нейрона. Теория многофункциональных автоматов расширяет классическую теорию автоматов Мили и Мура и позволяет создавать новый тип автомата 4-го рода, контролирующего катастрофические отказы в базовых схемах памяти. Элементарные схемы автоматной памяти расширяют элементную базу компьютерных устройств, обладают повышенной надежностью и позволяют в процессе работы изменять структуру запоминаемых состояний. В целом такого системного подхода новая информационная технология позволяет проектировать конкурентоспособные реконфигурируемые устройства компьютерной техники и устройства искусственного интеллекта © Мараховский Л. Ф., © Михно Н. Л., © ГЭТУТ, Рецензенты:

Стахов А.П. – доктор технических наук, профессор, академик Академии инженерных наук Украины, Почетный профессор Таганрогского радиотехнического университета, Президент Международного Клуба Золотого Сечения.

Борисенко А.П. – доктор технических наук, профессор, заведующий кафедрой электроники и компьютерной техники Сумского государственного университета МОН молодежи и спорта Украины.

Вербицький В.Г. – доктор технических наук, профессор, директор ІМП НАНУ

СОДЕРЖАНИЕ

Предисловие……………………………………………….. Список сокращений………………………

Введение…………………………………………... Часть І. ОСНОВЫ ТЕОРИИ АВТОМАТОВ МИЛИ, МУРА И МАРАХОВСКОГО……………………………….. 1. Особенности автоматов ………………………………….. 1.1. Развитие теории автоматов..………………………………..… 1.2. Понятия автомата: термины и определения …

1.2.1. Алфавитный способ преобразования информации.…..… 1.2.2. Понятие об алгоритме 1.2.3. Понятие о дискретном автомате Заключение 2. Абстрактная теория автоматов 2.1. Понятие об абстрактном автомате 2.2. Понятие об абстрактных автоматах Мили и Мура....

2.3. Понятие об многофункциональных абстрактных автоматах Мили и Мура 2.4. Некоторые понятия об изменениях в функционировании и самоорганизации в автоматах ……….…………… 2.5. Некоторые модификации абстрактных конечных автоматов 2.6. Понятие об абстрактных многофункциональных автоматах Мараховского 2.7. Понятие об абстрактных автоматах, с перестраиваемой структурой запоминания состояний 2.8. Понятие об абстрактных вероятностных автоматах 3-го рода 2.9. Понятие об абстрактных нечетких автоматах 3-го рода 2.10. Классификация детерминированных абстрактных автоматов 2.11. Классификация недетерминированных абстрактных автоматов 2.12 Понятие об автоматах четвертого рода, контролирующих работоспособность базовых схем памяти Заключение 3. Способы задания автоматов …. 3.1. Некоторые понятия в теории абстрактных автоматов.

3.2. Табличные и графические способы задания классических автоматов Мили и Мура 3.3. Табличные способы задания многофункциональных абстрактных детерминированных автоматов 3.4. Табличные способы задания абстрактных вероятностных автоматов 3-го рода 3.5. Табличный способ задания абстрактных нечетких автоматов 3-го рода.. 3.6. Графические способы задания переходов в многофункциональных абстрактных автоматах 3.7. Математическая модель иерархического абстрактного автомата с многофункциональной системой организации памяти 3.8. Способ задания иерархического абстрактного автомата с многофункциональной системой организации памяти с помощью полиграммы 3.9. Формулирование полиграммы Заключение Часть 2. ОСНОВЫ ПОСТРОЕНИЯ СХЕМ АВТОМАТНОЙ ПАМЯТИ………………………………………….…. Введение 4. Монофункциональные элементарные схемы памяти 4.4. Триггер RS-типа на элементах потенциальной системы 4.5. Триггер RS-типа на элементах динамической системы 4.6. Проблемы обеспечения надежности работы автоматов 4.7. Методы проектирования монофункциональных схем памяти с 5. Структурная организация многофункциональных схем памяти 5.2. Метод микроструктурного синтеза элементарных МФСП 5.4. Исследование возможных вариантов многофункциональных 5.5. Синтез многофункциональных схем памяти по символьному 5.6. Определение входных слов схем автоматной памяти 5.6.1. Определение однозначных элементарных входных слов 5.6.2. Определение укрупненных элементарных входных слов 5.7. Вопросы надежности многофункциональных схем памяти 5.7.1. Вопросы повышения надежности многофункциональных 5.7.3. Вопросы контроля работоспособности базовых схем памя- 6. Структурная организация многоуровневых схем памяти 6.2. Разработка символьного языка описания многоуровневых схем 6.4. Разработка метода синтеза многоуровневых схем памяти по 6.5. Разработка принципа структурной организации элементарных 6.6. Разработка метода проектирования общего автомата стратегии 6.7. Метод логического проектирования многоуровневой схемы паM мяти класса L с одним автоматом стратегии 6.8. Метод логического проектирования многоуровневой схемы паB мяти класса LN с автоматом стратегии для каждой группы многоуровневых схем памяти 6.9. Классификация базовых элементарных схем памяти 6.10.1. Определение количества логических элементов, необходимых для построения схем памяти 6.10.3. Определение количества внутренних связей схем памяти 6.10.4. Определение количества внешних связей схем памяти 6.10.5. Определение количества элементов на одно состояние 6.11. Вопросы построения надежных устройств на многоуровневых 6.11.1. Вопросы надежности многоуровневых схемах памяти 6.11.2. Вопросы живучести многоуровневых схем памяти 6.11.4. Повышение надежности устройств, использующих МФСП

ЧАСТЬ 3. СИСТЕМНЫЙ ПОДХОД К ПОСТРОЕНИЮ РЕКОНФИГУРИРУЕМЫХ КОМПЬЮТЕРНЫХ УСТРОЙСТВ





Введение 7.1. Развитие реконфигурированных систем с памятью на триггерах 7.2. Разработка методов построения реконфигурированных регистров на многоуровневых схемах памяти 7.3. Анализ параметров реконфигурированных параллельных регистров на многоуровневых схемах памяти 7.4. Разработка методов построения реконфигурированных регистров сдвига на многоуровневых схемах памяти 7.5.2. Методы построения реконфигурировананых счетчиков на 7.6. Методы построения реконфигурированного устройства управления на многоуровневых схемах памяти 7.7. Методы построения реконфигурированных процессоров и компьютеров на схемах автоматной памяти 7.7.2. Методы построения реконфигурированной архитектуры 7.7.3. Исследование последовательной и параллельной обработки иерархической информации в современных процессорах 8. Способов задания иерархических автоматов на многоуровневых 9. Принципы построения реконфигурированных процессоров и компьютеров, одновременно обрабатывающих общую и частную 11. Ускорения выполнения алгоритмов в реконфигурированных компьютерных системах на многоуровневых схемах памяти

ЧАСТЬ 4. МОДЕЛЬ ЦИФРОВОГО ИСКУССТВЕННОГО

НЕЙРОНА НА СХЕМАХ АВТОМАТНОЙ ПАМЯТИ.

Введение 12.1. Предварительные понятия о модели нейрона 12.3. Основы кратковременной памяти человеческого мозга 12.4. Проблемы создания модели человеческого мозга 12.5. Информационные характеристики нейрона человеческого 12.6. Методы проектирования модели искусственного нейрона на 12.7. Структурная модель цифрового искусственного нейрона

ВЫВОДЫ

ПРЕДИСЛОВИЕ

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

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

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

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

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

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

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

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

Авторы будут благодарны за замечания данные читателями.

Контактные данные: Леонид Федорович Мараховский, д.т.н., профессор, основатель научной школы, член-корреспондент РАЕ: (044) 525-77-39, e-mail: marachovsky@ukr.net, Киев-28, Проспект Науки 35, корп. 4, кв. 23.

СПИСОК СОКРАЩЕНИЙ

ВТ – вычислительная техника;

ИИ – искусственный интеллект;

МСП – многостабильная схема памяти;

МФСП – многофункциональные схемы памяти;

МУСП – многоуровневые схемы памяти;

ЭА – элементарный автомат;

x(t) – устанавливающий входной сигнал;

e() – сохраняющий входной сигнал;

р (Т) – входное слово;

М – число устойчивых запоминаемых состояний схемы памяти;

rх – число устанавливающих x(t) входных сигналов в схеме памяти;

rе – число сохраняющих e() входных сигналов в схеме памяти;

Fp – предельная рабочая частота переключения;

РQ – нагрузочная способность по выходам;

Scв – число внутренних связей;

Sвc – число внешних связей;

L –·число элементов на одно состояние;

МЭА – многофункциональный элементарный автомат;

БА – базовый автомат;

у1(t) – выходной сигнал автомата 1-го рода;

у2(Т) – выходной сигнал автомата 2-го рода;

у3() – выходной сигнал автомата 3-го рода;

р0(Т) – однозначное входное слово;

ру(Т) – укрупненное входное слово;

СБИС – сверхбольшие интегральные схемы;

ЦИН – цифровой искусственный нейрон.

ВВЕДЕНИЕ

Парадигма основы новой информационной технологии на схемах автоматной памяти – новое междисциплинарное направление, объединяющее теорию автоматов, теорию построения схем памяти, принципы анализа базовых схем памяти при их катастрофических отказах, методы логического проектирования реконфигурируемых устройств компьютерной техники и принципы построения цифрового искусственного нейрона. Автор надеется, что основы новой информационной технологии на схемах автоматной памяти будут способствовать построению конкурентоспособных устройств. Она позволит расширить функциональные возможности, повысить надежность и живучесть, позволит выявлению катастрофических отказов в базовых схемах памяти реконфигурируемых устройств вычислительной техники (ВТ), реализованных с памятью на триггерах, с начала их промышленного использования [3–53; 86–95; 97–122; 124–138; 140–143].

Исторически работы по ВТ пошли сразу по двум направления [109]:

попытки смоделировать деятельность мозга, его психофизиологические свойства воспроизвести на логической машине или на электронной вычислительной машине (ЭВМ), или с помощью специальных технических устройств: искусственный интеллект или искусственный разум;

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

В 1981 году Япония предложила программу создания ЭВМ пятого поколения, которая позволила бы компьютерам частично владеть искусственным интеллектом (ИИ), т. е. самостоятельно составлять программы для решения конкретных задач, принимать самостоятельные решения и т.д. [99]. В году в США была принята стратегическая компьютерная программа, предусматривающая опережение японских разработок по машинам пятого поколения. Соответствующие программы были приняты в Англии, Франции, ФРГ, а также в странах членов СЭВ до 2000 года [109]. К сожалению и эти проекты не дали ожидаемых результатов по ИИ [100–102].

Формально, в 70-80 гг. прошлого века было окончательно установлено, что уровень развития вычислительной техники не позволяет говорить даже о возможности приближения к Искусственному Разуму. «Разумность» автоматических систем была снята с рассмотрения [101].

В эти годы многие ученные поняли, что путь их пришел в тупик, вследствие незнания фундаментальных основ построения устройств ИИ.

Рис.1. Динамика развития цифровых технологий Прогнозирование эволюционного развития цифровых микросхем и технологий с использованием математических формул, предложенных В. И. Акуновым, продемонстрировало совпадение прогнозов с реальными достижениями в этой области: линейная зависимость (закон Мура) по данным всемирно известной фирмы Интел (рис. 1) перестанет действовать к 2010 – 2015 г.г. [139].

В ноябре 2011 г. в Портленде (штат Орегон) Supercomputing Conference'09 фирма IBM заявила о существенном прогрессе в создании вычислительной системы, которая симулирует и эмулирует способность мозга чувствовать, воспринимать, действовать, взаимодействовать, познавать, и при этом сравнима с мозгом по низкому энергопотреблению и размерам.

BlueMatter – новый алгоритм, созданный IBM Research в сотрудничестве Рис. 2. Суперкомпьютер BlueGene/Р, на котором симулировалась со Стэнфордским университетом, использует суперкомпьютерную архитектуру BlueGene/Р (рис. 2) для измерения и отображения связей между всеми локусами коры и подкорки в мозге человека с помощью диффузной спектральной томографии [1–2; 96].

Специалисты компании IBM разработали передовой процессор, имитирующий работу человеческого мозга. «Это наше первое когнитивное компьютерное ядро, которое сочетает в себе вычисления в виде нейронов, память в виде синапсов, а связи - в виде аксонов», - рассказал в интервью CNET руководитель исследования Дхармендра Модха.

«Биологический» процессор основывается на алгоритме BlueMatter, который был разработан 2009 г. при попытке выявить связь между корковыми и подкорковыми структурами головного мозга. Разработка этого алгоритма была необходима для того, чтобы понять, как этот орган обрабатывает и обменивается информацией, отметил Модха [1–2].

В статье [96] указывается, что «современные вычисления базируются на модели хранимой программы, традиционно реализуемой в цифровых синхронных последовательных централизованных схемах общего назначения с явной адресацией памяти, которая без разбора перезаписывает данные и создает границу между вычислениями и данными. В отличие от этого когнитивные вычисления, подобные тем, что выполняет мозг, будут использовать повторяемые вычислительные блоки, нейроны и синапсы, реализуемые в смешанных аналого-цифровых асинхронных параллельных распределенных реконфигурируемых специализированных и отказоустойчивых биологических субстратах с неявной адресацией памяти, которая обновляется только при изменении информации, размывая границы между вычислениями и данными».

По мнению Модха, такие процессоры могут прийти на смену архитектуре фон Неймана, на которой построено большинство современных компьютеров. Когда появятся первые коммерческие приложения для «биологических» чипов, Модха не сообщил. Как считает аналитик Рик Доэрти, глава Envisioneering Group, такие программы могут быть готовы к 2015 или 2016 году [1–2; 96].

Для создания подобных чипов в IBM объединили достижения в области нанотехнологий, нейробиологии и суперкомпьютеров. Начальный этап исследований в области нейросинаптических чипов профинансировало американское агентство передовых научных разработок DARPA, выделив на проект 21 млн. долларов. Исследования велись в рамках научного проекта Systems of Neuromorphic Adaptive Plastic Scalable Electronics (SyNAPSE). Сейчас исследователи говорят, что созданные чипы пока способны анализировать данные, но не способны самоперестраиваться, а также память еще находится не в нейронах. Данные способности, как надеются исследователи, у них появятся в будущем.

Будущие приложения будут предъявлять повышенные требования к компьютерам и нам либо придется значительно наращивать вычислительные возможности чипов, либо делать их более интеллектуальными, - говорит Дхармендра Модха, руководитель данного проекта в IBM Research.

Исследуя неудачи и трудности создания ИИ на современном этапе автор приходит к выводу, что фундаментальные исследования в области человеческого мозга, его нейрона еще не привели к созданию соответствующей модели клетки нейрона, его модели связей, характеризующих реальный объект. В связи с этим и используются супер-компьютеры (рис.2), которые по внешним характеристикам создают пока только модель «действия кошки».

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

В данной монографии рассматривается фундаментальные основы реконфигурируемых устройств компьютеров, которые являються новым научным направлением, объединяющее теорию автоматов, схемы памяти, реконфигурируемые устройства компьютеров и искусственного нейрона на схемах автоматной памяти [54–55; 60–64; 66–68; 70–85].

Доктор технических наук, профессор Стахов А.П. пишет в статье [129], что недавно пришло сообщение об очередном аварийном запуске космического аппарата связи «Меридиан». Считается, что потери от аварийного запуска этого космического аппарата могут составить до 2 млрд. рублей. До этого подобные аварийные запуски происходили и ранее (при запуске спутников «Глобалстар»). Одной из возможных причин такого «сбоя» могут быть «сбои» в цифровой системе управления двигателями. По странному совпадению, аварии начались после усовершенствования системы управления и ее переводе на цифровую технику. И вот в этом, возможно, и «зарыта собака».

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

На низкую информационную надежность современных микропроцессоров (особенно иностранного производства) обращает внимание выдающийся российский ученый академик Ярослав Хетагуров, который пишет, что применение микропроцессоров, контроллеров и программного обеспечения вычислительных средств (ВС) иностранного производства для решения задач в системах реального времени (СРВ) военного, административного и финансового назначения таит в себе большие проблемы. Это своего рода «троянский конь», роль которого только стала проявляться. Потери и вред от их использования могут существенно повлиять на национальную безопасность России, Украины и многих других стран [137].

Стахов А.П. в своих работах [128–130], развивая мысли академика Хетагурова Я.А., сделал следующее, на первый взгляд парадоксальное утверждение: «Таким образом, человечество становится заложником классической двоичной системы счисления, которая лежит в основе современных микропроцессоров и информационных технологий. Поэтому дальнейшее развитие микропроцессорной техники и основанной на ней информационной технологии и классической двоичной системы счисления следует признать тупиковым направлением. Двоичная система не может служить информационной и арифметической основой специализированных компьютерных и измерительных систем (космос, управление транспортом и сложными технологическими объектами, нанотехнологии), а также наноэлектроннных систем, где проблемы надежности, помехоустойчивости, контролеспособности, стабильности, живучести систем выходят на передний план».

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

На взгляд авторов, одной из проблем в создании нового класса перестраиваемых компьютеров и создания модели исскуственного нейрона лежит широко используемая двоичная память, которая представляет собой закрытую структуру, «нулевую» избыточность и обладает жестким алгоритмом работы, не надежна при работе компьютерных систем и, как пишут авторитетные ученые: Я.А. Хетагуров [137], А.П. Стахов [128–130], не способна к перестройки структуры своих запоминаемых состояний.

многофункциональных автоматов [55; 60; 64; 70], делается попытка представить базовую перестраиваемую автоматную схему памяти, которая имеет ряд преимуществ перед базовой двоичной схемой памяти (RSтриггера). Это позволит по иному взглянуть на создание реконфигурируемых типовых устройств ВТ и самих суперкопьютеров и принципы построения цифрового искусственного нейрона.

ОСНОВЫ ТЕОРИИ АВТОМАТОВ МИЛИ, МУРА

И МАРАХОВСКОГО

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

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

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

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

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

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

[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].

1.2. Понятия автомата: термины и определения 1.2.1. Алфавитный способ преобразования информации Философы и математики, заметив одинаковые законы развития разнообразных объектов, предложили общее понятие – сложная система.

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

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

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

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

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

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

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

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

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

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

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

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

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

Различие между словами алфавитов разговорных языков и словами абстрактного алфавита состоит в том, что слово в абстрактном алфавите может содержать и простое сочетание букв, которое в обычном языке не имеет аналогов и считается бессмысленным (например, сочетание букв «ккллммнн»).

Количество букв в конкретном слове называют обычно длиною этого слова.

Наряду со словами положительной длины (состоящими не менее чем из одной буквы) в абстрактном алфавите рассматривается также пустое слово, не содержащее ни одной буквы.

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

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

При рассмотрении многофункциональных автоматов Мараховского (многофункциональных автоматов 1-го, 2-го и 3-го рода) с памятью, которые в процессе функционирования под влиянием пустого слова е могут изменять структуру запоминания в схеме памяти, дискретное автоматное время не подходит. В этом случае вводиться непрерывное автоматное время, в котором слову е выделяется длина, как букве абстрактного алфавита [55].

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

Рассмотрим понятие преобразование информации, которая представлена в алфавитной форме. С абстрактной точки зрения преобразование информации есть отображение одного класса явлений в другой класс явлений в соответствии с определенным законом. Например, явление из некоторого класса А явлений влечет за собою некоторое определенное явление из того же самого или из другого класса явлений В, то говорят, что задано преобразование информации где стрелка «» – знак преобразования информации, то есть отображение явления в явление.

Если подобное отображение осуществляется определенным объектом, то такой объект называется преобразователем информации.

Алфавитным отображением (оператором) называется всякое соответствие (функция), сопоставляющее слово в том или ином алфавите слова в том же самом или в некотором другом фиксированном алфавите.

Первый алфавит при этом называется входным, а второй – выходным алфавитом другого оператора. В случае совпадения входного и выходного алфавита говорят, что алфавитный оператор задан в соответствующем алфавите.

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

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

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

Большое значение имеет кодирующее отображение, которое называют просто кодированием. В наиболее простом виде кодирование заключается в сопоставлении каждой букве а1 алфавита А некоторой конечной последовательности b b... b в алфавите B, называемой кодом соответствующей букi1 i2 ik вы. Различным буквам алфавита А сопоставляются различные коды. Кодирующее отображение должно быть обратимым, то есть взаимная однозначность соответствующего кодирующего отображения. Обратимость кодирования будет всегда выполняться, если соблюдаются следующие два условия:

1. коды различных букв исходного алфавита А различны;

2. код любой буквы алфавита А не может совпадать ни с каким из отрезков кодов других букв алфавита В.

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

где n – число различных букв исходного алфавита А;

m – количество цифр двоичного алфавита, необходимых для кодирования букв алфавита А.

Кодирование информации в двоичном алфавите неоднозначно. Для любого исходного алфавита существует бесконечное множество таких преобразований. Такие преобразования называются двоичным кодированием исходной информации.

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

Это утверждение очень важно, потому что в реальных дискретных устройствах обычно значение сигнала разбивается на два типа: высокое давление – низкое давление, высокий потенциал – низкий потенциал и т. д., которые условно принимаются в двоичном алфавите за 1 или 0.

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

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

Предложил его автор книги c математики Abu Jafer Mohammed ibn Musa al Khowarizmi. Он определил его как определенный специальный метод разрешения поставленной проблемы.

Любое целенаправленное действие сложной системы связано с понятием алгоритма. Он определяет последовательность действий объекта для достижения цели. Так первобытные люди придумывали алгоритмы охоты и изобретали алгоритмы первых кулинарных рецептов. Алгоритмы повседневной жизни человека отличаются неоднозначностью и расплывчивостью выбора принятия решений, не всегда оптимальным исполнением. Это соответствует действию системы в ситуации с неполной информациею. Когда, как говорят, «картина» для человека ясна, то он старается действовать наиболее оптимальным или известным ему способом.

Человечество всегда искало способы описания найденных правил для решения своих задач в виде алгоритмов. Сохранились древние магические рецепты, математические тексты, книги боевого искусства, где описывались приемы действий в тех или иных ситуациях. Сохранились и переиздаются книги духовного содержания, такие как: Библия, Талмуд, Коран, где раскрываются расплывчатые алгоритмы духовного воспитания человека.

Потребности человечества в обобщении многочисленных подходов к решению разнообразных задач привели к созданию теории алгоритмов.

Понятие алгоритма является одним из фундаментальных понятий современной математики. В математической теории алгоритмов существует большое разнообразие определений алгоритма, которые ориентированы на различные способы вычислительной реализации. Например, арифметическое исчисление предикатов (К. Гедель, 1931), -определимые (А. Черч, 1936) и частично-рекурсивные (С. Клини, 1936) функции, машины Поста и Тьюринга (Э. Пост, 1936 и А. Тьюринг, 1937), алгоритмы Маркова (А. А. Марков, 1951) и многих других видных ученых. Попытку описать общую теорию алгоритмов предпринял В. М. Глушков в книге «Теория алгоритмов» [25], в которой он с системных позиций описал абстрактную теорию алгоритмов и связал ее с компьютерами, автоматами и самосовершенствующимися системами.

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

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

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

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

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

рі+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), в слова в том же самом алфавите, причем, как правило, алгоритм оказывается определенным лишь для части слов и задает, следовательно, частичное отображение.

НАЧАЛО

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

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

Теория машинных алгоритмов стала важною частью теории алгоритмов и прикладной математики.

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

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

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

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

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

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

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

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

101].

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

1.2.3. Понятие о дискретном автомате Дискретными автоматами Мили и Мура называют устройства преобразующие информацию в дискретные моменты времени, которые в математике отождествляются как точка на числовой оси (рис. 1.2, а) ti (i = 0, 1, 2, …, n, …), а в реальном устройстве как такт t (рис. 1.2, б).

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

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

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

Промежуток между тактами t в теории автоматов принято называть пустым словом е нулевой длины, т. к. под воздействием слова е автомат не способен переходить из одного состояния в другое, а только, выполняет функцию e сохранения установленного состояния [64]. Такое допущение дает возможность рассматривать функционирование цифрового автомата Мили или Мура в дискретном автоматном времени ti (рис. 1.2, б). При построении такого дискретного автоматного времени различают два основных случая:

1. синхронные автоматы, в которых машинный такт определяется генератором синхронизирующих импульсов, и, обычно, имеет одинаковые временные промежутки такта t, во время которого поступают устанавливающие х(t) входные сигналы на входы автомата. Промежутки между тактами t, на которые поступают пустые входные слова е, в работе автоматов Мили и Мура не принимаются во внимание потому, что они не способны участвовать в переходах схемы памяти автоматов на триггерах;

2. в асинхронных автоматах дискретное время определяется исключительно лишь в момент переходов в схемах памяти автомата из одного состояния в другое.

Теория асинхронных автоматов существенно отличается от теории синхронных автоматов тем, что в ней рассматриваются не только моменты фактически имевших место переходов, но также и такие переходы, которые в данный момент возможны, но не произошли переходы. К числу таких моментов причисляют моменты прихода входных сигналов х(t) импульсного типа (мгновенных) и изменения уровня напряжения сигналов потенциального типа, действующих во временном интервале такта t (рис. 1.2, б). При этом считают, что интервал дискретности автомата ограничивает минимально возможное расстояние между дополнительно вводимыми моментами автоматного времени. При таком допущении теория асинхронных автоматов в ряде случаев может быть сведена к синхронному случаю, поскольку фактически длины интервалов между последовательными моментами дискретного автоматного времени в идеализированной теории автоматов (без учета переходных процессов) не имеет никакого значения, так как на автомат в этот момент поступает пустое слово е нулевой длины. Имея в виду такое обстоятельство, в функционировании автоматов Мили и Мура используется абстрактное дискретное автоматное время, принимающее целые неотрицательные значения: t = 0, 1, 2, …, n, …, и строится теория, как теория последовательных синхронных автоматов, хотя в действительности она охватывает в значительной мере и теорию асинхронных автоматов.

Переходы из одного аi состояния автомата в другое ak вызываются входными сигналами x(t), возникающими вне автомата и передающимися в автомат по конечному числу входных каналов. В отношении х(t) входных сигналов цифровых автоматов принимаются два допущения: во-первых, для любого цифрового автомата число различных х(t) входных сигналов обязательно конечно, а, во-вторых, х(t) входные сигналы рассматриваются как причина перехода автомата из одного состояния в другое и относятся к моментам времени, определяемым соответствующими им переходами. Особо следует подчеркнуть, что реальный физический входной сигнал, вызывающий изменения состояния автомата в момент времени ti, может кончиться до наступления этого момента, однако, тем не менее, он относится именно к моменту времени ti, а не ti-1.

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

В многофункциональных автоматах Мараховского, которые названы по фамилии предложившего их автора, используется автоматная память [61–– 63], вводится и используется автоматное непрерывное время. В автоматном непрерывном времени кроме такта ti используется еще промежуток между тактами ti, интервал которого обозначим символом « ». Это объясняется тем, что в интервале используется сохраняющий входной сигнал е( ), который в автоматах Мили и Мура называется пустым словом нулевой длины и не учитывается при синтезе автоматов, а в многофункциональных автоматах может использоваться для осуществления укрупненных переходов в автоматной памяти автомата.

Рассмотрим автоматное непрерывное время с учетом синхронных сигналов j и дадим ряд определений.

Определение 1.1. Тактом t назовем промежуток времени, на протяжеi нии которого на автомат можно подавать произвольный синхронизирующий сигнал i.

промежуток времени между появлениями синхронизирующих сигналов i.

справа промежуток времени, который соответствует периоду синхронизированного сигнала i.

Такты, что определены, можно выразить такой формулой:

Информационные входные сигналы х(t) подаются на входные каналы сложного автомата и синхронизируются сигналом j. Эти входные сигналы воздействуют на автомат в автоматное непрерывное время такта t.

Определение 1.4. Внутренним единичным тактом 0 автоматного непрерывного времени назовем меньший открытый промежуток времени между появлением двух произвольных и последовательных синхронизированных сигналов р и р + 1.

Определение 1.5. Внешним единичным тактом Т0 назовем меньший открытый справа промежуток времени, который соответствует периоду времени между появлением двух произвольных и последовательных синхронизирующих сигналов р и р + 1.

Внешний единичный такт Т0 в соответствии со временем равен сумме продолжительности такта t и внутреннего единичного такту 0. Эта завиj симость рассматривается таким равенством:

Продолжительность внешнего такта равна продолжительности внешнего такта Та автомата. За один внешний такт Та на автомат воздействуют все синхронизирующие сигналы j по одному разу.

Определение 1.6. Внешним тактом Та автомата назовем меньший открытый справа промежуток времени, который соответствует периоду воздействия всех синхронизирующих сигналов j (j = 1, 2,…, C) на входных каналах автомата.

Автомат, что описывает реальное устройство компьютера, должен удовлетворять простейшим требованиям надежности и стабильности состояний аі и выходных сигналов уі.

Необходимо учитывать, что на входные каналы элементарных автоматов поступают сигналы определенной продолжительности j.

Под влиянием входного сигнала x(t) во время такта t элементарный автомат с памятью может переходить в определенное состояние при реализации однозначного перехода. Под воздействием входного сигнала е() во время внутреннего единичного такта 0 элементарный многофункциональный автомат с памятью может переходить в новое состояние при реализации функции укрупненного, вероятностного или нечеткого перехода.

Новое установленное состояние элементарного автомата может сохраняться после окончания такта t при однозначном переходе или после внутреннего единичного такта 0 при реализации функций укрупненного или вероятностного перехода.

Временные соотношения синхронизирующих и входных сигналов иллюстрирует рис. 1.3.

Выходной сигнал уj элементарного автомата фиксирует новое устойчивое состояние в автомате и сохраняет неизменным это состояние на всем формулою:

Внешний такт Та автомата своею продолжительностью равный сумме внешних единичных тактов Т0:

Автоматное непрерывное время дает более полную возможность исследовать закон функционирования автоматов Мили и Мура, реализованных на триггерах, чем дискретное автоматное время tі. Однако, исследовать многофункциональные автоматы Мараховского, реализованные на схемах автоматной памяти, на протяжении внутреннего такта і, необходимо только в автоматном непрерывном времени [64].

Рис. 1.3. Временные соотношения синхронизирующих и входных В автоматах Мили, рассматриваемых в автоматном дискретном времени, выходной сигнал у1(t) определяется парой (х(t), а(t-1)), а сам автомат называется автоматом первого рода.

В автоматах Мура, рассматриваемых в автоматном дискретном времени, сдвинутый выходной сигнал у2(Т) определяется парой одинаковых состояний а(t) и а(), где Т = t +. Состояние а(t) устанавливается только после перехода автомата в это состояние под воздействием х(t) входного сигнала.

Состояние а() сохраняется при сохраняющем е() входном сигнале. Сам автомат называется автоматом второго рода.

В многофункциональных автоматах, реализованных на схемах автоматной памяти и рассматриваемых в автоматном непрерывном времени, выходной сигнал исследуется как для многофункционального автомата 1-го и 2-го рода с использование входных сигналов х(t) и е(). Автоматы Мараховского являются более общим типом цифровых автоматом, а автоматы Мили и Мура являются их частным случаем. Кроме этого, в автоматах Мараховского рассматривается и автомат 3-го рода, который дополняет теорию автоматов 1-го и 2-го рода.

Схемы автоматной памяти представляют собою матрицу запоминаемых состояний [64], состоящую из блоков j, представляющих строки матрицы, в которых сохраняются подмножества определенных состояний автоматной схемы памяти под влиянием входного сигнала е(), и блоков µі, представляющие столбцы матрицы с определенными подмножествами состояний автоматной схемы памяти, устанавливаемых входным сигналом х(t).

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

В детерминированных автоматах Мараховского дополнительно рассматривается функция е сохранения состояний а(), которая определяется парой (а(t), е()). Входной сигнал е() сохраняет состояние а(t) автоматов 1го и 2-го рода после его установки на всем протяжении машинного такта Т в определенном подмножестве j (рис. 1.3). Функции переходов из одного состояния а(-1) в другое состояние а(t) определяется парой (а(-1), х(t)), а сохранение состояния а() во время промежутка определяется парой (а(t), е()).

В автоматах 3-го рода функция укрупненного перехода из состояния а(t) в состояние а() осуществляется под воздействием входного сигнала е() в определенном подмножестве µi и определяется парою (а(t), е()).

Типы выходных сигналов у определяют род автомата. Выходной сигнал у1 автомата первого рода определяется парой (а(-1), х(t)), выходной сигнал у2 автомата второго рода определяется парой (а(t), а()), а выходной сигнал у3 автомата третьего рода определяется парой (а(t), е()).

Общая теория автоматов при описанных допущениях разбита на абстрактную теорию автоматов и структурную теорию автоматов. В абстрактной теории автоматов отвлекаются от структуры самого автомата и его входных и выходных сигналов. Входные и выходные сигналы рассматриваются как буквы двух фиксированных алфавитов – входного и выходного.

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

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

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

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

Частным случаем дискретных автоматов являются автоматы, обладающие одним внутренним состоянием, которые называют комбинационными схемами или автоматами без памяти. Работа таких автоматов состоит в том, что они сопоставляют каждому входному сигналу х(t) соответствующий выходной сигнал у(t).

Основная идея методики синтеза автомата состоит в том, чтобы еще на уровне абстрактной теории преодолеть основные затруднения, вызванные наличием памяти, а на уровне структурной теории свести задачу синтеза к задаче синтеза комбинационных схем.

Теория многофункциональных автоматов, кроме детерминированных однозначных и укрупненных переходов, рассматривает еще вероятностные и нечеткие переходы.

Один тип вероятностных переходов определяет переходы из вполне определенного состояния автомата а(-1) подмножества i в состояние а() подмножества k (i k) с определенной вероятностью Р1 под влиянием пары (хр(t). ek()), в которой входной сигнал хр(t) устанавливает в схеме памяти не запоминаемое состояние ар(t) ни при одном входном сигнале e(). Другой тип вероятностных переходов определяет переходы из вполне определенного состояния автомата а(-1) подмножества i в состояние а() подмножества k (i k) под влиянием пары (х(t). ев()), в которой входной сигнал ев() с определенной вероятностью Р2 определяет подмножество сохраняемых состояний k. Вероятностный переход второго типа возможен при рассмотрении трех уровней автоматной схемы памяти в цифровом автомате.

Нечеткие переходы в нечеткие подмножества Qн, состоящие из определенного числа четких подмножеств i, определяют переходы из вполне определенного состояния автомата а(-1) подмножества i в состояние а() подмножества k (i k) с определенной вероятностью Рн под влиянием пары (хр(t). ев()).

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

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

2. АБСТРАКТНАЯ ТЕОРИЯ АВТОМАТОВ

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

В последующие годы, в связи с бурным развитием больших интегральных схем и сверхбольших интегральных схем (СБИС), которые представляют собою целые функциональные блоки компьютера (процессоры, оперативную память и т. д.), интерес к теории автоматов упал, хотя все они реализуются автоматами Мили и Мура. Даже некоторыми учеными в конце ХХ века высказывалась мысль, что теория автоматов себя изжила.

Однако, это совсем не так! Лучшим подтверждением является создание теории многофункциональных автоматов (в том числе и автоматов Мараховского), которые дали толчок для развития новых направлений в таких областях вычислительной техники, как:

1. теории построения схем автоматной памяти, которая в состоянии изменять свои состояния по двум переменным с реконфигурацией структуры запоминания состояний;

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

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

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

Рассмотрим понятия об абстрактных автоматах Мили, Мура и Мараховского.

2.2. Понятие об абстрактных автоматах Мили и Мура В теории абстрактных автоматов часто отвлекаются от его структуры.

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

С точки зрения последовательных монофункциональных автоматов Мили и Мура общая характеристика автомата достаточно полно описана в работе [26], в которой комбинационные схемы названы формерами. Известны канонические схемы автоматов Мили, Мура или в общем случае С-автомата.

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

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

у которого:

Х – конечное множество входных сигналов;

Y – конечное множество выходных сигналов;

: Х Y – функция выходов, реализующая отображение Х на Y.

Комбинационные схемы иногда называют функциональными преобразователями и изображают следующим образом (рис. 2.1):

Рис. 2.1. Функциональные преобразователи Определение 2.1. Абстрактный автомат А Мили или Мура задается как совокупность шести объектов:

где Х – конечное множество входных сигналов, называемых входным Y – конечное множество выходных сигналов, называемых выходным Q – произвольное множество, называемое множеством состояний а0 – элемент из множества Q, называемым начальным состоянием двух функций (а, х) и (а, х), задающих однозначные отображения Функция (а, х) называется функцией перехода автомата, а функция (а, х) – функцией выходов (для автомата Мили) или сдвинутой (а) функцией выходов (для автомата Мура). Автомат, заданный функцией выходов, называется автоматом первого рода; автомат, заданный сдвинутой функцией выходов, – автоматом второго рода.

Абстрактный автомат Мили или Мура функционирует в дискретном времени, принимая целые неотрицательные значения t = 0, 1, 2, …. В каждый момент времени t этого времени он находится в определенном состоянии а(t) из множества Q состояний автомата, причем в начальный момент времени t=0 автомат всегда находится в своем начальном состоянии а0, то есть а(0) = а0. В каждый момент времени t, отличный от начального, автомат способен воспринимать входной сигнал х(t) – произвольную букву входного алфавита Х и выдавать соответствующий выходной сигнал у(t) – некоторую букву выходного алфавита Y.

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

Автомат с начальным состоянием а0 называют инициальным абстрактным конечным автоматом.

Закон функционирования абстрактного автомата в случае автомата первого рода (автомата Мили) задается уравнениями в автоматном дискретном времени:

для автомата второго рода (автомата Мура), функционирующего в автоматном дискретном времени, – уравнениями:

а в случае С-автомата, в котором реализовались функции выходов автоматов Мили и Мура – уравнениями:

а(t) = (а(t – 1), х(t)), у1(t) = 1(а(t – 1), х(t)), у2(t) = 2(а(t)), Установлением закона функционирования заканчивается определение абстрактного автомата. Смысл понятия абстрактного автомата состоит в реализации некоторого отображения множества слов входного алфавита в множество слов выходного алфавита. Отображение в автоматах Мили и Мура реализуется так: каждое слово р х i1, x i2,..., x ik входного алфавита Х = (х1, х2, …, хn), или, более кратко, каждое входное слово, последовательно, буква за буквой, подается на вход данного абстрактного автомата А, установленного предварительно в начальное состояние а0. Возникающая таким обраА x(1) х,..., x(k ) x, на основании закона функционирования автомата выi1 ik зывает появление однозначно определенной конечной последовательности q= y(1), y(2), …, y(k) выходных сигналов. Эту последовательность называют выходным словом, соответствующим входному слову р. Допустимыми входными словами называются те и только те входные слова р, на которых с помощью функций и (описанным выше способом) определяются соответствующие выходные слова q=(р).

Рис. 2.2. Структурные схемы монофункциональных автоматов Построенное указанным способом искомое отображение, а именно: q = =(р), называют отображением, индуцированным абстрактным автоматом А.

Автомат называется конечным, если конечны все три определяющие его множества Х, Y, Q. Автомат называется вполне определенным, если его функции переходов и выходов заданы на всех парах (а, х), и частичным автоматом – в противном случае.

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

Каноническая схема автомата Мили (рис. 2.2, а), автомата Мура (рис. 2.2, б) или С-автомата в обобщенном виде (рис. 2. 2, в) состоят из, связанных между собою, регистра и комбинационных схем.

Монофункциональный автомат имеет жесткую структуру и всегда реализует одно и то же преобразование {X} в {Y}. Для такого автомата величина функциональности f равна 1 (f = 1).

2.3. Понятие об многофункциональных абстрактных автоматах С конца 60-х и начала 70-х годов ХХ века начались исследования последовательных многофункциональных логических устройств [32; 90–91; 138;

143]. Эти работы положили начало общей теории многофункциональных автоматов Мили и Мура. В этих работах использовались триггеры с коммутируемыми функциями входных и выходных сигналов, управляемые автоматами стратегии (настройки). Вначале в автоматах стратегии обрабатывалась общая информация, которая потом своими выходными сигналами настраивала многофункциональный автомат на реализацию одного монофункционального автомата Мили, Мура или С-автомата, в которых обрабатывалась частная информация.

Основа многофункциональных автоматов Мили и Мура была положена в структуры реконфигурируемых устройств компьютерной техники, в их алгоритмическое управление и в программное обеспечение искусственного интеллекта [16; 23; 25; 30; 33; 39; 41–42; 47; 52; 88; 91; 98; 102; 109–112; 116;

124; 132–134; 142].

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

Определение 2.2. Абстрактный многофункциональный автомат А Мили или Мура задается как совокупность восьми объектов:

где Х – конечное множество входных сигналов, называемых входным алфавитом;

Y – конечное множество выходных сигналов, называемых выходным алфавитом;

Q – произвольное множество, называемое множеством состояний автомата;

Q0 – множество из множества Q, называемым начальным множеством состояний автомата (Q0Q);

– множество функций переходов (i)(а, х) и (а, х), задающих однозначные отображения множества пар (а, х), где а Q и хХ, в множества Q и Х;

– множество функций выходов (i)(а, х), задающих однозначные отображения множества пар (а, х), где аQ и хХ, в множества Q и Х;

U – множество настроек функций переходов и выходов (U={U, U});

f – функциональность автомата, которая описывается как:

Некоторый i-й монофункциональный автомат Аі задается как шестикомпонентный кортеж или вектор:

в котором компоненты автомата не отличаются от компонентов, описанных в (2.2) Исходя из уравнений (2.3) и (2.4) функционирования монофункциональных автоматов 1-го и 2-го рода, получим уравнения законов функционирования детерминированных многофункциональных абстрактных автоматов таких же типов 1-го и 2-го рода:

Для многофункциональных автоматов 1-го рода (автоматов Мили) задается уравнениями в автоматном дискретном времени:

для автомата 2-го рода (автомата Мура), функционирующего в автоматном дискретном времени, – уравнениями:

а, в случае, объединенного С-автомата, в котором реализуются функции выходов автоматов Мили и Мура – уравнениями:

Смысл понятия многофункционального абстрактного автомата состоит в реализации некоторого множества отображений i множества слов входного i-го алфавита в множество слов выходного i-го алфавита. Отображение i в автоматах Мили и Мура реализуется так: каждое слово рi х i1, x i2,..., x ik входного i-го алфавита Хi = (х1, х2, …, хn), или, более кратко, каждое входное слово, последовательно, буква за буквой, подается на вход данного абстрактного автомата Аi из множества многофункционального автомата А, установленного предварительно в начальное состояние а(i)0. Возникающая таким образом конечная последовательность рi входных сигналов, автомата Аi x x(1), х(2),..., x(k ), на основании закона функционирования автомата выik зывает появление однозначно определенной i-й конечной последовательности qi= y(1), y(2), …, y(k) выходных сигналов. Эту последовательность qi называют выходным i-м словом, соответствующим входному слову рi. Допустимыми входными словами называются те, и только те, входные слова рi, на которых с помощью функций (і) и (і) (описанным выше способом) определяются соответствующие выходные слова qi=(рi).

Каноническая схема многофункционального абстрактного автомата с настройкой функций переходов и выходов представлена на рис. 2.3.

Монофункциональные и многофункциональные автоматы 1-го и 2-го рода и их объединение С-автомат [21; 24–26; 32; 90], реализующие свою регистровую память на триггерах и функционирование которых рассматривается в автоматном дискретном времени, являются частным случаем автоматов Мараховского (многофункциональных автоматов 1-го и 2-го рода) [55].

Рис. 2.3. Структурные схемы многофункциональных автоматов Мили и Мура с настройками U и U из автомата стратегии Автоматы Мараховского реализуют свою регистровую память на схемах автоматной памяти, и функционирование их рассматривается в автоматном непрерывном времени.

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

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

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

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

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

Области определения дискретных случайных величин могут быть конечными либо счетными бесконечными. В обоих случаях выполняется условие нормировки:

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

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

Работа реального устройства, которое исследуется в моделях автоматов Мили и Мура, наблюдается лишь в выделенные моменты времени t1, t2, и т.д.

Изменения, происходящие с устройством, между наблюдаемыми моментами с точностью до несущественных деталей определяются информацией в моменты t1, t2 и т.д. Одно из возможных обобщений этого допущения заключается в рассмотрении двух независимых последовательностей времени t1, t2 и 1, 2, таких, что в моменты t1, t2 наблюдаются поступающие на входные узлы внешние сигналы, а в моменты 1, 2 – наблюдаются выходные сигналы устройства. При этом предполагается, что устройство имеет функцию перехода.

Эта функция однозначно определяется по входному сигналу и состоянию устройства и описывается уравнением (2.3) во времена t1, t2, …. Выходные сигналы устройства определяются во времени 1, 2, …, которые определятся соотношениями: tn s s+1…s+l tn+1, и однозначно определяются по входному сигналу и состоянию устройства в момент времени tn.

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



Pages:   || 2 | 3 | 4 | 5 |   ...   | 6 |
 

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

«Г.М. Федоров, В.С. Корнеевец БАЛТИЙСКИЙ РЕГИОН Калининград 1999 Г.М. Федоров, В.С. Корнеевец БАЛТИЙСКИЙ РЕГИОН: СОЦИАЛЬНО-ЭКОНОМИЧЕСКОЕ РАЗВИТИЕ И СОТРУДНИЧЕСТВО Калининград 1999 УДК 911.3:339 (470.26) Федоров Г.М., Корнеевец В.С. Балтийский регион: социальноэкономическое развитие и сотрудничество: Монография. Калининград: Янтарный сказ, 1999. - 208 с. - ISBN Книга посвящена социально-экономическому развитию одного из европейских макрорегионов – региона Балтийского моря, на берегах которого...»

«Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Казанский государственный технологический университет В.Я. Пономарев, Э.Ш. Юнусов, Г.О. Ежкова, О.А. Решетник БИОТЕХНОЛОГИЧЕСКИЕ ОСНОВЫ ПРИМЕНЕНИЯ ПРЕПАРАТОВ МИКРОБИОЛОГИЧЕСКОГО СИНТЕЗА ДЛЯ ОБРАБОТКИ МЯСНОГО СЫРЬЯ С ПОНИЖЕННЫМИ ФУНКЦИОНАЛЬНО-ТЕХНОЛОГИЧЕСКИМИ СВОЙСТВАМИ Монография Казань, 2009 УДК 664 ББК Пономарев В.Я. Биотехнологические основы применения препаратов...»

«В. И. Соловьев СТРАТЕГИЯ И ТАКТИКА КОНКУРЕНЦИИ НА РЫНКЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ Опыт экономико-математического моделирования i Москва 2010 УДК 330.115 ББК 65 С60 Работа поддержана грантом Президента Российской Федерации для государственной поддержки молодых российских ученых МК 3663.2009.6 Р е ц е н з е н т ы: заместитель заведующего кафедрой экономики знаний Государственного университета управления, доктор экономических наук, кандидат физико математических наук, профессор Т. М. Гатауллин;...»

«Н.Н. Васягина СУБЪЕКТНОЕ СТАНОВЛЕНИЕ МАТЕРИ В СОВРЕМЕННОМ СОЦИОКУЛЬТУРНОМ ПРОСТРАНСТВЕ РОССИИ Екатеринбург – 2013 УДК 159.9 (021) ББК Ю 956 В20 Рекомендовано Ученым Советом федерального государственного бюджетного образовательного учреждения высшего профессионального огбразования Уральский государственный педагогический университет в качестве монографии (Решение №216 от 04.02.2013) Рецензенты: доктор педагогических наук, профессор, Л.В. Моисеева доктор психологических наук, профессор Е.С....»

«Ермоленко Татьяна Федоровна Морозова Ольга Михайловна ПОГОНЫ И БУДЕНОВКИ: ГРАЖДАНСКАЯ ВОЙНА ГЛАЗАМИ БЕЛЫХ ОФИЦЕРОВ И КРАСНОАРМЕЙЦЕВ 2 УДК 355.292:316.66(47+57)“1917/1920”(092) Издание осуществлено при финансовой поддержке Российского гуманитарного научного фонда (РГНФ) Ермоленко, Т.Ф., Морозова, О. М. Погоны и буденовки: Гражданская война глазами белых офицеров и красноармейцев / Т. Ф. Ермоленко, О. М. Морозова. – _. – 356 с. ISBN Монография посвящена феномену гражданского милитаризма и...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСТИТЕТ ЭКОНОМИКИ, СТАТИСТИКИ И ИНФОРМАТИКИ (МЭСИ) КАФЕДРА УПРАВЛЕНИЯ ЧЕЛОВЕЧЕСКИМИ РЕСУРСАМИ КОЛЛЕКТИВНАЯ МОНОГРАФИЯ ИННОВАЦИОННЫЕ ТЕХНОЛОГИИ УПРАВЛЕНИЯ ЧЕЛОВЕЧЕСКИМИ РЕСУРСАМИ Москва, 2012 1 УДК 65.014 ББК 65.290-2 И 665 ИННОВАЦИОННЫЕ ТЕХНОЛОГИИ УПРАВЛЕНИЯ ЧЕЛОВЕЧЕСКИМИ РЕСУРСАМИ: коллективная монография / Под редакцией к.э.н. А.А. Корсаковой, д.с.н. Е.С. Яхонтовой. – М.: МЭСИ, 2012. – С. 230. В книге...»

«В.М. Фокин ТЕПЛОГЕНЕРАТОРЫ КОТЕЛЬНЫХ МОСКВА ИЗДАТЕЛЬСТВО МАШИНОСТРОЕНИЕ-1 2005 В.М. Фокин ТЕПЛОГЕНЕРАТОРЫ КОТЕЛЬНЫХ МОСКВА ИЗДАТЕЛЬСТВО МАШИНОСТРОЕНИЕ-1 2005 УДК 621.182 ББК 31.361 Ф75 Рецензент Доктор технических наук, профессор Волгоградского государственного технического университета В.И. Игонин Фокин В.М. Ф75 Теплогенераторы котельных. М.: Издательство Машиностроение-1, 2005. 160 с. Рассмотрены вопросы устройства и работы паровых и водогрейных теплогенераторов. Приведен обзор топочных и...»

«Министерство образования и науки Российской Федерации Ярославский государственный университет им. П.Г. Демидова КРЕАТИВНОСТЬ КАК КЛЮЧЕВАЯ КОМПЕТЕНТНОСТЬ ПЕДАГОГА МОНОГРАФИЯ Ярославль 2013 УДК 159.922 ББК 88.40 К 79 Работа выполнена при финансовой поддержке РГНФ, проект №11-06-00739а Рецензенты: доктор психологических наук, профессор, главный научный сотрудник Института психологии РАН Знаков Виктор Владимирович; доктор психологических наук, профессор, председатель Российского отделения...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ МЕЖРЕГИОНАЛЬНЫЙ ИНСТИТУТ ОБЩЕСТВЕННЫХ НАУК МЕТОДОЛОГИЧЕСКИЙ СИНТЕЗ: ПРОШЛОЕ, НАСТОЯЩЕЕ, ВОЗМОЖНЫЕ ПЕРСПЕКТИВЫ ИЗДАТЕЛЬСТВО ТОМСКОГО УНИВЕРСИТЕТА 2002 УДК 930.2 ББК 63 М 54 Методологический синтез: прошлое, настоящее, возможМ 54 ные перспективы / Под ред. Б.Г. Могильницкого, И.Ю. Николаевой. – Томск: Изд-во Том. ун-та, 2002. – 204 с. ISBN 5-7511-1556-2 Предлагаемая монография является опытом обобщения материалов...»

«СОВРЕМЕННАЯ ГУМАНИТАРНАЯ АКАДЕМИЯ ИНСТИТУТ МЕЖДУНАРОДНОЙ ТОРГОВЛИ И ПРАВА М.Ф. СЕКАЧ ПСИХИЧЕСКАЯ УСТОЙЧИВОСТЬ ЧЕЛОВЕКА Монография Москва 2013 УДК 159.9 ББК 88.52 Секач М.Ф. Психическая устойчивость человека: Монография. – М.: АПКиППРО, 2013. – 356 с. Рецензенты: Кандыбович Сергей Львович, Заслуженный деятель науки РФ, лауреат премии Правительства РФ в области образования, лауреат премии Правительства РФ в области науки и техники, лауреат Государственной премии РФ им. Маршала Советского Союза...»

«В. К. Федюкин РЕШЕНИЕ ПРОБЛЕМЫ СВЕРХПРОВОДИМОСТИ ЭЛЕКТРИЧЕСКОГО ТОКА И СВЕРХДИАМАГНЕТИЗМА Санкт-Петербург 2011 УДК 338.945:530.1 ББК 31.232я73 Ф32 Рецензенты: – кафедра Управления качеством и машиноведения СПбГИЭУ, д.э.н., проф. В.П. Семенов, – д-р физ.-мат. наук, проф. С.А. Атрошенко – ведущий научный сотрудник СПб. института проблем машиноведения РАН, – канд. физ-мат. наук, проф. СПб. гос. политехн. ун-та Д.П. Иванов Одобрено к изданию научно-техническим советом СПбГИЭУ Федюкин В. К. Решение...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОУ ВПО ИРКУТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Е. И. Кулябина СОВЕРШЕНСТВОВАНИЕ ИННОВАЦИОННОЙ ДЕЯТЕЛЬНОСТИ ВУЗОВ Монография УДК 378:001.895 ББК 74.58 К90 Печатается по решению редакционно-издательского совета Иркутского государственного университета Рецензенты: д-р экон. наук, проф. Т. Г. Озерникова (БГУЭП) канд. экон., наук, доц. В. П. Чебунин (ИГУ) Кулябина Е. И. К90 Совершенствование инновационной деятельности вузов : монография / Е. И. Кулябина. – Иркутск...»

«И.М.Айтуганов ЮА.Дьячков E.А.Корчагин Е.Л.Матухин Р.С.Сафин Т.В.Сучкова НАУЧНЫЕ ОСНОВЫ ВЗАИМОСВЯЗИ ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ И ПРОИЗВОДСТВА Монография 2009 РОССИЙСКАЯ АКАДЕМИЯ ОБРАЗОВАНИЯ Институт педагогики и психологии профессионального образования Лаборатория специальной и практической подготовки ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ АРХИТЕКТУРНО-СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ И.М.Айтуганов, Ю.А.Дьячков, Е.А.Корчагин, Е.Л.Матухин, Р.С.Сафин, Т.В.Сучкова НАУЧНЫЕ ОСНОВЫ...»

«С.С. САВЕЛЬЕВА ПЕДАГОГИЧЕСКИЕ УСЛОВИЯ ФОРМИРОВАНИЯ ПРОФЕССИОНАЛЬНОЙ КОМПЕТЕНТНОСТИ УЧИТЕЛЯ В ОБРАЗОВАТЕЛЬНОМ ПРОЦЕССЕ ВУЗА МОНОГРАФИЯ КОЛОМНА 2012 С.С. Савельева ПЕДАГОГИЧЕСКИЕ УСЛОВИЯ ФОРМИРОВАНИЯ ПРОФЕССИОНАЛЬНОЙ КОМПЕТЕНТНОСТИ УЧИТЕЛЯ В ОБРАЗОВАТЕЛЬНОМ ПРОЦЕССЕ ВУЗА МОНОГРАФИЯ КОЛОМНА С УДК 378. ББК 74. Рецензенты: С.А. Ермолаева доктор педагогических наук, профессор, зав. каф. педагогики ГОУ ВПО МГОСГИ И.П. Куревлёва кандидат...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ИРКУТСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Г.Н. Кичигин, Н.А. Строкин Процессы энерговыделения в космической плазме УДК 533.9.55; 523.165; 621.039.64 Рецензент: доктор физ.-мат. наук, профессор Иркутского государственного университета путей сообщения В.М. Бардаков Редактор издательства Г.Н. Романова Кичигин Г.Н., Строкин Н.А. Процессы энерговыделения в космической плазме: Монография. – Иркутск: Изд-во ИрГТУ, 2007. - 396 с. В монографии излагаются...»

«Т.В. Матвеева С.Я. Корячкина МУЧНЫЕ КОНДИТЕРСКИЕ ИЗДЕЛИЯ ФУНКЦИОНАЛЬНОГО НАЗНАЧЕНИЯ НАУЧНЫЕ ОСНОВЫ, ТЕХНОЛОГИИ, РЕЦЕПТУРЫ МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ – УЧЕБНО-НАУЧНО-ПРОИЗВОДСТВЕННЫЙ КОМПЛЕКС Т.В. Матвеева, С.Я. Корячкина МУЧНЫЕ КОНДИТЕРСКИЕ ИЗДЕЛИЯ ФУНКЦИОНАЛЬНОГО НАЗНАЧЕНИЯ НАУЧНЫЕ ОСНОВЫ, ТЕХНОЛОГИИ, РЕЦЕПТУРЫ Орел УДК 664.68.022. ББК 36. М...»

«Министерство природных ресурсов и экологии Чувашской Республики Федеральное государственное учреждение Государственный природный заповедник Присурский ДОКЛАД Об охране окружающей среды Чувашской Республики в 2009 году Чебоксары 2010 УДК 502/504 ББК 20.1 Д 63 Редакционная коллегия: Краснов В.И., Юшин Е.В., Понятова Т.И., к.б.н. Димитриев А.В., Запасова М.Л., Волжанина М.В. Авторы-составители Доклада: Понятова Т.И., Запасова М.Л., к.б.н. Димитриев А.В. Авторы: Андреева И.И., к.г.-м.н. Васильев...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ИРКУТСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ В.Н. ШИХИРИН, В.Ф. ИОНОВА, О.В. ШАЛЬНЕВ, В.И. КОТЛЯРЕНКО ЭЛАСТИЧНЫЕ МЕХАНИЗМЫ И КОНСТРУКЦИИ Монография ИЗДАТЕЛЬСТВО Иркутского государственного технического университета 2006 УДК 621.8+624.074: 539.37 ББК 22.251 Ш 65 Шихирин В.Н., Ионова В.Ф., Шальнев О.В., Котляренко В.И. Ш 65 Эластичные механизмы и конструкции. Монография. – Иркутск: Изд-во ИрГТУ, 2006. – 286 с. Книга может быть полезна студентам,...»

«Российская академия наук Уральское отделение Ильменский государственный заповедник Г.В. Губко Ильменский государственный заповедник УрО РАН. Анализ эффективности управления. Миасс 2005 г. ББК 65.050.9(2) Губко Г.В. Ильменский государственный заповедник УрО РАН. Анализ эффективности управления. Миасс: “Геотур”, 2005г. - с. Монография посвящена анализу механизмов управления Ильменским государственным заповедником УрО РАН (ИГЗ), как активной социально-экономической системой. В издании...»

«ИНСТИТУТ ПРОБЛЕМ ОСВОЕНИЯ СЕВЕРА СИБИРСКОГО ОТДЕЛЕНИЯ РОССИЙСКОЙ АКАДЕМИИ НАУК Н. М. Добрынин ФЕДЕРАЛИЗМ ИСТОРИКО-МЕТОДОЛОГИЧЕСКИЕ АСПЕКТЫ Новосибирск Наука 2005 1 УДК 342.1/.3 ББК 67.400 Д57 Рецензенты доктор юридических наук, профессор, заслуженный деятель науки Российской Федерации С. А. Авакьян член-корреспондент РАН, доктор юридических наук, профессор Д. А. Керимов доктор юридических наук, профессор А. Н. Кокотов доктор юридических наук, профессор, заслуженный деятель науки Российской...»





 
© 2013 www.diss.seluk.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Методички, учебные программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.