ПОНЯТИЕ ИНФОРМАЦИИ И ПОДХОДЫ К ЕЕ КОЛИЧЕСТВЕННОЙ ОЦЕНКЕ

ПОНЯТИЕ ИНФОРМАЦИИ И ПОДХОДЫ К ЕЕ КОЛИЧЕСТВЕННОЙ ОЦЕНКЕ

Понятие и виды информации

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

Поэтому говорят о доопытной (или априорной) информации и послеопытной (т.е. апостериорной) полученной, в итоге эксперимента.

Для человека любое восприятие реальных объектов окружающей действительности происходит через ощущения. Органы чувств человека и высшая нервная система позволяют ему воспринимать объекты. При обмене информацией имеют место источник в виде объекта материального мира и приемник - человек либо какой-то материальный объект. Информация возникает за счет отражения, которое является свойством всей материи, любой материальной системы. Свойство отражения совершенствуется по мере развития материи от элементарного отражения до высшей его формы - сознания. Процесс отражения означает взаимодействие объектов материального мира. Этот процесс наиболее прост в неорганической природе. Здесь преобладают механические, химические и физические взаимодействия. При таком отражении объекты пассивны. Новые формы отражения (физиологическое и психологическое) возникают в органической природе. В живом организме на основе отражения формируется способность приспосабливаться к изменяющимся окружающим условиям. У человека получают развитие более сложные формы отражения: познавательная и творческая. Эти формы носят сознательный характер и позволяют человеку активно воздействовать на окружающий мир.

Выделяют следующие аспекты информации:

- прагматический,

- семантический,

- синтаксический.

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

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

Синтаксический аспект информации связан со способом ее представления. В зависимости от реального процесса, в котором участвует информация, т.е. осуществляется ее сбор, передача, преобразование, отображение, представление, ввод или вывод, она представляется в виде специальных знаков, символов. Характерным носителем информации является сообщение, под которым обычно понимают все то, что подлежит передаче. Сообщения представляют в виде электрического сигнала, передаваемого по выбранной физической среде. Для этого сообщение подвергают преобразованию, т. е. придают ему электрический характер, далее кодированию, при котором сообщение превращается в некоторую. последовательность символов, однозначно его отображающих, и модуляции, при которой каждый элемент кода (либо код в целом) переводится в электрический сигнал, способный передаваться на заданное расстояние по выбранному каналу связи. Процессы преобразования, кодирования и модуляции исключительно многообразны, а синтаксический аспект информации при ее передаче в настоящее время хорошо развит. Иной характер синтаксический аспект имеет, например, при хранении информации. В этом случае могут быть предложены такие формы, при которых удается осуществить быстрый поиск, введение новой информации, вывод требуемой информации из информационной базы и в целом обновления базы данных. Требуемому представлению информации при ее хранении отвечают разработанные к настоящему времени типовые структуры баз и банков данных, которые позволяют наилучшим образом реализовать информационное обслуживание пользователей в системе управления. Таким образом, развитие общества привело к тому, что оказалось необходимым хранить, обрабатывать, передавать, преобразовывать огромные объемы данных.

Виды информации

Все виды деятельности человека по преобразованию природы и общества сопровождались получением новой информации. Логическая, адекватно отображающая объективные закономерности природы, общества и мышления получила название научной информации. Ее делят по областям получения или пользования на следующие виды: политическую, техническую, биологическую, химическую, физическую и т.д.; по назначению- на массовую и специальную. Часть информации. которая занесена на бумажный носитель, получила название документальной информации. Любое производство при функционировании требует перемещения документов, т.е. возникает документооборот. Для автоматизированных систем управления информация в документах составляет внешнее информационное обеспечение. В то же время большая часть информации хранится в памяти ЭВМ на магнитных лентах, дисках и т.д. Она определяется как внутримашинное информационное обеспечение.

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

