Елизаров А.М. Математические методы в библиотечной работе

Подождите немного. Документ загружается.

к исходному файлу добавляется

новый элемент (буква Н — ука-

затель конца), а в самом файле к

элементу с буквой Г добавляется

еще один указатель на Н

(советуем построить дерево этого

файла).

Инвертированные ф а й-

лы. Пусть, например, в древо-

видном файле реализовано от-

ношение, описывающее админи-

стративную структуру библиотеки

(рис. 32). Этот файл будет хорош

при ответах на общие запросы о

работе библиотеки, но на

требование перечислить

сотрудников библиотеки ответ

можно дать, лишь просмотрев весь

файл — фамилии сотрудников

находятся на самом дальнем

уровне. Можно, однако, ор-

ганизовать этот же файл совершенно по-другому, со-

хранив отмеченную структуру. Для этого в качестве

элементов файла выберем дескрипторы „Александров",

„Борисов", „Володин" и для них перечислим ключе-

вые слова, с которыми они связаны, но уже в обратном

порядке:

Александров библиотекарь, отдел 1, библиотека;

Борисов методист, отдел 3, библиотека;

Володин библиограф, отдел 3, библиотека;

Рис. 32

Рис. 31. Древовидный

___ файл

После этого поиск по приведенному выше запросу

уже не составляет труда.

При создании инвертированных файлов все ука-

затели в основном файле ликвидируются и перено-

сятся в справочник с тем, чтобы для каждого эле-

мента указывалось столько ссылок сколько существует

записей, характеризуемых элементом. Основное пре-

имущество инвертированной организации файлов

заключается в быстроте поиска элемента с требуемы-

ми свойствами. При этом, если задано множество

ключевых слов, входящих в запрос, то первоначально

по справочнику отыскиваются списки номеров доку-

ментов, соответствующих запросам. Затем эти списки

объединяются и уже из основного файла извлекаются

элементы, обладающие должной степенью соответ-

ствия. Поскольку поиск по справочнику менее трудо-

емок и число обращений к основному файлу значи-

тельно сокращено, поиск в инвертированных файлах

осуществляется достаточно быстро.

К недостаткам инвертированных файлов можно

отнести большие размеры вспомогательного справоч-

ника и необходимость его ведения в определенном

порядке. Добавление нового элемента также сопря-

жено с изменением всех инвентарных списков спра-

вочника с целью внесения во все ключи номеров

вновь вводимого документа.

3. Индексирование запросов. Процесс индексиро-

вания запросов представляет собой логический анализ

вопросов пользователя и их запись на соответствую-

щем ИПЯ. Рассмотрим основные принципы анализа

запросов, осаовываясь на понятиях и фактах исчисле-

ния предикатов.

При логическом анализе запросов выделяют части

вопроса, которые соответствуют переменным, выска-

зывательным формам, логическим операциям и кван-

торам. Затем вводят сокращенные обозначения,

позволяющие сформулировать поисковые признаки и

задать поисковый образ запроса (ПОЗ), поисковое

предписание (ПП). Используемые высказывательные

формы должны быть максимально приближены к тем

формам, которые использовались при индексировании

документов и применены для записи информации

в ИПС.

Пример 1. Пусть в мини-ИПС из примера п. 1

хранятся библиографические данные о произведениях

русских писателей. Предположим, что поступил запрос

Какие книги написаны Булгаковым?, который

необходимо проанализировать. Переменной в данном

вопросе является „книги" (обозначим ее через у).

Другой частью предложения является высказыватель-

ная форма, связывающая переменную „книги"'и зна-

чение „Булгаков" и отражающая тот факт, что

описываются книги, написанные Булгаковым. Обозна-

чим эту форму Б(у) = ,,у написана Булгаковым".

Теперь мы ясно видим, что поиск по исходному

запросу свелся к нахождению таких книг а, что

высказывание Б (а) истинно. Иными словами, поиск

свелся к определению множества истинности Б (у).

Для приближения введенной формы к формам,

которые использовались при индексировании доку-

ментов, отметим тот факт, что Б (у) можно получить

из формы R

(x, у) = ,,х написал книгу у" путем под-

становки вместо х значения „Булгаков". Поэтому

окончательно наш запрос сформулируется в виде:

найти множество истинности высказывательной

формы R

(Булгаков, у).

Пример 2. Осуществим поиск в мини-ИПС по

запросу: Какие книги написаны Булгаковым или

Блоком, но не Ильфом и Петровым? Анализ этого

запроса проводится так же, как и в примере 1, одна-

ко здесь уже встретилось несколько поисковых

признаков. Как и ранее, рассмотрим в качестве пере-

