Читать книгу Системное программное обеспечение. Лабораторный практикум - Алексей Молчанов - Страница 11

Порядок выполнения работы

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

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

Лабораторная работа должна выполняться в следующем порядке:

1. Получить вариант задания у преподавателя.

2. Выбрать и описать хэш-функцию.

3. Описать структуры данных, используемые для заданных методов организации таблиц идентификаторов.

4. Подготовить и защитить отчет.

5. Написать и отладить программу на ЭВМ.

6. Сдать работающую программу преподавателю.

Требования к оформлению отчета

Отчет по лабораторной работе должен содержать следующие разделы:

• задание по лабораторной работе;

• описание выбранной хэш-функции;

• схемы организации таблиц идентификаторов (в соответствии с вариантом задания);

• описание алгоритмов поиска в таблицах идентификаторов (в соответствии с вариантом задания);

• текст программы (оформляется после выполнения программы на ЭВМ);

• результаты обработки заданного набора идентификаторов (входного файла) с помощью методов организации таблиц идентификаторов, указанных в варианте задания;

• анализ эффективности используемых методов организации таблиц идентификаторов и выводы по проделанной работе.

Основные контрольные вопросы

• Что такое таблица символов и для чего она предназначена? Какая информация может храниться в таблице символов?

• Какие цели преследуются при организации таблицы символов?

• Какими характеристиками могут обладать лексические элементы исходной программы? Какие характеристики являются обязательными?

• Какие существуют способы организации таблиц символов?

• В чем заключается алгоритм логарифмического поиска? Какие преимущества он дает по сравнению с простым перебором и какие он имеет недостатки?

• Расскажите о древовидной организации таблиц идентификаторов. В чем ее преимущества и недостатки?

• Что такое хэш-функции и для чего они используются? В чем суть хэш-адресации?

• Что такое коллизия? Почему она происходит? Можно ли полностью избежать коллизий?

• Что такое рехэширование? Какие методы рехэширования существуют?

• Расскажите о преимуществах и недостатках организации таблиц идентификаторов с помощью хэш-адресации и рехэширования.

• В чем заключается метод цепочек?

• Расскажите о преимуществах и недостатках организации таблиц идентификаторов с помощью хэш-адресации и метода цепочек.

• Как могут быть скомбинированы различные методы организации хеш-таблиц?

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