 |
|
|
Архитектура Астрономия Аудит Биология Ботаника Бухгалтерский учёт Войное дело Генетика География Геология Дизайн Искусство История Кино Кулинария Культура Литература Математика Медицина Металлургия Мифология Музыка Психология Религия Спорт Строительство Техника Транспорт Туризм Усадьба Физика Фотография Химия Экология Электричество Электроника Энергетика |
Розрахункова робота (якщо програма)
Розрахункова контрольна робота
Написати програму, яка одержує на вході набір ідентифікаторів, організує таблицю по заданому методу і дозволяє здійснити багаторазовий пошук ідентифікатора в цій таблиці. Список ідентифікаторів вважати заданим у вигляді текстового файла (кількість ідентифікаторів>=500). Довжина ідентифікаторів обмежена 32 символами. В усіх варіантах потрібно розробити програму, що реалізує комбінований спосіб організації таблиці ідентифікаторів. Для організації таблиці використовується найпростіша хеш-функція, зазначена у варіанті завдання, а при виникненні колізій використовується додатковий метод розміщення ідентифікаторів у пам'яті. У випадку, коли метод використовує дерево або список, то вони повинні бути зв'язані з елементом головної хеш-таблиці. У кожному варіанті потрібно, щоб програма повідомляла середню кількість колізій і середню кількість порівнянь, виконаних для пошуку ідентифікатора. Побудувати граматику, що породжує множину ланцюжків даної заданої мови ваших ідентифікаторів та побудувати КА, що розпізнає задану граматику.
Хід роботи 1. Дати визначення ідентифікатора ВАШОЇ мови. 2. Записати граматику побудови ВАШИХ ідентифікаторів. Для завдання правил використати різні форми опису: символічну, форму Наура-Бекуса, ітераційну форма й синтаксичні діаграми. 3. Побудувати КА, що розпізнає задану граматику. 4. Описати комбінований метод, хеш-функцію та спосіб вирішення колізій. 5. Визначити максимальне і мінімальне значення хеш-функції 6. Виписати 20 ідентифікаторів таких, щоби деякі з них містили колізії (~5). 7. Виконати покрокове заповнення таблиці ідентифікаторів відповідно до вашого варіанта. 8. Визначити середню кількість колізій і середню кількість порівнянь, виконаних для пошуку ідентифікатора для виконаного завдання. Порівняти їх із розрахованими аналітично. 9. Розробити схему організації хеш-таблиці. 10.Розробити алгоритм пошуку в хеш-таблиці. 11.Написати і налагодити програму на ЕОМ.
Додаток 1
ВАРІАНТИ ЗАВДАНЬ ДО РОЗРАХУНКОВОЇ РОБОТИ № 1
Розрахункова робота (якщо програма) повинна містити
1. Титульна сторінка роботи; 2. Анотація до роботи (на українській мові); 6. Технічне завдання - титульна частина; - основна частина за всіма пунктами; 7. Пояснююча записка - титульна частина; - інформаційна частина; - основна частина за всіма пунктами; 8. Опис мови - титульна частина; - інформаційна частина; - основна частина за всіма пунктами; 9. Опис програми - титульна частина; - інформаційна частина; - основна частина за всіма пунктами; 10. Текст програми - титульна частина; - інформаційна частина; - основна частина за всіма пунктами; 11. Програма та методика випробування - титульна частина; - інформаційна частина; - основна частина за всіма пунктами.
Поиск по сайту: |