Материал: Інформатика_1 (методи побудови алгоритмівта та їх аналіз)

OldHeader: segment; begin

begin

i:=h(x);

OldHeader :=A[i];

new(A[i]);

A[i]\element := x;

if not find (x, А) (Якщо елемент x у відповідному сегменті не знайдено, то} then

{визначаємо номер списку,}

{якому повинен належати елемент х;}

{запам'ятаємо адресу списку,}

(де повинен знаходитись х;}

{визначаємо нову адресу початку сегмента;}

{в поле значения елемента записуємо х;}

{в поле адреси записуемо попередню адресу}

{початку даного списку; тепер список буде}

A[i]".next := OldHeader {починатися з нового елемента /',}

end; {до нього буде «причеплена» стара частина списку.}

end;

Читання, або вилучення, заданого елемента з хеш-таблиці:

procedure del (х: string; var A: hash);

{Оскільки хеш-таблиця зміниться, використовуемо var А.} var i: word;

current: segment; begin

if find (x, А) {Якщо елемент x у відповідиому сегменті знайдено, то}

then begin

І := h (x); {визначаємо номер списку, якому належить елементх.}

if А[і]^л.element = X {Якщо елементх стоїть у списку першим, то}

thenA[i] := A[i]\next {вилучаємох зі списку.}

else {Якщо елемент х стоіть у списку не першим, то}

begin

{визначаємо адресу початку сегмента,} current := A[i]; {де може знаходитисях.}

103

end;

{Пошук у списку еломента зі значениям X.} while (current".next О nil)

and (current".next".element <> x) do current := current".next;

{Вилучаємо елементхзі списку.} current".next := current".next".next end; end;

При використанні відкритих хеш-таблиць середній час ви-конання операцій зростає зі зростанням значения N/m. Особ­ливо швидко він росте при перевищенні кількості елементів над кількістю сегментів. Для збереження стабільного часу виконання операщй над відкритою хеш-таблицею пропонуєть-ся при досягненні N досить великих значень створити нову хеш-таблицю з подвоєною кількістю сегментів. Наприклад, це раціонально робити для N > 2m. Така процедура називається реструктуризацією. Час на створення нової хеш-таблиці нада-лі компенсується більшою швидкістю виконання операцій зі збільшеним словником.

Нам залишилося розібратися, яким же с принцип доступу до елементів хеш-таблиці. Оскільки елементи списків доступні для перегляду посередництвом одновимірних масивів, еле­менти яких містять адресу початку даного списку в пам'яті комп'ютера, дана структура вважаеться структурою прямого доступу. Справді, оскільки доступ до інформації в масиві с пря­мим, тому й обробка інформації в хеш-таблиці буде набагато швидшою, ніж у тому випадку, якби весь словник було орга-нізовано як структуру даних «список».

/ Запитання для самоконтролю

1. Сформулюйте задачу обробки словниковоТ інформації.

2. Що називається ключем елемента х?

1. Який спосіб організації інформації називається прямою адреса-цією?

2. Які проблеми можуть виникнути при прямій адресаціі інфор-мації?

3. У чому полягає ідея хешування інформації? У чому полягає ко-лізія при такій організації інформаціі?

3. Що називається сегментами та хеш-таблицею?

4. Яким чином структура даних «хеш-таблиця» відображається на пам'ять комп'ютера?

4. Зобразіть схематично базову структуру при хешуванні списками.

5. Як виглядає опис хеш-таблиці мовою Pascal?

10. Як можна зробити обробку елементів хеш-таблиці ефектив-нішою?

104

11. Яка функція називається хєш-функцією?

12. Які існують алгоритми побудови хеш-функціі, що дають можли-вість більш-менш рівномірно розподілити елементи в сегментах?

13. Як визначаються параметри при обчисленні хеш-функцій за різ-ними алгоритмами? Обґрунтуйте свою відповідь.

14. Запишіть текст обчислення значень хеш-функції мовою Pascal.

15. Запишіть текст процедури пошуку елемента в хеш-таблиці та поясніть алгоритм, за яким вона працює.

16. Запишіть текст процедури запису елемента в хеш-таблицю та поясніть алгоритм, за яким вона працює.

17. Запишіть текст процедури читання елемента з хеш-таблиці та поясніть алгоритм, за яким вона працюе.

18. Що називається реструктуризацією хеш-таблиці? Для чого вона використовується?

19. Який принцип доступу здійснюється до елементів хеш-таблиці при їх обробці? Обґрунтуйте свою відповідь.

Завдання

1. Розробити діалогову меню-орієнтовану програму роботи з елементами хеш-таблиці за такими пунктами:

1. записати елемент у хеш-таблицю;

2. прочитати елемент із хеш-таблиці;

3. здійснити пошук елемента в хеш-таблиці;

4. завершити роботу з хеш-таблицею.

2. Протестувати програму завдання 1 для N - 100, застосу­ вавши для визначення хеш-функції метод ділення з остачею, за такою схемою:

• створити хеш-таблицю, використавши процедуру запису елементів;

• перевірити відсутність у хеш-таблиці елемента, що запи-сується;

• записати цей елемент у хеш-таблицю;

• перевірити наявність записаного елемента у хеш-таблиці;

• перевірити наявність у хеш-таблиці елемента, що вилу-чаеться;

• вилучити цей елемент із хеш-таблиці;

• перевірити відсутність вилученого елемента у хеш-таб-лиці;

• записати 10 нових елементів у хеш-таблицю, перевіряючи їх наявність у ній після запису;

• виконати реструктуризацію хеш-таблиці.

3. Зробити письмовий аналіз виконання завдань 1,2.

4. Виконати завдання 1 для тієї самої вхідної інформації, застосувавши для визначення хеш-функції метод множення. Зробити письмовий аналіз виконання програми.

5. Порівняти результати виконання завдань 2 і 4. Зробити письмовий аналіз порівняльної характеристики.

105

10 1

Розділ IV

ооііоіI

0 0 0 D

10 10!

ОСНОВНІ

П0ШУК0ВІ АЛГОРИТМИ

ПОНЯТТЯ ПОШУКОВИХ АЛГОРИТМІВ

Пошук необхідної інформації - це одна з фуидаментальних задач теоретичної інформатики та програмування. Саме пошу-кові алгоритми найчастіше є фрагментами різноманітних більш складних алгоритмів.

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

Пошукові алгоритми закладені в основи багатьох електрон-них систем обробки інформації: придбання квитка в заліз-ничних касах, отримання інформації про необхідний номер телефону в довідковій телефонній службі, користування по­шуковими сайтами в Інтернеті, пошук інформації в будь-яких текстових редакторах тощо.

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

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

Розглядаючи структури даних, ми вже торкнулися питания пошуку інформації у множині їх елементів. Тепер нашим зав-данням буде більш ретельний аналіз оцінки ефективності вико-нання тих чи ініпих пошукових алгоритмів на різних структу­рах даних.

Саме тому визначимо такі основні аспекти ознайомлення з пошуковими алгоритмами.

При обговоренні пошукових алгоритмів вважатимемо, що інформація описується певчими структурами даних. Якщо щ структури даних будуть складеними, такі, наприклад, як за­писи, що складаються з кількох полів, то нас цікавитиме зна­чения лише одного з цих полів.

106

Тому надалі будемо говорити про деякий абстрактний тип даних item, що описуе запис з деяким полем, що виконуе роль ключа. Наше завдання полягатиме в тому, щоб здійснювати пошук елемента, ключ якого дорівнює заданому «аргументу пошуку» х. Отриманий у результаті індекс і, що задовольняє умову A[i].key = х, забезпечує доступ до інших полів знайденого елемента. Але надалі спростимо опис структури, мотивуючи це таким. Оскільки нас у першу черту цікавить сам процес по­шуку, а не дані структури, то вважатимемо, що тип item і є тим самим ключей.

I останнє, вважатимемо, що група даних, у якій здійснюєть-ся пошук заданого елемента, є фіксованою. Це означатиме, що множина значень задається у кількості N елементів, що може бути описано таким масивом:

A: array[1„ N] of item;

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

ЛІНІЙНИЙ ПОШУК

Алгоритм лінійного пошуку

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

Спочатку розглянемо алгоритм поставлено! задачі в такому трактуванні:

1. Задати масив значень А для пошуку.

2. Задати шуканий елемент х.

1. Починаючи з першого елемента масиву до останнього по-рівнювати їх із шуканим елементом І, в разі хоча б одного збі-гання їх значень, зафіксувати дю ситуацію.

2. У разі хоча б одного збігання значень елементів масиву зі значениям шуканого елемента, повідомити про це. У протилеж-ному випадку повідомити про відсутність шуканого елемента в заданому масиві значень.

Запишемо текст фрагмента Pascal-програми, що реалізує описаний алгоритм:

flag := false; for i := 1 to n do

if a[i] = x then flag ;= true;

107

if Hag then writeln ('Шуканий елемент знайдеио')

else writeln ('Шуканий елемент не знайдено');

Оцінкою ефективності роботи наведеного алгоритму є, в пер­шу чергу, кількість порівняпь елементів масиву з шуканим елементом. Який висновок можна зробити, проаналізувавши виконання наведеного алгоритму?

Якщо шуканий елемент збігатиметься лише з ЛГ-м елемен­том масиву, тобто останнім у масиві, то для отримання резуль­тату треба виконати всі кроки циклу. У випадку, коли шука­ний елемент збігатиметься з елементом масиву, індекс якого менший за N, то будуть виконані зайві порівняння, тобто перегляд масиву до кінця недоцільний. Тому для запису дослі-джуваного алгоритму ефективніше використати цикл із перед-умовою, який виконуватиметься за таких умов:

— ознака того, що не всі елементи масиву ще переглянуті: i<N;

- незбігання шуканого елемента з поточним елементом масиву: а[і] * х.

Зрозуміло, що обидві ці ознаки повинні виконуватись од-ночасно. Наведений вище алгоритм тепер матиме такий ви-гляд:

1. Почнемо перегляд заданого масиву з першого елемента.

2. Поки шуканий елемент х не збігається з поточним елемен­том масиву а[і] і ми не вийшли за межі заданого масиву, то перейти до наступного елемента в масиві.

3. Якщо при відшуканні елемента х у масиві ми вийшли за його межі, тобто порядковий номер поточного елемента масиву сягнув значения N, то це означав, що шуканий елемент у за-даному масиві відсутній. У протилежному випадку шуканий елемент знайдено на і-му місці в масиві.

Цьому фрагменту алгоритму відповідає такий текст Pascal-програми:

i:=1;

while (a[i] <> х) and (i <= N) do i := i + 1;

if i <= N then writeln ('Шуканий елемент знайдено')

else writeln ('Шуканий елемент не знайдено');

Зрозуміло, що останній алгоритм набагато ефективніший, ніж перший його варіант. Але і його можна вдосконалити.

Проаналізуємо випадки виконання умови (а[і] О х) and (i <= N) і подумаємо, чи можна ЇЇ спростити. У цій умові ми перевіряє-мо, чи не вийшли за межі заданого масиву і чи збігається поточний елемент масиву з шуканим. Перша частина умови потрібна тільки у випадку, коли ми не впевнені в тому, що шуканий елемент у масиві є. Це означав, що в разі стовідсотко-вої наявності шуканого елемента в масиві цю частину умови

108

можна вилучити. А коли можна бути впевненими в тому, що елемент у масиві точно є? Лише тоді, коли ми самі його туди запишемо! I дописати його треба в кінець масиву, щоб він не заважав відшуканню інших таких елементів, якщо вони в ма-сиві є: a[N + 1 ] := х. Тепер виконання умови a[N + 1 ] = х стверджує той факт, що шуканий елемент відсутній у заданому масиві, оскільки знайдено елемент, який ми штучно дописали в кінець масиву.

Описавши масив a: array[1.. N + 1] of <тип>, перепишемо алго­ритм мовою Pascal у такому вигляді:

a[N + 1]:=x;

i:=1;

while (a[i] о х) do i :=i+ 1;

if i<N + 1 then writeln ('Шуканий елемент знайдено')

else writeln ('Шуканий елемент не знайдено');

Можна зробити висновок, що створено ефективний варіант лінійного пошукового алгоритму.

Оцінка ефективності лінійного пошуку напряму залежить від кількості елементів масиву. У найкращому варіанті, коли шуканий елемент знаходиться на першому місці, вона дорів-нює O(l), у найгіршому, коли шуканий елемент знаходиться на останньому місці або зовсім відсутній у масиві, — O(N), а в се-редньому варіанті - 0(N/2). Саме середній варіант можна ви-значити за остаточну оцінку даного пошукового методу.

/ Запитання для самоконтролю

1. Сформулюйте задачу пошуку задано! інформації в заданій групі значень.

2. Які алгоритми називаються пошуковими?

3. Наведіть приклади використання пошукових апгоритмів.

4. Визначте основні аспекти, на яких базується розробка пошуко­вих алгоритмів.

5. У чому полягає лінійний, або послідовний, пошук інформації?

6. Запишіть алгоритм і текст Pascal-програми лінійного пошуку ін-формаціі, при виконанні якого повністю переглядається весь масив.

7. У чому полягає удосконалення попереднього алгоритму? Обґрунтуйте його та запишіть фрагмент алгоритму І текст Pascal-програми.

8. За рахунок чого можна удосконалити умову виконання повто­рения при пошуку заданого значения величини серед елементів масиву?

9. Запишіть остаточний найефективніший варіант лінійного по­шукового алгоритму, що використовує найменшу кількість повторень і перевірок умов.

10. Якою є оцінка ефективності роботи лінійного пошукового алго­ритму?

109

Завдання

1. Реалізувати алгоритм лінійпого пошуку заданого елемеп-та в масиві за допомогою циклу з лічильником мовою Pascal.

2. Реалізувати алгоритм лінійного пошуку заданого елемен-та в масиві за допомогою циклу з передумовою мовою Pascal.

3. Реалізувати алгоритм лінійного пошуку заданого елемен-та в масиві за допомогою циклу з передумовою, дописавши шу-каний елемент у кінець масиву мовою Pascal.

4. Порівняти виконання алгоритмів щодо кількості викона-них порівнянь у завданнях 1-3, протестувавши їх для випад-ків, коли шуканий елемент розміщений:

1. на початку масиву;

2. у кінці масиву;

3. посередині масиву.

Бінарний пошук Пошук діленням навпіл

Кожен із вас мав нагоду шукати деяку інформацію у зви-чайній книжці чи в словнику. Різниця такого пошуку досить очевидна: у словнику вона впорядкована за алфавітом, а в книжці розташована в довільному порядку. Зрозуміло, що пер­ший випадок розміщення інформації набагато зручніший. Як можна скористатися впорядкованістю інформації? Прига-даємо, як ми здійснюємо пошук у словнику:

1) відкриваємо словник у довільному місці й дивимося: якщо шукане слово знайдено, то пошук припиняемо, в іншому випадку переходимо до наступного пункту;

2. якщо слово знаходиться попереду, то друга частина слов­ника нас уже не цікавить і ми відкриваємо його десь усередині першої частини і починаемо пошук так само, як і в пункті 1);

