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

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

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

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

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

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

о выполнении того или иного действия. Действие совершается, в результате чего изменяется состояние системы, а следовательно, н его описание. Управляющий орган анализирует это новое описание н т. д.

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

И еще два небольших добавления. Первое: описание состояния системы делается на некотором языке. Этот язык может сильно отличаться от того, что мы привыкли понимать под словом язык (например, русский или английский язык). Но если относительно чего-то мы имеем основание утверждать, что это суть описание (состояния системы), то с не меньшим основанием можно утверждать, что такое описание составлено на некотором языке. В дальнейшем мы столкнемся с примерами подобных языков. Второе; каждый раз прн анализе описания состояния системы рассматривается лишь какая-то часть этого описания. К примеру, при выполнении правила 4 (см. рнс. 1.2) анализируется часть описания, касающаяся состояния дверей кабины, н т. д.

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

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

Алфавит - термин, принятый в теории алгоритмов. Этот термин, конечно, отличается от общепринятого понятия алфавита.

Мы предполагаем, что читатель знаком с двоичной системой счисления.

1.3. Символы, сигналы и транзисторы

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

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

Как можно запомнить один из символов-О или 1? Проще всего это сделать с помощью электрического контакта. Приходя вечером домой, вы переводите рычажок выключателя, и выключатель запоминает ваше действие. Горящий свет и есть выражение того, что система помнит происшедшее в ней событие. При желании можно сказать, что замкнутое состояние контакта отражает логическое значение 1, а разомкнутое - 0. Стоит заметить, что, несмотря на распространенность и кажущуюся примитивность, электрический выключатель, в отличне, например, от кнопки звонка,- устройство довольно сложное. В нем предусмотрены специальные детали, которые удерживают (удерживать и есть запоминать) включенное или выключенное состояние.

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

и S-l-и Рис. 1.3. Условное обозначение транзистора:

а - с встроенным я-каналом; б - с индуцирован-Ю OJ ным п-каналом

На рис. 1.3 показано условное обозначение МДП-транзнстора. Буквами fi С п 3 помечены соответственно исток, сток и затвор. В дальнейшем мы не будем ставить эти буквы, а договоримся, что короткая вертикальная черта обозначает затвор, длинная вертикальная черта (штриховая, если канал индуцированный, и непрерывная, если канал встроенный) обозначает подложку.