менной у дескриптор „книги" и формы Б(у)=,,у

написана Булгаковым", БЛ(у)=,,у написана Блоком",

ИП(у) = „у написана Ильфом и Петровым". Тогда

можно представить запрос в виде (Б (у) БЛ(у))

и отыскать множество истинности этой

сложной высказывательной формы.

Для формулирования запроса на ИПЯ, близком к

используемому при индексировании документов в

мини-ИПС, заметим, что Б (у) R

(Булгаков, у),

БЛ(у) R

(Блок,у), а ИП(у) можно представить

как R

(Ильф, у) R

(Петров, у). Поэтому запрос

запишется как (R

(Булгаков, у) R

(Блок, у))

Построенное выра-

жение можно упростить, использовав закон де Мор-

гана Поэтому в окончательной форме

исходный запрос сформулируется в виде: найти мно-

жество истинности высказывательной формы

(Булгаков, у) R

(Блок, у))

(Петров, y)).

Аналогичным образом в сложных тематических

запросах могут применяться другие логические опе-

рации. При этом построенные логические выражения

должны быть упрощены и проанализированы со сле-

дующей точки зрения: отказ в выполнении той или

иной части запроса приводит к тому, что весь запрос

оказывается ненужным. Например, если в запросе из

примера 1 в качестве у взять „Золотой теленок", то

правая часть высказывания R

(Ильф, Золотой теле-

нок) R

(Петров, Золотой теленок) является тожде-

ственно ложной, следовательно, и весь запрос будет

ложным и анализ левой части не нужен.

Пример 3. Проанализируем запрос: Все книги

Булгакова, вышедшие в 1978 году. Для формули-

ровки этого запроса уже нужны две формы: R

(Бул-

гаков, у) = „Булгаков написал книгу у", R

(x, 1978)= =

„книга х вышла в 1978 году". Символически наш

запрос может быть записан как условное высказы-

вание: если Булгаков написал книгу у, то она (книга)

вышла в 1978 году, т. е. R

(Булгаков, у)→ R

(у, 1978). Но

в запросе идет речь о всех книгах Булгакова, поэтому

к отмеченной выше высказывательной форме должен

быть применен квантор всеобщности:

у(R

(Булгаков, у)→R

(y, 1978)) и поиск по исходному

запросу заключается в проверке: истинно или ложно

для М = {D

, D

} высказывание у М

(Булгаков, у)→R

(у, 1978)).

Разобранные в примерах способы индексирования

и записи запросов наиболее приемлемы при поиске,

производимом по принципу „все или ничего", т. е.

когда выдаются документы, в точности соответству-

ющие поисковым признакам. Указанная жесткость

ограничивает рамки применения ИПС с подобными

методами индексирования. В настоящее время раз-

рабатываются ИПС, в которых индексирование за-

просов осуществляется путем частичного или даже

полного отказа от логической стратегии поиска.

Однако многочисленные ИПС на перфокартах с крае-

вой перфорацией и малые ИПС вполне удовлетвори-

тельно обслуживаются путем указанных выше спосо-

бов индексирования документов и запросов.

ГЛАВА III

ЭЛЕМЕНТЫ ТЕОРИИ

ВЕРОЯТНОСТЕЙ

При изучении явлений окружающей действитель-

ности мы выделяем из бесчисленного множества фак-

торов самые главные, а влиянием остальных, прояв-

ляющихся в качестве возмущений или погрешностей,

просто пренебрегаем. Такой метод моделирования

постоянно применяется в физике, механике, технике.

Например, запустив ракету с определенной скоростью и

приняв во внимание основные действующие на нее

силы (тяготения, сопротивления воздуха и т. д.), мы

можем однозначно определить ее положение в любой

момент времени. Это пример детерминированного

процесса, в котором будущий ход и все прошедшие

события полностью определяются состоянием в на-

стоящий момент. Однако не меньшее число явлений,

имеющих важное значение в науке и ее приложениях,

не характеризуется полной однозначностью результа-

тов. Например, если подбросить монету, то невоз-

можно предсказать, какой стороной она ляжет ввеЬх —

гербом или цифрой. Здесь нет полной определённо-

сти результатов наших действий, но, повторив бро-

сание монеты большее число раз, мы уже отметим

некоторую закономерность: примерно в половине елу-

чаев выпадает герб. Приведенный пример относится к

вероятностным (или случайным) процессам. Факторы

неопределенности, многопричинности таких процессов

требуют создания специальных методов исследования.

Такие методы и разрабатываются в теории

вероятностей.

Теория вероятностей подобно другим разделам

математики развилась из потребностей практики. Уже

