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

Подождите немного. Документ загружается.

2 I ЭВМ как автомат

ВспомогагельньЕМИ устройствами автомата могут быть всевозможные

дополнительные средства, улучшающие или расширяющие возможност!'

ашомата.

Арифнетикз-

догическов

устройство

Периферийные

устройства

ШВ^Информация

Устройства

управлений

Рис. 2.2. Структурная схема ЭВМ

ЭВМ — ирограммно-уиравлиемый цифровой автомат.

Эю положение подкрепляет две фундаментальные идеи. Первая состой-

в том, 'ПО ЭВМ — автомат для переработки и преобразования цифровог

wm дискретной информации. Это означает, что вся подаваемая на вхо^

ЭВМ информация (текстовая, графическая, числовая и т. п.) должна быт1

преобразована в набор цифр или чисел, представленных в выбранной сие

теме счисления. Следовательно, выбор системы счисления является очен|

ответствеииой задачей для разработчика. Вторая идея заключается в том

что ЭВМ управляется специальной программой, которая может либо вво

ди1ься в ЭВМ, либо храниться в ее памяти. Следует подчеркнуть очей:

важ!1ые функции памяти ЭВМ.

[|амять (заиоминающее устройство) — функциональная часть ЭВМ

предназначенная для хранения и (или) выдачи входной информации, про

межуточных и окончательных результатов, вспомогательной информаци*-

В памяти маин!ны находятся также программы решения задач, через ко

манды коюрых осуществляется управление работой всей машины.

OciroBHbie параметры, характеризующие память, — емкость и врем

обращения к памяш.

Емкость памяти — количество слов информации, которое можно за

HHcaib в [1амя1и. flpn этом словом является упорядоченная последователь

иос1Ь символов алфавита конечной длины. Ячейка памяти — часть ггамят^

содержапм1я слово.

f^MKOdb памяти можно выразить количеством содержащихся в не1

слои млн я'юск, ^1д1ина ячейки памяти измеряется количеством битов (оди1

би!

равен одному двоичному разряду) или байтов (один байт содержит вс

семь битов). Ячейка памяти может вмещать информацию разной длины ил:

разной!

формата. Формат измеряется словом, двойным словом или полу

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

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

ния информации.

Время обращения — интервал времени меж/^у началом и окончанием

ввода (вывода) информации в память (из памяти). Оно характеризует затра-

ты времени на поиск места и запись (чтение) слова в память (из памяти).

Для построения запоминающих устройств в качестве физических эле-

ментов используют электронные схемы, ферритовые маг нитные материалы,

магнитные ленты и диски, барабаны с магнитным покрытием, оптические

запоминающие элементы и т. д.

Основным преобразователем цифровой информации являемся арифме-

тико-логическое устройство.

Арифметико-логическое устройство (АЛУ) — функциональная часть

ЭВМ, которая выполняет логические и арифметические ;^ейс1вия, нсобходи-

мь[е для переработки информации, хранящейся в памяти. Оно характеризует-

ся временем выполнения элементарных операций; средним быстродействи-

ем^

т. е. количеством арифметических или логических действий (операций),

вьиюлняемых в единицу времени (секунду); набором элементарр|ы.ч дейст-

вий, которые оно выполняет. Важной характеристикой AJfy является также

система счисления, в которой осуществляются все действия.

В современных вычислительных,устройствах основным исполгн11ель-

иым элементом является процессор (П) или микропроцессор (МП), коюрый

содери^ит в себе АЛУ, память (как правило, оперативную намять), блок

управления.

В микропроцессорах важную роль ифают шины данных и адресные пш-

\\ь\

или адреснь!е магистрали. Структурная схема микропроцессора представ-

лена на рис. 2.3. Числа в скобках указывают разрядность шин и устройств.

Вычислительные машины, построенные на основе микропроцессора,

называются микроЭВМ [18] и отличаются тем, что обычно имеют два вида

памяти: RAM (Random-Access-Memory) — память с нроизвольтгой выбор-

кой (ППВ) и ROM (Read-Oiily-Memory) — постоянная память (ПИ) па

HFI-

тетральных схемах. В постоянную память можно вложить уже ютовый

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

няющий определенную функцию. Это позволяет расширить возможности

микроэвм путем изготовления модулей расширения в виде ROM. C^ipyK-

гуртшя схема микроЭВМ представлена на рис. 2.4.

Наличие входного и выходного каналов, а также сре;^ств и методов

взаимодействия (интерфейса) ЭВМ с внешними устройствами тюзволяет

существенно повысить скорость работы всего комплекса от ввода инфор-

мации в машину до вывода ее. Фактически для осуществления подобного

< автомат

принципа работы необходимо иметь несколько ЭВМ, выполняющих разные

функции:

управление рабагой всего комплекса устройств, выполнение ариф-

метических и логических действий, ввод и вывод информации. Все уто сви-

дегельствуе! о существенном усложнении структуры ЭВМ, и эта тенденция

сохраняется для персональных ЭВМ, к которым уже в полной мере можно

применять термин «вычислительные сисгемы» (рис. 2.5).

АЗресная шина (fS)

Шина Ванных (S)

Cf6)

Регистр (^"У

адреса данных

(el

Регистр (Q)

номамо

программный

с чет чин

Ра мять

(б)

г?1

Арифметика-

яогичесное

устройство

Влон управления

и синхронизации

К компонентам

М-

ёаак

pezacrpoi

Рис. 2.J. Структурная схема микропроцессора

Синхроге-

нератер

Микро •

ароцес

сор

Адресная магистраль

ггт

1£

31£

Интер'

'eSo

ПТ

Числовая магистраль

т.

Интер •

фейЬ

выхода

иг

^--^

Управление

Рис. 2.4. Структурная схема микроЭВМ

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

Рис.

2.S. Структурная схема вычисли гсльной

системы

Автомат

Поста

2.2.

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

Классические примеры абстрактных автоматов -— машины Тьюрит а или

машины Поста*. Как правило, такая машина содержит бесконечную ленгу,

разделенную на отдельные секции (ячейки), в кш-орые можно либо заносить

мегку, либо счтывать метку с 1юмощью записываготсн

или считывающей головки (рис. 2.6). Лента (или головка)

может передвигаться в левую или правую С1ороны на

один шаг в зависимости от комаши>1- Лента всегда осга-

навливается так, чтобы напротив головки находилась

секция (ячейка). Команды абстрактного автомата обычно

включают в себя одно из следующих действий (на при-

мере машины Поста); движение головки вправо, движе-

ние головки влево, запись метки, стирание метки, пере-

дача управления, остановка (стоп).

Каждая команда имеет свой номер /. Стрелка указывает направле-

ние движения. Второе число 7, стоящее в конце команды, называется

wmT\

Рис.

2.6. Струк-

турная схема авто-

мата Поста

* Английский математик А. М. Тьюринг в работе «О вычислимых числах с приложением

к проблеме разрешения» и американский математик Э, X, Пост в работе «Финитные комби-

наторные процессы» почти одновременно в 1936 г. дали уточнения понятия «алгори1м» на

примере гипотетической машины с бесконечной лентой, Машина Тьюринга отличается от

машины Поста тем, что ячейки заполняются не просто меткой, а символами из заданною

множества.

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

отсылкой. У команды передачи управления могут быть две отсылки.

Поэтому программа абстрактного автомата должна обладать двумя свой-

ствами;

1) на первом месте в списке всегда стоит команда с номером I, на вто-

ром месте — с номером 2 и т. д.;

2) отсылка любой из команд всегда находится в списке команд про-

граммы.

После передвижения ленты влево или вправо головка считывает со-

стояние секции (пустая или записана метка). Информация о том, какие сек-

ции пусты, а какие отмечены, образует состояние ленты или состояние

автомата. Таким образом, обладая указанным выше набором команд, ав-

томат может осуществлять определенные действия, KOTopbie будут зада-

ваться программой. Программой абстрактного автомата будем называть ко-

нечный непустой список команд.

Для «работы» абстрактного автомата необходимо задать программу и

начальное состояние, т. е, положение головки и состояние ячеек ленты. По-

сле эюго автомат приступает к выполнению команды номер I. Все секции

(ячейки) ленты нумеруются в определенном порядке. Порядок нумерации

ячеек моисет совпадать с порядком, в котором расположены натуральные

целые числа.

Каждая команда выполняется за один шаг, после чего начинается вы-

полнение комаи;^ы, номер которой указан в отеь!лке. Если эта команда име-

ет две отсылки, то команда с номером верхней отсылки выполняется, если

под головкой находится пустая ячейка. Если исе под головкой находится

ячейка с меткой, то'выполняется команда с номером нижней отсылки. Вы-

полнение команды передачи управления не изменяет состояния автомата

(ни одна из меток не уничтожается и не ставится, и лента остается непод-

вижной). При запуске автомата может возникнуть одна из следующих си-

туаций:

автомат дошел до выполнения невыполнимой команды (запись метки в

заня1ую ячейку, стирание метки в пустой ячейке); выполнение программы

прекращается, автомат останавливается (назовем это состояние поломкой

автомата), происходит безрезультатная остановка;

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

происходи! результатная остановка;

автомат не доходит ни до результатной, ни до безрезультатной оста-

1ювки,

происходит бесконечная работа (автомат «завис»).

Рассмотрим работу автомата, начальное состояние которого задано

рис. 2.7 при выполнении следующей программы:

II 11

Kl III

ill

ll'lll

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

-> 3;

^ 4;

V 2;

5. стоп.

Если начш!ьное состояние соответствует рис. 2.7, а,

то

выполнение про-

граммы приводит

результатной остановке. Если

же

исходное состояние

автомата соответствует рис. 2.7, б,

то

программа

не

дает результата, авто-

мат «зависает». Таким образом, начальное состояние

автомата влияет на результативность его работы.

С другой стороны, различные программы, приме-

ненные

одному

тому

же

начальному сосюяииго,

дают разный результат.

На

таких элементарных автоматах,

как

машина

Рис. 2.7. Началь- Поста

или

машина Тьюринга, можно проводить раз-

ное состояние личные действия

над

числами.

Для

этого необходимо

ainoMaia

Представлять числа в абстрактном автомаге.

Назовем последовательность секций (ячеек), содержащих метку, мас-

сивом,

число секций

нем

—

длиной массива. Условимся число

пред-

ставлять на ленте массивом длины

и + I.

Тогда этот массив будем называть

aatmfMitmiihiM иа/бра.желием числа, f [апример, MHCjra

6, 3 и 2

преде гавлепь!

— соответственно

на

рис.

2.8

автоматными

1Т1Т1Т1Т1У1Т1У1

ITNTITI 1ТЫУ1

\ изображениями.

„

-о , ^

Представим себе,

что иа

машине

Рис. 2.8. Лшоматнос изображение

„ "^ ^ • ^

.„^^.gj,

Поста надо прибавить

I к

любому числу.

Для этого требуется написать программу

1ЩЙ

машины Поста, обладающую следующим свойством: для любого числа

/;, записанного

на

ленте, программа должна дать результатную остарювку

записью числа

произвольном месте лепты.

I [рограмма может выглядеть следующим образом:

1-й вариант

2-й

вариант

1.^2

V 4

7С]

V 4;

стоп.

В качестве начального состояния может быть выбрано любое состоя-

ние,

при

котором головка находится

на

одной

из

отмеченных ячеек ленты

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

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

ном месте ленты, то программа усложнится. Читателю предлагается само-

стоягельно написать такую программу.

С помощью абстрактного автомата можно реализовать и другие преоб-

разования числовой информации. Рассмотрим, например, сложение двух чи-

сел.

В самой обнйй постановке эта задача формулируется так: составить про-

грамму сложения двух чисел щ и nj записанных на ленте иа произвольном

расстоянии друг от друга. Начальное со- -г, п *1 п,*1

стояние авюмата показано на рис. 2.9. i I |т|т|т|т|т| I

MTITIITTI

/1ля написания программы можно, ~

например, передвигать левый массив иа- Рис. 2.9. Начальное состояние

автомата

для

программы

право до слияния с правым массивом.

у ''• I сложения чисел

Передвижение массива осуществляется

перенесением (стиранием) самой левой метки в ближайшую пустую сек-

цию справа (команды № f и № 7 программы, приведенной ниже). Когда

массивы сольются (команды № 5 и № 6), то оказывается, что результат ра-

вен ]ц +

/?2

+ 2. Значит, надо стереть одну лишнюю метку (команда № 4). В

окоича1ель!юм состоянии головка стоит левее образовавшейся суммы.

3 2; 4. 3 5; 7. V 8; 10. <- If;

^ 3; 5. -> 6; 8. ^ 9; , ^ 2

3 v-^12. 6 7^*^. 9 7^'*^- • •""'*^'

^4-

"• -^5'

•'^12'

12. стоп.

11редс1авленные примеры программ машины Поста не исчерпывают

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

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

Поста? Ответ на этот вопрос был сформулирован самим Э. Постом в сле-

дующем виде: «Задача иа составление программы, приводящей от исход-

иого даипого к результирующему числу, тогда и только тогда имеет ре-

шение, когда имеется какой-нибудь общий способ, позволяющий по

проиюолыюму и одному данному выписать результирующее число».

Формулировка постулата Поста подводит к понятию алгоритма*. Су-

щсс1вуег

М1ЮГО

определений термина «алгоритм». Например, по определе-

нию акад. Л, if. Колмогорова, алгоритм или алгорифм — это всякая сис-

ермим «алгоритм)) произошел от имени узбекского математика Аль-Хорезми, который

