Методы программирования. Кулаков Ю.В - 10 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Поиск в последовательно организованном файле.
3.2. Поиск посредством сравнения ключей
Поиск в деревьях. Оптимальные деревья двоичного поиска. Сбалансированные деревья.
3.3. Хеширование
Понятие хеширования. Разрешение коллизий.
Методические указания
3.1. Последовательный поиск
Познакомьтесь с определениями понятий поиск, ключ, таблица или файл, база данных, аргумент поиска,
удачный и неудачный поиск, поиск с вставкой. Обратите внимание на возможные способы классификации ме-
тодов поиска и взаимосвязь между поиском и сортировкой. Рассмотрите примеры возможных сложных задач
поиска и способы сведения их к более простым случаям. Познакомьтесь с историей вопроса поиска и его реше-
ния в докомпьютерный период, после появления ЭВМ с небольшой внутренней памятью и только последова-
тельными устройствами типа лент для хранения больших файлов, а также с развитием все большей и большей
памяти со случайным доступом.
Рассмотрите наиболее очевидный алгоритм S последовательного поиска, заключающийся в том, чтобы,
начав с начала, продвигаться, пока не найдешь нужный ключ, и тогда остановиться. Обратите внимание на то,
что у этого алгоритма может быть два разных исхода: удачный и неудачный. Проанализируйте время работы
алгоритма и обратите внимание на то, что этот способ последовательного поиска, несомненно, знакомый всем
программистам, не всегда самый лучший. Рассмотрите очевидное изменение, которое убыстряет работу алго-
ритма последовательного поиска при условии, что записей не слишком мало. Изучите алгоритм Q быстрого
последовательного поиска и оцените время его работы. Выполните этот алгоритм вручную для некоторых
входных данных и проанализируйте полученные результаты. Усвойте важный ускоряющий принцип, использо-
ванный при переходе от алгоритма S к алгоритму Q. Познакомьтесь с полезным изменением алгоритма после-
довательного поиска в условиях, когда ключи расположены в возрастающем порядке. Рассмотрите алгоритм Т
реализации последовательного поиска в упорядоченной таблице. Заметьте, что если величина ключа с равной
вероятностью принимает все возможные значения, то в случае удачного поиска алгоритм, по существу, не луч-
ше алгоритма Q. Однако, отсутствие нужной записи алгоритм T позволяет обнаружить примерно в два раза бы-
стрее. Обратите внимание на то, что в рассмотренных алгоритмах последовательного поиска в целях удобства
используются индексные обозначения для элементов таблицы, но аналогичные процедуры применимы и к таб-
лицам в связанном представлении. Оцените время последовательного поиска для известного и неизвестного
распределения вероятностей появления ключей.
3.2. Поиск посредством сравнения ключей
Познакомьтесь с задачей поиска в телефонной книге имени абонента по номеру телефона и ее решением
путем предварительного упорядочения файла и дальнейшего быстрого поиска. Изучите понятие бинарного по-
иска, основная идея которого довольно проста, детали же нетривиальны, и для многих хороших программистов
не одна попытка написать правильную программу закончилась неудачей. Познакомьтесь с алгоритмом B би-
нарного поиска и иллюстрацией поведения этого алгоритма в случаях, когда разыскивается аргумент, равный
имеющемуся в таблице, и когда разыскивается отсутствующий аргумент. Выполните доскональный разбор ал-
горитма B, представив его в виде бинарного дерева решений, и оцените быстродействие алгоритма для удачно-
го и неудачного поиска. Рассмотрите одну важную модификацию бинарного поиска, полученную использова-
нием в нем вместо трех указателей лишь двух: на текущее положение и величину его изменения. Изучите алго-
ритм U однородного бинарного поиска, реализующего упомянутую модификацию. Сравните быстродействие
однородного бинарного поиска с быстродействием алгоритма B и сделайте выводы. Познакомьтесь далее с фи-
боначчиевым поиском, способным соперничать с бинарным поиском. Для снятия некоторой таинственности с
фибоначчиева поиска постройте соответствующее дерево решений и проанализируйте его. Рассмотрите алго-
ритм F фибоначчиева поиска и оцените его быстродействие.
Обратите внимание на то, что ранее рассмотренные методы поиска предназначены, главным образом, для
таблиц фиксированного размера, поскольку последовательное расположение записей делает вставки и удаления
довольно трудоемкими. Уясните, что эффективный поиск по динамически изменяемой таблице возможен при
явном использовании структуры бинарного дерева. Познакомьтесь с алгоритмом Т поиска с вставкой по дереву
и оцените время поиска. Сравните эффективность алгоритма Т с алгоритмами бинарного поиска, использую-
щими неявные деревья. Изучите алгоритм D удаления узла из дерева, поскольку иногда бывает нужно заставить
ЭВМ забыть один из элементов таблицы.
Исследуйте проблему нахождения оптимального дерева – наилучшего дерева для поиска по таблице, если
ключи запрашиваются с данными частотами. Рассмотрите алгоритм К нахождения оптимальных бинарных де-
ревьев поиска.
Изучите понятия высоты дерева, сбалансированного дерева и показателя сбалансированности. Позна-
комьтесь с оценкой, как далеко сбалансированное дерево отклоняется от оптимального. Рассмотрите алгоритм
А поиска с вставкой по сбалансированному дереву и проанализируйте его быстродействие.
3.3. Хеширование

Страницы