Міністерство Освіти України Національний університет «Львівська політехніка» Методичні вказівки До лабораторної роботи № 9 На тему: «Методи пошуку. Пошук в глибину» з дисципліни «Алгоритми і структури даних» Для базового напрямку 6.0804 «Комп’ютерні науки» ЗАТВЕРДЖЕНО на засіданні кафедри програмного забезпечення протокол № від 2008 року місто Львів 2008 рік Методичні вказівки до лабораторної роботи з дисципліни «Алгоритми і структури даних» Для базового напрямку 6.0804 «Комп’ютерні науки» Укладачі: [ім’я автора приховано] [ім’я автора приховано] [ім’я автора приховано] Відповідальний за випуск: Рецензенти: Тема роботи: Ознайомлення із методами пошуку. Алгоритм пошуку в глибину. Мета роботи: Вивчити та дослідити методи пошуку, як один із методів обробки даних. Ознайомитись із методом пошуку в глибину. Виконати лабораторну роботу використавши здобуті знання з методів пошуку, зокрема методу пошуку в глибину. ТЕОРЕТИЧНІ ВІДОМОСТІ Пошук в глибину (англ. Depth-first search (DFS)) — один з методів обходу графа. Коротко суть алгоритму можна викласти так: для кожної непройденої вершины необхідно знайти всі непройдені суміжні вершини та повторити пошук для них. На рис. 1 представлено дерево, вершини якого пронумеровано в порядку обходу цього дерева алгоритмом пошуку в глибину.
Рис. 1. Порядок обходу дерева в глибину. РЕКОМЕНДОВАНІ ДЖЕРЕЛА http://www.wikipedia.org/. Donald Ervin Knuth «The Art of Computer Programming». 2. ВКАЗІВКИ ДО ВИКОНАННЯ РОБОТИ При реалізації алгоритму застосувати здобуті знання на лабораторній роботі. Тобто у всіх завданнях необхідно реалізувати алгоритм пошуку в глибину. Використовувати мову програмування C/C++. Лабораторна робота вважається зданою при наявності програмного продукту звіту і проведеного відповідного захисту виконаної роботи. 3. ПОСЛІДОВНІСТЬ ВИКОНАННЯ РОБОТИ Отримати індивідуальне завдання у викладача; Уточнити завдання (можливі різні трактування завдання); Написати програмну реалізацію виконання індивідуального завдання із використанням вивченого методу (алгоритму) на даній лабораторній роботі; Протестувати на наявність логічних помилок програми; Оформити звіт відповідно до стандарту; Захистити виконану роботу. 4. КОНТРОЛЬНІ ПИТАННЯ Які ви знаєте методи пошуку? Який метод пошуку був розглянений на даній лабораторній роботі? Від чого прямо – залежним являється швидкість пошуку? Опишіть характеристики даного методу. Порівняєте даний метод із іншими методами пошуку вам відомими. Наскільки являється ефективним даний метод пошуку? Чи використовують даний метод на практиці, і наскільки часто? Чи можлива оптимізації даного методу? Якщо так, то яка? Якщо ні, то по яких причинах? Чим оригінальним виділяється даний метод від інших?