Задачи поиска в информатике

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

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

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