Это делается индукцией по длине α.
Из этой теоремы следует, что при исследовании возможностей автоматов достаточно пользоваться автоматами Мура. Это удобно потому, что автомат Мура можно рассматривать как автомат без выходов, состояния которого различным образом отмечены. Без потери общности можно считать, что этих отметок всего две (например 0 и 1), и они делят состояния на два класса. Зафиксируем один из этих классов и будем называть его состояния заключительными. Это приводит еще к одному определению автомата — автомата без выходов S = (A, Q, q1, F ), где F Q — множество заключительных состояний. Будем далее рассматривать инициальные автоматы без выходов S и с начальным состоянием q1.
Программная реализация логических функций и автоматов
Представление автомата схемой из элементов — это исторически первый и наиболее исследованный вид структурной реализации автомата. Другой ее вид — реализация автомата программой. Здесь мы ограничимся вопросами программной реализации логических функций.
Под программой будем понимать пронумерованную последовательность команд κ1 . . . κs взятых из некоторого фиксированного набора (системы команд). Программа работает над конечным множеством пронумерованных (или проименованных) двоичных ячеек. Номер (или имя) ячейки называется ее адресом; именем ячейки часто будет служить имя логической переменной, значения которой хранятся в этой ячейке.
Система команд содержит команды-операторы вида b := f(a1, . . . , ap) (выполнить операцию f над содержимым ячеек α, . . . , αp и результат положить в ячейку b) и условные двухадресные переходы двух видов:
1.«если α, то i, иначе j» (если α = 1, то перейти к выполнению команды κi, иначе j)
2.« если α(α = 0), то i, иначе j».
•Назад •Первая •Предыдущая •Следующая •Последняя •Перейти •Предметный указатель
Операция f(a1, . . . , ap) — это логическая функция p переменных; в частности, она может быть константой 0 или 1. Если j = i + 1, то переход можно считать одноадресным: «если α, то i (иначе перейти к κi+1)», а если i = j, то безусловным: «перейти к i». Любая из команд указанных типов может быть заключительной, что указывается словом «конец».
Процессом вычислений программы κ1 . . . κs называется последовательность шагов κ(1), κ(2), . . . , κ(t), на каждом из которых выполняется одна команда программы. Эта последовательность определяется так:
1.κ(1) = κ1;
2.если κ(i) = κr — оператор, то κ(i + 1) = κr+1;
3.если κ(i) — условный переход, то номер команды κ(i + 1) указывается этим переходом;
4.если κ(i) — заключительная команда, то процесс вычисления останавливается после ее выполнения. Число T называется временем вычисления.
Программа Π вычисляет логическую функцию f(x1, . . . , xn) = y, если для любого двоичного набора
σ = (σ1, . . . , σn) при начальном состоянии памяти x1 = σ1, x2 = σ2, . . . , xn = σn (состояние остальных ячеек несущественно) программа через конечное число шагов останавливается и при этом в ячейке y
лежит величина f(σ1, . . . , σn) .
Если под сложностью, реализующей автомат, обычно понимается число элементов в схеме, то сложность программы можно понимать в различных смыслах:
1.число команд в тексте программы;
2.объем промежуточной памяти, т.е. число ячеек для хранения промежуточных результатов вычислений;
•Назад •Первая •Предыдущая •Следующая •Последняя •Перейти •Предметный указатель
3. время вычисления, которое будет характеризоваться двумя величинами: средним временем
1 X
tcp(Π) = 2n τp(σ)
σ
и максимальным временем
tmakc(Π) = max τp(σ),
σ
где сумма и максимум берутся по всем 2n двоичным наборам σ, а τp — время работы программы Π на наборе σ.
Любой схеме, реализующей функцию f и содержащей N элементов, нетрудно поставить в соответствие программу, реализующую f и состоящую из N команд, следующим образом. Занумеруем элементы схемы числами 1, 2, . . . , n так, чтобы на любом пути от входа к выходу номера элементов возрастали; при этом номер 1 получит один из входных элементов, а номер N — выходной элемент. Пусть элемент ei схемы реализует функцию ϕi и к его входам присоединены выходы элементов ei1, . . . , ejp (некоторые из них , возможно, являются входами схемы). Поставим элементу ei в соответствие либо ячейку у и ко-
манду αi = ϕi(αj1, . . . , αjp), если i <> N; либо ячейку y и команду «y := ϕN(αj1, . . . , αjp) конец», если i = N. Получим программу, не содержащую условных переходов (такие программы будем называть
операторными), в которой порядок команд в точности соответствует нумерации элементов в схеме, а система команд — базису схемы.
Проблемы синтеза операторных программ в основном сводятся к проблемам синтеза схем: в частности, вопросы функциональной полноты системы команд и минимизации собственного текста операторной программы совпадают соответственно с задачами о функциональной полноте системы функций и о минимизации схем. Поскольку операторная программа не содержит условных переходов, время её
вычисления на любом наборе одно и то же; отсюда tmakc = tcp = N, т.е. оба вида временной сложности совпадают со сложностью текста программы и, следовательно, в силу теоремы !!! 7 − 12 при достаточ-
но больших n почти для всех функций близки к 2nn . Наоборот, проблема минимизации памяти (за счет
•Назад •Первая •Предыдущая •Следующая •Последняя •Перейти •Предметный указатель
многократного использования одной ячейки для нескольких промежуточных результатов) для операторных программ является нетривиальной комбинаторной задачей.
Другой «крайний» вид программы, вычисляющих логические функции — это программа, состоящие из команд вида y := σ(σ = 0 или σ = 1) и условных переходов. Такие программы называются бинарными программами. Всякую булеву формулу F , содержащую N букв, можно реализовать бинарной программой, вычисляющей F за время tmakc = N и содержащей N команд условного перехода (а также две команды y := 0 и y := 1, которые в оценках не учитываются). Для описания метода реализации используем представление программы в виде графа(в котором вершины соответствуют командам, а ребра — переходам). Пусть G1 — граф программы для функции f1 с начальной вершиной ν10 и двумя заключительными вершинами ν10z (с командой «y = 0») и ν11z (с командой «y = 1»); G2 — граф программы для f2 с началом ν20 и концами ν20z и ν21z. Тогда
1.программа, граф G которой получен присоединением G2 к «нулю» G1 (т.е. отождествлением вершин ν10z и ν20; команда «y := 0» при этом отбрасывается), вычисляет функцию f = f1V f2;
2.программа, граф G0 которой получен присоединением G2 к «единице» G1 (отождествлением ν11z и ν20), вычисляет f = f1&f2;
3.программа, граф которой получен из G1 заменой команд в ν10z и ν11z на инверсные («y := 0» на «y := 1» и наоборот) вычисляет f1 . Заметим что в графе G получаются две единичные, а в графе G0 — две нулевые заключительные вершины. В обоих случаях их надо отождествить.
Пример. Формула (x1 x2)(x3x4 x5) реализуется бинарной программой граф которой приведён на рисунке
•Назад •Первая •Предыдущая •Следующая •Последняя •Перейти •Предметный указатель
|
|
_ |
|
|
|
O |
|
|
|
|
|
|
|
|
|
x |
|
_ |
|
|
|
|
2 |
|
x |
5 |
|
|
|
|
|
|||
|
|
|
|
|
||
|
|
|
|
|
|
|
_ |
|
_ |
_ |
|
|
|
x1 |
x2 |
x3 |
x4 |
|
|
x5 |
|
x1 |
x2 |
|
|
x4 |
|
Описанный метод не гарантирует минимальность получаемых программ по времени и числу ко- |
||||||
манд. |
|
|
|
|
|
|
•Назад •Первая •Предыдущая •Следующая •Последняя •Перейти •Предметный указатель |
||||||