С1Г1С н IX п

(;(|н>рмулиро1«1л

правила

m.iiJOjmeHHfl

чаырёх арифмегических действий. Поя-

вишиееся несколько позже слово «алгорифм)» связано с Евклидом, древнегреческим матема-

1ИК0М. сформулировавшим правила нахождения наибольшего общего делителя двух чисел.

(.-онреметгной

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

Автомат

как

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

систем

тема вычислений, выполняемых по строго определенным правилам, кото-

рая после какого-либо числа шагов заведомо приводит к решению

поставлеинай задачи.

В инженерной практике часто используется следующее онре;^елеиие;

алгоритм — конечная совокупность точно сформулированных правид ре-

шения какой-то задачи [I].

По форме задания алгоритмы могут быть словесными и математиче-

скими. Пример словесной формы алгоритма — алгоритм Евклида для на-

хождения наибольшего общего делителя двух чисел а и Ь.

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

Сравни обозреваемые числа {а равно Ь, а меньше, больше Ь) и пере-

ходи к следующему пункту.

Если а vib равны, то прекрати вычисление: каждое из чисел даег ис-

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

Если первое число меньше второго, то переставь их местами и пере-

ходи к следующему пункту.

Вычти второе число из первого и сделай обозрение двух чисел: вы-

читаемого и остатка; переходи к п. 2.

По указаниям этого алгоритма можно найти наибольший общий дели-

тель для любой пары целых чисел.

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

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

решения задачи при заданных исходных данных;

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

расчлененность его на отдельные элементарные шаги;

— массовость, позволяющая применять один и тот же алгоритм

AJIA

некоторого множества однотипных задач.

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

ясняют смысл этого термина в математике.

Пример алгебраической формы алгоритма — любая математическая

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

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

= (-/j± ^j{b^ ~ 4ас))/2а, которая представляет собой алгоритм нахождения

этих корней. Однако для того, чтобы реализовать математическую (|)орму

алгоритма, требуется дать еще ряд словесных указаний, показать обласгь

применения алгоритма.

Детерминированный алгоритм — алгоритм, имеющий место при чег-

кой и ясной системе правил и указаний и однозначных действиях.

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

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

случайного выбора тех или иных правил.

Алгоритм должен обеспечивать получение результата через конечное

число шагов для любой задачи определенного класса. В противном случае

задача неразрешима. Нахождение алгоритма решения задачи называется ал-

гор um.Mmaijue и.

Процесс выполнения алгоритма называется алгоритмическим процес-

сом-

Для некоторых исходных данных он заканчивается получением иско-

мого результата после конечного числа шагов. Однако возможны случаи,

когда искомьЕЙ результат не достигается или безрезультатно обрывается.

Тогда говорят, что к таким исходным данным алгоритм неприменим.

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

делать?» в каждый момент времени, однако создать алгоритм не всегда

возмоисно.

Численный алгоритм — алгоритм, соответствующий решению постав-

ленной задачи с помощью арифметических действий.

Логический алгоритм — алгоритм, используемый в случае, если при

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

Процесс решения задачи на ЭВМ прежде всего должен быть выражен

каким-то ajriopHTMoM. Разработка алгоритмов решения задач — задача про-

ipaMMHCia, а разработка алгоритмов функционирования цифрового автома-

га ДJiя решения 1юставлениых задач — задача инженера-разработчика.

23.

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

11опятие автомата бь!Ло введено в гл. I в качестве модели для описания

функционирования устройств, предназначенных для переработки дискрет-

ной информации.

Для формального описания цифрового автомата широко применяют

аг|[1арат ш!гебры логики, являющейся одним из важных разделов математи-

ческой логики*.

Основное понятие алгебры логики — высказывание. Высказывание —

некоторое предложение, о котором можно утверждать, что оно истинно

или ложно. Например, высказывание «Земля — это планета Солнечной

системы» ИС1ИННО, а о высказывании «на улице идет дождь» можно ска-

СЧядатель алтебры логики — английский математик Дж. Буль (!815-1864), Поэтому

ал!ебру логики пазывшот 1акже алгеброй Буля. В последние годы алгебра Буля получила

зпачшельиое развитие блаюдаря работам таких ученых, как Э. Посг, К. Шейной,

1 Л Шестаков. R М. Глушкон [6], С. В. Яблонский [21] и др.

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

зать,

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

погоде в данный момент.

Любое высказывание можно обозначить символом х и считать, что

= I, если высказывание истинно, а х =

— если высказывание ложно.

Логическая {булева) переменная — такая величина х, которая может

принимать только два значения: х =

{0,1}.

Высказывание абсолютно истинно, если соответствующая ей логиче-

ская величина принимает значение х =

при любых условиях. Пример

абсолютно истинного высказывания — высказывание «Земля -— планета

Солнечной системы».

Высказывание абсолютно ложно, если соответствующая ей логическая

величина принимает значение х =

при любых условиях.

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

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

X,,),

принимающая значение, равное нулю или единице на наборе логиче-

ских переменных Х|, Xj, ...,

Х„

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

Таблица 2,1

/|(«)

/2(-1)

М')

/Л')

в соответствии с введенными определениями функция /|(х) является

абсолютно истинной (константа единицы), а функция fiix) — абсолютно

ложной функцией (константа нуля).

Функция

/^{х),

повторяющая значения логической переменной, —

тождественная функция

[/з(х)

= х], а функция

f^(x),

принимающая зна-

чения, обратные значениям х, —логическое отрицание, или функция НЕ

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

Дизъюнкция {логическое слож:ение) — функция /7(х,, Х2), которая ис-

тинна тогда, когда истинны или х,, или х^, или обе переменные.

Дизъюнкцию часто называют также функцией ИЛИ и условно обозна-

чают так: fi

(Xj,

Xj) -

+ Xj = Xj V Х2.