Порівняльний аналіз простих методів пошуку

Размещено на http://www.allbest.ru/

ЕКОНОМІКО-ПРАВНИЧИЙ КОЛЕДЖ

ДЕРЖАВНОГО ВИЩОГО НАВЧАЛЬНОГО ЗАКЛАДУ

«ЗАПОРІЗЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ»

МІНІСТЕРСТВА ОСВІТИ І НАУКИ УКРАЇНИ

КУРСОВА РОБОТА

З дисципліни «Основи програмування»

На тему:

«Порівняльний аналіз простих методів пошуку»



ЗМІСТ

1) РЕФЕРАТ

2) ВСТУП

3) РОЗДІЛ 1. ПОНЯТТЯ АЛГОРИТМУ ПОШУКУ

3.1 Сортування та пошук даних

3.2 Лінійний (послідовний) метод пошуку

3.3 Бінарний (двійковий) метод пошуку

4) РОЗДІЛ 2.ПОРІВНЯЛЬНИЙ АНАЛІЗ

4.1 Теорія складності обчислень

4.2 Використання методів пошуку на практиці

4.3 Результати порівняльного аналізу

5) ВИСНОВКИ

6) ДОДАТКИ

7) СПИСОК ЛІТЕРАТУРИ



РЕФЕРАТ

Обсяг роботи сторінок, таблиця, зображень, джерел, додатка.

Об'єкт дослідження - є алгоритмічні моделі та засоби пошуку елементів масивів.

Предмет дослідження - особливості простих методів пошуку.

Мета - дослідити особливості роботи простих методів пошуку, переваги використання окремих методів на практиці.

Завдання:

- Проаналізувати ефективність простих методів пошуку.

- Визначити корисність використання методів у задачах пошуку.

- Обґрунтувати відмінності за результатами.

КЛЮЧОВІ СЛОВА: ПРОГРАМУВАННЯ, ПРОСТІ МЕТОДИ ПОШУКУ, МАСИВИ, PASCAL.



ВСТУП

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

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

Масив є прикладом структурованого типу, тобто він, у свою чергу, складається з елементів іншого типу.

Одним з найбільш використовуваних дій з масивами у програмуванні є пошук.

Пошук - це процес знаходження в заданому наборі даних об'єкта, що володіє певними властивостями. Існують прості та складні методи пошуку.

У цій роботі буде розглянуто прості методи пошуку, а саме:

- Лінійний метод пошуку;

- Бінарний метод пошуку;

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



РОЗДІЛ 1. ПОНЯТТЯ АЛГОРИТМУ ПОШУКУ

1.1 Сортування та пошук даних

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

Мета пошуку - знаходження елементів, значення яких відповідають параметрам пошуку.

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

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

Впорядкованість - наявність відсортованого ключового поля, яка дозволяє прискорити процес пошуку.

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

Метою сортування є полегшення подальшого пошуку елементів у множині при обробці даних.

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

Загальний алгоритм пошуку можна описати так:

1. Обчислення елемента, що часто передбачає отримання значення елемента, ключа елемента і т.д.

2. Порівняння елемента з еталоном або порівняння двох елементів.

3. Перебір елементів множини, тобто проходження по елементах масиву.

Різняться види пошуку методом перебору і стратегіями пошуку. В лінійних структурах існують такі основні алгоритми.

Послідовний або лінійний пошук

Це найпростіший вид пошуку деякого елемента серед інших. Він здійснюється за допомогою перевірки кожного елемента до тих пір, доки вони не будуть збігатися. Загальна ідея цього виду пошуку така: усі елементи розглядаються послідовно, один за одним. Це дає змогу не пропустити жодного елемента. Якщо збіг буде знайдено, то пошук припиняється і його результат є позитивним. Якщо не знайдено, то результат буде негативним.

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

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

Бінарний або двійковий пошук

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

Ідея цього пошуку така: пошук даного значення серед деякого масиву починається, коли визначається центральний елемент цього масиву. Значення цього елемента порівнюється зі значенням елемента, який треба знайти. Якщо потрібне нам значення збігається з центральним, то пошук завершено. Якщо воно або більше або менше, то створюється масив, який складається з елементів, що знаходяться ліворуч або праворуч від центрального значення і тепер пошук відбувається в цьому масиві.

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

1.2 Лінійний (послідовний) метод пошуку

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

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

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

