Учебное пособие по информатике 2014. Основы информатики

• Название: Основы информатики
• Анкор: Учебное пособие по информатике 2014.pdf
• Дата: 28.03.2018
• Размер: 4.61 Mb.
• Имя файла: Учебное пособие по информатике 2014.pdf
• Тип: Учебное пособие; #17317
• страница: 8 из 28

Контрольные вопросы
1.
Перечислите известные вам свойства алгоритма.
2.
Перечислите известные вам виды алгоритмов.
3.
Какие способы представления алгоритмов вы знаете?
4.
Что такое структурная схема алгоритма и из каких элементов она состоит?
5.
Как происходит разработка иерархической схемы реализации алгоритма?
6.
Что вы знаете о нормальном алгоритме Маркова, в чем его суть?
7.
Перечислите несколько классификаций языков программирования.
8.
В чем отличия поколений языков программирования?
9.
Сформулируйте последовательность этапов жизненного цикла программного обеспечения.
10.
Расскажите об основных принципах проектирования программы

66
3. МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ
3.1 Понятие дискретного автомата
В технике термином «автомат» пользуются для обозначения системы механизмов и устройств, в которой процессы получения преобразования, передачи и использования энергии, материалов и информации, необходимые для выполнения ее функций, осуществляются без непосредственного участия человека. К системам такого типа относятся: станки-автоматы, фасовочные автоматы, автоматы для съемки и изготовления фотографий, торговые автоматы и многое др.
В кибернетику, однако, вошел и прочно в ней укрепился термин
«дискретный автомат» или кратко просто «автомат» для обозначения гораздо более абстрактного понятия, а именно - модели, обладающей следующими особенностями: а) на входы модели в каждый из дискретных моментов времени t
1
, t
2
,… поступают m входных величин x
1
,x
2
,…x
m
. каждая из которых может принимать конечное число фиксированных значений из входного алфавита
Х; б) на выходах модели можно наблюдать n выходных величин y
1
,…y
n
каждая из которых может принимать конечное число фиксированных значений из выходного алфавита Y; в) в каждый момент времени модель может находиться в одном из состояний z
1
,z
2
,…z
n
; г) состояние модели в каждый момент времени определяется входной величиной x в этот момент и состоянием z в предыдущий момент времени; д) модель осуществляет преобразование ситуации на входе
x={x
1
,x
2
,…,x
m
} в ситуацию на выходе y={y
1
,y
2
,…,y
n
} зависимости от ее состояния в предыдущий момент времени.
Рисунок 3.1 – Дискретный автомат
Такая модель (рисунок 3.1) удобна для описания многих кибернетических систем.
Автоматы, у которых ситуация y на выходах однозначно определяется ситуацией х на входах, мы будем относить к классу автоматов без памяти.
Автоматы, у которых у зависит не только от значения х в данный момент, но и от состояния модели z, определяемого значениями х в предыдущие моменты времени, относятся к классу автоматов с конечной памятью.
A
Z
1
, Z
2
, ... x
1
x
2
x m
y
1
y
2
y n

