III Поиск информации с использованием компьютера

1 Поиск данных

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

1.1 Постановка задачи поиска данных

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

Первый атрибут: набор данных. Это вся совокупность данных, среди которых осуществляется поиск. Элементы набора данных будем называть записями. Запись может состоять из одного или нескольких полей. На­пример, запись в записной книжке состоит из полей: фамилия, адрес, те­лефон.

Второй атрибут: ключ поиска. Это то поле записи, по значению которо­го происходит поиск. Например, поле ФАМИЛИЯ, если мы ищем номер телефона определенного человека.

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

Заметим, что ключей поиска может быть несколько, тогда и критерий поиска будет сложным, учитывающим значения сразу нескольких клю­чей. Например, если в справочнике имеется несколько записей с фамили­ей Сидоров, но у них разные имена, то составной критерий поиска будет включать два условия: ФАМИЛИЯ — Сидоров, ИМЯ — Владимир.

Как при «ручном поиске, так и при автоматизированном важнейшей задачей является сокращение времени поиска. Оно зависит от двух обстоятельств:

1) как организован набор данных в информационном хранилище (в словаре, в справочнике, на дисках компьютера и пр.);

2) каким алгоритмом поиска пользуется человек или компьютер.

1.2 Организация набора данных

Относительно первого пункта могут быть две ситуации: либо данные никак не организованы (такую ситуацию иногда называют «кучей»), либо данные структурированы.

Под словами «данные структурированы» по­нимается наличие какой-то упорядоченности данных в их хранилище: в словаре, в расписании, в компьютерной базе данных.

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

Структурированные системы данных, хранящиеся на каких-либо носителях, будем называть структурами данных.

Однако бывает и так, что хранимая информация не систематизирована. Представьте себе, что вы записывали адреса и телефоны своих знакомых в записную книжку без алфавитного индекса («лесенки» из букв по краям листов). Записи вели в порядке поступления, а не в алфавитном порядке. А теперь вам нужно найти телефон определенного человека. Что остается делать? Просматривать всю книжку подряд, пока не попадется нужная запись! Хорошо, если повезет и запись окажется в начале книжки. А если в конце? И тут вы поймете, что книжка с алфавитом гораздо удобнее.