Нехай заданий якийсь масив невпорядкованих значень. Алгоритм полягає в послідовному порівнянні елементів набору даних Масив [i] з шуканим значенням - X. Порівняння проводиться до тих пір, поки не буде знайдений шуканий елемент чи занехають переглянуті всі елементи набору даних. Якщо черговий елемент збігається з X, то задача вирішена і потрібно вивести номер і значення знайденого елемента. Відповідно алгоритм має дві умови закінчення пошуку:

- шуканий елемент знайдений, Масив [i] = Х;

- весь набір даних переглянутий, збігів не виявлено.

Основою даного алгоритму служить цикл з умовою виходу. У циклі кожен елемент Масив [i] порівнюється з X. Якщо знайдений елемент, для якого виконується умова Масив [i] = X, то елемент з індексом i вважається знайденим.

У тому випадку, якщо елементи послідовності Масив [i] мають повторювані значення, то відповідно до блок-схемі, наведеній на рисунку, буде знайдений елемент з мінімально можливим індексом, для якого виконується умова Масив[i] = X, тобто це перший з таких елементів.



1.3 Бінарний (двійковий) метод пошуку

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

Алгоритм бінарного пошуку можна описати так:

1. Визначення значення елемента в середині структури даних. Отримане значення порівнюється з ключем.

2. Якщо ключ менше значення середини то пошук здійснюється в першій половині елементів, інакше - в другій.

3. Пошук зводиться до того, що знову визначається значення серединного елемента в обраній половині і порівнюється з ключем.

4. Процес триває до тих пір, поки не буде знайдений елемент зі значенням ключа або не стане порожнім інтервал для пошуку.

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

Розглянемо упорядкований по зростанню набір даних, для якого виконується умова: Масив> [i - 1]? Масив [i] для всіх i з інтервалу (0, n).

· Позначимо Масив [k] середній (за номером) елемент набору даних, порівняємо його з шуканим елементом X.

· Змінні A і B містять ліву і праву межу відрізка набору даних, в якому знаходиться шуканий елемент. Якщо X = Масив [k], то завдання виконане, X> Масив [k], то це означає, що шуканий елемент розташований нижче Масив [k] (між елементами з номерами A = n / 2 + 1 і B = n).

· Якщо X <Масив [k], то це означає, що шуканий елемент розташований вище середнього елемента (між елементами з номерами A = 0 і B = n / 2 - 1).

· Після того як визначена частина набору даних, в якій може перебувати шуканий елемент, за формулою (A + B) / 2 обчислюється нове значення k, і пошук триває.

· Алгоритм бінарного пошуку, закінчує свою роботу, якщо шуканий елемент знайдений або якщо перед виконанням чергового циклу пошуку виявляється, що значення A> B.

Таким чином, в результаті кожної перевірки ми вдвічі звужує область пошуку. Двійковий пошук - дуже ефективний метод. Якщо, наприклад, довжина набору даних дорівнює 1023, після першого порівняння область звужується до 511 елементів, а після другої - до 255. Легко порахувати, що для пошуку в масиві з 1023 елементів досить 10 порівнянь.



РОЗДІЛ 2.ПОРІВНЯЛЬНИЙ АНАЛІЗ

2.1 Теорія складності обчислень

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

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