3. якщо слово знаходиться далі, то перша частина словника нас не цікавить і ми відкриваємо його десь усередині другої частини та починаемо пошук так само, як і в пункті 1).

Ми, фактично, записали алгоритм пошуку інформації в упо-рядкованій послідовності елементів. Він носить назву бінарно-го (двійкового) пошуку, або пошуку методом поділу навпіл.

Визначимося щодо нашої задачі в алгоритмічних термінах. Нам задано масив а₍, і - 1, 2, ..., п, для елементів якого справджується умова: a_t < a, + 1, і - 1, 2, .... п - 1. Шуканий елемент позначимо х, а елемент масиву, відносно якого масив ділиться на дві частини, - через а\т].

110

Тепер алгоритм бінарного пошуку виглядатиме так:

1. Визначимо т.

2. Якщо а[т] = х, то пошук завершено і переходимо до п. 5, в іншому випадку переходимо до п. 3.

3. Якщо а[т] < х, то всі елементи з індексами, меншими за т, можна відкинути і перейти до п. 1.

4. Якщо а[т] > х, то всі елементи з індексами, більшими за т, можна відкинути і перейти до п. 1.

5. Вивести результат (фп].

Нам необхідно однозначно визначитися щодо елемента, від-носно якого відбувається поділ масиву на дві частини. Таким елементом може бути довільний елемент масиву, навіть визна-чений випадковим чином у проміжку [1; N]. Але зрозуміло, що наикращим варіантом буде вибір «центрального» елемента a[N + 1 div 2], оскільки при цьому в будь-якому разі буде від-кидатися половина масиву.

