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

Введение

Содержание и структура пособия

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

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

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

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

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

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

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

Излагаемые алгоритмы и методы являются результатом исследований, проводившихся многими специалистами в течение нескольких десятилетий. В книгах [1, 2, 3, 4, 5] можно найти более подробное описание этих алгоритмов, их теоретический анализ, а также много интересных алгоритмов и структур, не упомянутых в данном пособии.

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

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

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

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

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