Алгоритми пошуку (ДЗ)

Готові до тренування? 🤩

Сьогодні ви зможете використати знання алгоритмів пошуку, їхніх переваг і недоліків для розв’язання практичних завдань.

У цьому практичному завданні ви закріпите такі навички:

• досліджувати ефективність алгоритмів шляхом вимірювання їх часу виконання,
• порівнювати різні алгоритми пошуку та використовувати той, який найкраще підходить для вашої задачі, враховуючи їх ефективність,
• вміти програмно реалізувати алгоритм у вигляді окремої програми.

Домашнє завдання буде складатися з трьох незалежних завдань.

Опис домашнього завдання

Завдання 1

Додати метод delete для видалення пар ключ-значення таблиці HashTable, яка реалізована в конспекті.

Завдання 2

Реалізувати двійковий пошук для відсортованого масиву з дробовими числами. Написана функція для двійкового пошуку повинна повертати кортеж, де першим елементом є кількість ітерацій, потрібних для знаходження елемента. Другим елементом має бути "верхня межа" — це найменший елемент, який є більшим або рівним заданому значенню.

Завдання 3

Порівняти ефективність алгоритмів пошуку підрядка: Боєра-Мура, Кнута-Морріса-Пратта та Рабіна-Карпа на основі двох текстових файлів (стаття 1, стаття 2). Використовуючи timeit, треба виміряти час виконання кожного алгоритму для двох видів підрядків: одного, що дійсно існує в тексті, та іншого — вигаданого (вибір підрядків за вашим бажанням). На основі отриманих даних визначити найшвидший алгоритм для кожного тексту окремо та в цілому.

Підготовка та завантаження домашнього завдання

1. Створіть публічний репозиторій goit-algo-hw-05.
2. Виконайте завдання та відправте його у свій репозиторій.
3. Завантажте робочі файли на свій комп’ютер та прикріпіть їх у LMS у форматі zip. Назва архіву повинна бути у форматі ДЗ5_ПІБ.
4. Прикріпіть посилання на репозиторій goit-algo-hw-05 та відправте на перевірку.

Important

ВАЖЛИВО Перегляньте Інструкцію щодо завантаження робочого файлу з репозиторію на Github

Файли для роботи

Текстові файли для виконання завдання 3:

• стаття 1,
• стаття 2.

Формат здачі

• Прикріплені файли репозиторію у форматі zip з назвою ДЗ5_ПІБ.
• Посилання на репозиторій.

Критерії прийняття ДЗ

Прикріплені посилання на репозиторій goit-algo-hw-05 та безпосередньо самі файли репозиторію у форматі zip.

Завдання 1:

Код виконується, і метод delete видаляє задану пару ключ-значення в таблиці HashTable.

Завдання 2:

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

Завдання 3:

Програмно реалізовано алгоритми пошуку підрядка: Боєра-Мура, Кнута-Морріса-Пратта та Рабіна-Карпа.

На основі виконання кожного з трьох алгоритмів визначено найшвидший алгоритм для кожного з двох текстів.

Зроблено висновки щодо швидкостей алгоритмів для кожного тексту окремо та в цілому. Висновки оформлено у вигляді документа формату markdown.

Формат оцінювання

Залік/незалік

---

Висновки завдання № 3

Порівняння ефективності алгоритмів пошуку підрядка

Вступ

У даному дослідженні ми порівняли ефективність трьох алгоритмів пошуку підрядка: Боєра-Мура, Кнута-Морріса-Пратта та Рабіна-Карпа на основі двох текстових файлів. Ми виміряли час виконання кожного алгоритму для двох видів підрядків: одного, що дійсно існує в тексті, та іншого — вигаданого.

Результати

Стаття 1

Підрядок	Боєра-Мура	Кнута-Морріса-Пратта	Рабіна-Карпа
Існуючий	0.001729 с	0.018051 с	0.021425 с
Вигаданий	0.002020 с	0.016112 с	0.021219 с

Стаття 2

Підрядок	Боєра-Мура	Кнута-Морріса-Пратта	Рабіна-Карпа
Існуючий	0.001805 с	0.022221 с	0.030910 с
Вигаданий	0.002143 с	0.022438 с	0.030888 с

Висновки

Для першої статті найшвидшим алгоритмом для існуючого підрядка був алгоритм Боєра-Мура, а для вигаданого — алгоритм Кнута-Морріса-Пратта. У другій статті алгоритм Боєра-Мура показав найкращий результат для існуючого підрядка, а алгоритм Кнута-Морріса-Пратта — для вигаданого.

Загалом, алгоритм Боєра-Мура виявився найефективнішим для обох текстів в цілому. Це може бути пов'язано з певними особливостями текстів та вибраних підрядків.

Примітка: Час виміряно для 10 запусків кожного алгоритму, результати усереднено.