Ще однією домовленістю повинна бути визначеність щодо обставини «відкидання» правої чи лівої частини масиву. Щоце означав? Якщо на самому початку межами масиву є індекси 1 i N, то з кожним кроком цей проміжок звужується. При цьому або значения лівої межі переміщається вправо, або пра­во! - вліво. Для того щоб бути однозначними також і в позна-ченні меж проміжку значень індексів елементів масиву, що розглядається, давайте ліву межу будемо позначати змінною L, а праву - R. У цих термінах «відкидання» лівої частини маси­ву відносно <i[N + 1 div 2] буде відповідати дії' L := (N + 1 div 2) + 1, правої - R := (N + 1 div 2) - 1.

Перш ніж переходити до створення алгоритму, поміркуємо ще над умовами його завершения, тобто над ознаками визна-чення результату пошуку. На кожному кроці ми визначаємо центральний елемент послідовності, відповідно до значения якого відбувається порівняння із шуканим елементом х. Тому, якщо значения шуканого елемента співпаде зі значениям елемента а[т], алгоритм пошуку можна припиняти. Для пе-ревірки цієї умови введемо логічну змінну flag, яка набуватиме значения true у випадку, коли на певному кроці пошуку ми натрапимо на шуканий елемент, тобто виконається умова а[т] = х.

Представимо наведений алгоритм бінарного пошуку мовою Pascal:

L := 1;R:=N; flag := false; while (L <= R) and not flag do begin

m:=(L+R)div2; if a[m] = x then flag := true