Теория автоматовКомпанія, що виробляє та реалізує деякий товар, планує одержати такі результати на кінець поточного року:
Фінансові плани тепер готують на рік вперед. Є така інформація: 9. Очікують, що зменшення ціни реалізації з 11 до 10 грн. приведе до збільшення обсягу реалізації на 50%; 10. Обсяг закупівель матеріалів зросте, отже, буде 5% знижка на закупівлю сировини. Очікують, що використання матеріалів на од. випуску продукції становитиме 98% порівняно з поточним роком; 11. Погодинні ставки заробітної плати основних працівників збільшаться на 10%. Продуктивність праці залишається на тому ж рівні. 20000 од. продукції будуть виробляти у понаднормові години з надбавкою в обсязі 25%. Доплати за понаднормові години розглядають як прямі витрати; 12. Очікують, що сукупні змінні накладні витрати на реалізацію збільшаться пропорційно сукупним доходам від реалізації; 13. Змінні виробничі накладні витрати й накладні витрати на організацію збуту повинні збільшитися в цілому пропорційно до збільшення обсягів реалізації; 14. Згідно з прогнозом постійні накладні витрати зростуть на 20% порівняно з поточним роком; 15. Місячне виробництво буде заплановано таким чином, що запаси готової продукції на кінець місяця будуть достатні для забезпечення прогнозованого попиту на наступні півтора місяці; 16. Матеріали будуть закуповувати з розрахунком, що їх залишків буде достатньо для забезпечення виробничих потреб у подальшому.
Передбачають, що: 3. ціни та виробництво залишаться на одному рівні протягом поточного року; 4. запаси матеріалів та готової продукції на кінець поточного року задовольняють умови пп. 7, 8, застосованих до наступного року, тобто залишків сировини буде достатньо для забезпечення виробничих потреб у першому місяці нового року. А. Підготуйте план очікуваних прибутків на наступний рік. Б. Розрахуйте та порівняйте точки беззбитковості для цих двох років.
Теория автоматов Конечный автомат "в чистом виде" - это математическая модель устройства с конечной памятью, преобразующего дискретную информацию. Конечный автомат является одним из важнейших видов управляющих систем. Содержательно конечный автомат можно охарактеризовать как устройство, имеющее входной и выходной каналы и находящееся в каждый из моментов дискретного времени, называемых тактовыми моментами, в одном из состояний. По входному каналу в каждый тактовый момент в устройство поступают сигналы a - буквы входного алфавита A; в те же моменты по выходному каналу устройство выдает сигналы b - буквы выходного алфавита B, причем b определяется состоянием s из алфавита состояний S и буквой a; внутреннее состояние s' в следующий тактовый момент также определяется состоянием s и буквой a из предыдущего момента. Таким образом, для некоторых функций j и f имеет место b = j (a, s), s' = f (a, s); эти функции называются соответственно выходной и переходной функциями; они определяют закон ╚ переработки╩ слов в алфавите A, подаваемых побуквенно на входной канал устройства при условии задания начального состояния устройства. Для конечных автоматов предполагается конечность алфавитов A, S, B. Если считать указанную ╚переработку╩ слов главной характеристикой устройства, то его можно отождествить с набором (A, S, B, j, f), который и называют конечным автоматом. Для этой формы описания конечного автомата характерно отношение исследователя к устройству как внешнего наблюдателя. Само задание конечного автомата называется при этом абстрактным конечным автоматом. В случае когда устройство рассматривается с учетом того, что оно собрано по некоторым композиционным правилам из абстрактных конечных автоматов, приходят к понятию структурного конечного автомата, который в итоге также реализует некоторый абстрактный конечный автомат. Автомат "вообще" (от греческого automat oz - самодействующий) - управляющая система, являющаяся конечным автоматом или некоторой его модификацией, полученной путем изменения его компонент или функционирования. Основное понятие - конечный автомат - возникло в середине 20 века в связи с попытками описать на математическом языке функционирование нервных систем, универсальных вычислительных машин и других реальных автоматов. Характерной особенностью такого описания является дискретность соответствующих математических моделей и конечность областей значений их параметров, что приводит к понятию конечного автомата. Наряду с понятием конечного автомата рассматриваются различные его обобщения и модификации, отражающие те или иные особенности реальных устройств. Для конечного автомата (A, S, B, j, f) существующие модификации можно разбить на следующие три основные группы. К первой группе относятся автоматы, у которых некоторые из алфавитов A (входной), S (состояний) или B (выходной) бесконечны, в связи с чем такие автоматы называются бесконечными. Ко второй группе относятся автоматы, у которых вместо выходной и переходной функций j и f допускаются произвольные отношения или случайные функции. Таковы частичные, недетерминированные, вероятностные и другие автоматы. К третьей группе относятся автоматы со специфическими множествами входных объектов. Таковы, например, автоматы с переменной структурой. Существуют автоматы, принадлежащие одновременно разным группам. Наряду с этим большую роль играют специальные подклассы конечных автоматов, например, автоматы без памяти. Кроме того, использование понятий и методов из других разделов математики также приводит к появлению специфических классов автоматов и связанных с ними задач. Например, при применении алгебраических средств возникают понятия автоматов над термами, линейного, группового, свободного и других; вопросы теории кодирования порождают понятия самонастраивающихся, обратимых автоматов и другие. Теория автоматов - это раздел теории управляющих систем, изучающий математические модели преобразователей дискретной информации, называемые автоматами. С определенной точки зрения такими преобразователями являются как реальные устройства (вычислительные машины, автоматы, живые организмы и т.д.), так и абстрактные системы (например, формальная система, аксиоматические теории и т.д.). Наиболее тесно теория автоматов связана с теорией алгоритмов. Большинство задач теории автоматов - общие для основных видов управляющих систем. К ним относятся задачи анализа и синтеза автоматов, задачи полноты, минимизации, эквивалентных преобразований автоматов и другие. Задача анализа состоит в том, чтобы по заданному автомату описать его поведение или по неполным данным об автомате и его функционированию установить те или иные его свойства. Задача синтеза автоматов состоит в построении автомата с наперед заданным поведением или функционированием. Задача полноты состоит в выяснении, обладает ли множество M' Í M автоматов свойством полноты, т.е. совпадает ли с M множество всех автоматов, которые получаются путем конечного числа применений некоторых операций к автоматам из заданного подмножества автоматов M'. Задача эквивалентных преобразований в общем виде состоит в том, чтобы найти систему правил преобразований (так называемую полную систему правил) автоматов, которые удовлетворяют определенным условиям и позволяют преобразовать произвольный автомат в любой эквивалентный ему автомат (два автомата эквивалентны, если они имеют одинаковое поведение автомата. Поведение автомата - математическое понятие, описывающее взаимодействие автомата с внешней средой. Примером внешней среды конечного автомата является множество входных слов, а поведением - словарная функция, реализуемая автоматом, или событие, представимое автоматом.) Помимо перечисленных, в теории автоматов имеются специфические проблемы, характерные для автоматов. Так, в зависимости от условий задачи поведение автомата удобно задавать на разных языках, в связи с чем важными задачами являются выбор достаточно удобного адекватного языка и перевод с одного языка на другой. В тесной связи с задачами синтеза и эквивалентных преобразований находится задача минимизации числа состояний автомата, а также получение соответствующих оценок. Близкий круг вопросов возникает в связи с моделированием поведения автоматов одного класса автоматами другого класса. Здесь также представляют интерес вопросы минимизации моделирующих автоматов и оценки их сложности. Специальный раздел теории автоматов связан с так называемыми экспериментами с автоматами (т.е. способами получения информации о внутренней структуре автоматов по их поведению). Основная задача здесь состоит в том, чтобы получить определенные сведения о строении автомата путем наблюдения его реакции на те или иные внешние воздействия. При этом возникает большой круг задач, связанный с классификацией экспериментов и с вопросами разрешимости задач определенными видами экспериментов, а также с оценками длин минимальных экспериментов, достаточных для решения тех или иных задач. Понятие эксперимента с автоматами используется также в задачах надежности и контроля управляющих систем, в частности контроля автоматов. Многие из перечисленных выше задач могут рассматриваться как алгоритмические проблемы. Для конечных автоматов большинство из них имеют положительное решение. Теория автоматов находит применение как и в других областях математики, так и в решении практических задач. Например, средствами теории автоматов доказывается разрешимость некоторых формальных исчислений. Применение методов и понятий теории автоматов к изучению формальных и естественных языков привело к возникновению математической лингвистики (математическая лингвистика - математическая дисциплина, предметом которой является разработка формального аппарата для описания строения естественных и некоторых искусственных языков.) Понятие автомата может служить модельным объектом в самых разнообразных задачах, благодаря чему возможно применение теории автоматов в различных научных и прикладных исследованиях. Пример 1. Рассмотрим следующий конкретный конечный автомат M = [ A, S, B, j, f]. Входной алфавит A = {0, 1}; выходной алфавит B = {0, 1}; три внутренних состояния S = { s 0, s 1, s 2}; функции выхода и перехода задаются предписаниями j: (s 0, 0) a s 1 f: (s 0, 0) a 0 (s 0, 1) a s 0 (s 0, 1) a 1 (s 1, 0) a s 2 (s 1, 0) a 1 (s 1, 1) a s 1 (s 1, 1) a 0 (s 2, 0) a s 0 (s 2, 0) a 1 (s 2, 1) a s 2 (s 2, 1) a 0 Подадим на вход последовательность 0, 1, 0, 1. Если автомат находился сначала в состоянии s 0, то, считав первый символ 0, он перейдет в состояние s 1 и выпечатает 0. Считав затем 1, он останется в состоянии s 1 и выпечатает 0. Считав следующий 0, он перейдет в состояние s 2 и выпечатает 1. Наконец, считав последний символ 1, автомат закончит работу в состоянии s 2, имея на выходной ленте последовательность 0, 0, 1, 0.Таким образом, автомат преобразовал вход 0, 1, 0, 1 (или, короче, 0101) в 0, 0, 1, 0 (или 0010).
Есть два удобных способа описать этот автомат. Прежде всего, можно построить помеченный ориентированный граф, называемый диаграммой состояний. Вершины этого орграфа помечены символами, обозначающими внутренние состояния. Каждая дуга помечена парой символов a, b, где a - входной символ, вызывающий переход в следующее состояние, отвечающее этому ребру, а b - выходной символ, который автомат выпечатывает. Второй способ описания - таблица состояний, табличное представление функций j и f.
Автомат считывает входную последовательность из нулей и единиц, и его состояние в любой момент времени совпадает с начальным, скажем, s0, если число считанных к этому моменту единиц четно, и равно s1, если число считанных единиц нечетно. Выходная последовательность совпадает с входной.
Считав Q, автомат выпечатывает EVEN, если число ранее считанных единиц было четно, и ODD - если нечетно. Например, входная последовательность 0110 Q 1110 Q будет переработана в 0110 EVEN1110 ODD.
|
Оба способа имеют свои преимущества и недостатки. Таблица обычно удобнее при вычислениях, диаграмма нагляднее. Например, по диаграмме легче обнаружить состояния, не достижимые из других состояний. На следующем рисунке показана диаграмма состояний автомата, у которого состояние s1 недостижимо, если автомат начинает работу из состояния s0 или s2.
Пример 2. Автомат с двумя состояниями, изображенный на следующем рисунке - автомат для проверки четности.
Пример 3. Автомат, изображенный ниже, проверяет четность и выпечатывает EVEN (четный) или ODD (нечетный) в ответ на запрос, который соответствует входному символу Q.
