Понятие алгоритма

Появление алгоритмов связывают с зарождением математики. Более 1000 лет назад (в 825 году) ученый из города Хорезма Абдулла (Абу Джафар) Мухаммед бен Муса аль-Хорезми создал книгу по математике, в которой описал сто способы выполнения арифметических действий над многозначными числами. Само слово «алгоритм» возникло в Европе после перевода на латынь книги этого среднеазиатского математика, в которой его имя писалось как «Алгоритмы».

Алгоритм — описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов.

Алгоритмизация — процесс разработки алгоритма (плана действий) для решения задачи.

Виды алгоритма

Существует 4 вида алгоритмов: линейный, циклический, разветвляющийся, вспомогательный.

- Линейный (последовательный) алгоритм — описание действий, которые выполняются однократно в заданном порядке.

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

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

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

Условие – это выражение находящееся между словом «если» и словом «то» и принимающее значение «истина» или «ложь».

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

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

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

Например: вы в детстве учились суммировать единицы, затем десятки, чтобы суммировать двузначные числа, содержащие единицы вы не учились новому методу суммирования, а воспользовались старыми методами.

Схема алгоритма

R_а=0

Сч(а) 1

S 0

R A[Сч(а)]

R(a)=R(a)+1

S=S+R

Сч(а)=Сч(а)+1

Описание алгоритма

1. Начало

2. Обнуляем регистр адреса  R_а=0

3. Счетчик массива А записываем 1; Сч(А) 1

4. Записываем в регистр суммы чисел S число 0

5. Считываем в регистр R число из массива А с порядковым номером Сч(А):R A[Cч(а)]

6. Производим слоение числа находящихся в регистре S и числа находящийся в регистре R

7. Проверяем последнее и это число массива (а) ; Cч(а)]=К , если «да» выходим на 8 , если «нет» выходим 9

8. Выводим сумму S=

9. Увеличиваем R_а на 1: R_а R_a + 1

10. Увеличиваем значение счетчика Сч(А) на 1 : Сч(А) +1

11. конец

Схема алгоритма в макрокомандах

Rа=0

Сч(а) 1

Y₁:

Y₂:

S 0

y₃:

y₄:

R_a A[Сч(а)]

R(a)=R(a)+1

S=S+R

y₈: y₅:

Сч(а)=Сч(а)+1

y₇:

С:

Y₆:

Схема алгоритма в микрооперациях

Y1: y₁; y₂; y₃

А₀

Y2: y₄

А₁

А₂

Y3: y₅

Y5: y₆

А₅

А₃

Y4: y₇; y₈

А₄

Схема графа функционирования

А₀-А₁ Выполняем первичным устройством R_A 0

Записываем в счетчик Сч(А) число

1: Сч(А) 1

Записываем в регистр S число 0:

S 0

А₁-А₂ Считываем в регистр R число из массива А с порядковым номером Сч(А)

А₂-А₃ Производим сложение числа находящегося в регистре S и числа находящегося в регистре R .Результат помещаем в регистр S: S S+R

А₃-А₄ Проверяем последнее ли это число массива А: Сч(А) = К, если число последнее выводим S = ; и конец

А₃-А₅ Увеличиваем значение счетчика Сч(А) на единицу

Сч(А) Сч(А) +1

А₅-А₁ читаем следующее число

Таблица состояния дешифратора 3-8

	Х1	Х2	Х4
У0	0	0	0
У1	0	0	1
У2	0	1	0
У3	0	1	1
У4	1	0	0
У5	1	0	1
У6	1	1	0
У7	1	1	1

X1 DC y1

X2 y2

y3

X4 y4

Y5

Y6

Y7

Y8

E

6. Цифровые устройства, входящие в состав процессора

6.1 Триггеры

Триггер – это логическая схема, имеющая два устойчивых состояния, которые называются единичным и нулевым и обозначаются 1 и 0.

Триггер предназначен для хранения значения одной логической переменной. В соответствии с этим триггер имеет два состояния: одно из них обозначается как состояние 0, другое – как состояние 1. Воздействуя на входы триггера, его устанавливают в нужное состояние.

Триггер имеет два выхода: прямой Q и инверсныйQ. Входы триггера бывают различных типов:

S ( от англ. Set) – вход установки триггера в состояние 1;

R ( от англ. Reset) – вход установки в состояние 0;

J – вход установки универсального триггера в состояние 1;

K – вход установки универсального триггера в состояние 0;

T – счётный вход;

D – информационный вход установки триггера в состояние, соответствующее логическому уровню на этом входе;

С – управляющий (синхронизирующий вход).

Перевод триггера в единичное состояние называют установкой (set), перевод триггера в нулевое состояние называют сбросом или гашением (reset).

Классификация триггеров

1). По типам входов бывают SR-триггеры, JK-триггеры, D-триггеры и Т-триггеры. Эти типы триггеров являются основными.

2). По характеру реакции на входные сигналы триггеры бывают асинхронные и синхронные.

Асинхронные триггеры имеют только информационные (логические) входы. В таком триггере входные сигналы воздействуют на состояние триггера непосредственно с момента их подачи на вход.

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

