Архитектура ЭВМ. Способы представления конечных автоматов

Способы представления конечных автоматов

Конечный автомат можно представлять несколькими способами:

- ориентированным графом (графом состояний), в котором

состояния есть вершины графа, а дуги есть переходы между состояниями:

a₃,V₃

q₂ q₄

a₁,V₁

a₅,V₆

q₁

a₃,V₅

a2,V₂ q3 q5 q6

a4,V₄ a6,V8

Рис. 10.1. Граф состояний

a_i - символы входного алфавита, вызывающие переходы; V_i - символы выходного алфавита; q_i - состояния автомата.

- таблицей переходов, в которой по строкам располагаются

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

	a1	a2	a3	a4	a5	a6
q1	q2, V1	q3, V2
q2			q4, V3
q3				q5, V4
q4			q5, V5		q5, V6
q5						q6, V7
q6

- матрица переходов, которая представляет собой квадратную

матрицу, строки и столбцы которой соответствуют внутренним состояниям автомата. Клетки матрицы заполняются входными символами a_k,при которых автомат переходит из состояния q_i в состояние q_j, а также выходными символами, соответствующими паре (ak, qi).

	q1	q2	q3	q4	q5	q6
q1		a1, V1	a2, V2
q2				a3, V3
q3					a4, V4
q4					a3, V5 a5, V6
q5						a6, V7
q6

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

Определение. Конечный автомат называется полностью определенным, если его таблица переходов не содержит пустых клеток. Иначе автомат называют частично определенным.

Компьютер можно рассматривать как совокупность взаимодействующих конечных автоматов. Рассмотрим такую структуру подробнее.

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

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

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

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

Кроме оперативной памяти, компьютер имеет внешнюю память (ВЗУ) с большой емкостью, но с большим временем записи или считывания информации. Внешняя память реализуется с помощью внешних носителей информации: магнитных или оптических дисков.

Джон фон Нейман предложил ряд принципов, которые легли в основу фон Неймановской или классической архитектуры компьютера:

1. Память состоит из однородных ячеек памяти с адресами.

2. Программа состоит из последовательных команд.

3. Хранение программы и обрабатываемых ею данных – одинаковое, в битовом виде.

4. Команды выполняются последовательно, данные извлекаются в соответствии с командами.

5. Процессор – один и имеет централизованное управление и доступ к памяти.

Структура ЭВМ фон Неймановской архитектуры приведена на 11.1.

Рис. 11.1. Структура ЭВМ фон Неймановской архитектуры

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

Пример. Команды АЛУ – просты: "сравнить два числа", "переслать число", "взять дизъюнкцию" и др.

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

Совокупность АЛУ и УУ, информационно-управляющих линий называется процессором компьютера (его структура приведена на рис. 10.3; жирная линия – информационное взаимодействие, другая – управляющее).

Рис. 11.2. Структура процессора

Обмен информацией с компьютером осуществляется устройствами ввода и устройствами вывода.

Пример. Устройствами ввода являются, например, клавиатура, мышь. Устройствами вывода — дисплей, принтер, плоттер.

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

Ядро персонального компьютера – системная (материнская плата), на которой размещаются: микропроцессор, микропроцессорная память, интерфейсная система микропроцессора для сопряжения и связи с другими устройствами, генератор тактовых импульсов, контроллеры устройств (схем), интегрированных в материнскую плату, микросхемы ОЗУ и ПЗУ и др.

Другими важными устройствами персонального компьютера являются:

· дисковод;

· CD-ROM (устройство только для чтения компакт-дисков) или CD-RW (чтение и перезапись);

· монитор (дисплей);

· видеокарта (видеоадаптер) для обеспечения связи системного блока и монитора;

· клавиатура;

· принтер;

· сканер;

· плоттер (графопостроитель);

· дигитайзер (кодирующий планшет);

· манипулятор-мышь или манимулятор-трекбол;

· звуковая карта (адаптер);

· звуковые колонки;

· модем и другие устройства.

Классификацию компьютеров проводят по быстродействию, технологии использования и др.

Необходимо соблюдать простые санитарно-гигиенические и эргономические правила работы на компьютере, в компьютерном зале:

• работа с компьютером не более 4-х часов подряд с 10-минутными перерывами после каждого часа интенсивной работы или после 2-х часов менее интенсивной работы;
• расстояние от глаз до поверхности экрана – не менее 0,6 м;
• перемещаемость клавиатуры относительно экрана в пределах 0,5-1,0 м;
• преимущественно желтый, зеленый, серый или светло-голубой фон дисплея;
• температура воздуха в помещении – 15-25 градусов по Цельсию;
• относительная влажность помещения – 45-75%;
• наличие свободной площади рабочего стола не менее 0,3x1,0 м;
• размер экрана по диагонали – не меньше 17 дюймов;
• разрешение экрана – не менее 800x600;
• частота обновления кадра – не менее 70 Гц;
• размер зерна экрана (расстояние между точками на экране) – не более 0,26;
• частота кадров (мерцание экрана) – не менее 75 Гц;
• стандарты безопасности, например MPR-II.

Дата добавления: 2014-01-20