Предметная область теоретической информатики

Теоретические основы информационных процессов И СИСТЕМ введение из истории науки. В 1948 году вышла в свет работа Клода Шеннона «Математическая теория связи», в которой развивались идеи помехоустойчивого кодирования при передаче сообщений по каналам с шумами. Этот труд лег в основу нового научного направления, получившего название «Теория информации». В рамках теории информации был получен ряд значительных результатов, связанных с различными вопросами кодирования передаваемых сообщений. Это результаты «в области алгебраической теории кодирования, построения различных оптимальных кодов, в области декодирования избыточных кодов, получения границ вероятности ошибки и различных информационных пределов избыточности» [Советов, с.13]. Многие из них были успешно использованы на практике, например, при решении задачи выбора комплекса технических средств и обеспечения его оптимального функционирования. Однако с развитием вычислительной техники – появлением персональных ЭВМ и их сетей – наиболее актуальными оказались проблемы не оптимального кодирования, а оптимального поиска и хранения данных в искусственной памяти, а также другие вопросы, связанные с обработкой данных. Поэтому в 80-е годы прошлого столетия на основе классической теории информации сформировалась новая наука с более широкой предметной областью - теоретическая информатика, включившая теорию информации как один из разделов. Курс «ТОИПС» охватывает некоторые основные направления развития теоретической информатики. Предметная область теоретической информатики. Теоретическая информатика – это наука о типовых информационных процессах и их наиболее общих закономерностях. Она обобщает результаты других наук с точки зрения их значимости для обработки данных, базируясь на философских законах и категориях. Предметная область теоретической информатики не имеет строго очерченных границ и мнения различных исследователей о том, что к ней следует относить, расходятся. Согласно некоторым, наиболее общим представлениям в теоретической информатике можно выделить следующие основные направления: 1. Хранение данных (организация баз данных и знаний, моделирование данных и т.п.). 2. Поиск данных (виды поиска, их эффективность, помехоустойчивость поиска и т.п.). 3. Передача данных (кодирование сообщений, помехоустойчивость кодирования и другие вопросы теории информации). 4. Преобразование данных (конечные и бесконечные автоматы, формальные языки и грамматики, рекурсивные функции, алгоритмы, нечеткие множества, нейронные сети и т.п.). 5. Построение информационных систем различного назначения (информационно-поисковых, автоматизированного обучения, менеджмента и др.). Изучаемый курс включает материал, относящийся ко второму, третьему и пятому из указанных направлений. Цели и задачи курса. Овладение набором теоретических сведений, используемых при проектировании алгоритмов обработки данных. 1.КОДИРОВАНИЕ СООБЩЕНИЙ §1. Информационные процессы С категорией «информация» (см. разд.1, §5) тесно связано понятие информационного процесса (ИП). Под ИП понимается: 1) Процесс движения данных. При движении данных осуществляется не только их передача, но и преобразование из одной формы в другую (см., например, рис. 1.1); Рис.1.1 Движение данных в АИС 2) Процесс обработки данных. Напомним (см. курс «ТЭИС»), что обработка данных – это всевозможные действия, производимые над данными. Процессы обработки данных связаны с процессами их движения – в процессе обработки происходит преобразование данных из одной формы в другую. Например, на рис. 1.1 показана взаимосвязь процесса движения данных с тремя процессами обработки; 3) Система информационных процессов (т.е. совокупность взаимосвязанных ИП). Таким образом, определение ИП строится по принципу рекурсии. Рассмотрим теперь информационные процессы передачи и кодирования данных в АИС, являющихся подсистемами различных АСУ. §2. Передача и кодирование данных в АИС Передача данных в АИС от источника к приемнику осуществляется при помощи технических устройств по каналу или линии связи (см. рис. 1.2). Рис.1.2 Передача данных в АИС Различные виды кодирования в АИС поясняются на рис. 1.3. Рис.1.3 Виды кодирования в АИС При кодировании сообщений по некоторой системе кодирования каждому знаку алфавита ставится в соответствие определенный код – один знак из алфавита системы кодирования или последовательность таких знаков, называемая также кодовым словом. При кодировании сообщений в вычислительной технике используется обычно двоичная система кодирования с алфавитом {0,1}, из знаков которого составляются различные кодовые слова. Во многих системах кодирования генерируемые кодовые слова имеют одинаковую длину (так называемые равномерные коды). Например, коды, используемые в ЭВМ, представляют собой последовательности байтов – наборов из восьми двоичных знаков. Последовательность из двух байтов называется полусловом, из четырех байтов – словом, а из восьми байтов – двойным словом. Выбор систем кодирования для осуществления кодирования конкретных типов сообщений определяется многими факторами, к числу которых относятся: - удобство получения исходных сообщений из источника; - быстрота передачи сообщений через канал связи; - объем памяти, необходимой для хранения сообщений; - удобство обработки данных; - удобство декодирования сообщений приемником и т.п. §3. Сжатие данных как информационный процесс Закодированные сообщения передаются по каналам связи, хранятся в запоминающих устройствах (ЗУ), обрабатываются процессором. Объемы данных, циркулирующих в АИС, велики, и поэтому во многих случаях важно обеспечить такое их кодирование, которое характеризуется минимальной длиной получающихся сообщений. Это проблема сжатия данных. Ее эффективное решение обеспечивает увеличение скорости передачи данных и уменьшение требуемой памяти ЗУ. В конечном итоге это ведет к повышению эффективности обработки данных. Известны два основных принципа сжатия данных: 1) сжатие, основанное на анализе содержания данных; 2) сжатие, основанное на анализе статистических свойств кодируемых сообщений. Второй принцип, в отличие от первого, носит универсальный характер и может использоваться всегда, когда при передаче сообщений выделяются вероятностные закономерности. Рассмотрим оба этих принципа. §4. Сжатие на основе смыслового содержания данных Пусть имеется алфавит A из n знаков (символов), т.е. A={ai}, i=1,…,n , и по некоторому каналу связи нужно передать m сообщений (S={sj}, i=1,…,m). Каждое сообщение имеет длину lj, т.е. составляется из lj знаков алфавита A. Требуется передать сообщения через канал связи двоичными кодовыми словами минимальной длины. Обозначим через R минимальное количество двоичных разрядов, достаточное для кодирования каждого из сообщений. Возможны два подхода к кодированию. Первый из них основан на кодировании сообщений целиком, когда двоичное кодовое слово ставится в соответствие каждому из m передаваемых сообщений. При этом справедлива формула (1.1). (1.1) Здесь […] – целая часть числа. Второй подход основан на посимвольном кодировании сообщений, когда двоичное кодовое слово формируется путем объединения кодов, соответствующих каждому из символов передаваемого сообщения. При этом справедлива формула (1.2). (1.2) Здесь - длина самого большого сообщения. Очевидно, что выбор наиболее экономного способа кодирования зависит от сравнения целочисленных величин RI и RII : при наличии небольшого числа длинных сообщений предпочтителен первый подход, если же имеется много коротких сообщений, составленных из небольшого количества знаков, то предпочтительнее второй подход. Однако, количество передаваемых сообщений может быть заранее неизвестно. В этом случае необходимо производить посимвольное кодирование. Пусть способ кодирования выбран. Теперь решим вопрос о том, каким образом можно дополнительно сократить количество разрядов R двоичного кодового слова. Из вышеприведенных формул следует, что: при первом подходе нужно постараться уменьшить число передаваемых сообщений m , например, путем отбрасывания повторяющихся сообщений. В тех случаях, когда точное число сообщений неизвестно, необходимо по возможности снижать значение верхней границы их оцениваемого количества. Однако существенное сокращение размерности множества сообщений, как правило, невозможно, потому что на практике каждое сообщение несет информацию о некоторой ситуации, число которых может быть фиксировано; при втором подходе можно, во-первых, уменьшить размерность алфавита, что на практике почти невозможно, потому что связано с сокращением выразительных возможностей языка – попробуйте, например, выбрасывать буквы из алфавита от А до Я – и, во-вторых, уменьшить количество знаков в передаваемых сообщениях путем их сжатия по контексту (на основе смыслового содержания данных). Это гораздо более реальный путь, который лежит в основе большого количества практических методов сжатия данных. Рассмотрим некоторые из них. §5. Переход от естественных обозначений к более компактным. Многие данные, несущие информацию о каких-либо объектах, как правило, имеют вид, удобный для их чтения человеком. При этом они содержат обычно больше символов, чем это необходимо для адекватного восприятия передаваемой с их помощью информации. Наличие такой избыточности позволяет перекодировать информацию более компактно, поступаясь наглядностью ее представления в интересах эффективности передачи по каналу связи. Например, дата записывается обычно в виде «26 сентября 2007 г.» (18 символов, включая пробелы) или в более краткой форме «26.09.07». При анализе смыслового содержания выясняется, что информацию о дате можно кодировать и шестью десятичными разрядами, если договориться, что первые два разряда несут информацию о числе, следующие два разряда – о месяце и последние два – о годе даты (существование американского формата даты, когда первыми идут две цифры месяца, доказывает, что вводимые соглашения вовсе не так очевидны, как это кажется на первый взгляд). В этом случае рассматриваемую дату можно будет записать в виде «260907» - еще менее наглядно, но зато более компактно. Для посимвольного двоичного кодирования даты потребуется бита (в формуле 4.2 n=10, т.к. A={0,1,…,9}, и LSmax=6). Однако, легко заметить, что многие кодовые комбинации – такие, как 331853 или 950011 – вообще никогда не используются и рассматриваемый способ кодирования является избыточным. Вычислим количество возможных кодовых комбинаций (а, значит, и число m возможных сообщений о дате). Поскольку ЧИСЛО = {01, 02, … , 31}; МЕСЯЦ = {01, 02, … , 12}; ГОД = {00, 01, … , 99}, то m ≤ 31∙12∙100 = 37200 и по формуле 1.1 бит, т.е. при кодировании сообщений целиком нам потребуется 16 двоичных разрядов, что на 33,3% экономнее, чем при посимвольном кодировании. Здесь следует отметить, что на практике было бы более удобно, хотя, теоретически, и не так экономно, кодировать число, месяц и год в отдельности, выделив для этого соответствующее количество разрядов, и затем объединить полученные коды в единое двоичное кодовое слово. При этом формула 1.1 примет вид С учетом того, что m1=31, m2=12, m3=100 получим бит. Однако и этот способ кодирования не оптимален. Допустим, при анализе выясняется, что нас будут интересовать даты не от 1 января 2000 г. по 31 декабря 2099 г., а из более узкого диапазона, например, от 1 января 2007 г. по 17 сентября 2096 г. В этом случае можно еще больше сжать данные и кодировать информацию о дате не шестью, а пятью десятичными разрядами. Для этого применим способ, известный еще в средние века: записывать общее число дней, прошедших до некоторой даты от выбранной точки отсчета (начала диапазона), в нашем случае – от 1 января 2007 г. Так как от этой даты до 17 сентября 2096 г. прошло 32768 дней, то становится понятно, почему для кодирования потребуется пять десятичных разрядов. Получим ли мы выигрыш при двоичном кодировании дат в указанном диапазоне? Да, т.к. 32768=215 и бит. Обратим внимание, что при раздельном кодировании числа, месяца и года дат этого диапазона выигрыша мы бы не получили: бит. Также экономия отсутствовала бы, если бы нас интересовали даты из более широкого диапазона, скажем, с 1 января 2006 г.: в этом случае количество дат в диапазоне до 17.09.96 превысило бы 215 дней и RI=16 бит. Аналогично датам могут быть сжаты номера изделий, уличные адреса и т.п. §6. Подавление повторяющихся символов Во многих данных часто присутствуют повторяющиеся подряд символы: в числовых – повторяющиеся старшие или младшие нули, в символьных – пробелы и т.п. Избыточность таких данных можно уменьшить, если вместо последовательности повторяющихся символов вида кодировать эквивалентную последовательность символов вида pka , в которой р – признак повторения (специальный символ или слово), k – число повторений символа a. Очевидно, что эффективность такого метода определяется значением величины Е : Здесь n – размерность алфавита А ( ); R(p) – фиксированное число битов для кодирования признака повторения; R(k) – фиксированное число битов для кодирования числа повторений символа a. В случае, когда величина Е принимает отрицательное или нулевое значение, от использования данного метода вообще следует отказаться. §7. Кодирование часто используемых данных Некоторые данные, такие как имена и фамилии, принадлежат множеству возможных значений очень большого размера. Однако в большинстве случаев используется лишь малая часть возможных значений (действует так называемое «правило 90/10» - в 90% случаев используется 10% возможных значений). Поэтому для сжатия данных можно определить множество наиболее часто используемых значений, экономно закодировать его элементы и использовать эти коды вместо обычного представления. В частности, можно составить список из 256 наиболее употребительных имен людей и кодировать их одним байтом. Одновременно следует обеспечить возможность записи имен, не входящих в закодированные: например, используя признак, аналогичный признаку повторения, кодируемый одним байтом и указывающий на то, что последующие байты содержат полное написание имени. Таким же образом может быть произведено кодирование наиболее употребительных фамилий (для этого могут потребоваться двухбайтовые коды). Многие сообщения и файлы данных содержат текстовые фрагменты из некоторых областей знаний. В таких текстах можно выделить множество наиболее употребительных слов, например, терминов, пронумеровать их и закодировать по вышеизложенному способу. Данный метод, таким образом, сочетает в себе оба подхода к кодированию (см. формулы 1.1 и 1.2). §8. Сжатие данных на основе сравнения В упорядоченных наборах данных часто совпадают начальные символы или даже целые последовательности начальных символов записей. Поэтому можно кодировать данные на основе их сравнения с предыдущими. В этом случае сжимаемым элементам данных может предшествовать специальный признак, указывающий на то, что элемент данных: - совпадает с предыдущим; - имеет следующее по порядку значение; - совпадает с предыдущим кроме m последних символов; - не имеет связи с предыдущим. При использовании подобных признаков закодированные данные содержат только отличия текущих элементов от предыдущих. §9. Целесообразность сжатия данных Реализация сжатия данных в информационных процессах требует дополнительных программных и аппаратных затрат, а также затрат времени и памяти на предварительное кодирование с целью сжатия и последующее декодирование для восстановления данных в первоначальном виде. Это означает, что сжатие данных – это не всегда целесообразное мероприятие. Например, в базах данных обычно сжимаются архивные файлы с невысокой частотой использования. Сжатие применяется также для сокращения размеров индексных таблиц, используемых для организации поиска данных в индексно-последовательных файлах. §10. Сжатие на основе статистических свойств данных и неравномерные коды Методы такого сжатия изучаются в специальном разделе теории информации (подразделе теоретической информатики), который называется теорией экономного или эффективного кодирования. Экономное кодирование основано на использовании систем кодирования с переменной длиной кодового слова. В системах равномерного кодирования, как нам уже известно, каждому символу алфавита A={ai}, i=1,…,n, ставится в соответствие кодовое слово с фиксированным числом разрядов. Например, в случае рассмотренного нами посимвольного двоичного кодирования каждому знаку алфавита A соответствует или бит (двоичных разрядов). Однако давно известны и системы кодирования, в которых длина кодового слова непостоянна, например, код Морзе. При использовании таких неравномерных кодов сразу же возникает проблема выделения кодовых слов из закодированной последовательности символов для однозначного декодирования сообщений. Например, в коде Морзе для этого предусмотрена специальная кодовая комбинация-разделитель (тройная пауза). Однако более экономным является использование при кодировании так называемого условия префиксности кода (условия Фано): никакое кодовое слово не должно являться началом другого кодового слова. Выполнение этого условия гарантирует однозначное разбиение последовательности символов на кодовые слова без применения разделителей: очередное кодовое слово получается последовательным считыванием символов до тех пор, пока получающаяся комбинация не совпадет с одним из кодовых слов. Пусть, например, A={0,1, … ,9}. Закодируем символы данного алфавита наборами двоичных знаков следующим образом: 0 – 00 5 – 110 1 ­– 01 6 – 1110 2 – 1000 7 – 11110 3 – 1001 8 – 111110 4 – 101 9 – 111111 Нетрудно видеть, что перед нами – префиксный код. Теперь появляется возможность однозначного декодирования любого сообщения. Например, последовательность 1110110111110100000000110011111110101 допускает лишь одно разбиение на кодовые слова 1110 110 111110 1000 00 00 01 1001 111111 01 01 и соответствует сообщению 65820013911. Префиксный код называется примитивным, если его нельзя сократить, т.е. при вычеркивании любого знака хотя бы в одном кодовом слове код перестает быть префиксным. Префиксный код, приведенный выше в качестве примера, является примитивным. §11. Двоичное кодирование и бинарные деревья Двоичное кодирование удобно представлять в виде бинарного кодового дерева. Если условиться сопоставлять любой левой ветви бинарного дерева нуль, а любой правой – единицу, то каждой вершине дерева будет однозначно соответствовать некоторый набор двоичных знаков, показывающий, в какой последовательности нужно сворачивать налево и направо, добираясь до этой вершины из корня дерева. Любой из таких наборов может быть выбран в качестве кодового слова. Например, рассмотренному выше коду соответствует дерево, приведенное на рис. 1.4. Рис.1.4 Пример кодового дерева примитивного префиксного кода Очевидно, что условие префиксности кода в терминологии бинарных деревьев можно сформулировать следующим образом: никакие две вершины, изображающие некоторую пару кодовых слов, не лежат на одном пути из корня кодового дерева. Процесс двоичного кодирования можно интерпретировать следующим образом. На каждом шаге движения по кодовому дереву, начиная от корня, происходит выбор одного из двух поддеревьев: правого и левого. Это соответствует разбиению множества знаков алфавита на два подмножества – правое и левое – с присвоением им очередных двоичных знаков (единицы и нуля). Так, в рассмотренном примере множество {0,…,9} было разбито на два подмножества {0,1} и {2,3,…,9}. При дальнейшем движении вправо множество {2,3,…,9} в свою очередь было разбито на два подмножества {2,3,4} и {5,6,…,9}, а при движении влево множество {0,1} было разбито на два подмножества {0} и {1} и т.д. до тех пор, пока во всех подмножествах не осталось по одному элементу. Таким образом, двоичные коды, соответствующие вершинам кодового дерева, характеризуют «историю» последовательного разбиения исходного множества знаков на правые и левые подмножества. §12. Кодирование сообщений словами переменной длины Пусть имеется множество передаваемых сообщений S={sj}, i=1,…,m, причем известна вероятность pj появления каждого из сообщений на входе устройства кодирования (при соблюдении условия нормировки ). Пусть также имеется множество двоичных кодовых слов переменной длины, используемых для кодирования этих сообщений K={kj}, причем lj =l(kj) – длина кодового слова kj, соответствующего сообщению sj. Тогда в качестве критерия эффективности кодирования сообщений множества S кодовыми словами множества K выступает величина λkS , называемая средней длиной кодового слова и определяемая следующим образом: (1.3) Рассмотрим пример. Пусть множество сообщений S={s1, s2, … , s10} характеризуется вероятностями появления, определяемыми по следующей формуле: (1.4) (Можно проверить, что условие нормировки при этом соблюдается). Воспользуемся для кодирования данных сообщений кодовыми словами рассмотренного выше префиксного кода так, как это показано в таблице 1.1. Таблица 1.1 Сообщение sj Вероятность pj Кодовое слово kj Длина кодового слова lj s1 1/55 111111 6 s2 2/55 111110 6 s3 3/55 11110 5 s4 4/55 1110 4 s5 5/55 1001 4 s6 6/55 1000 4 s7 7/55 110 3 s8 8/55 101 3 s9 9/55 01 2 s10 10/55 00 2 По формуле (4.3) получим: (бит/сообщение) Если бы мы закодировали сообщения равномерным кодом, то, согласно формуле (1.1) нам потребовались бы кодовые слова длины (бит/сообщение), т.е. кодирование словами переменной длины оказывается более эффективным. Заметим, что в приведенном примере кодовые слова ставились в соответствие сообщениям таким образом, что их длина оказывалась обратно пропорциональной вероятности появления каждого из сообщений. Тем самым обеспечивалось наиболее экономное кодирование, поскольку при данном способе распределения значение величины λkS минимально. Как же выбирать кодовые слова в общем случае, чтобы для заданных вероятностей p1, p2, … , pm обеспечить по возможности меньшую среднюю длину кодового слова, т.е. λkS → min? Заметим, что если , то минимальную среднюю длину кодового слова λkS обеспечивает равномерное двоичное кодирование. На каждом шаге двоичного кодирования производится разбиение множества сообщений на два подмножества, причем одному из них приписывается единица, а другому – ноль. Таким образом, на каждом шаге производится кодирование подмножеств равномерным кодом длиной в один двоичный знак. Отсюда следует принцип: нужно стремиться так производить разбиение на два подмножества, чтобы суммарные вероятности подмножеств были одинаковыми или как можно более близкими друг к другу. Рассмотрим две процедуры экономного кодирования, основанные на использовании этого принципа. §13. Процедура Шеннона-Фано В этом алгоритме предварительно производится упорядочивание сообщений по возрастанию или убыванию вероятностей pj. Разбиение на подмножества производится путем выбора разделяющей границы в упорядоченной последовательности так, чтобы суммарные вероятности подмножеств были по возможности одинаковыми. Кодовое дерево, построенное этим методом для примера в таблице 1.1, приведено на рис.1.5. Возле каждой вершины дерева указывается суммарная вероятность соответствующего подмножества. Рис.1.5 Кодовое дерево в процедуре Шеннона-Фано Выполнив расчеты по формуле 1.3, получим: λkS=3,145 (бит/сообщение). Таким образом, код, полученный при помощи процедуры Шеннона-Фано, оказывается более экономным, чем код из таблицы 1.1. §14. Процедура Хаффмана Рассмотренная в §13 процедура Шеннона-Фано является простым, но не всегда оптимальным алгоритмом построения экономного кода. Причина состоит в том, что способ разбиения на подмножества ограничен: вероятности сообщений, отнесенных к первому подмножеству, всегда больше или всегда меньше вероятностей сообщений, отнесенных ко второму подмножеству. Оптимальный алгоритм, очевидно, должен учитывать все возможные комбинации при разбиении на равновероятные подмножества. Это обеспечивается в процедуре Хаффмана. Процедура Хаффмана представляет собой рекурсивный алгоритм, который строит бинарное дерево «в обратную сторону», т.е. от конечных вершин к корню. Основная идея алгоритма состоит в том, чтобы объединить два сообщения с наименьшими вероятностями – например, p1 и p2 – в одно множество и далее решать задачу с m-1 сообщениями и вероятностями p1’ = p1 + p2; p2’ = p3; … ; pm-1’ = pm. Кодовое дерево, построенное процедурой Хаффмана для рассматриваемого примера, приведено на рис.1.6. Рис.1.6 Кодовое дерево в процедуре Хаффмана Расчеты по формуле 1.3 дают среднее значение длины кодового слова λkS=3,145 (бит/сообщение), что совпадает с результатом применения процедуры Шеннона-Фано. Это означает, что для данного примера процедура Шеннона-Фано также оказалась оптимальной. §15. Кодирование последовательностей символов Пусть количество передаваемых сообщений заранее неизвестно и, следовательно, заранее неизвестны вероятности поступления каждого из сообщений на вход канала связи. Однако, известно, что сообщения формируются из символов алфавита A={a,b}, появляющихся независимо друг от друга с вероятностями p1=0,7 и p2=0,3. При посимвольном кодировании этих сообщений, например, с помощью процедуры Шеннона-Фано, получим равномерные коды, приведенные в таблице 1.2: Таблица 1.2 Символ ai Вероятность pi Кодовое слово ki Средняя длина кодового слова λkA a 0,7 1 1 бит/символ b 0,3 Однако, процедуру Шеннона-Фано можно применить не только к отдельным символам алфавита A, но также и к их всевозможным комбинациям – двухсимвольным, трехсимвольным и т.д. – другими словами, можно кодировать целые последовательности символов в сообщениях (при условии, что сообщения будут иметь длину, кратную числу символов в каждой такой последовательности). Например, для всевозможных двухсимвольных последовательностей алфавита A получим данные, приведенные в таблице 4.3. Из сравнения данных в таблицах 1.2 и 1.1 видно, что кодирование двухсимвольных комбинаций более экономно, чем трехсимвольное кодирование. Еще лучшие результаты дает трехсимвольное кодирование (0,895 бит.символ). Таблица 1.3 Последовательность символов aiaj Вероятность pij Кодовое слово kij Средняя длина кодового слова λkA aa 0,49 1 0,905 бит/символ ab 0,21 01 ba 0,21 001 bb 0,09 000 При дальнейшем увеличении размерности кодируемых комбинаций средняя длина кодового слова уменьшается, стремясь к предельному значению, приблизительно равному 0,881 бит/символ. Повышение экономности кода достигается за счет того, что с увеличением числа кодируемых последовательностей расширяется диапазон возможных значений вероятностей их появления и на каждом шаге кодирования удается точнее разбивать множество кодируемых последовательностей на приблизительно равновероятные подмножества. §16. Помехоустойчивость данных На сообщения, передаваемые по каналу связи от источника к приемнику, могут действовать различные возмущения, называемые также помехами. Помехи могут присутствовать как на этапе кодирования информации (например, ошибки оператора-отправителя, сбои устройств ввода), так и на этапах передачи информации (шумы и искажения сигналов, отказы каналов и т.п.) и ее декодирования (ошибки оператора-получателя, сбои устройств отображения и др.). Кроме того, помехи могут действовать на сообщения, хранящиеся в запоминающих устройствах источника и приемника (повреждение магнитного слоя носителей, попадание под действие сильного магнитного поля и т.п.). Действие помех может приводить к искажению передаваемой информации или даже полной ее утрате. Следовательно, большое значение имеют методы обеспечения помехоустойчивости передаваемых данных. Рассмотрим некоторые из них, приняв ряд упрощающих предположений: 1. По каналу связи передается последовательность сообщений, закодированная двоичными знаками. 2. Помехи действуют только на канал связи, не затрагивая ни источник, ни приемник сообщений. 3. Помехи носят случайный характер, т.е. возникающие ошибки заранее непредсказуемы, но подчиняются вероятностным закономерностям. Это означает, что, получив закодированное сообщение, мы можем оценить вероятности искажений каждого из двоичных символов и на этой основе принять меры к восстановлению исходного сообщения. 4. При заданной длине кодового слова ошибки большей кратности характеризуются меньшими вероятностями появления. При этом кратностью ошибки называется число знаков, которые были искажены в некотором кодовом слове (например, двукратные, трехкратные и т.д. ошибки). Как обнаружить появление ошибок и исправить их? Издавна известен следующий простой способ: многократно повторять исходные знаки. Например, вместо двоичных знаков 0 и 1 можно передавать через канал связи последовательности 0…0 и 1…1, каждая из которых содержит нечетное число знаков. Ясно, что если помехи действуют на знаки независимо и вероятность искажения знака меньше 1/2, то принятая комбинация будет содержать больше неискаженных знаков, чем искаженных. Следовательно, приемник сообщений должен подсчитывать число нулей и единиц в полученных комбинациях и делать вывод о том, что была передана единица, если в некоторой комбинации больше единиц, или был передан нуль, если в ней больше нулей. Чем больше кратность повторения, тем достовернее такой вывод. Применение процедуры повторения ведет к тому, что при кодировании сообщений используются не все возможные кодовые комбинации. Такое кодирование называется избыточным. При этом используемые кодовые комбинации называются разрешенными, а неиспользуемые – запрещенными. Например, если вместо знаков 0 и 1 мы передаем кодовые слова 00000 и 11111 (пятикратное повторение), то разрешенными являются всего две кодовые комбинации из 25 = 32 возможных. Отметим, что как в приведенном примере, так и в общем случае помехоустойчивость передаваемых данных достигается за счет избыточности: при безызбыточном кодировании любая ошибка переводит одну разрешенную кодовую комбинацию в другую, также разрешенную, и не может быть ни обнаружена, ни, тем более, исправлена. Если же коды обладают избыточностью, то могут быть обнаружены те ошибки, которые переводят разрешенные комбинации в запрещенные. Необходимо отметить, что меры обеспечения экономности и помехоустойчивости взаимно противоречивы: экономность достигается за счет уменьшения избыточности, а помехоустойчивость – за счет ее увеличения. §17. Методы обеспечения помехоустойчивости Основными методами обеспечения помехоустойчивости данных, используемыми в настоящее время, являются: 1. Метод контроля четности. Данный метод является простейшим способом обнаружения некоторых из возможных ошибок. В качестве разрешенных используется половина возможных 2n кодовых комбинаций, а именно те из них, которые имеют четное число единиц. При передаче через канал связи возникновение однократной ошибки неизбежно приведет к нарушению четности, что и будет обнаружено на выходе канала. Ясно, что ошибки нечетной кратности (однократные, трехкратные, пятикратные, …) могут быть обнаружены этим методом, а ошибки четной кратности (двукратные, четырехкратные, …) – не могут. Метод контроля четности реализуется на практике следующим образом. Из последовательности символов, подлежащих передаче через канал связи, выбирается очередной блок из (k-1) символов, называемых информационными, и к нему добавляется k-й символ, называемый контрольным. Значение контрольного символа выбирается таким, чтобы обеспечить четность получаемой кодовой комбинации из k символов, т.е. сделать ее разрешенной. В тех случаях, когда вероятность появления более чем одной ошибки мала, метод контроля четности представляет собой значительную ценность – ведь если наверняка знать, что прием сопровождался ошибкой, то можно просто проигнорировать полученное сообщение и, если это допустимо, повторить передачу. В то же время скорость передачи данных, особенно при больших k, уменьшается незначительно (в k/(k-1) раз). 2. Метод контрольных сумм. Рассмотренный выше метод контроля четности можно применять несколько раз для каждого передаваемого кодового слова и это уже позволяет во многих случаях не только обнаруживать, но и исправлять обнаруженные ошибки. Рассмотрим пример. Каждые четыре информационных символа a1, … , a4 будем дополнять тремя контрольными a5, a6, a7 так, чтобы оказались четными следующие три суммы: S1 = a1 + a2 + a3 + a5 S2 = a1 + a2 + a4 + a6 S3 = a1 + a3 + a4 + a7 Контроль четности сумм S1, S2 и S3 на выходе канала связи позволяет однозначно установить, была ли допущена однократная ошибка и, если была, то какой из переданных символов был искажен: если один из семи символов искажен при передаче, то хотя бы одна из сумм обязательно окажется нечетной, так что четность всех трех сумм свидетельствует об отсутствии однократных ошибок; лишь одна сумма будет нечетной тогда и только тогда, когда искажен входящий в эту сумму один из трех контрольных символов (a5, a6 или a7); нечетность двух из трех сумм S1, S2 и S3 будет означать, что искажен тот из символов a2, a3 или a4, который входит в обе эти суммы; и, наконец, нечетность всех трех сумм означает, что неверно принят входящий во все суммы первый символ a1. Нетрудно видеть, что разрешенными являются следующие кодовые комбинации: 0000000 1000111 0001011 1001100 0010101 1010010 0011110 1011001 0100110 1100001 0101101 1101010 0110011 1110100 0111000 1111111 Их использование сокращает скорость передачи данных в 7/4=1.75 раза и позволяет исправлять все однократные ошибки (но не ошибки большей кратности). §18. Способность кодов обнаруживать и исправлять ошибки Кодовым расстоянием или расстоянием Хэмминга между двумя кодовыми словами одинаковой длины называется число несовпадающих в них символов. Например, расстояние Хэмминга между комбинациями 10010011 и 10000001 составляет d=2. Чем больше минимальное расстояние между разрешенными кодовыми комбинациями, тем больше избыточность. При безызбыточном кодировании d=1. Ошибка кратности r приводит к тому, что искаженная комбинация отодвигается на расстояние d=r от исходной. В то же время ошибка не может быть обнаружена, если она переводит одну разрешенную кодовую комбинацию в другую. Следовательно, способность кодов обнаруживать ошибки зависит от кодового расстояния между разрешенными кодовыми словами: чем больше расстояние, тем большей кратности требуется ошибка, переводящая одну разрешенную комбинацию в другую. Таким образом, если минимальное кодовое расстояние между разрешенными комбинациями равно dmin, то можно обнаружить ошибки кратностью r≤ dmin -1. Способность кодов исправлять обнаруженные ошибки состоит в возможности однозначного отнесения запрещенной кодовой комбинации к некоторой единственной разрешенной комбинации. Для этого достаточно, чтобы выполнялось условие dmin ≥ 2r +1, следовательно, коды с заданным dmin обеспечивают исправление ошибок кратностью r≤ (dmin -1)/2. В рассмотренном примере коды содержат 4 информационных и 3 контрольных символа, dmin=3, поэтому они могут обнаруживать однократные и двукратные ошибки, а исправлять только однократные. 2. ПОИСК ДАННЫХ §1. Проблема поиска данных С проблемой кодирования данных, передаваемых по каналу связи, тесно связаны проблемы их хранения в запоминающих устройствах (ЗУ) и поиска необходимых данных по специальному запросу. Действительно, чтобы исходному сообщению поставить в соответствие определенное кодовое слово, это слово часто нужно найти в некотором ЗУ. Приняв кодовое слово, также бывает необходимо найти в ЗУ данные, соответствующие исходному сообщению. С другой стороны, сложные системы поиска (например, в СУБД) в процессе своего функционирования используют большое число процедур кодирования и декодирования информации. При рассмотрении задач поиска будем предполагать, что данные находятся в ЗУ в виде записей, каждая из которых содержит специальное поле, называемое ключом. Обычно требуется, чтобы ключи были различными и чтобы каждый ключ однозначно определял свою запись. Совокупность записей образует таблицу или файл, размещаемый в запоминающем устройстве. Поиск обычно начинается с получения извне аргумента поиска и состоит в отыскании записи, ключ которой совпадает с аргументом поиска или находится с ним в определенном соотношении. Существуют две возможности окончания поиска: либо поиск оказался удачным, т.е. позволил найти нужную запись, либо неудачным, т.е. показал, что записи с данным ключом в таблице отсутствуют. Хотя целью поиска являются данные, содержащиеся в некоторой записи, их извлечение, когда запись найдена, принципиальных затруднений не вызывает. Поэтому для простоты можно считать, что записи состоят только из ключей. Конкретные процедуры поиска и их эффективность во многом определяются теми возможностями, которые предоставляют различные виды запоминающих устройств. Поэтому изучение методов поиска целесообразно начать с рассмотрения важнейших разновидностей ЗУ. § 2. Виды ЗУ С точки зрения поиска данных большинство известных запоминающих устройств можно отнести к одному из трех видов: последовательные, адресные и ассоциативные. Последовательные ЗУ при каждом считывании предоставляют во внешнюю среду очередную запись таблицы или файла. Чтобы получить в распоряжение некоторую i-ю запись таблицы, нужно прежде произвести считывание предыдущих (i-1) записей. Последовательный доступ к данным реализуют такие технические устройства, как накопитель на магнитной ленте, автомат магазинной памяти и т.п. Адресные ЗУ при каждом считывании предоставляют запись, находящуюся в ячейке, адрес которой указан на входе устройства. Чтобы получить некоторую i-ю запись таблицы, нужно на входе ЗУ указать адрес (номер) ячейки, в которой размещена эта запись. На рис. 2.1 представлена схема адресного ЗУ. Рис.2.2 Схема адресного ЗУ Адресное ЗУ состоит из двух частей: дешифратора адреса и матрицы ЗУ. Записи хранятся в строках матрицы ЗУ. Двоичный код адреса записи поступает на вход дешифратора адреса, который преобразует его в унитарный код с числом разрядов, равным количеству строк в матрице ЗУ. Логическая единица появляется на выходе дешифратора, номер которого соответствует двоичному коду адреса. Под действием сигнала логической единицы содержимое соответствующей строки матрицы ЗУ выводится на выход устройства. В качестве адресных ЗУ выступают такие технические устройства, как оперативное и постоянные запоминающие устройства ЭВМ, накопители на магнитных, оптических дисках и т.п. Ассоциативные ЗУ при каждом считывании выдают на выходе запись, содержимое определенного поля которой совпадает со значением ключевого слова, поданного на вход устройства. Чтобы получить в распоряжение i-ю запись таблицы, нужно на вход ЗУ подать кодовое слово, соответствующее ключевому слову i-й записи. На рис. 2.2 приведена схема ассоциативного ЗУ. Рис.2.2 Схема ассоциативного ЗУ Ассоциативное ЗУ состоит из справочника и матрицы ЗУ. В строках матрицы ЗУ хранятся записи. Каждая ячейка справочника представляет собой регистр, рассчитанный на хранение одного ключевого слова соответствующей записи матрицы ЗУ. Он дополнен специальными комбинационными логическими схемами, предназначенными для сравнения содержимого регистра с ключевым словом, поступающим одновременно на вход всех ячеек. Выходные шины справочника выполняют функцию адресных линий, следовательно, необходимость в дешифраторе адреса отпадает. В качестве ассоциативных ЗУ выступают технические устройства, называемые памятью с адресацией по содержанию, файлом с параллельным поиском, ассоциативным процессором и т.п. Из запоминающих устройств всех видов ассоциативные ЗУ непосредственно решают задачу поиска: подавая на вход ассоциативного ЗУ аргумент поиска, на выходе сразу получаем запись, ключ которой совпадает с аргументом. Однако ассоциативные ЗУ являются также наиболее дорогими и сложными технически, поэтому в настоящее время задачи поиска обычно приходится решать на основе адресного или последовательного ЗУ. Адресное ЗУ позволяет легко получить запись, зная ее порядковый номер в таблице. Следовательно, чтобы решить задачу поиска, нужно от аргумента поиска перейти к номеру записи в таблице. Для этого перехода требуется осуществить либо некоторую процедуру преобразования аргумента в адрес, либо некоторую процедуру проверки содержимого последовательности записей. В последовательных ЗУ поиск строится на основе просмотра содержимого записей. Далее будут рассмотрены методы поиска, ориентированные, в основном, на адресные ЗУ. При этом, отвлекаясь от конкретных способов задания адресов в различных ЭВМ и системах программирования, будем считать, что имеется возможность получить значение ключа записи по ее номеру в файле или таблице. Методы поиска можно разделить на два класса: поиск, основанный на преобразовании аргумента в адрес; поиск, основанный на сравнении ключей. Рассмотрим оба этих класса. §3. Поиск на основе преобразования ключа в адрес Идея данных методов поиска состоит в том, чтобы по аргументу поиска определить адрес соответствующей записи и получить эту запись за одно считывание данных. Простейшей реализацией этой идеи является использование аргумента, эквивалентного адресу. Например, на каждой квитанции по квартплате может быть указан адрес записи в файле, соответствующей данному абоненту. Физический адрес вводится в ЭВМ и по нему считываются необходимые данные. Примерно такой же простотой и быстротой характеризуется поиск, основанный на определенной регулярности возможных значений ключей. Например, если в файле успеваемости студентов в качестве ключей использовать последовательность NMP, то адрес записи с информацией об успеваемости студента с номером N в месяце M по предмету с номером P может вычисляться по формуле (N-1)∙35∙12∙L + (M-1)∙12∙L + (P-1)∙L + 1, где L – длина записей в файле. Рассмотренные способы основаны на учете конкретных закономерностей значений ключей, поэтому они носят ограниченный характер. Во многих задачах поиска нежелательно или недопустимо накладывать какие-либо ограничения на возможные значения ключей. Так, в предыдущем примере может потребоваться искать записи по фамилиям студентов, а не по их порядковым номерам. В этом случае нет практически никакой регулярности в возможных значениях ключей и вышеуказанные методы неприемлемы. Строку символов, составляющих ключ, всегда можно взаимно однозначно преобразовать в целое число. Например, ее можно рассматривать как запись числа в системе счисления с основанием, равным размеру алфавита. Так, для русского алфавита А=0, Б=1, В=2, …, Ю=31, Я=32 и фамилия «ДЕЕВ» будет преобразована в число 4∙333 + 5∙332 + 5∙331 + 4∙330 = 149362. Однако и после такого преобразования значения ключей не приобретут регулярности. §4. Перемешивание Простым и в то же время универсальным методом поиска, основанным на преобразовании аргумента в адрес, является так называемое перемешивание. Этот метод называется также хешированием (кешированием) или рандомизацией. Идея данного метода заключается в том, что записи размещаются в ячейках памяти, адреса которых получены преобразованием ключей в псевдослучайные числа из диапазона возможных значений адресов. Пусть, например, таблицу поиска составляют записи с данными о 31 студенте группы и в качестве ключей выступают фамилии студентов. Воспользовавшись тем, что дни рождения более или менее равномерно распределены в диапазоне от 1 до 31, будем в качестве адреса использовать день рождения студента. В этом случае может быть получена таблица адресов, приведенная на рис. 2.3. Рис.2.3 Пример использования перемешивания Теперь, если требуется найти в таблице сведения о каком-либо студенте группы, то его фамилию (аргумент поиска) нужно «преобразовать» в день рождения (адрес), по которому обратиться к соответствующей ячейке памяти. В приведенном примере отражены две существенные проблемы перемешивания: 1) как найти преобразование значений аргумента в целые числа из заданного диапазона, при котором числа были бы распределены в диапазоне достаточно равномерно? 2) как поступать в тех случаях, когда двум различным аргументам в результате преобразования присваиваются одинаковые значения адресов и возникает так называемая коллизия? Для преобразования аргумента в адрес, которое называется функцией перемешивания или хеш-функцией, предложено много алгоритмов, идеи которых в большинстве случаев связаны с методами формирования на ЭВМ псевдослучайных чисел. Процедура получения хеш-адресов выполняется обычно в три этапа: 1. Перевод аргумента (если он не числовой) во взаимно однозначное числовое представление. 2. Преобразование числового представления аргумента в псевдослучайное число, имеющее тот же порядок, что и значения адресов памяти. 3. Нормирование полученного числа для того, чтобы оно строго укладывалось в диапазоне значений адресов памяти. Следует особо отметить, что псевдослучайный, а не чисто случайный характер получаемых хеш-адресов имеет принципиальное значение. Функция перемешивания должна быть строго детерминированной, так как она используется как при начальном заполнении таблицы или файла, так и при последующем поиске (в обоих случаях по одному значению аргумента должен получаться один и тот же хеш-адрес). Наиболее распространенная функция перемешивания основана на методе деления. Аргумент в числовом представлении делится на число, равное или близкое к числу записей в таблице. Остаток от деления дает относительный хеш-адрес. Данный метод при всей его простоте обеспечивает достаточно равномерное рассеивание хеш-адресов при заполнении таблицы. Для лучшей равномерности перемешивания делитель должен быть нечетным числом, не должен выражаться степенью основания, по которому ключи переводятся в числовую форму, по мере возможности это должно быть простое число. Например, если число адресов равно 7000, то в качестве делителя подходит число 6997. Пусть числовая форма ключа равна 149362 (строка «ДЕЕВ»), тогда остаток от деления ее на число 6997 равен 2425. Поэтому запись с ключом «ДЕЕВ» при заполнении таблицы направляется в ячейку с адресом 2425, а при поиске извлекается из той же ячейки. Проблема коллизий решается достаточно просто: при заполнении таблицы для записи, претендующей на уже занятую ячейку, отводится место, расположение которого легко установить, зная адрес коллизии. Простейший прием состоит во введении ячеек переполнения и указании в точках коллизии ссылок на эти ячейки (метод ячеек переполнения). Другой прием заключается в просмотре последовательности ячеек, следующих за вычисленным хеш-адресом, до тех пор, пока не будет обнаружена свободная (метод внутренней адресации). В любом случае при наличии одной или нескольких ячеек с одинаковыми адресами необходимо иметь возможность идентифицировать по ключам попавшие туда записи, поскольку неизвестно, каким образом эти записи распределены по ячейкам памяти. Обычно для этого вместе с данными записывается ключ соответствующей записи, а на этапе поиска он сравнивается с аргументом поиска. Возможность коллизий приводит к тому, что не всегда нужная запись находится за одно считывание данных из памяти. При возникновении коллизии, возможно, потребуется два, три или даже более считываний данных – так называемых опробований, пока не будет найдена требуемая запись или не выяснится, что данная запись отсутствует. Другой особенностью данного метода организации поиска является наличие пустых мест в таблице. Дело в том, что чем плотнее заполнена таблица, тем больше вероятность коллизии и, следовательно, больше опробований нужно совершить, чтобы найти нужную запись. Поэтому для сокращения времени поиска целесообразно не заполнять таблицу до конца (на практике плотность заполнения таблицы обычно не более 80-90%). Во многих случаях методом перемешивания удобно определять адреса не отдельных ячеек, а групп из установленного числа ячеек – участков. По мере заполнения памяти записи помещаются в свободные ячейки участка с вычисленным хеш-адресом. При поиске определяется хеш-адрес участка и далее перебираются записи в участке до тех пор, пока не будет найдена та из них, ключ которой совпадает с аргументом поиска. §5. Поиск на основе сравнения ключей Идея данного метода поиска состоит в том, чтобы в определенной последовательности считывать записи таблицы до тех пор, пока не будет считана запись, ключ которой совпадает с аргументом поиска. В простейшем случае порядок считывания и проверки записей определен заранее (последовательный поиск), в более совершенных процедурах поиска выбор следующей проверяемой записи определяется результатами сравнения с аргументом поиска ключей предыдущих считанных записей. Важным показателем сложности поиска, основанного на сравнении ключей, является число сравнений, необходимых для нахождения требуемой записи. Необходимое число сравнений в рамках заданного метода определяет время поиска. Поэтому при рассмотрении методов поиска интересуются прежде всего числом необходимых сравнений. §6. Последовательный поиск Этот вид поиска является единственно возможным для последовательных ЗУ, однако ввиду своей простоты и универсальности он часто применяется и для адресных ЗУ. Алгоритм последовательного поиска заключается в следующем: на каждом шаге считывается очередная запись и ее ключ сравнивается с аргументом поиска. Шаги повторяются, начиная с первой записи таблицы, до тех пор, пока либо ключ очередной записи не совпадет с аргументом поиска, либо не будут считаны все записи таблицы. В первом случае поиск заканчивается удачно, во втором – неудачно. В случае удачного поиска возможное число сравнений лежит в пределах [1,N], где N – число записей в таблице. Для случая неудачного поиска всегда требуется N сравнений. Пусть значения аргумента случайны, т.е. в текущем запросе с некоторой вероятностью Q аргумент не совпадает ни с одним ключом таблицы, а с вероятностью 1-Q совпадает хотя бы с одним ключом (Q – вероятность неудачного поиска). Кроме того, в случае удачного поиска существуют вероятности pi того, что аргумент совпадает с ключом i-й записи таблицы (). Тогда среднее число сравнений в случае удачного поиска составляет Для равновероятных запросов , Среднее число сравнений с учетом как удачного, так и неудачного поиска составляет Для равновероятных запросов аргумента последняя формула принимает вид: Пусть записи в файле или таблице упорядочены по возрастанию ключей, т.е. K1 KN при i=N+1. Тогда среднее число сравнений при неудачном поиске составляет… Для равновероятного случая Среднее число сравнений при поиске в упорядоченном файле с учетом как удачного, так и неудачного поиска составляет Для равновероятного случая эта формула принимает вид Поскольку упорядочивание файла по ключам не влияет на сложность удачного поиска, то, если заранее известно, что поиск в большинстве случаев удачный, файл можно упорядочить по убыванию вероятностей pi. При этом удается уменьшить среднее число сравнений: ведь чем ближе часто запрашиваемая запись к началу файла, тем меньше сравнений требуется совершить при ее поиске. §7. Блочный поиск Пусть файл или таблица упорядочены по возрастанию ключей и пусть на каждом шаге поиска имеется возможность выбирать любую по счету запись для сравнения ее ключа с аргументом поиска. Как организовать последовательность сравнений в этом случае, чтобы уменьшить сложность поиска? Можно просматривать не каждую, а, например, сотые записи таблицы. Как только будет обнаружена запись с ключом, превышающим аргумент поиска, просматриваются (методом последовательного поиска) последние пропущенные 99 записей. Этот алгоритм называется поиском с пропусками или блочным поиском: записи группируются в блоки и сначала ищется нужный блок, а затем в нем ищется нужная запись. Оптимальное число записей в блоке при равновероятных запросах равно квадратному корню из числа записей в файле. Среднее число записей, которые должны быть просмотрены при удачном поиске, в этом случае также равно . Примем это без доказательства. §8. Двоичный поиск Пусть, как и в предыдущем случае, таблица поиска упорядочена по возрастанию ключей. Если теперь выбрать для проверки запись из середины таблицы, то, если эта запись не окажется искомой, множество возможных претендентов сократится приблизительно в два раза: искомая запись находится в одной из половин таблицы. На этой идее последовательного деления множества записей пополам основан двоичный или дихотомический поиск. На каждом i-м шаге двоичного поиска считывается и сравнивается с аргументом запись , находящаяся примерно в середине некоторого множества последовательно расположенных записей таблицы , где , и соответствуют начальной, серединной и конечной записям множества на i-м шаге поиска. Взяв в качестве исходного множества всю таблицу , шаги повторяются до тех пор, пока либо аргумент поиска не совпадет с ключом сравниваемой записи , либо множество не станет пустым. В первом случае поиск оканчивается удачно, во втором - неудачно. В качестве множества для следующего шага берется правое или левое подмножество текущего шага, причем Рис. 2.4 поясняет алгоритм двоичного поиска на примере таблицы из 16 записей и значения аргумента . В этом методе особенно удивительно то, что уже после двух сравнений три четверти таблицы будут вне области поиска. Рис.2.4. Пример двоичного поиска записи в таблице Двоичный поиск удобно представить в виде двоичного дерева (см. рис.2.5). Вершинами дерева двоичного поиска являются ключи, сравниваемые с аргументом поиска. При этом корнем является ключ записи, сравниваемой на первом шаге. Поиск можно интерпретировать как прохождение дерева от корня до искомой записи. Если достигнута конечная вершина, а заданный ключ не найден, то искомая запись в файле отсутствует. Число вершин на единственном пути от корня к искомой записи равно числу сравнений, выполняемых алгоритмом двоичного поиска при попытке отыскания нужной записи. Рис.2.5. Представление двоичного поиска в виде бинарного дерева Среднее число сравнений в случае равновероятных запросов равно Ни один метод, основанный на сравнении ключей, не может дать лучших результатов при равновероятных запросах. Рассмотрим случай неравновероятных запросов. Пусть, например, некоторая запись файла запрашивается с вероятностью, намного превосходящей суммарную вероятность запросов остальных записей. В этом случае, очевидно, что, прежде всего, целесообразно проверить эту запись, а только затем - остальные. Приведенные рассуждения показывают, что в случае неравновероятных запросов двоичный поиск, вообще говоря, не является оптимальным. Даже в случае равновероятных запросов преимущества двоичного поиска не всегда бесспорны. Это, прежде всего, относится к ситуациям, когда время считывания записей непостоянно. В последнем случае доступ к серединным записям может быть сопряжен с большими затратами времени, чем доступ к записям в начале таблицы и алгоритм двоичного поиска оказывается менее эффективным. §9. Поиск по бинарному дереву При рассмотрении двоичного поиска бинарное дерево было использовано для пояснения работы алгоритма. Поиск можно организовать на основе явного использования бинарного дерева. Такой метод имеет два важных преимущества: позволяет достичь минимума среднего числа сравнений в условиях неравновероятных запросов; позволяет легко осуществлять поиск в часто изменяющихся (динамических) таблицах или файлах, не производя сортировку после каждого добавления записей. Для реализации бинарного дерева в явном виде в каждой записи таблицы помимо поля ключа предусматривается два поля указателей UR и UL, в которых записываются адреса правого и левого преемников вершины дерева, соответствующей данной записи. Для свободных вершин, не имеющих преемников, в указателях помещается специальный символ «T» (тупик). Чтобы иметь возможность начать поиск, требуется адрес записи, соответствующей корню дерева: будем хранить его в специальной ячейке V. Пример явного задания бинарного дерева приведен на рис. 2.6. Рис.2.6 Явное задание бинарного дерева поиска На каждом i-м шаге алгоритма поиска по бинарному дереву производится чтение из таблицы некоторой записи с ключом Ki и указателями UiR и UiL . При этом первый шаг всегда начинается с корня дерева, адрес которого содержится в указателе V. На каждом шаге ключ Ki сравнивается с аргументом поиска A и по результатам сравнения выполняются следующие действия: а) A= Ki – запись найдена, поиск заканчивается удачно; б) A> Ki, UiR =T или A< Ki, UiL =T – тупик, запись в таблице отсутствует, поиск заканчивается неудачно; в) A> Ki, UiR ≠T – поиск продолжается, считывается очередная запись (Ki+1, Ui+1R, Ui+1L) по указателю UiR; г) A< Ki, UiL ≠T – поиск продолжается, считывается очередная запись (Ki+1, Ui+1R, Ui+1L) по указателю UiL. При продолжении поиска (случаи в и г) аналогичным образом выполняется (i+1)-й шаг для записи Ki+1, полученной на i-м шаге. Конкретный вид бинарного дерева для заданного множества записей определяется порядком, в котором записи заносятся в таблицу. Например, оно может выродиться в цепочку (линейный список) или принять сбалансированный вид, когда свободные вершины находятся на примерно одинаковом расстоянии от корня (см. рис. 2.7). Рис.2.7 Возможные варианты бинарного дерева В первом случае на рис. 2.7 поиск по бинарному дереву соответствует последовательному поиску, во втором – двоичному. Следовательно, необходимое число сравнений определяется видом бинарного дерева. Например, при равновероятных запросах и удачном поиске среднее число сравнений меняется примерно от log2N-1 (двоичный поиск) и до N/2 (последовательный поиск). Если записи добавляются в таблицу в случайном порядке с одинаковыми вероятностями (что часто встречается на практике), то получаются бинарные деревья, для которых среднее число сравнений приблизительно равно . Это несколько больше, чем для двоичного поиска, но существенно меньше (особенно при больших N), чем для последовательного поиска. Как уже отмечалось, метод бинарного дерева широко применяется для организации поиска в динамических таблицах, поскольку при его использовании не требуется сортировка записей таблицы. При добавлении новой записи ее просто помещают в конец таблицы и корректируют указатели некоторой старой записи, чтобы присоединить к бинарному дереву новую вершину. При этом, чтобы найти вершину для присоединения новой записи, достаточно проследить в дереве путь неудачного поиска для аргумента, равного ключу добавляемой записи. В связи с этим, большинство практических алгоритмов совмещают в себе операции поиска с операциями добавления новой записи в случае неудачного поиска. Несколько сложнее, но также вполне реализуема процедура удаления какой-либо записи из таблицы. Недостатком поиска по бинарному дереву является дополнительный расход памяти в каждой записи на хранение указателей правого и левого преемников. §10. Чистый бинарный поиск Поиск данного вида представляет собой обобщение двоичного поиска. Сформулируем задачу чистого бинарного поиска следующим образом. Имеется таблица из N записей и задан некоторый аргумент поиска, причем заранее известно, что в таблице существует запись с ключом, равным аргументу поиска. Каждая запись таблицы имеет известную вероятность выбора pi и выполняется условие нормировки . Поиск осуществляется следующим образом. На каждом шаге выбирается некоторое подмножество записей и выясняется, принадлежит или нет искомая запись выделенному подмножеству. Необходимо построить алгоритм, состоящий из подобных шагов и решающий любую задачу поиска при минимуме среднего числа сравнений. Каждое сравнение при этом делит текущее подмножество непроверенных записей на два других подмножества, одно из которых будет проверяться на данном шаге, а другое – нет. Для построения такого алгоритма предположим, что записи упорядочены по возрастанию значений pi и разобьем каждое из множеств непроверенных записей посередине (если число записей в множестве нечетно, то для определенности будем относить серединную запись к подмножеству с меньшими значениями pi). Пример такого разбиения приведен на рис. 2.8. Рис.2.8. Пример чистого бинарного поиска Для приведенного примера на первом шаге алгоритма выясняется, «равен ли аргумент поиска пяти или больше», т.е. производится первое сравнение. Пусть ответом на поставленный вопрос будет «нет», тогда следующим вопросом (второе сравнение) будет: «тройка или четверка?» и т.д. Прямой подсчет среднего числа сравнений для рассмотренного примера дает: C10’=4∙(1/55 + 2/55) + 3∙(3/55 + 4/55 + 5/55) + 4∙(6/55 + 7/55) + 3∙(8/55 + 9/55 + 10/55) = 3,291. Рассмотренная задача соответствует удачному поиску. Однако, если сравнить этот алгоритм с алгоритмом двоичного поиска, то легко заметить, что его поведение в точности соответствует случаю неудачного двоичного поиска. Сравнивая задачу чистого бинарного поиска с рассмотренной в разделе 1 задачей экономного кодирования, легко убедиться, что они идентичны. Дерево поиска соответствует при этом бинарному кодовому дереву. Следовательно, для улучшения алгоритма чистого бинарного поиска можно воспользоваться процедурами экономного кодирования (Шеннона-Фано или Хафмана). Так, применение этих процедур к рассматриваемому примеру обеспечивает среднее число сравнений, равное 3,145. При этом, ввиду оптимальности процедуры Хафмана, это число не может быть меньше. §11. Помехоустойчивый поиск В рассмотренных методах поиска негласно предполагалось, что ключи однозначно закреплены за соответствующими записями и не содержат ошибок. Между тем очень сложно добиться того, чтобы в больших базах данных соблюдалась абсолютная точность записи значений полей всех видов. Участие человека-оператора в процедурах ввода данных делает ошибки неизбежными. Например, принято считать, что частота ошибок при вводе с клавиатуры достигает порой 1% и далеко не всегда их удается обнаружить и исправить. Неточность данных может быть обусловлена и другими причинами. В частности, ключевое слово может быть известно только по звучанию, а некоторые собственные имена даже теоретически допускают неоднозначное написание. Следовательно, большое значение имеет построение алгоритмов, способных осуществлять поиск в условиях помех. Например, предположим, что в роли ключей выступают слова, которые могли быть слегка искажены, и мы хотели бы найти нужную запись, несмотря на эту ошибку. Если сделать две копии файла, в одной из которых ключи расположены в обычном алфавитном порядке, а в другой они упорядочены справа налево (как если бы слова были прочитаны наоборот), искаженный аргумент поиска в большинстве случаев совпадает до половины своей длины или более с записью одного из этих двух файлов. Таким способом удается отыскать возможные претенденты на искомую запись. Другая идея решения этой задачи состоит в том, чтобы найти некоторое преобразование аргумента в код (маску), собирающий вместе все варианты данного ключа. За рубежом нашел широкое применение следующий метод кодирования фамилий: а) оставить первую букву; все буквы A, E, H, I, O, U, W, Y, стоящие на других местах, - вычеркнуть; б) оставшимся буквам (кроме первой) присвоить следующие значения: (B, F, P, V) -> 1; (C, G, J, K, Q, S, X, Z) -> 2; (D, T) -> 3; L -> 4; (M, N) -> 5; R -> 6; в) если в исходном имени (перед шагом а) рядом стояли несколько букв с одинаковыми кодами, пренебречь всеми, кроме первой из этой группы; г) дописывая в случае надобности нули или опуская лишние цифры, преобразовать полученное выражение в форму «одна буква, три цифры». Например: Ключевое слово Код маски EULER E460 GAUSS G200 HILBERT H416 KNUTH K530 Разумеется, такая система собирает вместе не только родственные, но и достаточно различные имена. С другой стороны, некоторые родственные имена могут иметь различную кодировку. Но, вообще говоря, этот метод намного увеличивает вероятность обнаружить имя под одной из его масок. §12. B-деревья: общие сведения На практике широко распространены модели данных в виде B-деревьев. Использование В-дерева обеспечивает высокое быстродействие поиска при удалении, добавлении и чтении записей без осуществления сортировки всего содержимого файла после каждого изменения. Отличительной особенностью деревьев данного вида является то, что в них допускается более двух ветвей, исходящих из одной вершины. Каждая вершина В-дерева состоит из совокупности значений первичного ключа, указателей индекса и ассоциированных данных. Указатели индекса используются для перехода на следующий, более низкий уровень вершин в В-дереве. Ассоциированные данные фактически представляют собой совокупность указателей данных и служат для определения физического местоположения данных, ключевые значения которых хранятся в этой вершине индекса. Хотя записи данных можно было бы разместить непосредственно в вершинах индекса, для баз данных большой размерности такой способ оказался бы неэффективным. Обычно В-деревья используют только для организации индекса; записи данных располагаются в отдельной области. Основные достоинства В-дерева: 1. Во всех случаях полезное использование памяти для хранения индексов составляет свыше 50%. Обеспечивается динамическое распределение и использование памяти. С ростом степени полезного использования памяти не происходит снижения качества обслуживания пользовательских запросов. 2. Произвольный доступ к записи реализуется посредством небольшого количества подопераций (обращений к физическим блокам) и по эффективности сопоставим с методами перемешивания. 3. В среднем достаточно эффективно реализуются операции включения и добавления записей. При этом сохраняется естественный порядок ключей с целью последовательной обработки, а также соответствующий баланс дерева для обеспечения быстрой произвольной выборки. 4. Упорядоченность по ключу обеспечивает возможность эффективной пакетной обработки. Основной недостаток В-деревьев состоит в отсутствии для них средств выборки данных по вторичному ключу. В-дерево степени k () обладает следующими свойствами: 1. Все пути от корневой вершины до вершин-листьев имеют одинаковую длину h, называемую также высотой В-дерева (т.е. h есть количество вершин от корня до листа включительно). 2. Для каждой вершины, за исключением корня и листьев, количество подчиненных ей вершин (вершин-преемников) должно быть не меньше k+1 и не больше 2k+1. 3. Для корневой вершины количество подчиненных ей вершин должно быть не меньше двух и не больше 2k+1. 4. В каждой вершине, за исключением корня, количество ключей должно быть не меньше k и не больше 2k. В корне допускается только один ключ. В общем случае любая неконечная (ветвящаяся) вершина с j ключами должна иметь j+1 подчиненных вершин. На основании этих свойств легко видеть, что B-дерево степени 1, в котором из каждой вершины выходят в точности две ветви, представляет собой полностью сбалансированное бинарное дерево поиска. Вследствие переменного количества ключей в вершинах B-деревья оказываются более гибкими в сравнении с бинарными деревьями. Так, многие операции включения и удаления можно выполнять без последующего преобразования дерева. Физическая организация ветвящейся вершины В-дерева подобна физически последовательной структуре, как показано на рис. 2.9. p0 k1 α1 p1 k2 α2 p2 k3 α3 … pn-1 kn αn pn Рис.2.9 Структура ветвящейся вершины B-дерева с n ключами При реализации каждый блок (или страница), как правило, содержит только одну вершину. Поэтому в блоке 2k-n ключевых позиций и соответствующих им указателей свободны. Ключевые значения обозначены через ki, указатели индекса - pi, а соответствующие указатели данных - αi. На рис. 2.10 приведены примеры В-деревьев степеней 1, 2 и 3. В явном виде показаны действительные ключевые значения, а указатели ветвей изображены стрелками, обозначающими направление путей доступа. Ассоциированные данные, соответствующие вершинам B-дерева, на рисунке не показаны. Все листья располагаются в В-дереве на одинаковом уровне, поскольку любое B-дерево полностью сбалансировано по высоте. Отметим также, что независимо от степени дерева его корень может иметь самое меньшее один ключ. Рис.2.10 Возможные конфигурации В-дерева для файла с 12 ключами: а) дерево степени 1 (h=3); б) дерево степени 2 (h=2); в) дерево степени 3 (h=2). По мере возрастания степени В-дерева его высота уменьшается. Следовательно, при условии размещения каждой вершины в отдельном блоке или на отдельной странице В-дерево обеспечивает ускорение поиска по сравнению с бинарным деревом. Алгоритм поиска для В-дерева аналогичен алгоритму поиска в бинарном дереве. Выполняется просмотр упорядоченных ключей в вершине с целью поиска хранимого ключа (индекса), равного или большего аргумента поиска. Если найден ключ, равный аргументу поиска, поиск считается завершившимся удачно и для определения местоположения записи используется значение указателя данных. Если в некоторой позиции найден ключ ki, больший аргумента поиска, то осуществляется переход на вершину следующего уровня в соответствии со значением предыдущего указателя индекса pi-1 и просмотр ключей в данной вершине. Если же все хранимые в вершине ключи меньше аргумента поиска, то осуществляется переход на следующий уровень в соответствии со значением самого правого указателя индекса pn. Если аргумент поиска не найден в вершине-листе, то поиск заканчивается неудачно. Так, на рис. 2.10 поиск ключа 25 потребует: в случае а – трех обращений к блокам, в случае б – одного обращения к блоку и в случае в – двух обращений к блокам. §13. B-деревья: добавление ключей Операция добавления ключей в В-дерево начинается с выполнения операции поиска, когда аргумент поиска равен значению нового ключа. Если ключ действительно новый, то поиск завершится неудачно обнаружением некоторой вершины-листа. При этом возможны 4 случая: 1. В вершине-листе есть место для нового ключевого значения. Новый ключ помещается в соответствующее место этой вершины. 2. Вершина-лист содержит 2k ключей. В этом случае ее необходимо разделить на две вершины, каждая из которых содержит k ключей. После добавления нового ключа всего ключей станет 2k+1, но один из них должен быть включен в вершину-предшественник разделяемой вершины, которая является неполной. 3. Вершина-предшественник также является полной. В этом случае она также делится на две и этот процесс деления вершин может распространяться на все вершины вплоть до корня, при этом высота дерева увеличивается на единицу. 4. Вместо разделения заполненной вершины с целью добавления нового ключа можно проанализировать правую подобную ей вершину на наличие в ней свободного места. Если свободное место имеется, то последний ключ из заполненной вершины (после добавления в нее нового ключа) вытесняется в вершину-предшественник, а ключ из вершины-предшественника в свою очередь вытесняется на первую позицию правой подобной вершины со сдвигом ее содержимого вправо. При этом сохраняется и упорядоченность вершин, и приблизительно одинаковая степень их полезного использования. Примеры добавления ключей для случаев 1-3 приведены на рис. 2.11, а для случая 4 – на рис. 2.12. Рис.2.11 а) до добавления ключей 7, 37, 57; б) после добавления. Рис. 2.12 а) до добавления ключа 60; б) после добавления. §14. B-деревья: удаление ключей Необходимость удаления ключа из В-дерева индекса возникает вследствие удаления записи из области данных. Удалению ключа предшествует успешный поиск вершины, содержащей этот ключ. После завершения поиска возможны три случая: 1. Ключ удаляется из вершины-листа и в ней по-прежнему остается не меньше k ключей (т.е. отсутствует так называемое антипереполнение). На рис. 2.13 приведен пример этого случая. Рис.2.13 Удаление при отсутствии антипереполнения а) до удаления ключа 5; б) после удаления. 2. Ключ удаляется из ветвящейся вершины. Даже при отсутствии антипереполнения его необходимо заменить каким-то другим ключом в целях сохранения правого поддерева удаляемого ключа. Он замещается ключом из левой вершины-листа правого поддерева удаляемого ключа. Для этого при удалении ключа из корневой вершины приходится просмотреть максимум h вершин. Как только найдена вершина-лист, левый ключ из нее удаляется и включается в новую вершину. Если удаление ключа из вершины-листа не вызывает антипереполнения, то операция заканчивается. На рис. 2.14 приведен пример случая 2. Рис. 2.14 Удаление ключа из ветвящейся вершины В-дерева (случай 2): а) до удаления ключа 20; б) после удаления ключа 20 и его замены ключом 21. 3. Удаление ключа из вершины-листа вызывает антипереполнение (в вершине остается меньше k ключей). В этом случае недостающий ключ можно занять из левой или правой соседней (подобной) вершины. При этом в целях получения сбалансированного распределения ключей между двумя соседними вершинами можно занять несколько ключей. Последнее требует наличия в двух вершинах не менее 2k ключей. Если ключей меньше 2k, то выполняется сцепление вершин: все ключи переносятся в одну из вершин, а другая вершина из дерева удаляется. Операция сцепления по своему действию противоположна операции деления вершин. Она подразумевает также пересылку в оставшуюся подобную вершину ключа из вершины-предшественника, разделяющего две соседние подобные вершины. Удаление ключа из вершины-предшественника может вызвать в ней антипереполнение, и в худшем случае оно может распространиться вверх до корневой вершины. Возможны следующие операции для случая антипереполнения: А) перераспределение ключей в подобных вершинах (см. рис.2.15); Рис.2.15 Удаление ключа из ветвящейся вершины В-дерева (случай 3а): а) до удаления ключа 276; б) после удаления ключа 276 и перераспределения ключей в подобных вершинах. Б) сцепление вершин на одном уровне (см. рис.2.16); Рис.2.16 Удаление ключа из ветвящейся вершины В-дерева (случай 3б): а) до удаления ключа 15; б) после удаления ключа 15 и сцепления подобных вершин. В) в худшем случае процесс сцепления вершин распространяется вверх до корня, т.е. имеет место сцепление на уровнях (см. рис.2.17). Рис.2.17 Удаление ключа из ветвящейся вершины В-дерева (случай 3в): а) до удаления ключа 20; б) после первого сцепления ключей 6 и 16; в) после второго сцепления ключей 23 и 25; г) после третьего сцепления ключей 57 и 91 и организации новой корневой вершины. 3. ИНФОРМАЦИОННЫЕ СИСТЕМЫ § 1. Категория "система управления" После выбора цели и постановки задачи осуществляется третий шаг описания осознанной, целенаправленной деятельности человека - это проектирование системы управления. Система управления - это динамическая система, состоящая из трех основных (могут быть еще дополнительные) элементов: объекта управления, управляющего объекта и цели управления. Воздействия объекта управления на управляющий объект рассматриваются как передача информации о текущем состоянии объекта управления и называются информационными воздействиями, воздействия управляющего объекта на объект управления определяются на основе информационных воздействий и называются управляющими воздействиями. Цель управления рассматривается как новое состояние объекта управления и управляющие воздействия направлены на ее достижение. Таким образом, аппарат систем управления является универсальной методологией описания человеческой деятельности в любой области - промышленности, медицине, сельском хозяйстве и т.п. Объект управления является динамическим объектом и поэтому часто говорят о его движении как о процессе, о процессах, протекающих в объекте управления или об управляемом процессе. Если объект управления рассматривается как система, то вводится понятие "управляемая система". Управляющий объект - это сложный динамический объект, внутренними объектами которого могут быть люди, автоматы и другие устройства, здания и сооружения, каналы связи, средства труда и т.п. Если управляющий объект рассматривается как система, то он называется "управляющей системой". Цель управления, как правило, является общей целью проектировщика системы и людей, входящих в управляющий объект. По результатам декомпозиции или разбиения на подцели она может рассматриваться как пространство целей. §2 Понятие информационной системы Термин «информационная система» употребляется обычно в двух значениях – как «система данных» или как «система обработки данных». Определение. Информационной системой (ИС) называется: А) система, элементами которой являются взаимосвязанные данные; Б) система управления, объектом управления в которой являются данные, основное управление сводится к обработке этих данных, а цель управления представляет собой уже обработанные данные, выдаваемые пользователю в том или ином виде. Таким образом, во втором случае информационная система определяется более широко, помимо самих данных она может включать и другие объекты, обеспечивающие их обработку. Так, в управляющий объект подобной системы могут входить люди, различные технические устройства (например, автоматы), модели, алгоритмы управления и др. Отметим, что программы для автоматов в принципе также могут рассматриваться как данные и храниться совместно с обрабатываемыми данными – объектом управления. Такое совместное хранение реализуется, например, в простейших экспертных системах без накопления знаний (см. далее). Особо следует подчеркнуть, что многие авторы (например, В.М.Жеребин) вообще не рассматривают информационные системы как системы управления, хотя и допускают включение в их состав человека, а также различных средств обработки данных. Такие взгляды обусловлены тем, что результаты обработки любых данных не имеют самостоятельного значения, а рассматриваются как информационное сопровождение процессов управления некоторым объектом. При этом информационная система является подсистемой некоторой системы управления и реализуемая в ней обработка данных управлением не считается. Подобная точка зрения, к сожалению, широко распространенная как в теории, так и на практике, является ошибочной, потому что она неоправданно сужает область определения понятия "управление". Уже в "Энциклопедии кибернетики", изданной в 1974 году под редакцией В.М. Глушкова, говорится об "управлении данными" и это совершенно справедливо, поскольку любая целенаправленная деятельность людей может быть описана с помощью категорий систем управления. Обработка данных, как показывает приведенное выше определение Б), не является здесь исключением. Тот же факт, что информационная система является подсистемой некоторой системы управления, нисколько не мешает отдельному рассмотрению задач по обработке данных. Например, деятельность копировальщиков, операторов ЭВМ и даже администраторов баз данных очень мало связана с информацией, закодированной при помощи данных, и ее использованием в управлении каким-либо объектом. Между тем эта деятельность направлена на достижение определенных целей и безусловно может быть отнесена к управлению, а именно - к управлению данными. Обработанные данные (как правило, сообщения, документы), являющиеся целью управления в информационных системах (подход Б), выдаются пользователю в различном виде: рукописном, печатном, на экране средств отображения (видеограмма или видеокадр) или даже в виде устной речи. Пример: справка в справочном бюро железнодорожного вокзала. На управляющий объект информационной системы ограничений не накладывается: в него могут входить все те же объекты, что и в управляющий объект любой системы управления - люди, устройства, в том числе автоматы, и т.д. Отметим, что программы для автоматов также могут рассматриваться как данные и храниться совместно с обрабатываемыми данными - объектом управления. В качестве управляющего объекта может выступать один автомат или совокупность (последовательность, иерархия) взаимодействующих автоматов. В качестве синонимов категории "информационная система" по определению Б могут быть использованы понятия "система обработки информации", "система обработки данных" и др. Если обработанные данные выдаются пользователю в форме инструкций, советов, рекомендаций, т.е. сообщений о каких-либо действиях, которые необходимо предпринять, то говорят об "информационно-инструктирующей" или "информационно-советующей" системе. Отметим, что к классу информационных систем по определению Б не относятся так называемые СУБД - системы управления базами данных, которые, несмотря на название, не могут самостоятельно реализовать управление данными: требуется их взаимодействие с пользователем, прикладными программами, операционной системой, автоматом. Поэтому каждая СУБД, представляющая собой часть системного программного обеспечения некоторой АСУ или САУ, является лишь одним из внутренних объектов (элементов) управляющего объекта информационной системы. Отдельный интерес представляет задача хранения данных, являющаяся одной из типовых задач информационной технологии. Совокупность совместно хранящихся данных образует так называемую информационную базу. В смысле информационной базы часто понимается термин "информационная система" в определении А, если связи между ее элементами рассматриваются как связи между совместно хранящимися данными. Целью задачи хранения данных являются сами исходные данные, извлеченные из информационной базы в некоторый последующий момент времени, т.е. цель управления в информационной системе, обеспечивающей хранение данных, относится к классу целей второго вида, достижение которых (управление) сводится к отпарированию действия возмущений. Примеры отпарирования возмущений, действующих в информационных базах: защита хранимых данных от огня, сырости, несанкционированного доступа, компьютерных вирусов и т.п. Подобно носителям информации информационные базы делятся на внутримашинные (размещаемые в памяти автомата) и внемашинные (размещаемые вне автоматов). Внутримашинная информационная база называется также базой данных. База данных как информационная система по определению А представляет собой совокупность взаимосвязанных файлов данных или просто файлов, каждый из которых несет информацию о каких-либо типовых объектах. В свою очередь файл можно также рассматривать как информационную систему, элементами которой являются взаимосвязанные данные о каждом отдельном типовом объекте - записи. Отсюда следует, что принципиальной разницы между базами и файлами данных нет и иногда эти понятия используются в литературе как синонимы. В качестве примеров внемашинных информационных баз можно привести всевозможные картотеки, библиотеки, журналы регистрации, хранилища папок с документами (например, в отделе кадров) и т.п. §3 Классификация систем управления по степени автоматизации управляющего объекта В соответствии с указанным в заголовке признаком различают ручные системы управления, автоматизированные системы управления (АСУ) и системы автоматического управления (САУ). Рассмотрим сначала вопрос об определении АСУ. Чаще всего термин АСУ используется в литературе без определения. В некоторых случаях цитируется ГОСТ 19675-74, согласно которому АСУ - это "человеко-машинная система, обеспечивающая автоматизированный сбор и обработку информации, необходимой для оптимизации управления в различных сферах человеческой деятельности". Главный недостаток данного определения состоит в том, что термин АСУ в нем никак не соотносится с более общим понятием - "система управления". Кроме того, определение относится скорее к автоматизированным информационным системам (см. далее), представляющим собой лишь частный случай АСУ, и под него не подходят, например, системы, в которых сбор и обработка информации осуществляются вручную, а автоматизируется процесс выдачи управляющих воздействий - как в системе управления, связанной с работой экскаватора. Заметим также, что сбор и обработка информации в АСУ осуществляется прежде всего не для оптимизации, а для реализации управления объектом, оптимизация же происходит в результате автоматизации управляющего объекта системы управления при ее развитии. Введем и будем далее пользоваться следующим определением: АСУ - это система управления, управляющий объект которой является автоматизированным. Очевидно, что введенное определение основывается на понятиях системы управления, ее управляющего объекта и на понятии автоматизированного объекта. Если проанализировать взаимосвязь всех понятий, использованных при выводе определения АСУ, то можно построить схему, представленную ниже. На схеме знаком (*) изображаются различные понятия, а их взаимосвязи означают: А * * В - понятия А и В определены совместно; А * * В - понятие В определяется на основании понятия А; А * Понятие В определено наложением ограничений на понятие А (В есть разновидность А). В * объект * * автомат * сложный объект * статический * цель * составной объект 1 и 2 объект видов динамический * * * состояние объект процесс система *цель 3 вида * * автомати- динамическая * зирован- система * управляющий объект ный объект система * управления * объект управления * АСУ Рис. Взаимосвязь понятий, использованных при определении АСУ Аналогично АСУ может быть введено понятие автоматизированной информационной системы (АИС): АИС - это информационная система, управляющий объект которой является автоматизированным. Заметим, что АИС удовлетворяет определению АСУ и может рассматриваться как ее разновидность. Синонимами являются понятия "автоматизированная система обработки информации" (АСОИ), "автоматизированная система обработки данных" (АСОД). Помимо АСУ две другие важнейшие разновидности систем управления могут быть введены следующим образом: САУ - это система управления, управляющий объект которой является автоматическим. Система управления называется ручной, если ее управляющий объект является неавтоматизированным. § 4. Классификация подсистем АИС Как правило, АИС - это сложная система, в которой выделяется большое число внутренних объектов, многие из которых являются подсистемами. Поэтому для облегчения ее рассмотрения как при синтезе (на этапе планирования, а также в ходе перепроектирования на этапе оперативного управления), так и при анализе в ходе функционирования (на этапе оперативного управления) принято выделять типовые подсистемы АИС, т.е. подсистемы, входящие во многие АИС. Рассмотрим наиболее общие типовые подсистемы. Различают функциональную и обеспечивающую части АИС. Функциональная часть - это совокупность так называемых функциональных подсистем некоторой АИС, в каждой из которых решается одна из задач (выполняется одна из функций) технологии управления. Каждая функциональная подсистема, таким образом, представляет собой некоторую систему управления, являющуюся подсистемой АИС, хотя данная подсистема сама может и не относиться к классу АИС, если решаемая в ней задача не требует применения автоматов. Выделение в АИС функциональных подсистем напрямую связано с декомпозицией решаемой в системе задачи управления. Поэтому функциональная часть АИС представляет собой иерархическую систему, элементами которой являются вложенные друг в друга функциональные подсистемы. Обеспечивающая часть - это совокупность обеспечивающих подсистем некоторой АИС, которые выделяются независимо от решаемых в АИС задач, а в соответствии с каким-либо иным системообразующим фактором. Поэтому обеспечивающие подсистемы не являются системами управления, хотя и может быть произведена их декомпозиция по входимости в различные функциональные подсистемы. Каждая обеспечивающая подсистема называется также обеспечением АИС. Принято выделять следующие виды обеспечения АИС: 1. Информационное обеспечение - это одна или несколько информационных баз, хранящих данные для решения всех задач технологии управления, а также для перепроектирования АИС. 2. Лингвистическое обеспечение - это система научно-технических терминов и других языковых средств, используемых в АИС. 3. Техническое обеспечение (или комплекс технических средств - КТС АИС) - это система всех технических устройств (в первую очередь - автоматов, применяемых в АИС. 4. Математическое обеспечение - это система математических методов и моделей, используемых в АИС, а также алгоритмов решения задач технологии управления. 5. Программное обеспечение - это система программ для функционирования всех автоматов КТС АИС. 6. Организационное обеспечение - это система, элементами которой являются люди или коллективы (службы), входящие в управляющий объект АИС, а связями - производственные отношения между ними, включающие отношения подчиненности. При необходимости иногда выделяют и другие виды обеспечения АИС: алгоритмическое, правовое и т.п. Разработка функциональной и обеспечивающей частей составляет основу проектирования любой АИС. § 5 Системы искусственного интеллекта как информационные системы Системы искусственного интеллекта могут быть определены на основе двух понятий: понятия информационной системы как системы управления данными и понятия интеллектуального автомата, в качестве которого может рассматриваться в принципе любой автомат (например, ЭВМ), если только его функционирование уподобляется деятельности человеческого мозга. Система искусственного интеллекта - это информационная система, управляющий объект которой включает интеллектуальный автомат, объектом управления является база данных, размещенная в памяти данного автомата (внутримашинная информационная база), а обработка данных организована по аналогии с мыслительными операциями в сознании человека. Если в управляющий объект кроме интеллектуального автомата входит еще хотя бы один человек, то система искусственного интеллекта относится к классу автоматизированных информационных систем и, следовательно, является разновидностью АСУ. Для обозначения области научных исследований и проблем, связанных с созданием систем искусственного интеллекта, используется понятие искусственный интеллект. Основными направлениями работ по искусственному интеллекту в настоящее время являются: 1. Когнитивное моделирование или построение различных моделей работы человеческого мозга и его отдельных функций. Например, это построение так называемых нейронных сетей, имитирующих свойства нервной системы как системы взаимосвязанных нервных клеток (нейронов). Большое внимание уделяется также моделированию нейронных структур рецепторных органов низших животных. 2. Разработка систем искусственного интеллекта для практического применения – в целях обучения, диагностики, прогнозирования и т.п. Например, широкое применение системы искусственного интеллекта нашли в медицине, обеспечивая обработку данных от датчиков диагностического оборудования, постановку диагноза и определение курса лечения. 3. Разработка средств общения с ЭВМ на естественном языке (для машин пятого поколения). Здесь выделяются четыре ключевые проблемы: а) машинный перевод – использование компьютеров для перевода текстов с одного языка на другой; б) поиск данных – обеспечение с помощью компьютеров доступа к данным по конкретной тематике, хранящимся в большой базе данных. В настоящее время возможен только поиск по ключевым словам, но не по контексту или аналогии; в) генерация документов – применение компьютеров для преобразования документов определенной формы в эквивалентные документы другой формы; г) взаимодействие с компьютером – организация диалога между неподготовленным пользователем и компьютером (распознавание речи). 4. Обработка визуальной информации (распознавание образов). Сущность задачи распознавания образов заключается в отображении множества визуальных входных сигналов на множество решений, при котором каждому подмножеству множества сигналов, задающему некоторое изображение, ставится в соответствие одно решение. Другими словами, задачу распознавания образов можно понимать как задачу классификации изображений, при которой различным изображениям одного класса соответствует один «распознаваемый» образ в сознании человека. 5. Разработка экспертных систем – до недавнего времени это направление считалось главным направлением работ по искусственному интеллекту. Подробнее его содержание излагается ниже. § 6 Имитация логического мышления в экспертных системах Одним из направлений по моделированию на ЭВМ деятельности мозга является имитация логического мышления человека в процессе экспертизы. Человек становится экспертом в некоторой предметной области, получая информацию об объектах данной области (новые образы в сознании), перерабатывая и накапливая ее (новые ассоциативные связи между образами), т.е. приобретая знания. Таким образом, человеческое знание - это система взаимосвязанных образов объектов предметной области. Знания используются экспертом при проведении экспертизы задач, относящихся к предметной области. Процесс проведения экспертизы включает три этапа: а) получение от клиента исходной информации, соответствующей условию задачи; б) мыслительный процесс, когда в сознании активизируется последовательность ассоциативно связанных образов, началом которой служит исходная, а концом - результирующая информация. При этом мышление называется логическим, если связи между образами можно описать какими-то обобщенными, общепринятыми правилами, т.е. правилами логики; в) выдача клиенту результирующей информации в виде экспертного заключения. Для имитации на ЭВМ логического мышления человека-эксперта необходимо разместить в машинной памяти, во-первых, данные об объектах предметной области, и, во-вторых, данные, изображающие ассоциативные связи между образами этих объектов в сознании. Так мы приходим к понятию машинных знаний или просто знаний. § 7 Знания и базы знаний Знаниями называются данные, которые подразделяются на: а) факты, несущие информацию о каких-либо объектах, которым соответствуют определенные образы в сознании человека; б) правила [обработки фактов], которые несут информацию о взаимосвязях этих образов в сознании. Соответственно, база знаний - это база данных, представляющих собой знания. Таким образом, база знаний содержит совместно хранящиеся данные двух видов - факты и правила. "Совместное хранение" можно понимать по-разному, и в качестве баз знаний могут рассматриваться не только отдельные файлы, каждый из которых содержит и факты, и правила, но также совокупности файлов, в которых одни файлы хранят только факты, а другие - только правила, связывающие эти факты. Например, факты в виде записей о студентах могут быть размещены в .dbf-файлах СУБД FoxPro, а правила их обработки, выраженные конструкциями IF, CASE, WHILE и т.д. - в .prg-файлах той же СУБД. Если же факты, обрабатываемые в подобных конструкциях, не извлекаются всякий раз из отдельного .dbf-файла, а размещаются непосредственно в программе, то такой .prg-файл сам по себе может рассматриваться как база знаний. Последний способ хранения фактов является наиболее простым. Кроме фактов и правил, база знаний может также включать так называемые коэффициенты определенности, выраженные в процентах или десятичных дробях, которые позволяют оценить достоверность вывода по тому или иному правилу. § 8 Экспертные системы Экспертная система - это система искусственного интеллекта, объектом управления в которой является база знаний, управляющий объект содержит человека-пользователя, взаимодействующего с интеллектуальным автоматом при помощи аппаратного и программного интерфейса, а также программу или совокупность программ - так называемую машину вывода, которая размещается в памяти автомата и осуществляет непосредственную обработку знаний. Обработка знаний при этом заключается в следующем: а) пользователь задает автомату некий факт или совокупность фактов, выступающих в роли исходной информации для экспертизы. Каждый такой факт отыскивается в базе знаний или заносится в нее заново; б) с помощью правил, порядок применения которых задается машиной вывода, устанавливаются последовательности фактов, связанных с исходными, и определяются конечные (результирующие) факты; в) результирующие факты, а иногда и все логические цепочки взаимосвязанных фактов, снабженные комментариями, выдаются пользователю в виде экспертного заключения. Тем самым достигается цель управления экспертной системы - получение пользователем новых знаний. Общая схема экспертной системы может быть представлена на следующем рисунке. Пользователь Интерфейс Машина База вывода знаний Объект У п р а в л я ю щ и й о б ъ е к т управления Интеллектуальный автомат (ЭВМ) Рисунок 1 - Экспертная система как система управления § 9 Продукции в экспертных системах Правила базы знаний формулируются обычно в виде продукций, имеющих следующий формат: ЕСЛИ <предпосылка> ТО <заключение> <предпосылка> называется также посылкой или антецедентом и может иметь вид: <предпосылка> = <факт1> {И,ИЛИ} <факт2> ... {И,ИЛИ} <фактN> Выражение {И,ИЛИ} означает выбор одной из логических связок И, ИЛИ. На практике стараются избегать логической связки ИЛИ, разбивая одну продукцию на несколько, содержащих только связки И. <заключение> называется также консеквентом и имеет вид, аналогичный предпосылке. § 10 Функции когнитолога Информация, необходимая для базы знаний, собирается специалистом - когнитологом, который, как правило, непосредственно руководит созданием экспертной системы. В функции когнитолога входит выбор экспертов, их опрос с последующим сопоставлением и обобщением полученной информации об объектах предметной области, а также представление этой информации в виде знаний, т.е. совокупности фактов и правил, в форме, пригодной для непосредственного занесения в базу знаний. Правила, которыми когнитолог руководствуется при выборе экспертов для заполнения базы знаний: а) «накопленный опыт эксперта важнее, чем его интеллектуальные способности»; б) «практический опыт важнее теоретических обобщений»; в) «энтузиазм эксперта должен соответствовать объему извлекаемых знаний». § 11 Представление фактов базы знаний через пары "характеристика-значение" Анализируя суждения эксперта, когнитолог извлекает содержащиеся в них факты, представляя их либо тройками "объект-характеристика-значение", либо - более просто - парами "характеристика-значение" (например, таблица 1). Таблица 1 - Факты в виде пар "характеристика-значение" Cуждение эксперта Объект Пара "характеристика-значение" "У пациента температура" Пациент наличие_температуры = да "Температура высокая" Пациент температура = высокая "У пациента лихорадка" Пациент наличие_лихорадки = да "Цена минимальная" Лекарство цена = минимальная Каждая характеристика любого объекта может принимать значения из некоторого списка (множества) разрешенных значений, также определяемого когнитологом при помощи эксперта. Например, характеристики "наличие_температуры" и "наличие_лихорадки" принимают одно из двух значений (да, нет), характеристика "цена" - одно из нескольких значений (минимальная, договорная, максимальная, постоянная...). В свою очередь, совокупность всех выделенных когнитологом характеристик некоторого объекта (или предметной области в целом) образует так называемый список разрешенных характеристик данного объекта (предметной области). Списки разрешенных характеристик и разрешенных значений этих характеристик охватывают множество всех имеющихся фактов, подлежащих хранению в базе знаний экспертной системы. Каждый из списков не является жестко фиксированным, а может изменяться в ходе перепроектирования базы знаний, например, вследствие пополнения ее новыми знаниями. § 12 Представление правил базы знаний в виде продукций Правила базы знаний когнитолог формулирует обычно в виде продукций. Примеры описания правил с помощью продукций приведены в таблице 2. Таблица 2 - Правила в виде продукций Предпосылка (антецедент) Заключение (консеквент) ЕСЛИ температура = высокая ТО наличие_лихорадки = да ЕСЛИ цена = минимальная ТО необходимость_закупки = да ЕСЛИ класс = млекопитающее И потребление_мяса = да ТО отряд = хищник § 13 Проектирование управляющего объекта После заполнения базы знаний (формирования объекта управления) осуществляется проектирование управляющего объекта экспертной системы, которое начинается с выбора КТС (§ 4) и системного программного обеспечения (если это не было сделано на этапе постановки задачи). На выбор той или иной ЭВМ, а также того или иного программного пакета влияют, как правило, следующие факторы: а) быстродействие, удовлетворяющее ограничениям по времени решения задачи (т.е. времени проведения экспертизы); б) технические возможности, обеспечивающие удобство реализации экспертной системы и ее последующего использования (в том числе возможности компьютерной графики); в) стоимость, удовлетворяющая финансовым возможностям заказчика и т.п. Далее разработка экспертной системы осуществляется программистом. Исходя из запросов потенциальных пользователей он формирует требования к программному интерфейсу. Трудности программирования обусловлены, в первую очередь, неоднозначностью реализации программных компонент экспертной системы. Например, отсутствует четкая граница между базой знаний и машиной вывода с одной стороны (правила обработки фактов можно включать как правила в базу знаний, а можно реализовать их в управляющей структуре машины вывода), и между машиной вывода и интерфейсом пользователя - с другой (интерфейс может поддерживаться непосредственно машиной вывода). Кроме того, по-разному можно подойти к реализации базы знаний. Наиболее простой способ здесь - непосредственное включение правил в текст программы. Более гибкий подход состоит в создании пополняемой системы накопления пар "характеристика-значение" и связей между ними в виде правил. При программировании машины вывода возникает вопрос о выборе способа обработки правил и формирования экспертного заключения. Прямой вывод предусматривает отслеживание логической цепочки от исходных фактов к результирующим, когда правила (продукции) обрабатываются напрямую, т.е. от предпосылки к заключению. При обратном выводе логическая цепочка отслеживается в направлении от предполагаемых результирующих фактов (гипотез) к исходным фактам, подтверждающим их или опровергающим. Правила обрабатываются при этом в обратном порядке (от заключения к предпосылке). Иногда в машине вывода выделяют подсистему объяснения - программные средства, генерирующие в тексте экспертного заключения фрагменты-комментарии к логической цепи взаимосвязанных фактов, имитирующие рассуждения человека. Проектирование экспертных систем завершается тестированием и отладкой программного обеспечения, оформлением и передачей готового проекта заказчику. § 14 О перепроектировании экспертных систем Необходимость перепроектирования экспертных систем обусловлена, в первую очередь, изменениями, происходящими в предметной области, которые приводят к необходимости пополнения базы знаний новыми знаниями. Например, внедрение новой диагностицирующей аппаратуры, новых способов лечения болезней требуют занесения в базу знаний медицинской экспертной системы как новых фактов, так и новых правил. Эта деятельность осуществляется инженером-когнитологом, который в данном случае выступает в роли лица, принимающего решения. Часть управляющего объекта экспертной системы, предназначенная для пополнения базы знаний, называется подсистемой приобретения знаний.