Ця теорія виникла з потреби порівнювати швидкодію алгоритмів (наприклад, алгоритмів пошуку і сортування), чітко описувати їх поведінку (час виконання і обсяг необхідної пам'яті) в залежності від розміру входу.

Складність алгоритму - це міра використання алгоритмом ресурсів часу або простору.

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

Такі дії у програмуванні ,як пошук або сортування відносяться до класу складності Р. Тобто це ті проблеми, вирішення яких вважається «швидким», тобто залежать від розміру вхідних даних.

Розглянувши прості методи пошуку за теорією складності, отримуємо результат:

Лінійний метод

За:

· Не вимагає сортування значень безлічі.

· Не вимагає додаткового аналізу функції.

· Не потребує додаткової пам'яті. => Отже, може працювати в потоковому режимі при безпосередньому отриманні даних з будь-якого джерела.

Проти:

· Малоефективний в порівняннім з іншими алгоритмами пошуку.

· Отже, використовується, якщо безліч містить невелику кількість елементів.



Бінарний метод

За:

· Відносна швидкість виконання пошуку (по лінійним).

Проти:

· Бінарний пошук може застосовуватися тільки на впорядкованій множині.

2.2 Використання методів пошуку на практиці

Практичне використання методу двійкового пошуку різноманітні:

· Широке поширення в інформатиці стосовно пошуку в структурах даних. Наприклад, пошук в масивах даних здійснюється за ключем, присвоєним кожному з елементів масиву (в найпростішому випадку сам елемент є ключем).

· Також його застосовують в якості чисельного методу для знаходження наближеного рішення рівнянь

· Метод використовується для знаходження екстремуму цільової функції і в цьому випадку є методом умовної одновимірної оптимізації.

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

Розглянемо прості методи пошуку на задачах:

Нехай дано масив елементів A і ключ b. Для b необхідно знайти збігається з ним елемент масиву А.

Лінійний пошук має на увазі послідовний перегляд всіх елементів масиву А в порядку їх розташування, поки не знайдеться елемент рівний b. Розглянемо на прикладі:

const N=10;

type Any=integer;

var A:array[0..N-1] of Any;

i:integer;

b:Any;

begin

writeln('Введіть елементи масиву:');

for i:=0 to N-1 do

readln(A[i]);

write('Введіть ключ:');

readln(b);

i:=0;

while (i<>N) and (A[i]<>b) do

i:=i+1;

if i<>N then

writeln('Елемент,що співпадає з ключем, виявлено.Позиція елемента -',i+1)

else

writeln('Елемент не виявлено');

end.

Тестовий приклад:

Використовуючи метод бінарного пошуку, розглянемо алгоритм , у якому масив А є впорядкованим :

const N=10;

type Any=integer;

var A:array[0..N] of Any;

Left,Right,m,i,j:integer;

b:Any;

begin

writeln('Введіть впорядковану послідовність елементів масиву ');

for i:=0 to N do readln(A[i]);

writeln('Введіть ключ');

readln(b);

Left:=0;Right:=N;

while Left<Right do

begin

m:=(Left+Right) div 2;

if A[m]<b then Left:=m+1

else Right:=m;

end;

if (Right<>N) or ((Right=N) and (a[N]=b)) then

writeln('Елемент виявлено. Позиція елемента : ',Right)

else

writeln('Елемент не виявлено');

end.

Тестовий приклад:

2.3 Результати порівняльного аналізу

Слід зазначити, що в загальному випадку при лінійному пошуку серед N елементів потрібно в середньому N / 2 порівнянь в разі успішного пошуку та N порівнянь в найгіршому випадку, і витрати часу для великих масивів тому великі.

Застосовується даний алгоритм, якщо ніякої додаткової інформації про дані масиву немає.

Знаходження елемента бінарним пошуком здійснюється дуже швидко. При пошуку серед N елементів потрібно log2 (N) порівнянь в найгіршому випадку. Крім того, бінарний пошук вже при N близько 100 значно ефективніше лінійного - як за швидкістю виявлення, так і за здатністю до отримання негативного результату.

Для доказу цього наведу такі характеристики лінійного та бінарного пошуку:

Лінійний пошук:

Кількість елементів	Середня кількість порівнянь при наявності елемента	Кількість порівнянь при відсутності елемента
10	5	10
1000	500	1000
1 000 000	500 000	1 000 000

Бінарний пошук:

Кількість елементів	Максимальна кількість порівнянь при наявності елемента	Максимальна кількість порівнянь при відсутності елемента
10	8	8
1000	10	10
1 000 000	20	20



ВИСНОВКИ

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

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

У практичному використанні наведені методи є найпростішими, загальновживаними.

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

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



СПИСОК ЛІТЕРАТУРИ

1. «Алгоритмы: введение в разработку и анализ» А.Левитин

2. «Алгоритмы и структуры данных» Н.Вирт (1985)

3. «Основи алгоритмізації та програмування» Співаковський О.В.(1997)

4. «Структуры данных и алгоритмы их обработки на языке программирования Паскаль» Касторнова В.А.



ДОДАТОК

1. Пошук підпослідовності в масиві (алгоритм Бойера-Мура-Хорспула)

пошук дані обробка обчислення

Функція здійснює пошук першого входження масиву W (розміру m) в масив T, в результаті функція видає номер першого елементу в масиві T починаючи з якого зустрічається масив W. У випадку, якщо масив W не зустрічається в масиві T результат функції рівний -1.

Спочатку функція створює BMH-таблицю, вміст якої залежить від шуканого масиву, а саме якщо число i не міститься в підмасиві W[1..m-1], то BMHTable[i]=m, якщо число i міститься в підмасиві W[1..m-1], то береться максимальний номер j, т.ч. W[j]=i і тоді BMHTable[i]=m-j. Надалі таблиця використовується для “ прискорення ” проходу масиву в якому здійснюється так: Покладемоj=m

Нехай k=m; i=j. Поки W[k]=T[j] і k>0, зменшуємо на одиницю до і i

Якщо k=0, означає масив W входить в масив T починаючи з номера i+1 і ВИХІД.

Збільшимо значення j на BMHTable[T[j]] (дійсно T[j] в масиві W може бути на відстані не меншому, ніж BMHTable[T[j]] від кінця).

Якщо j <= n переходимо до кроку 2, інакше ВИХІД і масив W не міститься в масиві T.

Алгоритм оптимізований в порівнянні з попереднім для випадку довгого шуканого масиву з не однаковими елементами. Цікаво, що алгоритм працює набагато помаліше попереднього наприклад у разі коли масив T складається з одних нулів, а масив W має наступний вигляд: 1000000.



ДОДАТОК

2. Пошук підпослідовності в масиві (алгоритм Кнута-Морріса-Пратта)

Функція здійснює пошук першого входження масиву W (розміру m) в масив T, в результаті функція видає номер першого елементу в масиві T, починаючи з якого зустрічається масив W. У випадку, якщо масив W не зустрічається в масиві T результат функції рівний -1.

Розглянемо спочатку функцію F, яка визначена на послідовностях X[1], …, X[k] таким чином: розглянемо всі засади послідовності X що одночасно є її кінцями, і виберемо з них щонайдовше. (Не рахуючи, звичайно, самої послідовності X). Тоді F(X) рівно довжині такої підпослідовності.

Робота алгоритму полягає в обчисленні функції F на послідовності одержаної злиттям масивів W і T з використанням роздільника, як яке повинен виступати елемент, що не міститься ні в першому ні в другому масивах: W[1], …, W[m], @, T[1], …, T[j]; j = 1, …, n. Тоді, якщо значення F при деякому j рівне m (довжині послідовності W), то масив W міститься в масиві T, інакше немає.

У першій частині алгоритму заповнюється масив L, при цьому L[i]= F(W[1], …, W[i]). На цьому стоїть зупиниться докладніше, оскільки методика заповнення масиву L є ключовою в даному алгоритмі. Отже тривіальне L[1]= 0 (оскільки F - довжина підпослідовності). Далі, допустимо ми заповнили масив L для елементів з першого по i-ий. Тепер необхідно визначити значення L[i+1]= F(W[1], …, W[i],W[i+1]). Для цього покладемо спочатку len = L[i]. По побудові масиву L ми знаємо, що W[i-len+1]= W[1], …, W[i]= W[len], і якщо W[i+1]= W[len+1], то L[i+1]= L[i]+1, допустимо це не так, тобто W[i+1] не рівне W[len+1], означає треба зменшити довжину початкового підмасиву який ми розглядаємо, покладемо len_ = L[len], тоді одержуємо W[i-len+1]= W[1]= W[len-len_+1]= W[i-len_+1], …, W[i-len+len_]= W[len_]= W[len]= W[i], або виписавши тільки важливі для нас співвідношення: W[1]= W[i-len_+1], …, W[len_]= W[i], і залишилося знову порівняти W[i+1] і W[len_+1], якщо вони знову не рівні покладемо len = len_; len_ = L[len], продовжуючи цей процес ми на деякому кроці одержимо або len = 0 і тоді L[i+1]= 0, якщо W[i+1]<>W[1] і L[i+1]= 1, якщо W[i+1]= W[1], або рівність W[i+1]= W[len_+1] і означає L[i]= len_+1.

Після заповнення масиву L здійснюється обчислення функції F на масиві W[1], …, W[m], , T[1], …, T[j]; j = 1, …, n, скориставшися алгоритмом схожим на той, що використовувався в алгоритмі Бойера - Мура - Хорспула, при цьому роздільник як такий не використовується.

Размещено на Allbest.ru

...