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



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

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

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

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

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

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

На тему:

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

ЗМІСТ

  1. РЕФЕРАТ……………………………………………………………………3
  2. ВСТУП………………………………………………………………..……...4
  3. РОЗДІЛ 1. ПОНЯТТЯ АЛГОРИТМУ ПОШУКУ………………………....5

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

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

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

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

1.1Теорія складності обчислень ………………………………………………...12

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

1.3Результати порівняльного аналізу…………………………………………….16

  1. ВИСНОВКИ………………………………………………………………….18
  2. ДОДАТКИ……………………………………………………………………19
  3. СПИСОК ЛІТЕРАТУРИ…………………………………………………….22

РЕФЕРАТ

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

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

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

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

Завдання:

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

ВСТУП

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. Обчислення елемента, що часто передбачає отримання значення елемента, ключа елемента і т.д.
  2. Порівняння елемента з еталоном або порівняння двох елементів.
  3. Перебір елементів множини, тобто проходження по елементах масиву.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. Визначення значення елемента в середині структури даних. Отримане значення порівнюється з ключем.
  2. Якщо ключ менше значення середини то пошук здійснюється в першій половині елементів, інакше - в другій.
  3. Пошук зводиться до того, що знову визначається значення серединного елемента в обраній половині і порівнюється з ключем.
  4. Процес триває до тих пір, поки не буде знайдений елемент зі значенням ключа або не стане порожнім інтервал для пошуку.

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

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

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

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

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

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

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

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

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

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

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

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

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

За:

Проти:

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

За:

Проти:

1.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.

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

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

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

2.

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

  1. «Алгоритмы: введение в разработку и анализ» А.Левитин
  2. «Алгоритмы и структуры данных» Н.Вирт (1985)
  3. «Основи алгоритмізації та програмування» Співаковський О.В.(1997)
  4. «Структуры данных и алгоритмы их обработки на языке программирования Паскаль» Касторнова В.А.




Похожие работы, которые могут быть Вам интерестны.

1. Порівняльний аналіз зарубіжного та вітчизняного коректурного процесу

2. Аналіз методів розрахунку забруднення атмосфери від джерел компресорних станцій магістральних газопроводів

3. Застосування математичних методів в психології

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

5. ВПРОВАДЖЕННЯ НОВІТНІХ МЕТОДІВ ДЛЯ МОДЕРНІЗАЦІЇ ФІНАНСОВОЇ СИСТЕМИ УКРАЇНИ ЗАДЛЯ ЗАБЕЗПЕЧЕННЯ

6. Розробка теоретичних основ і методів підвищення якості електричної енергії вентильних перетворювачів

7. ОСОБЛИВОСТІ ЗАСТОСУВАННЯ МЕТОДІВ АРТ-ПЕДАГОГІКИ В ПРОЦЕСІ СОЦІАЛЬНОЇ ІНТЕГРАЦІЇ ДІТЕЙ З СИНДРОМОМ ДАУНА

8. ЕКСПЕРЕМЕНТАЛЬНА ПЕРЕВІРКА СИСТЕМИ ІГРОВИХ ПРИЙОМІВ ТА МЕТОДІВ НАВЧАННЯ АНГЛОМОВНОМУ СПІЛКУВАННЮ НА ПОЧАТКОВОМУ ЕТАПІ

9. Аналіз системи комунікацій на підприємствах

10. АНАЛІЗ ФІНАНСОВОГО СТАНУ ПІДПРИЄМСТВА