в начале XVII века Г. Галилей пытался подвергнуть

научному исследованию ошибки физических измере-

ний, рассматривая их как случайные величины и оце-

нивая их вероятности. В это же время подвергались

анализу такие массовые явления как смертность, за-

болеваемость, статистика несчастных случаев. Поня-

тие вероятности возникло в письмах Б. Паскаля и

П. Ферма, обсуждавших решение некоторых задач

игрового характера. Первая глубокая теорема теории

вероятностей была доказана в конце XVII в. Я. Бер-

нулли и послужила стимулом для дальнейшего раз-

вития теории. Новые результаты были получены в ра-

ботах А. Муавра, П. Лапласа, К. Гаусса, С. Пуассона

и особенно в работах П. Л. Чебышева, А. А. Маркова

и А. М. Ляпунова. В настоящее время наибольшее

развитие теория вероятностей получила в работах

советских математиков.

§ 7. Основные понятия теории вероятностей

1. Случайные события. В теории вероятностей

изучается следующая модель явлений окружающей

действительности: проводится опыт (испытание), в ре-

зультате которого происходят случайные события.

Под опытом (испытанием) понимается выполнение

определенного комплекса условий. Мы будем исполь-

зовать термин „опыт" для описания любого действия,

которое можно повторить, не изменяя его условий.

Например, опытами являются бросание монеты или

игральной кости, выбор книг из коллекции и т. д.

Случайное событие (кратко — событие) — это яв-

ление, которое при неоднократном воспроизведении

одного и того же опыта протекает каждый раз не-

сколько по-иному. В примере с бросанием монеты

выпадение герба — одно случайное событие, выпаде-

ние цифры — другое. События будем обозначать бук-

вами A, B, C, ... Например, Г = „выпал герб", Ц = „вы-

пала цифра". Среди всевозможных событий имеются

два события со специальными свойствами.

Определение 1. Событие называется досто-

верным (обозначается U), если оно обязательно

происходит в результате опыта, и невозможным

(обозначается Ø), если оно не может произойти.

Так, в опыте с монетой U= "выпали герб или

цифра", Ø = „не выпали ни герб, ни цифра". Рас-

смотрим случай более богатый событиями, чем бро-

сание монеты.

Пример 1. Изучим посещение читателей мини-

ёиблиотеки, в которой записано 10 человек. Так как

время прихода читателей за книгами случайно, то

здесь мы сталкиваемся со следующими событиями:

= „пришло n человек",

= „число пришедших читателей четно",

= „число пришедших читателей нечетно",

Qпp = „число пришедших читателей — простое".

Уже на этом примере мы можем заметить некото-

рые взаимосвязи между событиями. Например, собы-

тия Q

и Q

не могут произойти одновременно — ведь

не может сразу прийти четное и нечетное число чи-

тателей. Подобная ситуация встречается довольно

часто и получила специальное название.

Определение 2. Два события называются не-

совместными, если они не могут произойти одно-

временно в рассматриваемом опыте. В противном

случае события называются совместными.

Например, совместными являются события Q

и Q

пp

(пришли два читателя). Отметим, что между парами

событий Q

и Q

пр.

, с одной стороны, и Q

, Q

пp

., с другой,

имеется существенная разница: если из того, что

произошло Q

, мы делаем вывод, что произошло и Q

пp

то для второй пары это уже не так. В подобных слу-

чаях говорят, что событие А благоприятствует собы-

тию В, если из того, что произошло событие А, сле-

дует, что произошло В (обозначают А В), Таким

образом, в приведенном примере Q

np.

Отметим важный факт: в опыте с мини-библиоте-

кой события Q

, Q

, ..., Q

попарно несовместны,

и в то же время одно из них обязательно происхо-

дит (мы исключаем из рассмотрения тот случай, когда

в библиотеку никто не пришел). Описанная ситуация

очень важна для теории вероятностей.

Определение 3. Множество событий рассмат-

риваемого опыта, одно из которых обязательно

происходит при данном опыте, а любые два попарно

несовместны, называется множеством элементар-

ных событий (или исходов).

Так, в примере с мини-библиотекой события Q

, ..., Q

составляют множество элементарных событий.

Обратим внимание, что для одного и того же опыта

можно составить разные множества, элементарных

событий. Например, в опыте с мини-библиотекой

таковым будет и набор {Q

, Q

} (убедитесь в этом!).

Введенное понятие позволяет связать с любым со-

бытием некоторое подмножество множества элемен-

тарных событий, и, наоборот, каждое подмножество

1-я книга

2-я

книга

3-я книга

Элементарны

е события.

ИИИ

