Поняття про інформацію та її види. Три підходи до вивчення теорії


с. 1 с. 2 ... с. 10 с. 11

Поняття про інформацію та її види. Три підходи до вивчення теорії інформації. Порівняння аналогової та цифрової обчислювальної техніки

Інформацію назив. відомістю, які можна отримати, передати, керувати, обробляти, зберігати.

Інформація є міра різноманітності або однорідності в матеріалі , речовині та енергії у просторі та часі.

Порівняння АТ та ЦТ

1. Точність АТ=102/1=103/1=104/1

Відношення Сигнал/Завада ЦТ=1010/1

2. Швидкодія

АТ властивий паралельний алгоритм роботи.

3. Універсальність

ЦОМ – універсальні,спеціалізовані ,а АОМ – спеціалізовані

4. Вартість


3 підходи до вивчення теорії інформації:

1. Структурна теорія інформації

2. Статистична (поняття ентропії)

3. Семантична (Акад. Маркевич О.О. Вартість інфи тим вища, чим більше змін робиться в сфері керування)


Поясніть, у чому полягає зміст та значення теореми Котельникова.

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

Кожний процес має обмеження на частоту спектра Fm.

Согласно теореме В.А.Котельникова, если функция s(t) не содержит частот выше некоторой Fm, то она полностью определяется своими мгновенными значениями в моменты времени, отстоящими друг от друга на величину


1/(2Fm ), т.е.

,

где k - порядковый номер отсчета функции; t = 1/(2Fm) - шаг дискретизации по времени,sk = s(tk) - мгновенные значения сигнала s(t) в k-ой отсчетной точке tk = k/m = k/(2Fm) = kt.

Из этой теоремы следует, что для однозначного представления функции с ограниченным спектром на интервале времени Т достаточно иметь некоторые n значений этой функции, где
n = T / t = 2FmT.
При выполнении этого равенства (условия) непрерывная и дискретная функции обратимы между собой, т.е. тождественны. Таким образом, произвольный сигнал, спектр которого не содержит частот выше Fm может быть представлен в виде последовательности импульсов, амплитуда которых равна значению исходного сигнала в дискретные моменты времени kt= а интервалы между ними t = 1/(2Fm).

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



Основні ознаки алгоритму. Навести підхід до формального визначення алгоритму. Універсальні формальні алгоритмічні системи. Основна гіпотеза теорії алгоритмів.



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

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

Ознаки алгоритму:


  1. Справа з даними (вхідні, провідні, вихідні)

  2. Пам'ять для зберігання

  3. Алгор. виконується по кроках, к-ть яких скінченна

  4. Алгор. мусить бути детермінований

  5. Результативність

Більш строге визначеня можна дати в рамках теорії Формальних Алгор. Системах (ФАС):

  1. Рекурсивні ф-ції

  2. Машина Тюрінга

  3. Машина Поста

  4. Нормальні алгор. Маркова

  5. Схема Колмагорова

  6. Цифрові автомати Мілі та Мура

  7. Сист Черкаського

Основна гіпотеза теорії алгоритмів: будь-який алгор.. може бути використаний із допомогою ФАС.

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



Автомат. Класифікація автоматів. Поняття про модель цифрового автомата типу Мілі та Мура.



Цифровой автомат это устройство, характеризующееся набором некоторых внутренних состояний A = {a1(t), a2(t), ..., an(t)}= в которые оно попадает под воздействием входных сигналов и команд программы решения задачи.

Пусть имеется автомат с одним входом и одним выходом:


A = {ai(t)}

z(t) (t)



Рис.1.3. Цифровой автомат


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

Синхронный автомат характеризуется тем, что функционирует под управлением тактовых (или синхронизирующих) сигналов - ТС, с постоянной длительностью tТС и постоянной частотой fТС, если квантование времени равномерное. Такт (квант) времени ti совмещается с фронтом i-того сигнала ТС. Входные сигналы могут воздействовать на автомат лишь при наличии сигнала ТС и не изменяются в течение tТС. Период следования сигналов ТС должен быть больше или равен времени, которое необходимо реальному автомату для перехода из одного состояния в другое. Когда рассматривается абстрактный автомат, то считается, что изменение внутренних состояний автомата происходит в интервалы времени между смежными ТС, а выходные сигналы формируются по фронту очередного ТС.

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

Как отмечалось в главе 1, абстрактный автомат с одним входом и одним выходом можно представить следующим образом:

A
X Y



Для задания конечного автомата фиксируются три конечных множества (алфавита):

- множество возможных входных сигналов:

X = {x1, x2, ..., xm};

- множество возможных выходных сигналов:

Y = {y1, y2, ..., yk};

- множество возможных внутренних состояний автомата:

A = {a0, a1, ..., an}.

На этих множествах задают два логических оператора:

- функцию переходов f, определяющую состояние автомата a(t + 1) в момент дискретного времени t + 1 в зависимости от состояния автомата a(t) и значения входного сигнала x(t) в момент времени t:

a(t + 1) = f[a(t), x(t)]; (10.1)

- функцию выходов , определяющую зависимость выходного сигнала автомата y(t) от состояния автомата a(t) и входного сигнала x(t) в момент времени t:

y(t) =  [a(t), x(t)]. (10.2)

Кроме того, на множестве состояний автомата фиксируют одно из внутренних состояний а0 в качестве начального состояния.

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

Работу абстрактного автомата следует рассматривать применительно к конкретным интервалам времени, т.к. каждому интервалу дискретности t будет соответствовать свой выходной сигнал y(t). Следовательно, функционирование автомата рассматривается через дискретные интервалы времени конечной продолжительности. В абстрактной теории цифровых автоматов считается, что входные сигналы воздействуют на синхронный автомат в момент начала каждого i-того интервала (кванта) времени, выделенного соответствующим синхроимпульсом (тактом), а изменение внутренних состояний автомата происходит в интервалы времени между смежными синхроимпульсами, когда нет воздействия входных сигналов.

Операторы, описывающие работу автомата, обычно задают таблицей переходов и таблицей выходов.

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

К примеру, рассмотрим таблицы переходов и выходов некоторого автомата.

Таблица переходов автомата



Входной

Состояние

сигнал

a0

a1

a2

a3

x1

a1

a2

a3

a3

x2

a0

a0

a0

a0

Таблица выходов автомата

Входной

Состояние

сигнал

a0

a1

a2

a3

x1

y2

y2

y1

y2

x2

y2

y2

y2

y3

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

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

Таблица переходов и выходов автомата



Выходной

Cостояние

сигнал

a0

a1

a2

a3

x1

a1

y2



a2

y2



a3

y1



a3

y2



x2

a0

y2



a0

y2



a0

y2



a0

y3


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

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

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

В настоящее время в классе синхронных атоматов рассматривают, в основном, два типа автоматов: автомат Мили и автомат Мура.

Графа атомата Мили, заданного вышеприведенными таблицами, отражен на рис. 10.1. Закон функционирования автоматов Мили может быть задан следующим образом:

a(t + 1) = f[a(t), x(t)];

y(t) =  [a(t), x(t)],

где t = 1, 2, .....

Отличительная особенность автоматов Мили состоит в том, что их выходные сигналы в некоторый момент времени не зависят как от состояния автомата, так и от значения входного сигнала в этот же момент времени.


Рис. 10.1. Граф автомата Мили.

У автоматов Мура выходные сигналы в момент времени t однозначно определяются состоянием автомата в этот же момент времени и в явном виде не зависят от значения входных сигналов xi(t).

Функции переходов и выходов автомата Мура, заданного на множестве входных сигналов X, множестве внутренних состояний A = {a0, a1, ,an} и множестве выходных сигналов Y, можно записать в виде


a(t + 1) = f[a(t), x(t)], (10.3)

y(t) =  [a(t)]. (10.4)


эти операторы удобно задавать отмеченной таблицей переходов.

Такие таблицы строятся так же, как и таблицы переходов автомата Мили, но над символами каждого внутреннего состояния записываются выходные сигналы, которые выдает автомат в данном состоянии.

Отмеченная таблица переходов автомата





Выходной сигнал




y2

y2

y2

y1

y2

y3

Входной

Состояние

сигнал

a0

a1

a2

a3

a4

a5

x1

a1

a2

a3

a4

a4

a1

x2

a0

a0

a0

a5

a5

a0

Граф автомата Мура, заданного этой таблицей, приведен на рис. 10.2.

На этом рисунке состояния автомата обозначаются сиволами bi.

На графах автомата Мура значения выходных сигналов записываются около узлов.



Рис. 10.2. Автомат Мура.

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

Помимо автоматов Мили и Мура выделяют еще, так называемый, совмещенный автомат - С-автомат. Абстрактный С-автомат можно представить в виде устройства с одним входом, на который поступают входные сигналы X, и двумя выходами, на которых появляются выходные сигналы Y и U.


A
Y рис. 10.3

X

U

Здесь X - входной алфавит; A - множество состояний; Y - выходной алфавит первого типа; U = {u1(t) ... um(t)} - выходной алфавит второго типа.

Отличие С-автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции выходов 1 и 2, каждая из которых характерна для этих моделей в отдельности. Этот автомат можно описать следующей системой уравнений:

a(t+1) = f [a(t), x(t)]; (10.5)

y(t) = 1[a(t), x(t)];

u(t) = 2[a(t)].

Выходной сигнал u = 2(as) выделяется все время, пока автомат находится в состоянии as. Выходной сигнал yk = 1(as, xn) выдается во время действия входного сигнала xn при нахождении автомата в состоянии as. От С-автомата легко перейти к автоматам Мили или Мура (с учетом возможных сдвигов во времени на один такт), так же как возможна трансформация автомата Мили в автомат Мура и наоборот.


с. 1 с. 2 ... с. 10 с. 11

скачать файл