Принцип работы триггеров

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

Таблица переходов SR-триггера				Таблица переходов JK-триггера
S	R	Q		J	K	Q
0	0	Q0		0	0	Q0
0	1	0		0	1	0
1	0	1		1	0	1
1	1	*		1	1	Q0

Первая таблица переходов соответствует работе SR-триггера. Здесь Q₀ – текущее состояние триггера (т. е. состояние до подачи на вход активного сигнала). Активными являются сигналы, соответствующие логической единице. Первая строка – активных сигналов на входе нет (S и R равны нулю), поэтому на выходе сохраняется текущее состояние. Во второй и в третьей строке на входе появляются активные сигналы (во второй R = 1, а в третьей S = 1). Эти активные сигналы переводят триггер в другое состояние: R – в состояние 0, а S – в состояние 1. В последней строке звёздочкой отмечено запрещённое состояние входных сигналов триггера (так как оба входа активны, а одновременный переход в противоположные состояния невозможен). Дело в том, что если на RS-триггер подать одновременно оба входных сигнала, то обоих выходах появятся нули. Если одновременно снять

единицы со входов, то оба элемента начнут переключаться в единичное состояние, стремясь оставить другой элемент в нулевом состоянии. Какой из элементов победит, зависит от скоростей переходных процессов, коэффициентов усиления и других факторов. Поэтому, комбинация R = S = 1 считается запрещённой.

Вторая таблица переходов соответствует работе JK-триггера. JK-триггер имеет входы установки (J) и сброса (K), подобные входам RS-триггера. В отличие от последнего, допускает одновременную подачу сигналов J и K и при J = К = 1 он устанавливается в состояние, противоположное текущемуQ₀. JK-триггер называется универсальным.

Рассмотрим таблицы переходов для D-триггеров и Т-триггеров.

Таблица переходов D-триггера			Таблица переходов Т-триггера
D	Q		Т	Q
0	0		0	Q0
1	1		1	Q0

У D-триггера сигналы на выходе такие же, как и на входе. Такой триггер называется информационным.

Т-триггер отличается тем, что если входной сигнал пассивен (т. е. Т = 0), то на выходе сохраняется текущее состояние. Если входной сигнал активен (Т = 1), то на выходе триггер переключается в состояние, противоположное текущему. Такой триггер называют счётным.

Построение и описание схем триггеров

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

И ИЛИ НЕ И-НЕ ИЛИ-НЕ

Логическое Логическое Логическое Отрицание Отрицание

умножение сложение отрицание конъюнкции дизъюнкции

(конъюнкция) (дизъюнкция) (инверсия)

Схема и описание асинхронного RS-триггера

Триггер состоит из двух логических элементов ИЛИ-НЕ, структурно расположенных строго друг под другом и связанных таким образом, что выход каждого элемента подключён к одному из входов другого (рисунок 1, а).

Логическая схема – более подробная, показывает, из чего состоит устройство. Условное обозначение – сокращённое, применяется в схемах. Буква Т в условном обозначении говорит о том, что это триггер.

Схема и описание синхронного RS-триггера

Триггер структурно состоит из асинхронного RS-триггера на элементах И-НЕ, к входам которого дополнительно подключены логические элементы И-НЕ. Внутренние входы триггера объединены во вход С для подачи управляющего сигнала (рисунок 2, а).

а) б)

Рисунок 2. Синхронный RS-триггер:

а). Логическая схема; б). Условное обозначение

Схема и описание синхронного D-триггера

Синхронный D-триггер отличается от синхронного RS-триггера тем, что у него только один информационный вход D. Вход С – управляющий и служит для подачи синхронизирующего сигнала. Принцип построения этого типа триггера такой же, как и синхронного RS-триггера. Обратим внимание на то, как соединены между собой входы логических элементов (рисунок 3). Данный тип триггера построен на логических элементах И-НЕ.

а) б)

Рисунок 3. Синхронный D-триггер:

а). Логическая схема; б). Условное обозначение

JK-триггер очень сложен по своей структуре и применяется довольно редко. JK-триггеры имеют широкие функциональные возможности.

По таблицам переходов RS-триггера и JK-триггера видно, что для первых трех строк (наборов переменных) входы J и K играют роль входов S и R RS - триггера. Однако, для четвертого набора переменных, когда J=K=1 состояние триггера сильно отличается от состояния RS-триггера. Для RS-триггера - это запрещенная комбинация входных переменных, а в JK-триггере меняется (инвертируется, отрицается) предыдущее состояние. JK-триггер можно построить на базе RS-триггера, подключив к его входам дополнительные логические элементы (рисунок 4).

а) б)

Рисунок 4. Синхронный JK-триггер:

а). Логическая схема, б). Условное обозначение

Схема и описание синхронного T-триггера

Т-триггеры строятся только на базе двухступенчатых (RS, D, JK) триггеров. Рассмотрим пример построения Т-триггера из D-триггера. Для того чтобы превратить D-триггер в счётный, необходимо ввести цепь обратной связи с инверсного выхода этого триггера на вход, как показано на рисунке 5.

Рисунок 5. Условное обозначение T-триггера,

построенного на основе D-триггера

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