Главная | Обратная связь

ПОРЯДОК ВИКОНАННЯ РОБОТИ

1. При підготовці до лабораторної роботи, необхідно засвоїти теоретичний матеріал по темі і підготуватись до контрольного опитування по розумінню питань даної тематики.

2. Згідно з індивідуальним завданням розробити алгоритм розв’язання задачі.

3. Підготувати програмну реалізацію розробленого алгоритму. Засобами вбудованого тексто-вого редактора інтегрованого середовища набрати текст підготовленої програми. Відкомпілювати, налагодити та виконати програму.

4. Протестувати програму згідно зі складеною системою тестів і, при потребі, відкоректувати текст програми. Проаналізувати отримані результати.

5. Написати контрольне опитування по темі.

6. Оформити звіт по роботі.

Без підготовкі до лабораторної роботи (програмної реалізації розробленого алгоритму) студент до роботи не допускається.

 

ЗАВДАННЯ НА ЛАБОРАТОРНУ РОБОТУ

 

Завдання

Написати програму, що отримує на вході послідовність слів (ключів), будує дві хеш-таблиці цих слів, виконує операції додавання нових слів в побудовані хеш-таблиці та вилучення заданих елементів з таблиць, виводить на екран вміст кожної таблиці, здійснює багаторазовий пошук довільних слів в цих хеш-таблицях, порівнює ефективності різних методів організації хеш-таблиць.

Список вхідних слів довжиною n=28 задати у вигляді текстового файла data.txt . Файл data.txt має містити таку інформацію (всі слова (або числа) записуються латинськими літерами підряд через кому):

- прізвище, ім'я, побатькові,

- день, місяць,рік народження,

- назва компанii мобільного зв'язку,

- підряд через пробіл всі цифри мобільного телефона, починаючи з кода оператора (всього 10 цифр),

- назва області, міста і вулиці в адресі прописки,

- номер будинку і квартири в адресі прописки,

- абревіатура інститута, кафедри, групи,

- день, місяць,рік виконання лабораторної роботи.

Наприклад: Вміст файлу data.txt :

Petrenko,Bogdan,Sergyjovuch,25,3,1989,Kyivstar,0,6,7,5,7,6,4,9,2,1,Lvivska,Lviv,Bandery,12,1,IKTA,EOM,KI-21,12,4,2010

 

Весь вхідний список слів розмістити в першій хеш-таблиці розмірністю m=37, метод побудови якої вибрати згідно з варіантом. Також весь вхідний список слів розмістити у другій хеш-таблиці, метод побудови якої вибрати самостійно. Забороняється вибирати хеш-функції, що співпадають з прикладами хеш-функції, наведених в цих методичних вказівках. При виборі хеш-функції намагатись, щоб ефективність організації другої таблиці була вищою, ніж першої.

Забезпечити виконання програмою на вимогу користувача операцій додавання та вилучення елементів з хеш-таблиць.

В процесі роботи з таблицями на вимогу користувача програма повинна виводити на екран вміст кожної хеш-таблиці.

Під час пошуку слів в хеш-таблицях програма повинна виводити на екран послідовність слів з якими виконуються порівняння і кількість виконаних операцій порівняння.

Для оцінки ефективностей побудованих методів підрахувати загальну кількість операцій порівняння для пошуку всіх слів в хеш-таблиці:

,

де С _і — кількість виконаних операцій порівняння в хеш-таблиці при пошуку і-го слова з файла data.txt , n- кількість слів в файлі data.txt.

Знайти значення С ⁿ для різніх степінів заповнення кожної хеш-таблиці. Для цього спочатку в хеш-таблицю розмістити тільки одне (n=1) слово (перше слово з файла data.txt) і обчислити значення С ¹ , потім розмістити два (n=2) слова (перші два слова з файла data.txt) і обчислити значення С ² , потім три (n=3) слова і т.д.

Відношення називається коефіцієнтом заповнення хеш-таблиці.

Згідно отриманих значень С ⁿ для кожної хеш-таблиці побудувати в звіті графік залежності ефективності методу побудови хеш-таблиці від коефіцієнтаїї заповнення, тобто графік С=f(α).

Аналогічно знайти значення С ^m для різніх розмірностей хеш-таблиці. Для цього спочатку розмістити всі слова з файла data.txt в хеш-таблицю розмірністю m=n=28 (для методу роздільних ланцюжків або для методу відкритого хешування прийняти спочатку m=1) і обчислити значення С ¹ , потім розмістити всі слова в хеш-таблицю розмірністю m+1 і обчислити значення С ² , потім в хеш-таблицю розмірністю m+2 і т.д. Згідно отриманих значень С ^m для кожної хеш-таблиці побудувати в звіті графік залежності ефективності методу побудови таблиці від її розмірності, тобто графік С=f(m).

Зробити грунтовний письмовий висновок стосовно порівняння ефективностей різних методів організації хеш-таблиць.