neopite / introtoproglab3

Повернутись

Assignment #3. Data structures

Варіант завдання – остача від ділення номеру бригади на 3. Варіантами можна обмінюватись, але не можна просто змінювати за власним бажанням. Будь ласка, перед виконанням заповніть цю таблицю. Вимоги до використання git такі самі, як і в попередній роботі. Також уважно ознайомтесь з загальними правилами здачі лабораторних та принципами оцінювання.

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

Питання та необхідні знання

Друга робота знайомить вас із імплементацією структур даних, які надалі використовуватимуться у більшості програм, які ви будете писати. В цій лабораторній для успішної здачі вам треба буде відповісти на кілька теоретичних питань. Отже для повноцінної здачі вам треба:

• Знати, що таке О-велике і для чого воно використовується.
• Розуміти, чому алгоритми та структури, запропоновані в цій роботі, мають ту чи іншу асимптотичну слкадність (вивчити напам'ять не значить зрозуміти, для здачі треба буде відповісти на питання чому певні алгоритми або структури мають саме таку складність, а не яку вони мають складність).
• Мати уявлення, в яких випадках краще використовувати одні структури, а в яких – інші.
• Розбиратися в структурах stack, queue, priority queue, linked list, doubly linked list, hash table.
• Пошук шляху у графі, алгоритм Дейкстри та A*
• Мати поняття, що таке евристика (посилання є нижче, в варіанті №1)
• Розуміти, як працює і яке завдання у хеш-функцій (зауважте, що існують також криптографічні хеш-функції, які не мають відношення до цієї роботи; якщо ви читаєте статтю про хеші і часто зустрічаєте слова "md5", "sha", "bcrypt", "криптографія" – ви читаєте не те, що треба)

Варіант #2. Словник

Розробити програму, яка на запит речення англійською мовою, видаватиме тлумачення кожного слова з цього речення або його переклад на іншу мову. Для цього найкраще буде використати структуру даних "хеш таблиця" (hash map, hash table, dictionary). Найпростіший спосіб зробити хеш таблицю – за допомогою масиву, в якому зберігаються зв'язні списки (linked list). Обидві структури треба написати власноруч. В простому варіанті завдання можна зазаделегідь виділити достатньо пам'яті для таблиці.

Складніше завдання (+1 бал): Ви не знаєте наперед, скільки елементів буде зберігатися в таблиці. Хеш-таблиця має розширюватися в два рази і перебудовуватися, коли кількість доданих значень перевищує 80% від кількості комірок в таблиці. Це стандартна поведінка, що використовується в більшості стандартних бібліотеках.

Вхідні та вихідні дані

Ви можете використати готовий словник з цього файла (там 22 Мб тексту, в блокноті краще не відкривати). Оригінал.

Слова даються програмі на вхід через стандартний потік вводу. Наприклад, якщо ви скомпілюєте свою програму в define.exe:

> define [Enter]
Type a sentence to get definition: hash [Enter]

HASH; Hash, n. Etym: [Formerly hachey, hachee, F. hachis, hacher to hash; of German origin; cf. G. hippe sickle, OHG. hippa, for happia.
Cf. Hatchet.]  1. That which is hashed or chopped up; meat and vegetables, especially such as have been already cooked, chopped into
small pieces and mixed.  2. A new mixture of old matter; a second preparation or exhibition. I can not bear elections, and still less
the hash of them over again in a first session. Walpole.
Type a word to get definition: ...

Посилання

• Відео лекції в MIT на тему хеш-таблиць
• Wiki
• Hash table з курсу прінстонського університету
• Хороше пояснення на stackoverflow

Таблиці використовуються практично в будь-якій складній програмі. В базах даних їх використовують для швидкого пошуку полів, хоча часто використовують складніші B-дерева; в інтерпретованих мовах програмування для збергіння структур (ключами є назви змінних, значеннями – їхні значення); в ядрі Linux простіше сказати, де хеші не використовуються; хеш-таблиці є у більшості файлових систем, наприклад для реалізації індексних дескрипторів; для пошуку помилок у файлових системах; в алгоритмі Рабіна—Карпа для пошуку рядків, який в свою чергу часто використовується для пошуку плагіату.

*Написання алгоритму хеш-функції та структур linked list і hash table є обов'язковою умовою для здачі цього варіанту