Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Методи пошуку. Алгоритм Кнута-Моріса-Прата.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2015
Тип роботи:
Методичні вказівки
Предмет:
Алгоритми і структури даних
Частина тексту файла (без зображень, графіків і формул):
Міністерство Освіти України
Національний університет «Львівська політехніка»
Методичні вказівки
До лабораторної роботи № 11
На тему: «Методи пошуку. Алгоритм Кнута-Моріса-Прата»
з дисципліни
«Алгоритми і структури даних»
Для базового напрямку 6.0804 «Комп’ютерні науки»
ЗАТВЕРДЖЕНО
на засіданні кафедри
програмного забезпечення
протокол № від 2008 року
місто Львів
2008 рік
Методичні вказівки до лабораторної роботи з дисципліни «Алгоритми і структури даних» Для базового напрямку 6.0804 «Комп’ютерні науки»
Укладачі: Семчишин Ю. Б.
Коротєєва Т. О.
Вовчак І. Г.
Відповідальний за випуск:
Рецензенти:
Тема роботи: Ознайомлення із методами пошуку. Алгоритм Кнута-Моріса-Прата.
Мета роботи: Вивчити та дослідити методи пошуку, як один із методів обробки даних. Ознайомитись із алгоритмом Кнута-Моріса-Прата. Виконати лабораторну роботу використавши здобуті знання з методів пошуку, зокрема алгоритму Кнута-Моріса-Прата.
ТЕОРЕТИЧНІ ВІДОМОСТІ
Алгоритм Кнута-Моріса-Прата (англ. Knuth–Morris–Pratt algorithm) шукає входження слова W у рядку S використовуючи просте спостереження, що коли відбувається невідповідність, то слово містить у собі достатньо інформації, для того щоб визначити, де наступне входження може початися, таким чином пропускаючи кілька разову перевірка попередньо порівняних символів.
Алгоритм був винайдений вченими Donald Knuth та Vaughan Pratt і незалежно J. H. Morris у 1977 році, але був опублікований у спільній статті.
Маємо масив символів S з n елементів (текст) та масив P з m - взірець. Необхідно знайти перше входження взірця в масив. Схема алгоритму полягає у поступовому порівнянні взірця з текстом та зсуву по тексту на кількість співпавших символів у разі знайденого неспівпадіння.
Алгоритм КМП
КМП1. Встановити і=0.
КМП2. j=0, d=1.
КМП2. Поки j<m, i<n
КМП 3. Перевірка: якщо s[i]=p[j], то d++, i++.j++ поки d != m.
Інакше встановити зсув взірця на d позицій по тексту. Перейти на крок КМП2.
КМП4. Кінець.
Складність алгоритму становить O(n+m).
Приклад,
Hoola-Hoola girls like Hooligan - текст
Hooligan – взірець
Hoola-Hoola girls like Hooligan
Hooligan i!=a, d=4
Hooligan H!=a, d=1
Hooligan H!=-, d=1
Hooligan i!=a, d=4
…..
Hooligan d=m=8
РЕКОМЕНДОВАНІ ДЖЕРЕЛА
http://www.wikipedia.org/.
Donald Ervin Knuth «The Art of Computer Programming».
2. ВКАЗІВКИ ДО ВИКОНАННЯ РОБОТИ
При реалізації алгоритму застосувати здобуті знання на лабораторній роботі. Тобто у всіх завданнях необхідно реалізувати алгоритм Кнута-Моріса-Прата.
Використовувати мову програмування C/C++.
Лабораторна робота вважається зданою при наявності програмного продукту звіту і проведеного відповідного захисту виконаної роботи.
3. ПОСЛІДОВНІСТЬ ВИКОНАННЯ РОБОТИ
Отримати індивідуальне завдання у викладача;
Уточнити завдання (можливі різні трактування завдання);
Написати програмну реалізацію виконання індивідуального завдання із використанням вивченого методу (алгоритму) на даній лабораторній роботі;
Протестувати на наявність логічних помилок програми;
Оформити звіт відповідно до стандарту;
Захистити виконану роботу.
4. КОНТРОЛЬНІ ПИТАННЯ
Які ви знаєте методи пошуку?
Який метод пошуку був розглянений на даній лабораторній роботі?
Від чого прямо – залежним являється швидкість пошуку?
Опишіть характеристики даного методу.
Порівняєте даний метод із іншими методами пошуку вам відомими.
Наскільки являється ефективним даний метод пошуку?
Чи використовують даний метод на практиці, і наскільки часто?
Чи можлива оптимізації даного методу? Якщо так, то яка? Якщо ні, то по яких причинах?
Чим оригінальним виділяється даний метод від інших?
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора