НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №4 з навчальної дисципліни “Програмування складних алгоритмів” Тема: «Методи пошуку у масивах» Варіант № 20 Дата «17» червня 2022 Мета роботи: Метою лабораторної роботи є отримання практичних навичок в обробці масивів, у пошуку елементів масивів різними методами. Дослідження і вивчення методів пошуку ключових елементів у масивах. Здійснення порівняння та аналізу ефективності використовуваних методів пошуку. Завдання до лабораторної роботи: 1. Знайти заданий елемент у невпорядкованому масиві (не менше 10х10) за допомогою методу пошуку з бар’єром. 2. Знайти заданий елемент у впорядкованому масиві (не менше 10х10) згідно варіантів за таким принципом. Завдання для варіанту 20: «Пошук послідовності елементів в масиві» Теоретична частина Алгоритм пошуку — алгоритм, який вирішує задачу пошуку, тобто, знаходить інформацію, яка зберігається в певній структурі даних. Структури даних можуть бути реалізовані за допомогою зв'язаних списків, масивів, дерев пошуку, хеш-таблиць чи інших методів зберігання інформації. Алгоритм пошуку на пряму залежить від структури даних для якої він реалізований. Пошук – знаходження будь-якої конкретної інформації у великому обсязі раніше зібраних даних. Дані діляться на записи, і кожний запис має хоча б один ключ. Ключ використовується для того, щоб відрізнити один запис від іншого. Метою пошуку є знаходження всіх записів, що підходять до заданого ключа пошуку. – Пошук елементу в масиві (послідовний пошук – неупорядкованої інформації, але також можна використовувати його й на відсортованих даних) – Двійковий пошук (Бінарний пошук) – Пошук послідовності елементів в масиві. – Алгоритм Рабіна-Карпа Лінійний пошук бар’єром Ідея пошуку з бар'єром полягає в тому, щоб не перевіряти щораз у циклі умова, пов'язане із границями масиву. Це можна забезпечити, установивши в масив так званий бар'єр: будь-який елемент, що задовольняє умові пошуку. Тим самим буде обмежена зміна індексу. Вихід із циклу, у якому тепер залишається тільки умова пошуку, може відбутися або на знайденому елементі, або на бар'єрі. Таким чином, після виходу із циклу перевіряється, не чи бар'єр ми знайшли? Обчислювальна складність пошуку з бар'єром менше, ніж у лінійного пошуку, але також є величиною того ж порядку, що й N - кількість елементів масиву. Пошук послідовності елементів в масиві Одне з найпростіших завдань пошуку інформації – пошук точно заданого підрядка у рядку. Пошук рядка формально визначається в такий спосіб. Нехай заданий масив Т з N елементами і масив W з M елементами, причому 0 < M ≤ N. Пошук рядка виявляє перше входження W у Т, результатом будемо вважати індекс і, що вказує на перший з початку рядка (з початку масиву Т) збіг зі зразком (словом). Виконання роботи Порівняння часу виконання в залежності від розміру масиву Спосіб сортування Розмір N*N Кількість ітерацій Час виконання  Barier search 10*10 91 4.078ms   30*30 758 8.075ms  Word search 10*10 100 0.746ms   30*30 900 5.348ms   / Результати Для масиву розмірністю 10 на 10 пошук бар’єром: / Для масиву розмірністю 10 на 10 пошук послідовності елементів в масиві:/ Для масиву розмірністю 30 на 30 пошук бар’єром: / / Для масиву розмірністю 30 на 30 пошук послідовності елементів в масиві: / Висновки: У ході виконання даної лабораторної роботи було отримано практичні навички в обробці масивів, у пошуку елементів масивів методами бар’єрного пошуку та пошуку послідовності, досліджено і вивчено методи пошуку ключових елементів у масивах. Здійснено порівняння та аналіз ефективності використовуваних методів пошуку. Код програми у вигляді скріншотів / / /