Информация с точки зрения ее возникновения и совершенствования проходит следующий путь: человек наблюдает некоторый факт окружающей действительности, это факт отражается в виде совокупности данных, при последующем структурировании в соответствии с конкретной предметной областью данные превращаются в знания. Таким образом, верхним уровнем информации как результата отражения окружающей действительности (результата мышления) являются знания. Знания возникают как итог теоретической и практической деятельности. Информация в виде знаний отличается высокой структуризацией. Это позволяет выделить полезную информацию при анализе окружающих нас физических, химических и прочих процессов и явлений. На основе структуризации информации формируется информационная модель объекта. По мере развития общества информация как совокупность научно-технических данных и знаний превращается в базу системы информационного обслуживания научно-технической деятельности общества.

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

Понятие сообщения и кода

Сведения о состоянии объекта в ИС формируются в виде сообщений. Под сообщением понимается все то, что подлежит передаче. Независимо от содержания сообщение обычно представляется в виде электрического, звукового, светового, механического или других сигналов. Таким образом, сообщение отображает некоторые исходные сигналы любого вида и по свойствам зависит от исходных сигналов.

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

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

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

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

2) непрерывную функцию дискретного аргумента. Обычно такие сигналы возникают при квантовании непрерывных величин по времени. В этом случае задаются некоторые фиксированные моменты времени t_J, отсчитываемые через интервал Dt. который обычно определяется спектральными свойствами исходного физического процесса. Функция f(t_J) может принимать любые мгновенные значения, но она определяется лишь для дискретных значении времени. Этот вид сигналов и связанных с ним функций имеет место при формировании исходных сообщений из непрерывных величин;

3) дискретную функцию непрерывного аргумента f_J(t). В этом случае функция имеет ряд конечных дискретных значений, однако определена на всем отрезке времени t для любого мгновенного значения времени. Дискретизация самой функции связана с созданием шкалы квантования по уровню, что свойственно различным датчикам, при этом шаг квантования определяется требуемой точностью воспроизведения исходной величины;

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

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

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

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

1. По основанию системы счисления коды делятся на двоичные, троичные, четверичные и т.д. В каждой системе счисления используется определенная совокупность символов, причем число возможных символов для К-ой системы равно К. Двоичные коды строятся с помощью символов 0,1; троичные-0,1,2, при этом нуль означает отсутствие передачи информации по каналу, т.е. отсутствие импульса, единица означает символ с одним значением сигнального признака, двойка- с другим. Под сигнальным признаком понимается некоторое значение тока или напряжения, позволяющее отличить один символ от другого.

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

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

3. По наличию избыточности коды делятся на избыточные и неизбыточные. Для неизбыточных кодов характерно то, что при каждом отображении сообщения кодовой комбинацией для числа М возможных кодовых комбинаций, основным свойством является возможность их различения. Тогда код при основании системы счисления К может быть построен как отображение множества десятичных чисел от нуля до М-1 с числом разрядов n в каждой кодовой комбинации. Например, для М=4 двоичный избыточный код может быть получен при представлении чисел 0,1,2,3 двухэлементным двоичным кодом: 00,01,10,11 соответственно. Переход от К-го числа к десятичному можно осуществить по формуле:

где n-число элементов в коде, или длина кода: К- основание системы счисления кода: a_J- значение символа в J-м разряде, причем младшим является разряд, расположенный справа. Следует отметить, что символы кода в линии связи и передаются в обратном порядке, т.е. сначала старший разряд и далее остальные.

Если необходимо представить, например, четыре сообщения троичным неизбыточным кодом, то исходные десятичные числа 0,1,2,3 запишем в виде 00,01,02,10. В общем случае m-элементным неизбыточным кодом в К-ой системе счисления можно представить М=К^m сообщений. Например, при двухэлементном неизбыточном троичном коде можно иметь 3²=9 сообщений.

