Основные параметры, характеристики и свойства ИС

Описание машины Тьюринга

Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: q_ia_j→q_i1a_j1d_k (если головка находится в состоянии qi, а в обозреваемой ячейке записана буква a_j, то головка переходит в состояние q_i1, в ячейку вместо a_j записывается a_j1, головка делает движение d_k, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации <q_i, a_j> имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

Варианты машины Тьюринга

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

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

По типу канала связи ИС можно разделить на:

Классификация. По архитектуре: локальные (все компоненты находятся на одном компьютере) и распределённые (компоненты распределены по разным компьютерам). По степени автоматизации: автоматизированные (требуется постоянное вмешательство персонала) и автоматические (вмешательство требуется эпизодически). По характеру обработки данных: информационно-поисковые и ИС обработки данных.

Важнейшей характеристикой ИС является алфавит, с помощью которого генерируются сообщения. В общем случае алфавит состоит из символов (букв) A{a_i}. Если количество символов в алфавите конечно, то такой алфавит называется конечным (дискретным). РС оперирует алфавитом состоящим из 2-ух символов А{0,1}. Число символов ИС наз. мощностью алфавита. В РС алфавит наз. бинарным, а в ИС – двоичным.

Важнейшей характеристикой алфавита явл. энтропия(мера неопреднлённости, неупорядоченности). Энтропия алфавита есть среднее количество информации, кот. соответствует одному символу алфавита.

р(а_i)=частота выпадений/общее число опытов Σр(a_i)=1

В англ. алф. больше всего встречается Е, р(Е)=0,13, меньше всего Z, р(Z)=0,0007.

Формула для определения энтропии, предложенная К. Шеннонам:

Энтропия алфавита при равновероятном появлении любого из N символов в сообщении зависит исключительно от мощности алфавита (энтропия по Хартли, как частный случай по К. Шеннону):

Для англ. алф. Н(А_англ)=4.7 bit, для двоичного Н(А₂)=1 bit.

Количество инф-ции определяется по формуле:

I(X_K)=K*H(A) [bit] К – кол-ва символов, Н(А)- энтропия авфавита

На клавиатуре исп. табл. Кодов ASCII. В ней каждый символ соответствует 1В или 8b. Т. е. а_i => 1B => 8b. Это означает, что сообщение преобразованное в двоичную форму характеризуется инф. избыточностью, как и любое др. сообщение.