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

Введение

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

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

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

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

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

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

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

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

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