ИИЛ

ИЛ

ЛИ

ЛЛ

ЛЛЛ

Рис. 33

этого множества определяет некоторое событие

в опыте.

Пример 2. На выставке новых поступлений

имеются книги по литературе (обозначаем их бук-

вой Л) и искусству (И), Построим множество элемен-

тарных событий, соответствующее опыту, связанному

с выбором читателем трех книг (для их обозначения

используем упорядоченные тройки букв) (рис. 33).

Рассмотрим теперь способы интерпретации с по-

мощью множеств введенных ранее теоретико-вероят-

ностных понятий. Будем обозначать события и под-

множества элементарных событий одними буквами.

Начнем с события, определяемого всем множеством

элементарных событий. Поскольку в результате опыта

одно из элементарных событий обязательно происхо-

дит, а исходное множество соответствует всем исхо-

дам, множество элементарных событий определяет

достоверное событие U. Пустое подмножество мно-

жества элементарных событий определяет невозмож-

ное событие Ø. Несовместным событиям отвечают

Рис. 34. Совместные и несовместные события

непересекающиеся подмножества множества элемен-

тарных исходов, и, напротив, пересекающиеся под-

множества задают совместные события, которые мо-

гут в некоторых случаях происходить одновременно

(рис. 34).

Поскольку события можно рассматривать как не-

которые подмножества U, то над ними можно проде-

лывать все теоретико-множественные операции. Нужно

только умело „переводить" понятия с теоретико-мно-

жественного языка на язык теории вероятностей,

В таблице 15 мы приведем „словарь" для такого пе-

ревода.

Таблица 15

Алгебра событий Алгебра множеств Обозначение

Множество элементар-

ных событий

Универсальное множе-

ство

Событие

Подмножество

А,

...

Достоверное событие

Универсальное множе-

ство

Невозможное событие П

стое множество

Событие

несовместно

с В

А не пересекается с В

A∩В=Ø

Событие

совместно

с В

А пересекается с В

А∩В≠ Ø

Событие А благопри-

ятствует событию В

А подмножество В

А В

Событие

или В

Объединение

Событие

и В" Пе

есечение A и В

∩

Событие „не А" Дополнение А Ā

Этот словарь, разумеется, можно продолжить, но

мы ограничимся лишь примером переформулировки

операции объединения на теоретико-вероятностный

язык.

Событием А или В (иногда говорят — объедине-

нием событий А и В) называется событие, состоящее в

том, что в результате опыта произошло хотя бы одно

из событий А или В. Например, событие Q

состоит в том, что пришло нечетное

число читателей, т. е. произошло Q

2. Вероятность случайного события. Мы часто

пользуемся высказываниями типа „вероятно, сегодня

будет дождь", наверное, читателю понравится эта

книга", „это невероятное происшествие". Тем самым

Рис. 35

мы каким-то образом отмечаем случайность события.

Не менее часты и высказывания вида „у шахматистов

шансы на выигрыш равны", „книги по искусству, ве-

роятно, будут более читаемы, чем книги по технике",

и т. д. Здесь уже намечается некоторая числовая ха-

рактеристика, дающая представление о том, насколько

вероятно то или иное событие. Мы не сможем сразу

привести общее определение вероятности (оно не очень

просто) и рассмотрим самый простой случай, когда

это понятие нетрудно сформулировать и изучить. Это

так называемое классическое определение вероятности

в опыте с равновозможньши элементарными событиями.

Осуществим опыт с подбрасыванием двух монет.

Известно, что математик Даламбер рассуждал так:

есть три события — а) выпали два герба; б) выпали

две цифры; в) выпали герб и цифра. Он считал, что

эти события равновозможны. Однако существует и

другое решение этой задачи. Построим дерево воз-

можных вариантов (рис. 35). Тогда множество эле-

ментарных событий будет состоять из {ГГ; ГЦ; ЦГ;

ЦЦ}. Мы видим, что выпадение герба и цифры встре-

тится в два раза чаще, чем предполагал Даламбер.

Какой же метод решения более правильный? Когда

мы продвинемся в изучении теории вероятностей, то

увидим, что решение с четырьмя равновозможными

событиями соответствует предположению о независи-

мости подбрасывания одной монеты от подбрасыва-

ния другой, что вполне согласуется с опытными дан-

ными.

Понятие о равновозможных событиях используется

в теории вероятностей в следующих случаях:

1. Для описания физических опытов, подобных

бросанию монеты;

2. Для получения фактов и сравнения их с эле-

ментарными данными. (Например, опыт с бросанием

двух монет, выполненный 50 раз, практически пред-

2-я монета

1-я монета

Начало