Основы информатики_Савельев А.Я_Учебник_2001

2 Автомат как основной элемент информационных систем

словом в зависимости от принятого для данной ЭВМ способа представле­ ния информации.

Время обращения — интервал времени меж/^у началом и окончанием ввода (вывода) информации в память (из памяти). Оно характеризует затра­ ты времени на поиск места и запись (чтение) слова в память (из памяти).

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

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

Арифметико-логическое устройство (АЛУ) — функциональная часть ЭВМ, которая выполняет логические и арифметические ;^ейс1вия, нсобходимь[е для переработки информации, хранящейся в памяти. Оно характеризует­ ся временем выполнения элементарных операций; средним быстродействи­ ем^ т. е. количеством арифметических или логических действий (операций), вьиюлняемых в единицу времени (секунду); набором элементарр|ы.ч дейст­ вий, которые оно выполняет. Важной характеристикой AJfy является также система счисления, в которой осуществляются все действия.

Всовременных вычислительных,устройствах основным исполгн11ельиым элементом является процессор (П) или микропроцессор (МП), коюрый содери^ит в себе АЛУ, память (как правило, оперативную намять), блок управления.

Вмикропроцессорах важную роль ифают шины данных и адресные пш- \\ь\ или адреснь!е магистрали. Структурная схема микропроцессора представ­ лена на рис. 2.3. Числа в скобках указывают разрядность шин и устройств.

Вычислительные машины, построенные на основе микропроцессора, называются микроЭВМ [18] и отличаются тем, что обычно имеют два вида памяти: RAM (Random-Access-Memory) — память с нроизвольтгой выбор­ кой (ППВ) и ROM (Read-Oiily-Memory) — постоянная память (ПИ) па HFIтетральных схемах. В постоянную память можно вложить уже ютовый транслятор с алгоритмического язь!ка или готовый пакет программ, выпол­ няющий определенную функцию. Это позволяет расширить возможности микроэвм путем изготовления модулей расширения в виде ROM. C^ipyKгуртшя схема микроЭВМ представлена на рис. 2.4.

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

32

2 2 Абстрактные автоматы и понятие алгоритма

(т. е. над набором числа). Если же головка будет находиться в произволь­ ном месте ленты, то программа усложнится. Читателю предлагается самостоягельно написать такую программу.

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

Передвижение массива осуществляется перенесением (стиранием) самой левой метки в ближайшую пустую сек­

цию справа (команды № f и № 7 программы, приведенной ниже). Когда массивы сольются (команды № 5 и № 6), то оказывается, что результат ра­ вен ]ц + /?2 + 2. Значит, надо стереть одну лишнюю метку (команда № 4). В окоича1ель!юм состоянии головка стоит левее образовавшейся суммы.

всех ее возможностей. Можно составить программы для умножения, деле­ ния чисел. Есть ли ограничения на вычисления, производимые на машине Поста? Ответ на этот вопрос был сформулирован самим Э. Постом в сле­

Формулировка постулата Поста подводит к понятию алгоритма*. Сущсс1вуег М1ЮГО определений термина «алгоритм». Например, по определе­ нию акад. Л, if. Колмогорова, алгоритм или алгорифм — это всякая сис-

' Л ермим «алгоритм)) произошел от имени узбекского математика Аль-Хорезми, который С1Г1С н IX п (;(|н>рмулиро1«1л правила m.iiJOjmeHHfl чаырёх арифмегических действий. Появишиееся несколько позже слово «алгорифм)» связано с Евклидом, древнегреческим матема1ИК0М. сформулировавшим правила нахождения наибольшего общего делителя двух чисел.

