КУРСОВА РОБОТА на тему:«Алгоритм пошуку послідовності масивів»

Зміст

Вступ    3

Розділ І. Алгоритми пошуку    5

1.1. Поняття складності алгоритму та задачі    5

1.2 Лінійний пошук    7

1.3. Дихотомічний пошук    8

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

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

1.6. Пошук підпослідовності в масиві (алгоритм ЗСУВ-І)    15

1.7. Нечіткий пошук    17

1.8. Двійковий (бінарний) пошук елементу в масиві    19

1.9. Знаходження загальних елементів двох масивів    20

1.10. Інтерполяційний пошук елементу в масиві    21

1.11. Окремий випадок задачі lis    22

Висновки    24

Вступ

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

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

Мета і задачі дослідження. Мета даної роботи полягає в: розробці інтегрованих алгебро-алгоритмічних моделей програм для пошуку підпослідовності масивів;

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

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

У відповідності до поставленої мети визначено такі основні завдання
дослідження:

  • Дослідити поняття алгоритму.
  • Вивчити поняття сортування.
  • Розглянути алгоритми пошуків та вказати їх відмінності.
  • Зробити висновки.

Структура і обсяг курсової роботи. Курсова робота побудована логічно правильно, згідно завдань дослідження. Складається із вступу, 2 розділів, висновків, списку використаної літератури. Загальний обсяг курсової роботи становить 25 сторінок,

Розділ І. Алгоритми пошуку

1.1. Поняття складності алгоритму та задачі

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

Нагадаємо, що алгоритм розв’язання масової задачі описує розв’язання будь-якого її екземпляра. Екземпляри багатьох задач можна охарактеризувати значенням деякого числового параметра. Наприклад, довжиною масиву чи кількістю чисел, які треба прочитати з клавіатури. Або натуральним числом, про яке ми хочемо дізнатися, чи просте воно. Найчастіше цим параметром є кількість скалярних значень, обробка яких задається алгоритмом. Кажуть, що екземпляр задачі має розмір N, якщо задається даними, складеними з N скалярних значень (наприклад, масивом із N елементів).

Нехай A позначає алгоритм розв’язання деякої масової задачі. Позначимо через F(A, екземпляр) кількість елементарних дій у процесі розв’язання цього екземпляра задачі за алгоритмом A, а через F(A, n) – максимум кількості елементарних дій серед усіх екземплярів розміру n.

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

F(A, n)=4
n
(n-1)/2.

Кожному n = 1, 2, 3, … відповідає певне значення F(A, n), тобто ми маємо функціональну залежність між розмірами n та максимальними кількостями елементарних дій, виконуваних за алгоритмом A. Ця функція називається складністю
алгоритму A
. Алгоритми практично всіх реальних задач мають складність, монотонно неспадну за n.

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

Функція G(n) є оцінкою для функції F(n), або F(n) є функцією порядку G(n), коли існують такі додатні скінченні числа C1 і C2, що за деякого m при всіх n > m

C1
G(n)
F(n)
C2
G(n).

Така залежність між функціями позначається за допомогою знака “О”:

F(n) = O(G(n)).

Функція F(n) називається функцією порядку, меншого від G(n)
за великих n
, і це позначається F(n)=o(G(n)).

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

Приклад
1.
n
(n-1) = O(n2), оскільки за n > 2 маємо

0.5
n2 < n*(n-1) < n2.

Аналогічно неважко довести, що n3 + 100
n2 = O(n3) = o(n3.1) = o(2n), 100 logn + 10000 = O(logn) = O(lgn) = o(n).

Приклад
2. Складність алгоритму бульбашкового сортування tb(n)=O(n2), алгоритму лінійного пошуку – t1(n)=O(n), бінарного пошуку – t2(n)=O(logn)=o(n).

Тепер означимо поняття складності задачі. Алгоритми пошуку в упорядкованому масиві свідчать, що одна й та сама задача може мати алгоритми розв’язання з різною складністю. Неформально, під складністю задачі розуміють найменшу зі складностей алгоритмів її розв’язання. Іншими словами, задача
має складність порядку G(n)
, якщо існує алгоритм її розв’язання зі складністю O(G(n)) і не існує алгоритмів зі складністю o(G(n)).

Наприклад, складність задачі пошуку в упорядкованому масиві визначається складністю алгоритму двійкового пошуку, тому й оцінюється функцією logn. Задача сортування масиву має складність порядку n
logn. Доводити ці факти ми не будемо – можна подивитися, наприклад, у книгу [АХУ]. Але в наступному пункті ми наведемо алгоритми сортування з цією оцінкою складності.

 

ЗАВАНТАЖИТИ

Для скачування файлів необхідно або Зареєструватись

Алгоритм пошуку підпослідовності масивів (139.0 KiB, Завантажень: 15)

Сторінка: 1 2 3 4
завантаження...
WordPress: 23.15MB | MySQL:26 | 0,348sec