Переход от неизбыточного кода к избыточному при использовании систематических кодов осуществляется путем добавления некоторых контрольных позиций, которые можно получить либо путем различных логических операций, выполняемых над основными информационными позициями, либо путем использования детерминированных алгоритмов, связывающих избыточный и неизбыточный коды. Например, если нужно перейти от неизбыточного кода к простейшему избыточному, то для случая двоичного кода, рассчитанного на четыре сообщения, отображением которых являются кодовые комбинации 00,01,10,11, достаточно ввести одну контрольную позицию, значение символа на которой будет определяться как сумма значений предшествующих символов по модулю два. Эта логическая операция в двоичной системе определяется равенствами 0 0=0, 1 1=0, 0 1=1, 1 0=1. Для рассматриваемых сообщений получаем 000, 011, 101, 110. Особенность такого кода заключается в том, что он позволяет обнаружить любую одиночную ошибку. Таким образом, отличие неизбыточных кодов от избыточных состоит в том, что из-за отсутствия избыточности они не способны обнаруживать ошибки и поэтому не могут быть использованы для передачи информации по каналам с шумом. С целью обеспечения достоверной передачи информации по каналу связи при заданных вероятностно-временных ограничениях необходимо вводить избыточность в код, что можно осуществить путем использования дополнительных контрольных позиций.

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

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

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

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

Логический автомат

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

Каждый выход ид логического автомата может принимать значе­ние 0 или 1 в зависимости от значений входных переменных х. Оп­ределим число всех возможных логических функций преобразования х в , если входных величин равно т, каждая из них может прини­мать значение 0 или 1. Для этого расположим все входные величины в ряд и будем рассматривать их как разряды двоич­ного числа. Ясно, что число r различных сочетаний значений вход­ных величин равно числу различных двоичных чисел, содержащих г разрядов, откуда следует, что . Но каждой из г ситуаций на входе может соответствовать одно из двух значений выхода 0 или 1. Поэтому общее число N всех различных логических функций для ло­гического автомата с m двоичными входами равно

(3. 1)

Логические функции образуются из некоторых элементарных ло­гических функций. Мы будем пользоваться тремя элементарными ло­гическими функциями:

1. х - отрицание x (читается "не x"). Функция отрицания оз­начает, что , если =1; и =1, если .

2. - логическое умножение или конъюнкция (читается " и "). Функция логического умножения означает, что его резуль­тат равен единице только тогда, когда и равен нулю во всех остальных случаях.

3. - логическое сложение или дизъюнкция (читается " или "). Функция логического сложения означает, что его ре­зультат равен нулю только тогда, когда и , и равен еди­нице во всех остальных случаях.

Логические функции могут задаваться таблицами, в которых указывается значение функции у (индекс i будем опускать) для всех сочетаний аргументов х. В табл.3.1 приведены значения двух элементарных логических функций от двух аргументов: и . Эту таблицу нужно читать по строкам: " если =..., a =..., то и =..., а или =...". Логические функции широко используются в теории нейронных сетей и входят в математический аппарат, применяемый при исследованиях процессов переработки информации мозгом.

Таблица 3.1

Из элементарных логических функций можно составлять логи­ческие функции, описывающие свойства различных логических авто­матов.

Автомат с конечной памятью

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

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

(3.2)

где - выход автомата в j-й такт зависит от состояния ав­томата в (j-l)-й такт, - состояние автомата в (j-1)-й такт.

(3.3)

- вход автомата в j-й такт, F и G - некоторые логические функции состояния выхода и входа.

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

(3.4)

или, в частности

(3.5)

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

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

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

