Варианты заданий

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

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

№	Тип хеш-функции (таблицы)	Способ разрешения коллизий
	Сумма кодов первой и второй букв	Бинарное дерево
	Сумма кодов первой и второй букв	Список с простым перебором
	Сумма кодов первой и второй букв	Упорядоченный список с логарифмическим поиском
	Сумма кодов первой и второй букв	Простое рехеширование
	Сумма кодов первой и второй букв	Рехеширование с использованием случайных чисел
	Сумма кодов первой и второй букв	Метод цепочек
	Сумма кодов первой и последней букв	Бинарное дерево
	Сумма кодов первой и последней букв	Список с простым перебором
	Сумма кодов первой и последней букв	Упорядоченный список с логарифмическим поиском
	Сумма кодов первой и последней букв	Простое рехеширование
	Сумма кодов первой и последней букв	Рехеширование с использованием случайных чисел
	Сумма кодов первой и последней букв	Метод цепочек
	Бинарное дерево по первой букве	Список с простым перебором
	Бинарное дерево по первой букве	Упорядоченный список с логарифмическим поиском
	Бинарное дерево по последней букве	Список с простым перебором
	Бинарное дерево по последней букве	Упорядоченный список с логарифмическим поиском

Рекомендуемая литература

1. Молчанов А.Ю. Системное программное обеспечение. Лабораторный практикум. – СПб.: Питер, 2005 – 284 с.

2. Молчанов А.Ю. Системное программное обеспечение: Учебник для вузов. 3-е изд. — СПб.: Питер, 2010 — 400 с.

3. Свердлов С.З. Языки программирования и методы трансляции: учеб. пособие. — СПб.: Питер, 2007 — 400 с.

4. Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение – СПб.: Питер, 2001 (2002) - 736 с.

5. Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты: Пер. с англ. — М.: Издательский дом «Вильямс», 2003 — 768 с.

6. Робин Хантер Основные концепции компиляторов – М.: Издательский дом «Вильямс», 2002 – 256 с.

7. Корсакова Н.В., Пятлина Е.О. Фильчаков В.В. Структуры данных - Л.: ЛИАП, 1986.

8. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции - М.: Мир, 1978, т.2.

9. Грис Д. Конструирование компиляторов для цифровых вычислительных машин - М.: Мир, 1975.