Четвертая лабораторная работа

Тема лабораторной работы: Поиск образца в тексте: алгоритм Рабина-Карпа

Темы, рассматриваемые на защите:

Хеш-функция. Определение, свойства. Примеры. Хеш-функция для последовательностей

Прямая адресация. Определение, свойства, пример.

Хеш-таблица. Определение. Отличие от таблицы с прямой адресацией.

Коллизии. Виды коллизий. Методы линейного исследования, квадратичного исследования, двойного хеширования.

Поиск подстроки в строке: постановка задачи. Наивный алгоритм. Алгоритм Рабина-Карпа.

Бинарный поиск. Бинарное дерево поиска. Операции вставки и поиска элементов. Сложность операций.

АВЛ-деревья. Операции вставки и поиска элементов. Сложность операций.

Красно-черные деревья. Операции вставки и поиска элементов. Сложность операций.

B-деревья. Операции вставки и поиска элементов. Сложность операций.