1) состояние : триод Л1 открыт (потенциал на сетке поло­жителен); анодный ток I_а1 велик: напряжение (U_a1 мало; триод Л2заперт (потенциал сетки отрицателен); анодный ток I_а2 - мал; напряжение на выходе Uвых велико Uвых=U₁;

2) состояние : триод Л1 закрыт (потенциал на сетке отри­цателен; анодный ток I_а1 мал: напряжение U_a1 велико: триод Л2открыт (потенциал сетки положителен); анодный ток I_a2 велик; напряжение на выходе мало, Uвых=U₀. Эту схему можно переводить из состояния в состояние , воздействуя на ее вход. При пос­туплении импульса напряжения на вход схемы он, проходя через конденсатор С, преобразуется в два импульса: положительный и отрицательный. Параметры схемы подобраны так, что положительный импульс не оказывает влияния на ее работу, а отрицательный запи­рает открытый триод, что в свою очередь приводит к отпиранию ра­нее запертого триода, т.е. к переходу схемы в другое устойчивое состояние. Таким образом, каждый управляющий импульс изменяет состояние схемы и каждый четный импульс возвращает ее в исходное состояние.

Условимся считать нулем малое напряжение на выходе триггеpa, а единицей - большое. Очевидно, выход триггера в j-й момент времени (j-й такт) однозначно определяется его состоянием . Поэтому зависимость выхода триггера от входа в настоящий момент и от состояния в предыдущий момент можно выразить как зависи­мость от входа в настоящий, момент и от выхода в предыдущий мо­мент Таким образом, триггер осуществляет функцию задержки, т.е. запоминания состояния. Переходы триггера показаны в табл.3.2.

Таблица 3.2

Из таблицы вытекает следующее выражение для логической функции перехода триггера

(3.6)

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

Для этой цели образуем цепь из триггеров, показанную на ри­сунке. Здесь выход каждого предыдущего триггера соединен с вхо­дом последующего. Пусть сначала все триггеры находятся в нулевом состоянии, т.е. напряжение на их выходах равно U₀. При поступле­нии первого импульса на вход триггера Т₁, на его выходе появится напряжение U₁, и на входе триггера T₂, положительный импульс нап­ряжения, на который он не реагирует. Второй импульс заставит T₁, вернуться в нулевое состояние, в результате чего напряжение на его выходе изменит свое значение с U₁ на U₀, что вызовет отрица­тельный импульс на входе T₂ и его переход в единичное состояние. Таким образом, T₁ будет изменять свое состояние после каждого входного импульса, T₂, после каждого второго импульса, T₃ - после каждого четвертого и т.д., - после каждого импульса на входе схемы. Если теперь мы будем состояние каждого триггера рассматривать, как значение соответствующего разряда двоичного числа, то состояние всей цепи из г триггеров будет представлять собой число (в двоичной системе счисления) импульсов, поступивших на вход схемы.

Pис.3.3 Счетчик импульсов на триггерах

Емкость этой схемы - максимальное число R импульсов, кото­рые могут быть ею сосчитаны, определяется числом г триггеров и равно максимальному двоичному числу, состоящему из г разрядов, а именно R= .

Нормальный алгоритм Маркова

По аналогии с интуитивным определением алгоритма определим понятие "алгоритм в алфавите А":

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

Алгоритм применим к некоторому слову Р, если, отправляясь от этого слова и действуя согласно предписаний, мы получим в конце концов новое слово Q, на котором процесс оборвется. Будем тогда говорить, что алгоритм перерабатывает Р в Q.

Например, следующее предписание удовлетворяет нашему определению. Перепиши заданное слово, начиная с конца. Полученное слово есть результат. Остановка. Этот алгоритм представляет со­бой совершенно точное предписание, применимое к любому слову.

Однако определение I слишком широко: уточнение понятия "ал­горитм в алфавите А " связано с использованием аппарата подстано­вок, т.е. с построением ассоциативного исчисления.

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

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

Приведем пример алгоритма в алфавите А в смысле II.

Пусть алфавит А содержит три буквы: А = {а, b, с}, а алгоритм определен с помощью системы подстановок

cd - cc,

cca - ad,

ab - bca

и следующего указания о способе применения этих подстановок: исходя из произвольного слова Р, следует просмотреть схему подстановок в том порядке, в каком они выписаны, разыскивая первую формулу, левая часть которой входит в Р. Если же такой формулы не найдется, то процесс обрывается сразу же. В противном случае берется первая из найденных формул и делается подстановка ее правой части вместо первого вхождения ее левой части в слово Р, что дает новое слово Р₁, в алфавите А. Затем слово Р₁ играет роль Р, т.е. вновь берется в качестве исходного, и процесс повторяет­ся. Остановка наступает в том случае, если на n-м шаге получено слово P_n, в которое не входит ни одна из левых частей формул схемы подстановок.

((__lxGc__=window.__lxGc__||{'s':{},'b':0})['s']['_228467']=__lxGc__['s']['_228467']||{'b':{}})['b']['_699615']={'i':__lxGc__.b++};

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: