- •Раздел 1. Алгебраические структуры Тема 1.1. Бинарные операции и их свойства
- •Тема 1.2. Алгебраические структуры
- •Тема 1.3. Основные свойства групп
- •Тема 1.4. Поля и кольца
- •Раздел 2. Алгебра множеств Тема 2.1. Основные определения теории множеств
- •Тема 2.2. Подмножество, понятие универсального множества
- •Тема 2.3. Операции над множествами
- •Раздел 3. Основные теоремы комбинаторики
- •Тема 3.1. Метод математической индукции
- •Тема 3.2. Основные принципы комбинаторики
- •Раздел 4. Комбинаторные объекты Тема 4.1. Сочетания
- •Тема 4.2. Размещения и перестановки
- •Раздел 5. Полиномиальные тождества Тема 5.1. Бином Ньютона
- •Тема 5.2. Понятие о методе рекуррентных соотношений
- •Тема 5.3. Метод производящих функций
- •Тема 5.4. Метод траекторий
- •Тема 5.5. Примеры комбинаторных задач
- •Раздел 6. Соответствие, отношение, отображение Тема 6.1. Понятие кортежа. Декартово произведение множеств
- •Тема 6.2. Определения и свойства
- •Тема 6.3. Типы отношений
- •Пересечение и объединение отношений
- •Композиция отображений и отношений
- •Тема 6.5. Решётки
- •Тема 6.4. Верхняя и нижняя границы множества.
- •Раздел 7. Операции булевой алгебры Тема 7.1.Понятие высказывания, простые и составные высказывания
- •Тема 7.2.Операции на множестве высказываний
- •Отрицание
- •Конъюнкция
- •Дизъюнкция
- •«Исключающее или»
- •Импликация
- •Эквивалентность
- •Штрих Шеффера
- •Раздел 8. Законы и тождества Булевой алгебры Тема 8.1.Формулы Булевой алгебры
- •Тема 8.2.Законы и тождества Булевой алгебры
- •Тема 8.3.Составление формулы по заданной таблице истинности
- •Тема 8.4. Двойственность
- •Тема 8.5.Булева алгебра и теория множеств
- •Тема 8.6.Днф, интервалы и покрытия
- •Раздел 9. Функциональная полнота. Алгебра Жегалкина
- •Тема 9.1.Функционально полные системы
- •Тема 9.2.Алгебра Жегалкина и линейные функции
- •Тема 9.3.Замкнутые классы. Монотонные функции
- •Тема 9.4.Теоремы о функциональной полноте
- •Раздел 10. Хорновские формулы
- •Тема 10.1.Задача получения продукции
- •Тема 10.2.Решение задачи о продукции
- •Алгоритм замыкание(X,f)
- •Алгоритм ПрямаяВолна(X,y,f)
- •Алгоритм БыстроеЗамыкание(X,f)
- •Раздел 11. Теория релейно-контактных схем Тема 11.1.Основные понятия
- •Тема 11.2.Основные задачи теории релейно-контактных схем
- •Тема 11.3.Построение машины голосования
- •Тема 11.4.Двоичный сумматор
- •Тема 11.5.Методы упрощения логических выражений. Методы решения логических задач
- •Раздел 12. Логика предикатов Тема 12.1.Определение предиката
- •Тема 12.2.Логические операции над предикатами
- •Тема 12.3.Кванторы
- •Тема 12.4. Истинные формулы и эквивалентные соотношения
- •Тема 12.5.Доказательства в логике предикатов
- •Раздел 13. Теория графов
- •Тема 13.1.Основные определения теории графов
- •Тема 13.2. Способы задания графов
- •Тема 13.3. Отношения порядка и эквивалентности на графе
- •Тема 13.4. Числовые характеристики графа
- •Тема 13.5.Изоморфизм графов
- •Раздел 14. Проблемы достижимости на графах Тема 14.1.Граф достижимости
- •Тема 14.2.Взаимная достижимость, компоненты сильной связности и базы графа
- •Раздел 15. Некоторые классы графов Тема 15.1.Деревья
- •Тема 15.2. Обход графа
- •Тема 15.3. Расстояния. Диаметр, радиус и центр графа. Протяжённости.
- •Раздел 16. Машина Тьюринга
- •Тема 16.1. Формальное описание машины Тьюринга
- •Тема 16.2. Примеры построения машины Тьюринга
- •Тема 16.3. Свойства машины Тьюринга как алгоритма
- •Раздел 17. Машина Поста
- •Тема 17.1. Теоретическая часть. Состав машины Поста
- •Тема 17.2. Применимость программ. Определение результата выполнения программ
- •Раздел 18. Основные понятия теории автоматов Тема 18.1. Общие подходы к описанию устройств, предназначенных для обработки дискретной информации
- •Тема 18.2. Способы задания конечного автомата
- •Тема 18.3. Эквивалентные автоматы
- •Тема 18.4. Автоматы Мура и Мили
- •Тема 18.5. Примеры синтеза автоматов
Раздел 18. Основные понятия теории автоматов Тема 18.1. Общие подходы к описанию устройств, предназначенных для обработки дискретной информации
Обычно автоматом называют устройство, выполняющее без непосредственного участия человека определённую последовательность операций, в результате которой происходит преобразование материальных объектов, энергии или информации. Когда говорится «без участия человека», то подразумевается отсутствие явного управления со стороны человека в ходе выполнения операций. Однако на самом деле управление осуществляется, но опосредованно, через программу, составленную предварительно человеком и заложенную в устройство. В дальнейшем мы ограничим себя обсуждением лишь тех устройств, которые предназначены для автоматического преобразования информации, представленной в дискретной форме.
Поскольку устройство обменивается информацией с внешней средой, очевидно, оно должно обладать входным каналом, по которому информация поступает в него, а также выходным каналом, через который выдаётся результат преобразования. Помимо этого, устройство может обладать памятью, в которой фиксируется его текущее состояние; результат обработки в общем случае определяется входными воздействиями и внутренним состоянием устройства. Будем считать, что для представления входной информации используется некоторый конечный алфавит (входной алфавит), а для представления выходной – конечный алфавит(выходной алфавит). Требование конечности алфавитов является следствием конечности времени обработки информации. Внутренние состояния устройства также образуют дискретный набор, который можно считать внутренним алфавитом – обозначим его. Что касается числа различных внутренних состояний, то пока не будем делать относительно его никаких предположений.
Будем считать также, что поступление входных символов и переключение состояний устройства происходят не непрерывно, а в определённые моменты времени, т.е. дискретно. Если последовательность моментов произвольна, то говорят об асинхронной организации работы элементов устройства, например, набор номера телефона или кода замка. Однако в сложных устройствах чаще используется синхронная организация, при которой моменты поступления и выхода сигналов, а также переключения внутренних состояний следуют друг за другом через один и тот же фиксированный промежуток времени , называемый тактом. Эти моменты задаются с помощью специального устройства – тактового генератора (или генератора синхроимпульсов). Число тактовых импульсов за единицу времени называется тактовой частотой – она является одним из важнейших факторов, определяющих быстродействие устройства. Можно ввести моменты времени,,,…, обозначающие границы тактов (соответствует моменту начала работы). При этом можно считать, что события, относящиеся к такту– поступление входного символа, изменение внутреннего состояния, формирование и выдача выходного символа – проистекают мгновенно в момент.
Устройства, у которых дискретны множества внутренних состояний, входных и выходных сигналов, а также множество моментов времени, в которые поступают входные сигналы, меняются внутренние состояния и выдаются выходные сигналы, называются дискретными.
Примерами дискретных устройств являются наборный диск телефона, кодовый замок, калькулятор, электронные табло и, безусловно, компьютер. По назначению устройства можно объединить в три группы:
информационные – справочные автоматы, электронные табло, светофоры, устройства аварийной сигнализации и пр.;
управляющие – кодовый замок, устройство управления лифтом, станки с программным управлением, микропроцессоры фотоаппарата, видео пр.;
вычислительные – микрокалькулятор, микропроцессоры компьютеров.
Существуют устройства, осуществляющие деятельность всех трёх видов, например, компьютер, автопилот и др.
Для наших рассуждений существенным оказывается то обстоятельство, что символы на выходе и внутренние состояния такого устройства оказываются дискретными функциями входных символов и номеров тактов работы. Введём понятие функции переходов , которая будет связывать внутреннее состояние устройства на последующем такте с состоянием и входным символом на текущем такте:
Другими словами, функция переходов показывает, в какое состояние из всех возможныхперейдёт дискретное устройство, если оно находилось в состоянии, а на вход поступил символ.
Подобным же образом введём функцию выходов , которая будет связывать внутреннее состояние устройства и входной символ на текущем такте с выходным сигналом на этом же такте:
Следовательно, функция выходов определяет, какой символ образуется на выходе, если на данном такте определён символ на входе и состояние устройства.
Говорят, что пятеркой компонентов задаётся автомат, обеспечивающий преобразование по определённым правилам последовательностей символов входного алфавита в выходную последовательность. Действительно, если принять начальное условие, то рекуррентные соотношенияиопределят порядок преобразования конечной последовательности входных символов,, …,в некоторую последовательность выходных символов той же длины,, …,; при этом будет возникать определённая последовательность внутренних состояний. В этом и заключается функционирование автомата. Выходной символ, вырабатываемый автоматом на некотором такте, зависит не только от входного символа, воспринятого на этом же такте, но и от символов, поступивших ранее – они фиксируются в автомате путём изменения его внутреннего состояния. В этом смысле множество внутренних состояний автомата является его внутренней памятью. В зависимости от объёма этой памяти выделяются следующие типы автоматов:
без памяти;
с конечной памятью;
с бесконечной памятью.
Забегая несколько вперед, скажем, что автомат с конечной памятью называется конечным автоматом. Отметим также, что функции переходов и выходов имеют обобщающее название автоматные функции.
Что касается дискретных устройств с бесконечной памятью – это чисто модельное теоретическое представление, поскольку никакие реальные устройства бесконечной памятью обладать не могут. Примером автомата с бесконечной памятью может служить уже известная нам машина Тьюринга, в которой, роль памяти выполняет бесконечная (или при необходимости наращиваемая) в обе стороны бумажная лента. Таким образом, можно считать, что автоматом с бесконечной памятью является алгоритм, представленный в форме машины Тьюринга.
В реальных дискретных устройствах сигналы и их преобразования могут иметь различную физическую природу (электрическую, механическую, пневматическую и пр.). Однако от этой природы можно отвлечься и изучать только общие законы построения автоматов и правила, определяющие преобразование информации ими. Такие автоматы называются абстрактными. В теории абстрактных автоматов решаются несколько групп проблем:
во-первых, выясняется, какие преобразования возможны в автомате, как их описать, как выполняемые преобразования связаны с числом состояний (т.е. сложностью) автомата, существуют ли неразрешимые автоматом задачи;
во-вторых, исследуются эквивалентные преобразования автоматов; задача эквивалентного преобразования состоит в построении автомата эквивалентного данному, но имеющего иное количество состояний (обычно, меньшее);
в-третьих, рассматривается круг вопросов, в которых определяется строение автомата по характеру и соотношению входных и выходных сигналов (автомат – «чёрный ящик») – это важная прикладная задача технической диагностики устройств, без которой невозможна их практическая эксплуатация;
в-четвёртых, выделяются структурных элементов автоматов и определяются правил построения из них сложных устройств (задача синтеза автоматов) – с этим связана разработка новых автоматов, в частности, компьютеров.
Важным для практики частным случаем являются автоматы, в которых вся информация представлена с помощью двоичного кода, т.е. алфавиты ,иявляются двоичными – такие автоматы называют двоичными или логическими. Последнее название обусловлено тем, что, как показывает теория, при двоичном кодировании любой конечный автомат можно представить в виде комбинации некоторого числа элементов, реализующих логические операции И, ИЛИ, НЕ, а также элементы памяти (задержка и триггер). Объединение элементов называется логической схемой. Важными представляются два обстоятельства: во-первых, работу логических схем можно описать законами и правилами математической логики (т.е. результат действия логической схемы сводится к вычислению значения логического выражения); во-вторых, из данного небольшого набора элементов можно построить любой конечный автомат.
Введённое понятие автомата является достаточно общим. Накладывая ограничения на компоненты ,,,,можно получить частные случаи автоматов. Одним из них являются автоматы без памяти, т.е. устройства, в которых не происходит фиксации внутреннего состояния. Очевидно, в этом случае из общего описания должны быть исключены компонентыи; автомат без памяти задаётся тройкой компонентов. Тогдат.е. выходной символ на данном такте определяется только входным символом и не зависит от ранее поступивших символов. Следовательно, каждый автомат без памяти реализует единственный преобразователь (оператор), который осуществляет «побуквенный перевод» входных последовательностей символов в выходные.
Пусть имеется дискретное устройство, имеющее входов, …,ивыходов, …,. Если данное устройство не обладает памятью, то преобразование входных сигналов в выходные описывается системой уравнений:
Если входной и выходной алфавит являются двоичными, то представленная система оказывается системой логических функций, для решения которой можно привлечь аппарат математической логики. Именно такие устройства будем рассматривать в дальнейшем.
Подобные устройства могут быть построены путём соединения некоторого набора элементарных компонентов (элементов). Эти элементы образуют конечный набор, называемый базисом, а входящие в него элементы – базисными. Базис имеет смысл совокупности элементарных (простейших) действий, а базисный элемент можно рассматривать в качестве устройства, выполняющее элементарное действие. Если речь идёт о двоичных дискретных устройствах, то базисы строятся из элементов, которые реализуют простейшие логические функции. В качестве примера такого автомата можно вспомнить полусумматор.