R (.-онреметгной ма|емагике угсогребляют термин «алгоритм»,

37

2 Автомат как основной элемент информационных систем

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

В инженерной практике часто используется следующее онре;^елеиие; алгоритм — конечная совокупность точно сформулированных правид ре­ шения какой-то задачи [I].

По форме задания алгоритмы могут быть словесными и математиче­ скими. Пример словесной формы алгоритма — алгоритм Евклида для на­ хождения наибольшего общего делителя двух чисел а и Ь.

1.Обозревая два числа av\b, переходи к следующему пункту.

2.Сравни обозреваемые числа {а равно Ь, а меньше, больше Ь) и пере­ ходи к следующему пункту.

3.Если а vib равны, то прекрати вычисление: каждое из чисел даег ис­ комый результат. Если числа не равны, то переходи к следующему пункту.

4.Если первое число меньше второго, то переставь их местами и пере­ ходи к следующему пункту.

5.Вычти второе число из первого и сделай обозрение двух чисел: вы­ читаемого и остатка; переходи к п. 2.

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

Характеристиками алгоритма являются:

—детерминированность, определяющая однозначное [ь peiyjibiara решения задачи при заданных исходных данных;

—дискретность определяемого алгоритмом процесса, означающая расчлененность его на отдельные элементарные шаги;

—массовость, позволяющая применять один и тот же алгоритм AJIA некоторого множества однотипных задач.

Эти характеристики не дают точного описания алгоритма, а лишь объ­ ясняют смысл этого термина в математике.

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

уравнения вида ах -¥bx-¥c = 0 можно найти по формуле л:, ^ =

= (-/j± ^j{b^ ~ 4ас))/2а, которая представляет собой алгоритм нахождения этих корней. Однако для того, чтобы реализовать математическую (|)орму алгоритма, требуется дать еще ряд словесных указаний, показать обласгь применения алгоритма.

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

38

2 3 Основные понятия алгебры логики

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

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

Процесс выполнения алгоритма называется алгоритмическим процес­ сом- Для некоторых исходных данных он заканчивается получением иско­ мого результата после конечного числа шагов. Однако возможны случаи, когда искомьЕЙ результат не достигается или безрезультатно обрывается. Тогда говорят, что к таким исходным данным алгоритм неприменим.

Таким образом, алгоритм дает возможность ответить на вопрос «что делать?» в каждый момент времени, однако создать алгоритм не всегда возмоисно.

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

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

Процесс решения задачи на ЭВМ прежде всего должен быть выражен каким-то ajriopHTMoM. Разработка алгоритмов решения задач — задача проipaMMHCia, а разработка алгоритмов функционирования цифрового автома­ га ДJiя решения 1юставлениых задач — задача инженера-разработчика.

2 3 . Основные понятия алгебры логики

11опятие автомата бь!Ло введено в гл. I в качестве модели для описания функционирования устройств, предназначенных для переработки дискрет­ ной информации.

Для формального описания цифрового автомата широко применяют аг|[1арат ш!гебры логики, являющейся одним из важных разделов математи­ ческой логики*.

Основное понятие алгебры логики — высказывание. Высказывание — некоторое предложение, о котором можно утверждать, что оно истинно или ложно. Например, высказывание «Земля — это планета Солнечной системы» ИС1ИННО, а о высказывании «на улице идет дождь» можно ска-

СЧядатель алтебры логики — английский математик Дж. Буль (!815-1864), Поэтому ал!ебру логики пазывшот 1акже алгеброй Буля. В последние годы алгебра Буля получила зпачшельиое развитие блаюдаря работам таких ученых, как Э. Посг, К. Шейной, 1 Л Шестаков. R М. Глушкон [6], С. В. Яблонский [21] и др.

39

2 Автомат как основной элемент информационных систем

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

Любое высказывание можно обозначить символом х и считать, что X = I, если высказывание истинно, а х = О — если высказывание ложно.

Логическая {булева) переменная — такая величина х, которая может принимать только два значения: х = {0,1}.

Высказывание абсолютно истинно, если соответствующая ей логиче­ ская величина принимает значение х = 1 при любых условиях. Пример абсолютно истинного высказывания — высказывание «Земля -— планета Солнечной системы».

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

Например, высказывание «Земля — спутник Марса» абсолютно ложно.

Логическая функща (функция алгебры логики) — функция /(х,, Х2,..-,

X,,), принимающая значение, равное нулю или единице на наборе логиче­ ских переменных Х|, Xj, ..., Х„ .

Логические функции от одной переменной представлены в таблице 2.1,

Т а б л и ц а 2,1

в соответствии с введенными определениями функция /|(х) является абсолютно истинной (константа единицы), а функция fiix) — абсолютно ложной функцией (константа нуля).

Функция /^{х), повторяющая значения логической переменной, — тождественная функция [/з(х) = х], а функция f^(x), принимающая зна­ чения, обратные значениям х, —логическое отрицание, или функция НЕ

Логические функции от двух переменных представлены в таблице 2.2.

Дизъюнкция {логическое слож:ение) — функция /7(х,, Х2), которая ис­ тинна тогда, когда истинны или х,, или х^, или обе переменные.

Дизъюнкцию часто называют также функцией ИЛИ и условно обозна­ чают так: fi (Xj, Xj) - X, + Xj = Xj V Х2.

40