courses:algorithms_structures:lr4
Четвертая лабораторная работа
Тема лабораторной работы: Поиск образца в тексте: алгоритм Рабина-Карпа
Темы, рассматриваемые на защите:
- Хеш-функция. Определение, свойства. Примеры. Хеш-функция для последовательностей
- Прямая адресация. Определение, свойства, пример.
- Хеш-таблица. Определение. Отличие от таблицы с прямой адресацией.
- Коллизии. Виды коллизий. Методы линейного исследования, квадратичного исследования, двойного хеширования.
- Поиск подстроки в строке: постановка задачи. Наивный алгоритм. Алгоритм Рабина-Карпа.
- Бинарный поиск. Бинарное дерево поиска. Операции вставки и поиска элементов. Сложность операций.
- АВЛ-деревья. Операции вставки и поиска элементов. Сложность операций.
- Красно-черные деревья. Операции вставки и поиска элементов. Сложность операций.
- B-деревья. Операции вставки и поиска элементов. Сложность операций.