67
Мы ограничимся рассмотрением лишь простейших из дискретных автоматов, входной и выходной алфавиты которых состоят всего из двух букв: 0 и 1. Это оправдывается тем что, как оказывается в теории автоматов, автоматы с такими "бедными" алфавитами способны решать такие же задачи, как и автоматы с любыми другими алфавитами.
Теория дискретных автоматов приобрела большое значение для решения некоторых фундаментальных проблем информатики, которые связаны с принципиальными возможностями переработки информации в ИС.
Логический автомат
Преобразования входных величин в выходные, осуществляемые дискретными автоматами без памяти, работающими в двухбуквенном алфавите, эквивалентны преобразованиям, совершаемым в формальной логике. Поэтому мы будем называть их логическими автоматами, а функции, описывающие преобразования, выполняемые логическими автоматами, - логическими функциями. Математическим аппаратом, используемым для решения задач анализа и синтеза логических автоматов, является алгебра логики. Первый вариант алгебры логики был разработан английским ученым Джорджем Булем в 1843 г., вследствие чего она часто называется булевой алгеброй.
Каждый выход из логического автомата может принимать значение 0 или 1 в зависимости от значений входных переменных х. Определим число всех возможных логических функций преобразования х
i
в y
i
, если число входных величин равно т, каждая из них может принимать значение 0 или 1.
Для этого расположим все входные величины в ряд x
1
, x
2
, …, x
m
и будем рассматривать их как разряды двоичного числа. Ясно, что число r различных сочетаний значений входных величин равно числу различных двоичных чисел, содержащих r разрядов, откуда следует, что r=2
m
. Но каждой из r ситуаций на входе может соответствовать одно из двух значений выхода 0 или 1. Поэтому общее число N всех различных логических функций для логического автомата с m двоичными входами равно
)
2
(
2 2
m
r
N


. (3.1)
Логические функции образуются из некоторых элементарных логических функций. Мы будем пользоваться тремя элементарными логическими функциями:
1.
- отрицание, инверсия x (читается «не x»). Функция отрицания означает, что x=0, если x=1; и x=1, если x=0.
2. x
1
˄ x
2
(x
1
& x
2
) - логическое умножение или конъюнкция (читается «x
1
и x
2
»). Функция логического умножения означает, что его результат равен единице только тогда, когда x
1
=1 и x
2
=1, и равен нулю во всех остальных случаях.
3. x
1
˅ x
2
(x
1
+ x
2
) - логическое сложение или дизъюнкция (читается «x
1
или x
2
»). Функция логического сложения означает, что его результат равен

68 нулю только тогда, когда x
1
=0 и x
2
=0 , и равен единице во всех остальных случаях.
Логические функции могут задаваться таблицами, в которых указывается значение функции у (индекс i будем опускать) для всех сочетаний аргументов х. В таблице 3.1 приведены значения двух элементарных логических функций от двух аргументов: x
1
и x
2
. Эту таблицу нужно читать по строкам: «если х
1
= ..., a х
2
= ..., то х
1
и х
2
=..., а х
1
или х
2
=
...». Логические функции широко используются в теории нейронных сетей и входят в математический аппарат, применяемый при исследованиях процессов переработки информации мозгом.
Таблица 3.1 – Задание логических функций таблицей
Функция
х
1
х
2
Примечание
00 01 10 11
f
0 0
0 0
0 f
0
– абсолютная ложь
f
1 0
0 0
1 х
1
^ x
2
(конъюнкция)
f
2 0
0 1
0
х
1

х
2
(запрет х
2
)
f
3 0
0 1
1
х
1

х
2 v х
1
х
2
(переменная х
1
)
f
4 0
1 0
0

х
1
х
2
(запрет х
1
)
f
5 0
1 0
1

х
1 х
2 v х
1 х
2
(переменная х
2
)
f
6 0
1 1
0
х
1

х
2
(сложение по модулю 2)
f
7 0
1 1
1 х
1
v х
2
(дизъюнкция)
f
8 1
0 0
0
х
1

х
2
(функция Пирса или "стрелка Пирса")
f
9 1
0 0
1
х
1

х
2
(равнозначность)
f
10 1
0 1
0

х
1

х
2 v х
1

х
2
(переменная

х
2
)
f
11 1
0 1
1
х
2

х
1
(импликация)
f
12 1
1 0
0

х
1

х
2 v

х
1
х
2
(переменная

х
1
)
f
13 1
1 0
1
х
1

х
2
(импликация)
f
14 1
1 1
0 х
1
/х
2
(функция Шеффера или "штрих Шеффера")
f
15 1
1 1
1 f
1
– абсолютная истина
Из элементарных логических функций можно составлять логические функции, описывающие свойства различных логических автоматов.
Логические элементы выполняют преобразования информации, которые описываются логическими функциями (таблица 3.1). Условные графические обозначения (УГО) элементов И, ИЛИ и НЕ на функциональных схемах приведены на рисунке 3.2.
Условное графическое обозначение элемента выполняют в виде прямоугольника, в левом верхнем углу которого указывают обозначение выполняемой функции. Входы элемента обозначают линиями слева, выходы
– справа. Инверсный выход обозначается кружком (рисунок 3.2в)

69
Рисунок 3.2 – Стандартные логические элементы
а – элемент И, б – элемент ИЛИ, в – элемент НЕ
Элементы И, ИЛИ и НЕ составляют функционально полную систему, т.е. из них можно составить любую комбинационную (логическую) схему.
Логические элементы, выполненные в виде интегральных схем, обычно реализуют логические функции И—НЕ (штрих Шеффера) или ИЛИ—НЕ
(стрелка Пирса). Каждый из этих элементов обладает свойством функциональной полноты. Обозначения элементов И—НЕ и ИЛИ—НЕ на функциональных схемах, а также примеры их реализации приведены на рисунке 3.3.
Рисунок 3.3 – Логические элементы И-НЕ, ИЛИ-НЕ
а – элемент И-НЕ на три входа, б – элемент ИЛИ-НЕ на три входа,
в – принципиальная электрическая схема И-НЕ транзисторно-транзисторной логики, г – принципиальная электрическая схема И-НЕ на МОП- транзисторах
Элементы И на два входа часто используют в качестве ключей
(вентилей), которые управляют передачей данных между двумя схемами
(рисунок 3.4).

70
При передаче одноразрядных данных (рисунок 3.4а) один вход элемента И является информационным, а второй — управляющим. На информационный вход поступают одноразрядные данные D от источника А.
Если на управляющем входе сигнал «Передать» равен «0», то на приемник В поступает сигнал «0» независимо от значения данных D. Если сигнал
«Передать» равен «1», то сигнал на выходе элемента И совпадает с информационным сигналом и на вход приемника поступают данные D.
При передаче многоразрядных данных (рисунок 3.4б) каждый разряд данных проходит через отдельный элемент И, а сигнал «Передать» подается одновременно на управляющие входы всех ключей.
Рисунок 3.4 – Схемы передачи данных
а – одноразрядных, б – многоразрядных
Автомат с конечной памятью. Триггеры
При изучении автоматов с конечной памятью обычно интересуются только установившимися состояниями, которые они принимают через достаточно большое время после изменения входных воздействий. Процессы перехода системы из одного установившегося состояния в другое здесь полагаются протекающими достаточно быстро по сравнению с интервалами времени между изменениями входных воздействий. Поэтому поведение автомата с конечной памятью удобно рассматривать в дискретные моменты времени t
1
, t
2
, ..., отделенные друг от друга интервалами

t. При этом мы будем полагать, что и выходные воздействия могут изменяться только в моменты t
1
, t
2
, ..., которые называются тактами.
В соответствии с определением выход автомата с конечной памятью в
j-й такт зависит от состояния автомата в (j-1)-й такт и состояния входов в j-й такт. Поэтому переходы такого автомата из одного состояния в другое, в общем виде, описываются выражениями








),
,
(
),
,
(
1 1
j
j
j
j
j
j
x
z
G
z
x
z
F
y
(3.2) где y
j
- выход автомата в j-й такт зависит от состояния автомата в (j-1)-й такт,
z
j-1
- состояние автомата в (j-1)-й такт.


j
m
j
j
j
x
x
x
x
,...,
,
2 1

(3.3)

71
x
j
- вход автомата в j-й такт, F и G - некоторые логические функции состояния выхода и входа.
Для того, чтобы автомат осуществлял преобразование (3.2), необходимо, чтобы он, кроме элементов, реализующих логические функции, содержал также элемент задержки, выход которого определяется значением его состояния в предыдущий такт, т. е. элемент, выход которого у связан с входом х выражением
)
(
1


j
j
z
f
y
(3.4) или, в частности,
1


j
j
z
y
(3.5)
Элемент задержки должен обладать памятью, в нем должен сохраняться след предыдущего состояния, ибо иначе его состояние не могло бы зависеть от предыдущего состояния.
Одним из распространенных дискретных элементов, обладающих памятью, является триггер, представляющий собой устройство с двумя устойчивыми состояниями. Это устройство может переходить из одного состояния в другое под воздействием сигнала управления.
Рассмотрим в качестве примера автомата с конечной памятью схему электронного счетчика, применяемого в цифровых вычислительных устройствах (рисунок 3.5). Задача этой схемы состоит в подсчете количества импульсов, поступивших на ее вход, т.е. в преобразовании количества импульсов в двоичный код числа, выражающего это количество.
Для этой цели образуем цепь из триггеров, показанную на рисунке.
Здесь выход каждого предыдущего триггера соединен с входом последующего. Пусть сначала все триггеры находятся в нулевом состоянии, т.е. напряжение на их выходах равно U
0
. При поступлении первого импульса на вход триггера Т
1
на его выходе появится напряжение U
1
, и на входе триггера T
2
, положительный импульс напряжения, на который он не реагирует. Второй импульс заставит T
1
вернуться в нулевое состояние, в результате чего напряжение на его выходе изменит свое значение с U
1
на U
0
, что вызовет отрицательный импульс на входе T
2
и его переход в единичное состояние. Таким образом, T
1
будет изменять свое состояние после каждого входного импульса, T
2
после каждого второго импульса, T
3
- после каждого четвертого и т.д., T
k
- после каждого 2
k-1
импульса на входе схемы. Если теперь мы будем состояние каждого триггера рассматривать как значение соответствующего разряда двоичного числа, то состояние всей цепи из r триггеров будет представлять собой число (в двоичной системе счисления) импульсов, поступивших на вход схемы.
Pисунок 3.5 – Счетчик импульсов на триггерах
T
r
T
2
T
1
U
вх
U
вых 1
U
вых 2
U
вых (r-1)
U
вых r
…
Ø
Ø

72
Емкость этой схемы - максимальное число R импульсов, которые могут быть ею сосчитаны, определяется числом r триггеров и равно максимальному двоичному числу, состоящему из r разрядов, а именно R=2
r
Все современные серии цифровых микросхем, как правило включают различные типы триггеров, представляющих устройство с двумя устойчивыми состояниями, содержащее бистабильный запоминающий элемент (ячейку) и схему управления.
Основу триггера составляет бистабильная ячейка, имеющая два устойчивых состояния. Бистабильные ячейки могут быть построены на двух логических элементах И—НЕ или ИЛИ—НЕ, соединенных перекрестными связями (рисунок 3.6).
Существование двух устойчивых состояний бистабильной ячейки объясняется наличием в ее схеме обратных связей, позволяющих сигналу с выхода элемента поступать на его же вход через второй элемент. Так, если на рисунке 3.6а, сигнал на верхнем выходе равен«1» и на оба входа подается сигнал «0», то сигнал «1» с выхода элемента 1 поступает на вход элемента 2 и формирует на его выходе сигнал «0». Этот сигнал поступает на вход элемента 1 и поддерживает такое состояние схемы, делая его устойчивым. В этом состоянии на выходе элемента 1 сигнал равен «1», а на выходе элемента
2 сигнал равен «0».
Рисунок 3.6 – Бистабильная ячейка
а – на элементах ИЛИ-НЕ, б – на элементах И-НЕ
Для изменения состояния схемы необходимо подать на верхний вход элемента 1 сигнал «1». При этом на выходе элемента 1 сигнал становится равным «0». Тогда на выходе элемента 2 формируется сигнал «1», который вместе с единичным входным сигналом устанавливает выходной сигнал элемента 1 равным «0». Такое состояние схемы также является устойчивым и после того, как сигнал на входе элемента 1 станет равным «0». В этом состоя- нии на выходе элемента 1 сигнал равен «0», а на выходе элемента 2 — «1».
При поступлении сигнала «1» на вход элемента 2 происходит возвращение схемы в начальное состояние. Таким образом, схема имеет два устойчивых

73 состояния, которые можно устанавливать подачей сигнала «1» на вход элемента 1 или 2. Аналогично работает бистабильная ячейка на элементах
И—НЕ (рисунок 3.6б).
Кроме бистабильной ячейки в состав триггера входит схема управления
(рисунок 3.7). Схема управления — это комбинационная схема, при помощи которой осуществляется запись информации в триггер (изменение состояний триггера). Конкретный вид схемы управления зависит от типа триггера.
Рисунок 3.7 – Общая структура триггера
Триггер имеет два выхода: прямой и инверсный (Q и

Q). Сигналы на выходах триггера всегда имеют различные значения. Если на прямом выходе сигнал равен «1», то на инверсном — «0» и наоборот. Состояние триггера определяется значением сигнала на прямом выходе (Q). Если сигнал на прямом выходе равен «1», то триггер находится в состоянии «1». Можно также сказать, что состояние триггера — это информация, записанная в триггере. Таким образом, если триггер находится в состоянии «1», то в нем записана единица.
Входы триггеров, как и сигналы, подаваемые на них делятся на информационные и вспомогательные. Информационные сигналы через соответствующие входы управляют состоянием триггера. Сигналы на вспомогательных входах служат для предварительной установки триггера в заданное состояние и его синхронизации. Вспомогательные входы могут при необходимости выполнить роль информационных. По способу приема информации триггеры подразделяют тактируемые (синхронные) и нетактируемые
(асинхронные) триггеры.
Изменение состояния нетактируемого (асинхронного) триггера происходит сразу же после соответствующего изменения потенциалов на его управляющих входах.
В тактируемом (синхронном) триггере изменение состояния может произойти только в момент присутствия соответствующего сигнала на тактовом входе. Если сигнал синхронизации равен «0», состояние синхронного триггера не изменится при любых значениях сигналов на его входах.
Тактирование может осуществляться импульсом (потенциалом) или фронтом (перепадом потенциала). В первом случае сигналы на управляющих входах оказывают влияние на состояние триггера только при разрешающем потенциале на тактовом входе. Во втором случае воздействие управляющих сигналов проявляется только в момент перехода единица - нуль или нуль -

74 единица на тактовом входе. Существуют также универсальные триггеры, которые могут работать как в тактируемом, так и в нетактируемом режиме.
Основные типы триггеров в интегральном исполнении носят следующие названия: D-триггеры, Т-триггеры, RS-триггеры и JK-триггеры.